2022.0822算法第42题判断是否为回文字符串 采用双指针，从左右两边位置开始遍历，如果出现两者不相等的情况 则返回false。否则左右两个指针逐步往中间靠拢 bool judge(string str) {     //定义左右两个指针，左闭右闭区间     int left=0,right=str.size()-1;     //初始化为true     bool&nbsp...

2022.0822算法第41题螺旋矩阵 这道题感觉没有弯弯绕，很直观的，但是写代码的时候感觉挺复杂的，需要考虑的情况较多 边界问题，终止条件等。在leetcode上看到一种解法，很好理解，代码也不复杂。 思想就是对矩阵的边界值进行更新，每次记录更新后的边界值，直到遍历完成 vector<int> spiralOrder(vector<vector<int> > &matrix) {     //结果数组    &nbsp...

2022.0822算法第40题最长无重复子数组 这题和leetcode第三题无重复字符的最长子串是一样的 可以使用滑动窗口进行求解。 第二次了这个也没写对，很离谱，删除元素时没搞懂怎么删除。 首先，定义start指针，和最大长度初始值， 要明确循环的变量表示的是窗口结束的指针， 主要思想为：将start指针指向0，先对结束指针进行遍历， 直到找到又重复数字存在，此时需要对start指针进行移动，这部分是最难的。 需要将start指针移动到重复数字的下一位 例如{1，2，3，4，2，5，6} 当i=4时，出现重复元素2，需要将start...

2022.0821算法第39题合并两个有序的数组 可以在创建一个数组，这样比较简单， 也可以采用双指针对原数组直接进行操作； 刚开始想着从前往后动手，但是没办法绕开插入元素的后移的问题， 交换两者元素也不行这样就破坏了两者的有序性。 之前的删除元素，是考虑两个数不相等的情况，反向思考了一波 这个问题也试着反向思考，从后往前进行，先找出最大的数，存到A数组的最后面，这样不会影响到前面的数值。 首先定义两个数组指针和指向A数组最后的指针。 int a_pos=m-1,b_pos=n-1; int index=m+n-1; ...

2022.0819算法第38题三数之和 这道题感觉挺麻烦的的，难度还可以就是复杂，细节点比较多。 首先思路还是挺简单的，采用双指针算法，先固定a，然后在剩余的数字中选择b和c，b和c通过向中心移动 逐步缩小范围，获取最终的结果。 算法有的点是需要去重的，结果中不能有重复的三元组，这点就需要做许多判断。 首先对数组进行排序，后面的判断依据就是根据有序的数组进行的。 （不能直接去除重复元素，这样会丢失解） sort(num.begin(),num.end()); 固定第一个元素a，遍历整个数组 for(int i=0;i<num.size...

2022.0818算法第37题买卖股票的最好时机(二) 这个也可以使用动态规划求解。 这个状态矩阵也是没想到，看了解析才知道采用二维数组 1、状态矩阵 定义状态 dp[i][0] 表示第 i 天交易完后手里没有股票的最大利润， dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利润。 vector<vector<int>> dp(prices.size(),vector<int>(2,0)); 2、初始值 dp[0][0]=0; dp[0][1]=-prices[0]; 3、状态转移方程 f...

2022.0818算法第36题买卖股票的最好时机(一) 这道题标注是简单，但是我真的没想出来，走弯路了 最优化的方式想不出来，需要先写复杂一点的。 1、状态矩阵 刚开始想的是第i天卖出的最大收益，但是后面做不出来了。 看了解析记录的是当前最小的股票价格，最大收益是计算得到的。 vector<int> dp(prices.size()); 2、初始值 这个还是比较简单的 dp[0]=prices[0]; int max_p=0; 3、状态转移方程 记录之前的最小值，这样每次只需要和当前值进行比较就行，空间换时间。 ...

2022.0818算法第35题打家劫舍(二) 这个没想出来，没成想嗜血要分成两种情况进行打家劫舍(一)的那种解法。 思考的时候想到了将这两者进行区分，还是太受局限了 1、状态矩阵 dp[i]表示前i个房间的最大偷窃金额， vector<int> dp(nums.size()+1); 2、初始状态 dp[1]=nums[0]; //或者 dp[1]=0; 只有一个房子的时候，不要犹豫，直接偷。 3、状态转移方程 dp[i]=max(dp[i-2]+nums[i-1],dp[i-1]); 这个因为首尾相连，第一个和最后一个不能同时偷，...

2022.0818算法第34题打家劫舍(一) 动态规划能求解，自己能想出来，应该不算难。 1、状态方程 dp[i]表示第i个房间的最大偷窃金额，就这一个数组，也没啥其他的选择 vector<int> dp(nums.size()); 2、初始状态 取前两个值 dp[0]=nums[0]; if(nums[0]<nums[1]){     dp[1]=nums[1]; } else     dp[1]=dp[0]; 3、状态转移方程 动态规划是从底层往...

2022.0817算法第33题兑换零钱(一) 动态规划问题，这个状态矩阵都没想出来。。。 1、状态矩阵 dp[i]表示目标值为i时的最小零钱兑换种类数。本来想到的是按照零钱数组进行创建状态矩阵 没想出来状态转移方程怎么写。 vector<int> dp(aim+1,aim+1); 2、初始值 dp[0]=0; 3、状态转移方程 首先对aim进行循环，找到每个目标值的零钱兑换的最小值 针对一个具体的i，循环零钱数组， 找到dp中所有i-arr[j]的位置，其中i>arr[j] 此时只需要找到dp[i-arr[j]...

2022.0816算法第32题把数字翻译成字符串 这题也是采用动态规划进行求解，但是状态转移方程就不是特别好想了。 1、状态矩阵 dp表示字符串i个位置可能的翻译方法。 vector<int> dp(nums.size()+1,1); 2、初始状态 初始状态需要考虑的比较多， dp[0]=1,dp[1]=1; if(nums=="0")     return 0; if(nums=="10"||nums=="20")     return&nbs...

2022.0816算法第31题矩阵的最小路径和 一样的套路，动态规划问题，相当于对路的方案数进行加权。 1、状态矩阵dp 为到达i，j位置的最小路径和 vector<vector<int>> dp=matrix; 2、初始值 将边界的值进行修改，进行向上累加。 int n=matrix.size(); int m=matrix[0].size(); for(int i=1;i<n;i++){     dp[i][0]=dp[i][0]+dp[i-1][0...

2022.0816算法第30题不同路径的数目(一) 动态规划问题，也能使用递归，感觉动态规划和递归是互通的，应为有状态转移方程存在。 1、状态矩阵 vector<vector<int>> dp(m,vector<int>(n,1)); 2、初始值 上边和左边为1. 3、状态转移方程 dp[i][j]=dp[i-1][j]+dp[i][j-1]; 最后返回最后的值 return dp[m-1][n-1]; 这个是自己想出来的，做的多了自然就能摸到套路了。 递归解法语句更简单，占内存。

2022.0816算法第29题最长上升子序列(一) 子序列不好使用暴力解法，主要是子序列的方案太多了。 采用动态规划进行求解。 1、状态矩阵dp 存储子序列末尾位置的最大长度，并且初始化为1. vector<int> dp(arr.size(),1); 2、初始值 dp[0]=1; 3、状态转移方程 dp[i]=max(dp[i],dp[j]+1); 这个转移方程还是不容易想出来的， for(int i=1;i<arr.size();i++){     for(int&...