还不是很完善暂时先把学到的/刷到的题型的一些知识点记录下来。后续会持续补充数组螺旋矩阵/数组123894765按照顺时针螺旋写进数组/读数组元素思路为沿边读不包括最后一个元素类似双指针左闭右开用while一圈圈循环里面四个for遍历四边//可以设置startystartx定义每一圈开始坐标 //offset代表圈数,设数组(m,n) while(offset n/2 offset m/2){ int i , j; //第一行只有列标动,每一次边之后ij都有改变第三次for也只有j动 for(j starty; jn-offset ; j){...} for(i startx; im-offset ; i) for(jstarty;j--) ... startx; ... } //中间还有 if(result.size() m*n){ //这个是题目要求可以用大小判断有没有存完 if(startx m-offset){ //中间剩下单行或单列 for(int k ..) } }while条件分别/2是判断纵向横向都能有完整一圈最后处理中间的字符串1.基本处理反转字符串也是用双指针的方法左右两个指针原地交换leetcode151思路是去多余空格、全部反转、单词反转。单词内反转思路可以用全部反转的方法去除多余空格从头到尾遍历字符串不是空格--是字母--加进StringBuilder是空格--sb最后一个是空格--说明是多余空格就要直接跳过是空格--sb最后一个不是空格--是正常的单词之间的空格--加一个空格因为如果是空格都会跳过所以自己加空格2. KMP算法用来匹配字符串查找文本串中是否有模式串。但是每次遍历会很麻烦用前后缀就可以减少查找的工作量找到一样的前后缀之后从后面开始继续查就少了相同前后缀这部分的查找比如aabaa相同前后缀是aa文本串和模式串开始不匹配时前面的都是aa就可以跳回b继续找如果b后面的一样加上前面的aa一样就直接找到结果了。前缀表一般用next数组或者profix用来匹配之后方便确定跳回哪里继续匹配可以右移前缀表作为next也可以全部元素-1。next[i]表示为这个元素包含这个元素之前的字符串最大相等前后缀的长度。比如aabaai指向b那么前面的字符串就是aab前缀a或aa//后缀ab或b没有相同前后缀长度就为0即next[i] 0。求next数组的代码部分A.设i指向后缀末尾j前缀末尾 初始化j前缀末尾0i因为是后缀所以要遍历找到相等的前后缀所以从1开始。B.前后缀字母不同说明要调整此时不是next应该记录的值。整个逻辑是i同时与j1比较所以比较的字母都是后面的。j为前缀末端当不相等的时候应该往前回退但是为了让回退效率更高不用一个个遍历就可以直接退到j的next的值的位置因为比的是j1所以是上一个即jC. 如果ij指向字母相同j此时j就是前缀长度赋值给next[i]。D. 用next数组来匹配字符串原理和前面的差不多但是j是计数器代表匹配好了几个字符最后是用jneedle.length()来判断不是length-1利用KMP求字符串重复单元重复单元即整个字符串-前缀/后缀算出next后--next【n-1】0 且长度n可以整除重复单元整除不了说明有剩下的字符不是完全由重复单元组成的3. 橡皮擦法eg一串n位数字相对顺序不改变删掉k位输出处理之后的最大值n位数字当然要换成字符串来解决如果数组排序之后删除前面的元素一旦位数多就很难处理。--- 所以用到橡皮擦法比如这道题要的最大值当然从高位 也就是数组0开始处理。要删k位类似于有k个橡皮擦一个可以删一位。将结果用StringBuilder-sb来记录遍历原始字符串数组c如果a.sb里面有字符数字 b. 现在c数组的数字比sb最后一个大 c.还有橡皮擦 ----- 把sb最后一个删掉还有剩余处理·如果橡皮擦没了长度比n-k大--- 多的数位从后面开始删·如果前面有0比如sb开头是009要把0删掉·写这道题逻辑容易有问题1. 在擦字符的时候应该用while循环while条件满足c[i]比sb最后一个大把sb删掉此时c[i]还是固定的持续找前面的数字如果一直小的话就要一直删处理完了再在while外把ci加入sb一开始用的if但是这样只会判断一位。比如sb123 此时要加9--- 正确93,删3 -- 12 -- 92,delete2 --...-- sb只有9if的话删掉3就没了2. 橡皮擦没有了不能break如果在while内橡皮擦rem 0break不会把处理完的后面的数位加入sb。eg 12345假设只有一个rem, sb1, c2, 21, sb变成2此时rem变为0如果break345不会被加入sb。4.贡献法这个方法可以处理某个元素出现在子集次数字串不同元素个数的问题。求这种问题不可能把子集求出来然后一个个计数。其实就是把子集对于元素换成了元素对于子集的思想针对字串中有多少个不同元素比如aba不同元素2。横着看是从左往右开始记录首次出现的元素[0,2]时2a为0因为0a2a都是a已经存在过了不再记录竖着看是 这个位置被多少个字串当作第一次出现。这个元素在所有子集出现的次数就是给这个完整结果贡献的次数。所以贡献法大致思路·字符串是数组c长度n现在元素位置为c[i]last是这个元素上一个出现的位置初始化为-1因为下标0开始大概情况[ ... last, .. i,..., n-1]·这个元素ci可以贡献的子集 的起点是[last,i]区间有i-last个·终点区间为[i, n-1]有n-i个·这个元素的贡献就是i-last*n-i更新last位置因为last记录了上一个元素所以下次遍历到相同元素的时候这个元素做出贡献的子集就不会有last元素可以按上面表格横向来理解last都1了再碰到一样的也是记0贪心部分最优解推出全局最优解写题设两个变量一个存当前答案一个存最佳答案不断更新最佳答案得到最终结果。1.股票问题算出每天利润和--最大利润加起来求总利润每天的利润和a天买b天卖是相邻的 和 买了隔几天卖其实是一样的eg abcdea买d卖 利润 d-a (d-c)(c-b)(b-a)-----每天的利润和2. 重叠问题A. 对二维数组里面一维排序B. 遍历数组从1i和i-1判断重不重叠重叠--先不加入结果更新最大右边界比如现在在判断第1、2更新边界后是2、3判断说不定123都是重叠的所以重叠先不做加入结果的操作不重叠-- 按照题目操作加入结果。。有时候需要两个变量来帮助加入结果比如一个left一个right后续if判断是否重叠也应该用right因为有刷新过而不是数组元素直接判断C. 加入最后一个结果用List来加结果动态规划动态规划的每一步都由上一步推导这是和贪心不一样的地方一般分为五个步骤1. 确定dp数组和下标含义。dp数组是用来记录状态的2. 确定递推公式。因为由这个结果才可以推下一个结果3. 初始化数组4. 确定遍历顺序。按照逻辑--哪个先遍历--从前还是从后开始5. 举例推导数组主要是推导整个逻辑的过程代码没有那么长1. 类斐波那契斐波那契dp[i] dp[i-1] dp[i-2]·其实这个数列还有规律取模会循环因为实质是状态转移假设数列每个对m取模那当前数cur pre1 pre2斐波那契每一项只由前两项决定f(n) f(n-1) f(n-2) % m取模只有0m-1m种可能所以cur最多只有m^2找周期的时候也要由前两个元素来决定比如最开始是112……等到11再次出现说明是一个周期但是不是只要连续两个余数重复出现后面所有数就会一模一样地循环--这表示有相同的一组就会停止寻找周期。所以如果有找周期的问题可以用pre1和pre2 1来退出判断。·爬楼梯题型一次只爬1阶或2阶如果要爬到第5阶--第4开始爬1 或 第3开始爬2如果题目里面算花费的话 注意花费和总台阶数关系注意下标和数组大小2. 最短路径问题dp[i][j] 表示到 (i,j) 的路径的数量推导到某个点路径过程是这样的m行n列i-1,jij-1i,jij是左边和上面的推导的到这两个点前面的路径是一样的且这两个点到目的点路径也是固定的题目规定只能向右走或者向下同理这两个点也是这么推导来初始化第一行第一列为1因为路径只能直走接着遍历利用公式dp[i][j] dp[i][j-1] dp[j-1][i]有障碍物的情况也类似首先判断起始点和终点有没有障碍否则return0再初始化遇到障碍物的时候障碍物后面的不初始化写代码要在for循环里面判断是否有障碍物如果循环内再写一个if判断-- if没有障碍物这个点1-- 障碍物后面的点也没有障碍物也会被初始化3. 背包问题背包也分为01背包n种东西各一个只有选和不选初始化dp[i][j]---- 考虑前i个物品背包容量为j的时候放完物品背包的最大价值递归dp[i][j] max(dp[i-1][j], dp[i][j-weight[i]] value[i])不放i在前i-1个考虑和放i背包容量要减去的最大值遍历时两层for从小到大一层背包一层物品顺序可以换也可以简化用一维数组除去i这一层dp[j] max(dp[j], dp[j-weight[i]] value[i])一维的时候两层for时背包要从大到小倒序正序会重复加物品完全背包n种东西每个都有很多个可以放多个进包内4. 打家劫舍1. 每个房子有对应价值不能连续打劫则打不打劫第i个取决于i-1和i-2设dp[i]为考虑前i个房子打劫得到的最大价值注意考虑不一定要选择初始化dp[0],dp[1]有递归公式dp[i] max( dp[i-2]value[i], dp[i-1] )i-2打劫了考虑i要不要打劫i-1打劫了所以i不能打劫这两种情况的最大值2. 如果是环形的打家劫舍会相对复杂一点房子的下标是01...n-1如果抢了0n-1就不能抢抢了n-1 0就不能抢。所以分为两种考虑一是0n-2二是1n-1开头结尾都不选的情况也包含在这两种内考虑不一定是要选可以用三个变量轮换来解决非环形的问题再将这两种情况求最大值就可以解决环形的问题public int Rob(int[] nums, int start, int end){ int x0, y0, z0; for(int i start; i end; i){ //x--dp[i-2],y--dp[i-1],z--dp[i] y z; z Math.max(xnums[i],y); x y; } return z; }3. 二叉树类型5要不要偷取决于46偷不偷所以应该从下遍历用一个数组res来代表某一个点的状态res[0]表示当前点不偷1表示偷此点不偷左右孩子偷但是偷的结果与孙子什么的有关所以偷了不一定结果会变大此点偷左右孩子不偷。因此可以得到递推公式result[0] Math.max(left[0],left[1]) Math.max(right[0],right[1]);result[1] root.val left[0] right[0];5. 递增/重复 子串数组长度A. 两个数组/两个字符串找这两个的重复序列最大长度之类的可以用二维数组记录·比如这个找重复子数组长度dp[i][j]表示以数组A下标i-1为结尾和B 下标j-1结尾 子数组的长度这样相当于规定了子数组的尾巴·递归公式dp[i][j] dp[i-1][j-1]1;------如果dp[i][j]都已经相同eg A的32B的32两个数组都再往后一位都是1也相同那最大长度也加一。·遍历的时候可以交换顺序先用for遍历A再for遍历B。eg A假设i是3时对应数组里面下标2也就是元素3。遍历B时可以想象成A固定在元素3B开始找相同的一直往后面遍历所以再后面有一样的也会记录长度。A再继续遍历往后固定一位B再次全部遍历与刚找到相同搭配的下一个元素还是一样所以dp 1。比较好理解为什么可以交换顺序可以用二维数组的图来理解A/B32141800000001000101020010000301000002002000010003000A\B32141810010102010000310000020200001003000可以看出来数字都是又左上往右下推的如果dp代表以下标j或者i的话第一行第一列不一定整齐要分别初始化比较麻烦。其他问题也是先推导公式找出初始化方法和推导顺序。要按不同情况分析。回溯回溯本质上就是暴力都可以抽象为树的问题大概分三步回溯函数模板返回值以及参数终止条件回溯搜索顺序大概套路是这样的定义两个数组一个存单结果一个存全部结果写一个回溯函数backtracting参数startindex规定开始的元素只组合后面的数避免重复在函数内判断startindex合不合法for循环遍历所有元素再调用backtracting因为后面startindex也要变大如果遍历方向多比如杨辉三角类型可以左下右下可以多设置几个参数。对应level层数start某层开始的下标现在的值之前的值等等·注意杨辉三角类型的有关左右步数不能设置left right 为全局变量回溯要回退全局变量改了的话回退不会跟着回去。子集子集问题关键是每个元素不是都要选。所以用startIndex来确定开始的范围这样选择其他元素只会向后遍历减少了重复的情况如果题目给的数组有重复可以加used[]判断这个数字有没有被用、去重的条件eg 122的子集定为11a1b如果有11a就不能在11b会重复去重条件if(i0 nums[i]nums[i-1] !used[i-1]){ continue; } // i0 判断i不越界这样主函数调用backtracting从0开始也不会进入这个判断 // 因为在nums数组内选择数如果前一个有被用说明已经在path内现在在叶子节点 // 如果前一个没有被用说明现在是选一个新开头1a选了后面的都判断完了 再选1b就没意义了子集部分问题也可以参考字符串的贡献法全排列全排列和子集不同在于全部元素都要参与就不用startIndex来区分了。去重条件也类似eg 1 1 21a1b21a--再选1b/2--112/1211b--再选1a/2--112/1212--再选1a/1b -- 211所以选了1a就可以不用再选1b反过来也一样全排列是在树层上去重子集是在树枝去重记得used[i] true时continue否则会有重复结果