引言
- 今天起的挺早的，早上把昨天录得关于JVM的相关八股都听完了，然后还背了一部分八股，洗了衣服，差不多十点钟开始刷算法题，还是有点慢的，不够快。
- 剩下的时间加把劲，加油！！
复习
新作
分割等和子集
题目链接
注意
- 只包含正整数
- 非空
- 分割成两个相等的子集
个人实现
- 首先，这不是一个连续的子集，所以不能使用单调队列或者区间DP，并没有任何意义，只能从实际的角度出发，按照集合的角度出发，去判断
- 这是一个子集的问题，所以每一个元素要么是放或者不放，究竟该如何使用集合的角度去考虑？
- 这里想不到什么别的方法，如果使用既然要保证相等，我就可以对nums进行排序，然后的使用两个单向队列进行实现，保证结果相同，如果两个指针相遇了，还不行，就是找不到。
class Solution {
public:
bool canPartition(vector<int>& nums) {
if(nums.size() == 1) return false;
sort(nums.begin(),nums.end());
int l = 0,r = nums.size() - 1;
int lsum = nums[l],rsum = nums[r];
while(l + 1 < r){
if(lsum < rsum ){
l ++;
lsum += nums[l];
}else if(lsum > rsum){
r--;
rsum += nums[r];
}else{
// 如果是双边合拢的，已经相等了，就直接返回
// if(l + 1 == r) return true;
l ++;
r --;
lsum += nums[l];
rsum += nums[r];
}
}
cout<<"l: "<<l<<"r: "<<r<<endl;
// 判定最终的结果
if(lsum == rsum && l + 1 == r ) return true;
else return false;
}
};
总结
- 思路有问题，明显没有考虑到对应的顺序不同的情况
参考实现
- 经典的零一背包问题，每一个物体的体积是每一个数字的值，然后价值为0，背包的容量应该是二分之和
属是没有考虑到，既然两个子集的和是相等的，那么加起来就是二分之一
sum是奇数的话，一定是无解的，因为没有办法进行有效平均
有一个很大的bug，完全没想到，就是已经求出来了所有元素的和，然后只要求出另外一半的和的构成，那么原来的数组减去这一半数组也就是综合的一半了吗？
完全没有想到！！！
- 搞明白上述的等式关系之后，就可以将其完全转换为对应的零一背包问题，f[i]表示当前容量i下，能不能第i个物体，刚好满足容量i。
- 就需要判定上一个f[i - x] 其中x是当前物体的容量，和那个值相与就行了。
根据思路提示写的代码
class Solution {
public:
bool canPartition(vector<int>& nums) {
// 判定当前的容器的个数
if(nums.size() == 1) return false;
// 计算对应的累加和
int s = 0;
for(auto i : nums) s += i;
if(s % 2 != 0) return false;
// 声明一个状态矩阵
int m = s / 2;
vector<int> f(m + 1,0);
f[0] = 1;
for(auto a:nums){
for(int i = m;i >= a;i --){
f[i] |= f[i - a];
}
}
return f[m];
}
};
注意，使用了滚动数组优化之后，第二个数组要逆序遍历
不同路径
题目链接
注意
- 机器人只能向下或者向右移动
- 目标和起点是一致的，然后只能向下和向右移动，说明只能走特定的步数m + n - 1;
个人实现
- 这就是一个数字三角形的问题，做过了很多，但是这里找不到了。
最低通行费
- 其他的我知道我做过的，也写过分析，但是找不到了，不过不重要，知道怎么做就行了。
- f[i][j]表示从起点到达第i，j格总共的路径数量，因为只有两种方向，所以是
- f[i][j] = f[i - 1][j] + f[i][j - 1]
- 同时对于总共的路径也有了限制为m + n - 1，具体实现如下
class Solution {
public:
int uniquePaths(int m, int n) {
typedef long long LL;
int step = m + n - 2;
vector<vector<LL>> f(m + 1,vector<LL>(n + 1,0));
f[0][0] = 1;
for(int i = 1;i <= step;i ++){
for(int row = 0;row < m && row <= i;row ++){
int col = i - row;
if(col <= n){
// 如果是第一列，就只能来自上面
if(row >= 1) f[row][col] += f[row - 1][col];
// 如果是第一行，只能来自左边
if(col >= 1) f[row][col] += f[row ][col - 1];
// cout<<f[row][col]<<endl;
}
}
}
return f[m - 1][n - 1];
}
};
实现效果
总结
- 代码框架是一个没记住，这是自己推出来的，然后之前写的东西找不到了。不过得好好去看看代码。
参考实现
- 和我的思路是一样，但是我这里明显整的有点复杂，他写的就很简单，很多东西都没有必要，具体实现步骤如下。
- 就是遍历所有的格子，按照行号和列号进行遍历就行了，然后使用状态转移方程，具体如下
class Solution {
public:
int uniquePaths(int m, int n) {
typedef long long LL;
vector<vector<LL>> f(m + 1,vector<LL>(n + 1,0));
f[0][0] = 1;
for(int r = 0;r < m;r ++){
for(int c = 0; c < n; c++){
if(r) f[r][c] += f[r- 1][c];
if(c) f[r][c] += f[r][c - 1];
}
}
return f[m - 1][n - 1];
}
};
最小路径和
题目链接
注意
- 只能向右或者向下移动
- 路径上的总和最小
- f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j]
个人实现
- 这道题就是爽题，和上面那道题基本上一模一样，只不多是状态转移方程变了而已，需要加上当前走这一步的路径。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(),n = grid[0].size();
vector<vector<int>> f(m + 1,vector<int>(n + 1,INT_MAX));
f[0][0] = grid[0][0];
for(int r = 0;r < m;r ++){
for(int c = 0;c < n;c ++){
if(r) f[r][c] = min( f[r][c], f[r - 1][c]+ grid[r][c]) ;
if(c) f[r][c] = min( f[r][c], f[r][c -1]+ grid[r][c]) ;
}
}
return f[m - 1][n - 1];
}
};
实现起来，基本上和之前的代码差不多
参考实现
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size();
if (!n) return 0;
int m = grid[0].size();
vector<vector<int>> f(n, vector<int>(m, INT_MAX));
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ ) {
if (!i && !j) f[i][j] = grid[i][j];
else {
if (i) f[i][j] = min(f[i][j], f[i - 1][j] + grid[i][j]);
if (j) f[i][j] = min(f[i][j], f[i][j - 1] + grid[i][j]);
}
}
return f[n - 1][m - 1];
}
};
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/363553/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
总结
- 基本上思路都是一样的，不过他判定了是否存在第一个元素的情况，这里我缺失了
最长回文子串
题目链接
注意
- 最长回文字符串，字符串可为单数也可以为奇数
个人实现
- 这道题之前实现过，自己做的时候，做出来过，具体链接如下
- 上一次做的链接
- 这里自己思考一下，怎么实现
枚举中心点，分奇数和偶数进行讨论
- 将每一个索引的字符串作为中心点，然后往两边进行进行便利，如果不行，直接退出。
class Solution {
public:
string longestPalindrome(string s) {
string res = "";
for(int i = 0;i < s.size();i ++){
// 奇数模式，两边相同，往两边进行遍历
int l = i,r = i;
while(l >= 0 && r < s.size() && s[l] == s[r]) l--,r++;
if(r - l - 1 > res.size()) res = s.substr(l + 1,r - l -1);
// 偶数模式
l = i ,r = i + 1;
while(l >= 0 && r < s.size() && s[l] == s[r]) l --,r ++;
if(r - l - 1 > res.size()) res = s.substr(l + 1,r - l -1);
}
return res;
}
};
总结
- 这个写的比第一次要好很多，对比着看一下
参考实现
字符串哈希+二分
- 时间不够了，这里贴一下人家的代码和思路吧，还有论文要写，不能花太多时间。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
typedef unsigned long long ULL;
const int N = 2e6 + 10 , base = 131;
ULL hr[N] , hl[N] , p[N];
char str[N];
ULL get(ULL h[] , int l , int r)
{
return h[r] - h[l - 1] * p[r + 1 - l];
}
int main()
{
int T = 1;
while(cin >> str + 1 , strcmp(str + 1 , "END"))
{
int n = strlen(str + 1), res = 0;
for(int i = 2 * n ; i >= 0 ; i -= 2)
{
str[i] = str[i / 2];
str[i - 1] = 'z' + 1;
}
n *= 2; p[0] = 1;
for(int i = 1 , j = n; i <= n ; i ++ , j -- )
{
p[i] = p[i - 1] * base;
hl[i] = hl[i - 1] * base + str[i];
hr[i] = hr[i - 1] * base + str[j];
}
for(int i = 1 ; i <= n ; i ++ )
{
int l = 0 , r = min(n - i , i - 1);
while(l < r)
{
int mid = l + r + 1 >> 1;
if(get(hl, i - mid, i - 1) == get(hr, n + 1 - (i + mid), n + 1 - (i + 1)))l = mid;
else r = mid - 1;
}
if(str[i - l] <= 'z')res = max(res , l + 1);
else res = max(res , l);
}
printf("Case %d: %d\n",T ++ , res);
}
return 0;
}
作者：tom233
链接：https://www.acwing.com/solution/content/33154/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
此情此景，多么相似，又是没有时间，笑死了
总结
- 目前来看，总是在最后快结束的时候，才把这些题目昨晚，总是会出点问题，很难受。对于函数的越界考虑的不够充分，最后的异常根据他给的条件又不好找。然后还有一个问题就是，最后的输出总是会输出，不要总是关注于平时的过程，还要关注于最终的输出。
- 一个上午，基本上就背了八股，然后做了两道题目，还是不够，有点欠缺，得继续加油加油，进度太慢了！明天腾讯复试，能不能进都无所谓了，现在好好准备秋招吧。马上提前批就开始了。
- 今天基本上关于迷宫路径的题目都做完了，整体看起来还不错，挺顺利的
- 今天到此为止吧，累了，明天还得早起背书，准备腾讯的面试，虽然我觉得进的概率不大，而且大概率是KPI，无所谓了，接收一下打击也不错！
