2022.0913算法第57题跳跃游戏(一) 这道题目使用贪心算法，代码简单，但是感觉还是挺难想的 每次都要找到当前位置所能跳到的最远位置，在最远位置内的位置都是能够到达的， bool canJump(vector<int>& nums) {         //记录当前位置能够到达的最远位置         //i + nums[i]位当前位置能够到...

2022.0906算法第56题不同路径的数目(二) 这道题对于做过不同路径的数目一，思路还是能够想到的 主要就是需要注意两点 1、初始化的时候，如果遇到障碍0的时候，0后面的数据都没法到达，需要赋值为0 2、当状态矩阵在进行递推时，如果遇到障碍0，则直接将该位置赋值为0，其余的情况不变依然时左边和上边相加 int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) {     //状态矩...

2022.0906算法第55题01背包 这道题也不容易想，但是竟然归为简单题， 我当时没想到需要和dp[i-1][j-vw[i-1][0]]离的那么远的值发生关系 1、状态矩阵建立了 2、初始值没弄ing错 3、状态转移方程没搞明白，已经把一个例子的状态矩阵写出来了         但是没想明白dp[i][j]是怎么得到的，有几个方向过去的 解释： dp[i][j]可以理解为物品i放置或者不放置，就这两种情况‘ 当然这是有前提的，就是当前的物品i有这两种选择 下面就要分情况讨...

2022.0906算法第54题编辑距离(二) 昨天做的编辑距离一，如果那个理解的准确，这个就完全没有问题，主要是要直到每条路径是怎么过来的 每个矩阵位置对应着怎样的操作，思路和一是完全一致的。 怎么都觉着这道题很棒，主要是和实际结合起来了。 good，下次遇到类似的题目应该不会出问题了！快没机会了。 int minEditCost(string str1, string str2, int ic, int dc, int rc) {   ...

2022.0905算法第53题编辑距离(一) 这道题真是自己找死，之前笔试碰到了这个题目，但是当时觉着难就没看，没成想今晚笔试又碰到了 气死个人，要是看了题解，可就AC了 结果今天看了才知道代码很简单，理解也不难，要是自己就是打死都想不出来。 以后做编辑字符的题目可不能再出错了。 下面str1[i]、str2[j]表示str的子串 1、二维的状态矩阵想到了     dp[i][j]表示str1[i]变换到str2[j]的最小操作数。。。。 2、下标的含义也明确了 3、在进行递推公式求解时，就是没想到会...

2022.0902算法第52题有效括号序列 这道题我自己是想不出来，刚开始看答案都没看明白 有map的那个还没看明白呢 不过使用栈进行求解的方法倒是明白了，这个算是利用括号匹配的特性了 想不出来 主要思路就是： 遇到左符号时，将左符号加入到栈中 遇到右符号时，看此时的右符号是否与栈顶元素组成对应的符号，不能则不是有效的序列                   &nbsp...

2022.0902算法第51题合并区间 这题在写代码时遇到一下困难： 1、每两个区间进行比较，这样总会少一个区间，例如从第一个开始，则最后一个就可能遍历不到     这样想的思路是有问题的，因为需要比较的是结果区间的最后一个元素和给定区间依次比较，这样是不涉及数组问题。 2、在添加到结果数组时，如果连着三个都是需要合并的区间，那么怎么比？比较的对象就应该是结果数组中的最后一个区间     也就是结果数组的最后一个区间与给定的区间进行依次比较。 以上两个问题，没有想明白，导致写代码时总是出错，可以看出，以上两个问题出现的...

2022.0901算法第50题括号生成 这题刚开始想到使用全排列，然后通过判断得到的排列是否符合要求进行存储。 但是结果字符中的判断并不好进行，使用左右括号出现的数量作比较应该可以。 最主要的原因是超时，n对括号进行的全排列就是2n级别的，当n=8时时间就超了 之后看了解析发现这题使用的套路并没有那么明显 将n对括号分为左右两个，根据左括号和右括号的关系进行递归，没感觉有回溯 这个感觉好难想，想不明白怎样进行的了 vector<string> res; void backtrack(int n,int ...

2022.0902算法第49题N皇后问题 N皇后问题难在哪，我觉着是题目叙述的方式不好理解，又或者这样的描述让问题看起来更加复杂 刚开始也是不会，看完解析之后发现，和递归回溯的模板是一致的 例如和排列问题作比较，就相当于，网格里每行放置 的都是1234等数字 然后每行选取一个数组组成全排列，列也不能重复； 此时没有对角线这个约束条件。 这样一想，是不是觉着两者十分的相似。 也就是每次循环的对象从一堆数字变成了一行网格。 这个思路大致理解之后，细节还是有一些问题存在的 比如对角线如何判断，有时候就不能想那么具体，想的太具体反而会影响思路 ...

2022.0831算法第48题反转字符串 这道题简单，直接for循环赋值即可， string solve(string str) {     //定义结果字符串     string res;     //循环从后往前取出str的字符，添加到结果字符中     for(int i=str.size()-1;i>=0;i--){    &nbs...

2022.0831算法第47题字符串的排列 这个题目直接套用包含重复数字的全排列，这两者是一样的思路和代码 典型的递归回溯问题，这次写的时候，在考虑去重的时候 只想到了前后两个相等的情况，忽略了前后相等时，也需要保证前一个已经选择，这样才能跳过 否则，有可能将未选择的跳过 如“aab”，第一次选“a”，第二层选的时候，优于第二个和第一个相等而且第一个已经选择了，那第二个a就不能选择了 此时第一个结果应为“aba”， 当第一层选第二个a时，优于第一个a并没有选择，此时第二层就能选择第一个a，此时结果为”aab“，注意这个a的顺序时反的 如果不判断前...

2022.0831算法第46题岛屿数量 最近学习了递归回溯算法，解决排列，组合，子集，分割字符串和网格问题 排列，组合，子集这三个已经写过，感觉就是模板，最难的操作在于想通树形结构怎么画 同时剪枝的操作也很重要，同时也十分的难想。 岛屿数量这道题，并不是标准的回溯，只是用到了递归。 刚开始有点想法，感觉就是用递归，但是对于具体的思路没想法，不会。 看了解析之后，理解是将每次遇到的1和它连通的区域都赋值为0，这样就一次遇到一个岛屿（连通域） 这样感觉还没回溯好想，总会有一些具体的代码或者过程想不通 刚开始边界处理我就想的比较复杂，想着这样就太麻烦了...

2022.0824算法第45题顺时针旋转矩阵 这题不需要想太多，模拟解题思路就行，没有算法难点 1、先转置矩阵 2、对每行进行反转 这样就能得到顺时针旋转90度的结果 vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {     //矩阵的转置，swap(mat[i][j],mat[j][i]);   &nb...

2022.0824算法第44题旋转数组 本题采用三次反转的方式，感觉也没啥亮点。 vector<int> solve(int n, int m, vector<int>& a) {     //取余，因为每次长度为n的旋转数组相当于没有变化     m=m%n;     //第一次逆转全部数组元素     reverse(a....