这个题乍一看用二叉搜索树做不难。但自己折在了“Count += root -> count + 1;“ 我写成了"cout = root-》count+1；insert_node = count" 这其实是难点所在。 每个节点的count都记录了左子树所有的节点的个数。这也是二叉搜索树的精华所在。可以 直接跳到下一个大于当前节点的位置。那这样看来count的值一定是+=计算下来的. 二叉搜索树示意： （8 9 10 （5 6 7））可以看到，每个节点左子树都记到了碰到比自己大的地方就停止了。 所以不会出现我想的重复加的情况。count(7) = 2; count(10) = 2;所以如果下一个是11 的话，计算过程是2+1+2+1 = 5;
首先说一句自己太菜了，这么简单地题做了很长时间 这道题跟迷宫题很像，只不过这道题相当于是多个出口。 先把所有的0全都压入队列，然后逆向bfs 判断是否入队列的条件就看这个点之前有没有入队列过 如果没有如果队列，就一定是1，此时也一定是到达这个位置的最短位置。 这个题学习两点：1.记住方向遍历的简单写法2.二维vector确定大小和初始化的写法
还是太菜了，试了很多想法要么是超时，要么是错误。想的麻烦了。 最朴素的dp就完事了。n2复杂度。对于每一次内循环，起点是不变的， 只需要更改区间[first,second]的j就可以，改变之前先检查一下，当前的数在 不在区间里。如果在返回true，不再就看是否会让这个上升区间拉长， 可以的话就把second改成当前的nums[j]。初始的first,second可以设置成nums[i] 显然这个做法不是最好的。但思路很清晰。 另一种：问题是在一个整数序列中，有没有一个子序列符合 ai < ak < aj, 其中 i<j<k 所以可以把问题转化成，找到一个元素 aj, 在区间[1, j-1]里有比他小的元素M1，在区间[j+1, n]里也有比他小的元素M2, 并且M2>M1 所以这里需要让M1尽可能小，所以第一步就是维护一个最小前缀值的数组，即aj对应的最小M1 因为有了前缀最小值，所以我们可以很快判断aj和M1的关系，接下来的任务就是找M2。 首先可以想到暴力解，遍历[j+1]到n的每一个数，时间复杂度是O(n^2)，那么有什么办法可以优化这部分，我们可以从数组尾部开始向前维护一个单调递减栈， 对于每一个aj，如果aj>M1，然后在当前栈中找比M1大的最小值，即以M1为最小标准值来维护这个递减栈之后的栈顶元素，如果栈顶元素小于aj，即找到我们所需要的情况 为什么以M1为最小值维护栈不会对后续造成影响 我们先看看最小前缀值数组有什么特征，很容易得出它是一个非递增数组， 后面的元素都小于或等于当前元素，所以如果当前栈里的元素小于 aj 对应的M1，那么肯定也小于a[j-1] 到a[1]对应的M1，所以直接出栈即可。 为什么最后可以直接入栈 在上一步以M1维护栈之后，栈里的元素都是大于M1，此时如果栈顶的最小值小于nums[i],就已经找到我们要的情况，否则的话栈内元素都是大于nums[i]的，直接把nums[i]推进栈，不影响递减。
水题。但是为什么我换成了尾递归只有，内存反而用的更多了？不理解。
水题。第一遍直接暴力反向dfs。但后来看了一个解答提了两个字方向。立刻恍然大悟。 就是一个if判断。哎还是太菜了。不能套思路，要活学活用啊！
贪心算法的水题。先把两个数组排序。从最小开始比，如果A[i] > B[i] 就把这个数相互对应，否则就消耗掉一个最大的B，使得这个A利益最大化。 为了找到排序后的要放的位置，对B的数进行了位置标记。
这道题也不难，就是自己写的太啰嗦了。总体来说就是栈。 从左到右扫描，分别记录上升序列，用最大的元素代表这个上升序列。 如果碰撞的话，最大碰不过的话，下面都碰不过了。最大的可以碰过，后面的也就都可以保护。
水题。没用递归，感觉递归不好用，直接用了for循环。还有就是字符串的加法。
这道题没有做出来，虽然想到了用二分，但是没有想到用抽屉原理。对于这种无序的数， 确定一个n长度的序列，随便猜一个这是重复的数t，如果小于等于t的个数>t，则说明 重复的数字一定就在[1,t]之间，否则就在[t+1,n]之间。这就是抽屉原理。
这道题是好题。第一次用快慢指针做循环链表入口问题，以前记得写文法的时候 遇到过判定的问题，直接暴力的在结构体上打标记。。。我再来简单证明一下。 快指针f，慢指针s。f移动速度是s的2倍。有循环时，第一次相遇有如下的结论： f=2s和f=s+nb(b是循环列表的长度)然后可得s=nb,f=2nb.说明相遇的时候s走了n倍的 环，f走了2n倍的环。如果让指针，定位到环开始位置（任何走到换开始位置的指针的步长 都是a+nb，a是不在循环里的步数），只需将一个指针x定位到head，让他和s指针一起移动， 在环入口时x走了a步，则s走了nb+a步，所以相遇时就一定在循环链表入口了。
这道题的难点在于限制了空间复杂度(O(C))时间复杂度(O(n)) 看了解析才会。初始想法当然是弄一个visit数组，看到一个数就visit[i]=1 标记完后从0--nums.size()为下标遍历，第一个没有visited的数就是所得。 但这样空间复杂度就会不满足要求。于是用"桶排序"（第一次听说)就是直接 在原数组的情况下，如果nums[i]!=i+1,就说明他不在原来的位置上。需要 调换nums[nums[i]-1]与nums[i]放到正确的位置，并同时i--，让下一次循环 处理这个新的nums[i],最后扫描数组 第一个不满足 nums[i]==i+1的就是结果。
贪心算法。这个题比较简单。维护一个严格单调递减栈。这个时候的基础和就是这个栈的长度n的 累加求和(n+1)*n/2,之所以说基础和是因为还要考虑边界问题。如果这个时候的边界的最左边a的糖果（也就是 最大值），小于等于上次的最右边b的糖果（也就是最小值），但同时a的得分大于等于b的得分时，就要多给a糖果， 使得满足要求。这样可以保证分发的糖果最小，因为从递减数列的最小的人开始发，而且边界值也得到了保证。
把2,3,5指针指向当前可扩展的对应数字a,b,c，然后比较2a,3b,5c最小的就是当前res[n]的值 并相应的吧指针++。同时为了避免重复2a,3b,5c可能会出现重复的情况，所以要用3个if，把三个数都扫描一遍。
这道题做了很久。哎。把“前n个数里包含几个丑数”都想到写出来了，都没想到用2分来确定这个数。还是对二分不熟悉。 这个题注意一下两点：第一：3个数a,b,c的最小公倍数 abc的最小公倍数/gcd(a,bc的最小公倍数),而bc的最小公倍数 是用bc/gcd(b,c)第二：二分法的应用。
水题。两遍二分就可以找到左右边界。值得注意的是，一般我们总是在二分的时候：if(nums[mid] < target)left = mid+1; 总是把等号加在right那边是有原因的，因为int自动向下取整，比如说对于数组5，7，7，8，8，10，想要查找8，如果判断条件 是if(nums[mid] <= target)left = mid;就会死循环左右指针会卡在4,5.解决办法就是对int向上取整。
这道题用的归并排序。总结一下几点： 1.归并排序的内容 2.能尽量在循环外赋值就在循环外赋值，找这个超时的点找了一个多小时 3.以后对区间和的题，要有意识的想到前缀和数组，这道题就是先求前缀和数组，然后对前缀和数组归并排序，当两遍排好序归并时 对于每个在左array的元素t，两个指针指向右边开始数组开始位置分别求<lower和<=upper的终点用右边的array的元素-t 差为b，以此来求出满足<lower和<=upper的区间和的终点，做差就是在lower和upper 之间的个数了，而且两个指针不用回溯，因为left对应的数在变大，两个指针对应的数只有变大才可能符合要求。
双指针，一边扫描一个链表倒数第n个结点，先让一个指针p1向前走n个，然后另一个指针p2指向头节点后，移掉最后时候p2指向的就是要删除的节点。
这道题是哈希和滑动窗口的应用。滑动窗口的长度等于words数组所有单词的总长度。哈希表里存放的是每个单词在words数组里出现的次数。 对s字符串遍历，每次取滑动窗口的大小，对于滑动窗口里的单词，如果可以在滑动窗口开头找到一个单词并且单词对应的哈希值不为0，就可以移动滑动窗口内部的 指针，直到吧滑动窗口遍历完。如果中途没找到单词，就break，说明这个滑动窗口不符合要求，否则这个滑动窗口就是一个答案，滑动窗口开始位置压进vector。
dp水题。
dp水题。
逆序dfs，一遍过哈哈哈哈哈哈！
更新：字符串不要用这个算法了。这个算法太破了。一点都不形象。算法去看132题。 总结两点： 1.找回文串就是把串倒过来匹配最长子串。 2.把字符串倒过来之后只是匹配最长字串还不行，可能有这种情况， aacbdfcaa 这个串和倒过来的串最长字串是aac是不对的 所以还要判断这个时候匹配的串和原来是不是一个位置 i:反转串指针 j原串指针 vv当前最长子串长度 判断他符不符合回文串： 用这个时候的坐标i-vv+1得到回文串在反转串起始位置 如果加上j等于等于总长度-1 就符合条件了。
dp水题。滚动数组优化。
这个dp写了块两个小时，不应该。 总体思路是栈加dp，但我的算法的dp感觉有些诡异。 首先确定Maxlength = 等于当前的括号对（也就是1）加上now在加上左括号对之前的挨着的最长的括号对 换句话说，maxlength=1+左括号之前的连续的括号对+当前括号对之间的连续的括号对 now指的是当前存在的最长的括号对 ()()这个时候的now就是2，()(这个时候的now就是0 当遇到(时，标记上这个左括号之前的最长的连续的括号对为now，存到tag[i]，然后把now请0，然后下标入栈。清0是因为我们maxlength求法的缘故，因为还要加上 括号对之间的，所以必须把(之前的要清0 当遇到)时，栈空是之间将now=0，表示对当前)的下一个符号来说，之前并没有连续的括号对了（因为当前已经不匹配了）。如果栈不空，根据栈顶元素找到 这个元素之前的now，在+1，再+tagi然后更新最长的length。
ps:https://www.cnblogs.com/ganganloveu/p/4148303.html这个讲的最好 用这个博主的思路做题会更清晰！！！！！ 这个题写了一天。哈哈哈哈哈。自己太浮躁了，被关了太久，沉静不下来学习。明天要改，今天相当于放假了。 这道题最终被我转化成了求最大矩形的题。最大矩形的题在csp2013年出过，我还做来着，可能当时就是用的暴力写的吧。 转换成最大矩形的思路就是对于每一行求最大矩形，没一行的每一位上的数字代表从当前位置向上连续一个个数，然后这个大小就代表了矩形的高度。从而转换成了 求最大矩形。 求最大矩形方法：维护一个严格递增的栈，当大于栈顶元素时就入栈。当小于等于时，需要把所有大于等于当前元素的数出栈。出栈后要更新这个时候的最大矩形的面积。 因为递增，所以高度肯定是刚刚出栈的元素的高度，底边长就是j-stack.top-1，为什么这么求，是因为存在这种情况2，5,4,6,3。5会在中途出栈，当3要插入时，5已经不在 栈中，所以要减去此时的栈顶，也就是要计算3到2的距离，因为不包括3本身（3到后面统一处理），所以要减去1.当弹出一个数后栈空时，说明此时插入的数目前最小，前面没有 小于他的数，所以直接用j出栈元素高度。插入栈元素完成后，会在栈里保留递增的序列。依次弹出他们，更新最大面积和上面稍有不同，只需要加1 j-stack.pop和(j+1) 出栈元素高度。因为要包括最后一个数了，因为他最大，一定可以包含在之前的矩形里面。https://blog.csdn.net/zhdl11/article/details/83578152
异或运算。找出数组出现一次的数字，其他数字都出现了两次。这个时候把所有数字异或就行了。两个相同的数异或是0,0和一个数异或等于这个数。并且异或有交换律。 2^2^1=1,2^1^2=1.保证了正确性。
异或运算。找出数组中出现一次的数字，其他数字出现了三次。这个思路和上面的一样。这个题用的通用解法，136题相当于是本题解法的简化。对于所有数的每各位， 出现1的次数应该是2的倍数或者2的倍数+1,所以那些2的倍数+1的位置就是只出现一次的数字的对应的1的位置。
这个方法很巧妙。题目“给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。”在一个数组里肯定是找不到的。 要把两个数分到两个数组里，再用上面的异或的方法找。那怎么分数组呢。把所有的数都异或后的结果应该等于那两个出现一次的数的异或。这个时候取lowbit，这个数一定 是这两个数其中一个造成的，肯定是一个数在这个位上是1，一个是0.然后判断所有的数和这个lowbit相与，等于lowbit的在一组，不等于lowbit在一组，这样两个出现一次的 数一定在两个数组里，并且相同的数也一定分在相同的数组里了。然后在运用上面的算法就可以了。
2的幂。判断这个数的lowbit是不是等于本身即可。比较坑的是，为了防止越界，要先把int扩展到long 再进行lowbit，要不取负数操作会越界。原来扩展到long要直接用赋值才行 像这样m=n，m是long，n是int。。。
朴素做法是滑动窗口+哈希。但是复杂度是10n，可以通过把字符映射成数字的情况，即A：00，C：01，G：10，T：11.每次向左移动两位，看看20bit的数是否之前出现过， 可以减少空间复杂度和时间复杂度。bitsets,相当于开了一个n大小的01数组（有点不太像set），这样可以节省空间，并且可以用作哈希表，可以随机访问，比如说 这次visit了一个数是1，那么就可以s.set(1),就做成visited的哈希了。
dp爬楼梯。水题。
编辑距离。用的朴素的二维dp，一遍过。最重要的还是转移方程。总结两点： 1.两层循环，第一层是要改变的word，第二层是模板word2。为了便于写代码，我自己在Word2前面加了 一个井号键，表示空，这样的话遇到这个字符直接等于第一层的word指针的下标之前的字符长度就行了（相当于把word变成空，全部删除即可），这样便于下面写 转移方程，就不用考虑边界问题了。对于word1也是，首先首先处理一下把空串转化成word2的步数。 2.转移方程时，dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1]分别对应替换，删除，插入。如果这个时候i和j指向的字符相等，转移方程就变成了 dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1，dp[i-1][j-1]).
dp.感觉对这种dp数组是一维的已经全都掌握了？？一遍过。 这个题需要记录两个数组，一个是到目前为止的解码方法dp，一个是记录以当前单个字符结尾的，即当前字符一个数结尾的个数 比如 1 2 dpDan[1]（1是指针，指向数字2）等于1。1232，dpDan[3] = 2,因为 1,2，3,2和12,3,2。初始dp[i]=0,当当前字符不为0时，说明可以以这个单个字符为结尾进行解码，此时dp[i]+=dp[i-1],同时更新dpDan[i-1]=dp[i]。然后看看当前字符 和前一个字符可以不可以组合来作为结尾进行解码，如果可以dp[i]还需要在加上dpDan[i-1](就是相当于直接把他放到了上i-1这个单个字符的后面，个数正好等于dpDan[i-1]）
三维dp。可以当做多维dp的入门题来复习。虽然没写出来。但不想多些思路了，可以看题解。
dp一遍过。分成左右字数去考虑。如果想递归，就很好做了，只不过是把递归改成递推。n个点的数结构个数=j个点的左子树的结构个数*n-1-j个右子树结构的个数，n-1是 是因为1个点要当根节点，j的范围从0-n-1。
自己的想法是取每个数的lowbit，设最大的lowbit为t，t假设=10000，则小于在这个1前面的位数不可能有1，因为这个1后面就都是0了。然后一步步求出结果。但是这样 复杂度也很高。看了一个答案说，“可以得出题目其实等价于求m和n从高位开始，有多少位是相同的，这些相同的位组成的数就是答案，”恍然大悟。自己的错误在于 还是没有充分利用题目给的信息，可以看到这些数都是连续的，连续的就一定存在进位，所以从最大数和最小数的最高位相等的位数就是结果了。而我那种方法适用于 不是顺序的情况。所以要充分利用信息。
这道题不知道为什么写的很有成就感，虽然写了3个小时。很慢。但是第一次用python写题，也是一次过的。 整体思路是dp的思想。一开始想的是从左到右dp，后来怎么算都不对，最后才发现只能从低位到高位dp。 整体的思想是：当前位之后所有的1（比如287，当前位置是8时，就是指87之前所有的1，当前位置是2是就是287之前所有的1）由三部分组成： 拿287举例:Sum(287)=Sum(87)+1100+220.Sum(87)是上一步dp的结果，也就是对应的201-287中的1的个数。1100对应的是101-199之间的个数。 220对应的是0-99，和101-199之间的1的个数（这里只统计101-109后两位的1的个数，所以202就可以了，第一位上的1在1100统计过了），20 怎么来的呢，通过def getInterNum(self,n)这个函数来的，整体思想和上面一样的，在代码里写了。可以找到规律，0:0,10:1,100:20,1000:300,10000,：4000.所以202就可以了，第一位上的1在1100统计过了），20直接 用O1的时间复杂度去获得，节省时间。 当0的时候直接跳过即可，当1的时候需要特殊处理，比如Sum(187)=Sum(87)+(1+87)+1*20,中间的一项变了，是因为不能100了，因为最多只能到达187,188-199的后两位 的1不能统计。 哦对，这个题我一开始就看到了连续这个条件，算是吸取了上个题的教训。
挺有意思，想到了肯定用递归，但没想到终止条件怎么写。原来用串联原则。
https://www.cnblogs.com/magisk/p/8809922.html 这个是bitset的用法。 这道题想了块一天，一直觉得马上就要做出来了，可以就是dp的含义定义不出来，所以导致不会写。原来是状态压缩。dp[i][j]表示第i行的坐法是j时前i行所容纳的 最大的学生数。首先是找出本行的可行的状态，可行状态表示要放到.的位置并且不能挨着坐。不可行的状态相应的dp值标记为-1.可行的话，再去找上一行与之可行的 分布，这里的可行就是斜着不挨着然后上一行本行也可行。如果找到的话就更新dp[i][j] = max(dp[i][j],dp[i-1][j]+(int)bs.count());
这道题又做了很久，是状态压缩+记忆化搜素。一开始一直不知道怎么记忆化，以为需要记忆的东西不仅是数的使用情况，还有在这种情况下的desiredTotal，其实不用 因为状态直接对应了最大的问题也就是maxChoosableInteger，desiredTotal下的结果，不论desiredTotal多大。所以只需要记录使用的数的情况就行了。用bitset，很好用。 一个用来记录是否被记忆过，一个来记录对应的真值。 整体思路就是深搜，当这个状态被记忆过，就返回相应的真值。否则，挨个使用没用使用过的数，(如果这个数，直接大于了desiredTotal，返回true),把相应的传进来的status 的第i位改变，以及desiredTotal减去i，继续传入dfs，注意这个时候我们要返回值的相反值，因为这个时候相当于是对方在取，如果对方做不成，才相当于我们完成了。
水题。dfs深搜枚举一遍过。
记得当时在算法课上的例子。忘了是不是用01背包的dp做的了。如果直接用O（counts^2）会超时，要用01背包思路借。这个是完全背包，完全背包是恰好装满 01背包的转移方程还好写。主要是初始化。如果朴素01背包，就是dp[c+1],全都初始化为0，每次倒着遍历。如果是完全背包，每个物品可以放好多次，dp[0]=0,其他的 初始化为最小值0-x3f3f3f（如果求最大值的话）,然后正着遍历。这个题可以当做模板题。
贪心水题。
二维费用背包dp。写了3道题01背包，我觉得最关键的就是找到那个是容量，那个是价值，那个是物品标号。不要把容量和价值搞混了。像这道题，我一直吧01的个数当做 了价值，其实他是容量，而每个数的价值是1，他的二维重量就是0的个数和1的个数。
第一次参加周赛，比较失败，继续努力。这是一道贪心的好题，我的思路想出来了，但是没想好用什么数据结构。 代码里的思路是这样的：首先明确一点： 对于同时开始的任务，我们会选择先做结束时间早的，这样可以把机会留个结束时间完的任务做。这个简单证明一下。 如果不是先做结束早的，就可能会错过当前结束时间早的，而少做任务。 然后我们看这道题，我们遍历每一天，我们也选择对于当前来说结束时间早的，，因为对于当前来说，那些之前开始的任务和今天开始没有区别，所以就可以把上面的 贪心的思想套用过来了。数据结构选择优先队列。但我没想到的是，怎么动态的选择对于当前天来说最早结束的会议？总不能每一天都排序吧。 原来是提前用On的时间算好每个时间点开始的会议的序号，然后从大到小遍历每个时间点，把当前时间点开始的结束时间压入队列（队列里还有之前开始的会议的结束点，都看作 是现在开始的），然后让小于当前时间点的结束点出队列，选择最小的结束点。然后ans++,出队列，继续遍历时间点。
这道题好简单。先排序，从大到小反着求，自己反向看是不是可以求出全1就可以了，为什么是hard呢？？ 对，这个题需要总结的是优先队列的排序，以前总是写成struct，把数据当做struct里的属性，然后重载<，学到一种新的pair的写法，重载()，在代码里。
贪心。首先确定所以出现的字母，然后记录每个字母出现的位置。然后在出现的子母中，从a-z遍历，如果当前字母的出现比某一个字母的最后出现的坐标还要大，则 这个位置不能把当前字母加进来，（举例cab，会先遍历a如果把a加进来，就会让c在a的后面，会打乱顺序了）因为会打乱相对位置，所以要向下遍历字母，直到当前字母的 最小坐标不会大于还没有出现过的最大坐标（cabc,这时a可以加入),当把a加入后，就要把a之前的字母从vector里删掉。
旋转链表，双指针，水题。
二维dp。按理说这题应该会的。失误！要复习! 整天思路就是dp[i+1][j+1]表示s2的前i+1个字符和s1前j+1个字符能否组成s3前i+j+2个，转移方程是dp[i+1][j+1] = (dp[i][j+1]&&s2[i]==s3[i+j+1] ) ||(dp[i+1][j]&&s1[j]==s3[i+j+1] );意思是当前能否成功取决于任意两个情况成立:要么s2前i个字符和s1前j+1个字符可以拼成s3，同时s2第i+1个字符等于s3的第i+j+2个字符 或者要么s2前i+1个字符和s1前j个字符可以拼成s3，同时s1第j+1个字符等于s3的第i+j+2个字符。 仔细想了想，自己没做出来的原因是被交替出现糊弄了，或者是根本因为交替出现就没想到这种dp，其实只要初始状态保证了交替出现，递推下来就都可以保证交替出现了。 这也是很重要的一点，所以以后要想初始情况满足，这里的初始情况就是当一个字符串为空，另一个不为空时，假设不空为s2，就匹配s2前缀和s3前缀最长的是true，当匹配到 不相等时直接跳出循环，后面的都是false，这其实就保证了交替出现的定义了。
一遍过。二维dp。主要就是转移方程。首先还是要考虑边界，也就是dp的两个维度多开一个，dp[0][0]表示都是空串的情况。 dp[i][j]表示s前j个字符包含多少个t的前i个字符。转移方程是 如果t[i-1]==s[j-1],dp[i][j]=dp[i-1][j-1]+dp[i][j-1];如果不等， dp[i][j] = dp[i][j-1]; 不等的情况好解释，就不解释了。解释第一种情况。当相等时，可以把s[j-1]当作是最后一个匹配的字符，相当于直接在dp[i-1][j-1]的匹配情况下结尾追加了一个字符。 当不考虑s[j-1]时，也就是s的前j-1个字符可以包含多少个t的前i个字符，也就是dp[i][j-1],把两者相加即可。
这道题不会做，很有挫败该。做了很久很久很久，做错了。总结两天，第一个两个字符串按字典序混合，使结果最大的函数。第二个求一个序列包含k长度子串的 字典序最大的函数。
贪心题。代码里的注释很详细，可以去看代码。核心是一个问题，当当前的可以覆盖的和的范围是[1,n)时，添加一个数m则覆盖范围是[1,n)并[m,m+n).所以每次为了连续，每次都添加最大的数，也就是n， 这样范围就是[1,2n)了。
贪心。思路可以看代码写注释了。在不满足交替的情况下相当于把上一个元素出队列，再把这次的元素进队列。举例：比如1,2,5，3,在指向5的时候不是递减了，就应该把2出队列，换成 5，让高低差距尽量大，这就是贪心，有利于后面把小于5而不是小于2的数加进来 正确性：首先把2换成5不会影响现在的结果，只会让结果>=当前结果。那如果在2开始把 2,5看做是交替数列的开头才能得到最大结果呢？这个时候 就相当于把2放缩成了1，结果还是对的。
贪心。南大夏令营机考原题。哎，现在看这题就很简单了，说明这段时间刷题还是有点进步的。 思路也很简单，O(N)的复杂度，找到第一个递减的数，把他删除掉即可，删除后，要把删除后的字符串的前导0删除，比如1005，把1删除后，在这次循环的末尾要两个0删除 ，如果在这次循环中指针已经到达了字符串末尾，说明前面都是递增的，直接删除当前指向的字符即可。
贪心算法，一遍过。首先想到的是要确定相对位置。就是对于进入ans vector的人，相对位置是不能再变的。本着这条原则去贪心，也就是让身高大的先进，对于 相同升高的，前面人数小的先进。因为对于身高大的来说，后面没有比自己更高的人了，所有后面的人在什么位置，都不会影响我目前在 队列里的相对位置。如果所有元素都保证了进入ans后相对位置不变，那加入所有元素后，自然所处的位置就是最终位置。
本质就是区间调度问题。主要是区间调度，先选早结束的贪心算法的正确性证明给忘了，这里稍微写一下。 假设早结束的为[1,X] ,这个时候因为这个区间被删除的区间为[2,x2],[3,x3],可以看到这些删除的元素互相之间也是相交的，所以并不会出现因为保留一个 被删除的区间会是最终保留的区间变多的情况，但这个时候我们只证明了保留早结束的区间的策略所获得的最终结果=保留删除的其中一个区间的策略所获得的最终结果， 但是我们选择的策略会尽早结束，给后面区间的开始时间更多地选择，所以此策略是可行的。
还是贪心，区间调度问题。只不过这里像[1,2]和[2,3]这样的也需要看成区间相交。
贪心水题。每次先发小的饼干给需要小的人。
贪心好题。这个思想可能会常用。一开始想用01背包做，但复杂度接受不了。于是想到贪心，但没想到用什么贪心。一开始想从小于等于当前W的需要资金的项目 里面找到收益最高的去贪心，但复杂度也是n2。总的来说就是实现思路不对。设置大顶堆A小顶堆B，大顶堆放入当前可选项目，按照收益排序。小顶堆放入当前不可选 的项目，按照需要资金排序。每次从A里选出收益最高的，也就是队列顶元素，然后出队列，然后将B中现在可选的项目加进A中，重复此操作。 这种思想应该适用于贪心的目标受两种限制，并且这两种限制的方向是相反的，也就是一个越大越好，一个越小越好。
这个题只想到了怎么去计算，当间隔足够大的时候安排，当任务数-1>间隔的时候怎么做。当大于的时候整体的时间就是总任务数了，因为相当于不会浪费时间，没有出现 等待时间。具体解释可以看 https://leetcode-cn.com/problems/task-scheduler/solution/ren-wu-diao-du-qi-by-leetcode/ 官方题解的方法三。
这道题又做了好久.贪心，错在了怎么贪心上。我想的是先选紧急的，也就是如果事件要完成，最晚需要考虑去做的时间，从小到大排序。如果可以做就做。 不可以做，就从现在已经选择做的是事情里选择占用时间最长的那一个，如果大于当前事件，就换掉，可以缩短当前所用的总时间，为后面的事件多出更多地空挡。 可是正确的做法是按照结束时间早晚排序，后面和我的做法相同。不知道我的为什么不对。
回溯算法，一遍过。
二维dp，一遍过。保留到达每个位置上的最小值。滚动数组优化，优化思想和01背包是一样的。
卡在双周赛的最后50秒ak。这种事情也可以让我赶上。
滑动窗口好题！这道题好好总结一下，滑动窗口的题应该就都会了。这个题不仅要记录t中的字母，还有次数 全都用visited数组解决，visited[i] 代表出现次数，未出现的为-1.设置窗口start end 当 碰到t中字母时，记录到visited 并统计这个时候出现字母的种类数（只有当每个字母出现的次数达到要求了种类数才会加1，所以也隐形检查了）是否满足要求， 满足要求的话这是可能不是最终答案，因为这是的start可能还可以向后移动，检查办法是检测相应的visit数组是不是负数， 是负数说明目前这个串中start指向的字母的个数多于要求的个数，然后移动到visited不是负数的地方，这是就是满足要求的串了。
这道题要复习，答案的写法很好，数据结构用的也很好。先统计出0-9的个数，然后求所有数字和的膜3的结果，如果==0，直接从达到小输出即可。 如果是1，要么是余数是1的数字多了一个了，要么是余数是2的数字多了两个，先删除余数为1的数字1个，如果没有，那肯定是多了两个余数是2的，删除这2个。 所有数字和的膜3结果=2的情况类似。
倒序建树。感觉不难，不知道为何是hard。已经快20天没做题了。为了赶due，可惜可能赶不上了。另外leetcode刷题超过100道了。
同样还是倒序建树。一样的思路，这道题就是medium的了。蜜汁难度设置。
贪心。不知道这个题的意义在哪里。这个贪心感觉有点勉强。水题。
贪心。学习的有两点：第一是代码的书写，思路想出来了，但自己写的代码和选的数据结构很啰嗦。第二是还没弄懂，为什么第一策略要选择把这个数作为结尾， 而不是作为一个新的三元组的开头呢？
写回溯算法的题的时候心情总是愉悦的，因为总能一遍过。
这个题真的不应该错。本想用贪心。但贪心太麻烦了。用dp很容易。每个时刻都有两个状态，持有股票，和不持有股票。 初始状态的hold = -price[0],nothold = 0.当遍历时，更新每个时刻的hold和nothold的值，具体规则就是hold要么不变，要么在之前nothold状态下买入股票， 两者取最大值。nothold要么不变，要么在之前hold的状态下卖出股票，并扣除手续费，取两者最大值。最后返回的是nothold也就是卖出股票状态下的最大值。
前缀最小数组，水题。
dp。思路和714差不多，只不过每个时刻的状态变为了5个。hold0,hold1,nothold0,nothold1,nothold2.意义分别是，完成0次交易hold股票的最大利润，完成1次交易 hold股票的最大利润，完成0次没有hold，完成1次没有hold，完成2次没有hold。最终结果就是nothold1和nothold2的最大值。转移方程也和上面类似，不多说。
判断单调递增数字，一遍过。思路：设当前数字长度为m,从低向高位检查，如果当前数字是递增的，返回；如果不是，就把低位n为都变成9，高m-n位数字的大小要减1， 保证变化后的数字不大于变化前的数字，n的变化从1到m变化。
贪心，复习。做了很长时间，但最终还是做出来了。我觉得对于这种区间贪心，对于区间的排序很重要，一开始我是让区间的第一个数小的在前面，但这样会造成一种错误的情况 出现，处理起来还挺麻烦的。后来猛地想起为了避免这种情况，按照区间结束小的在前面就可以拒绝这个现象。 算法思路：现对于区间按照第二位的大小排序。对于每个区间，如果当前set已经和这个区间相交2个元素了，continue；否则就设置两个数，在设置这两个数时用的是 贪心策略。我们每次都尽可能选取价值最大的数，也就是这个数，在包含在当前区间情况下，在下面未遍历的区间出现的次数最多。这样我们就要选择，最大的数， 和最大的数-1（如果这个区间只需要1个数了，那么第二个数不用选了，为了写程序方面，设置成一个无效数，比如-100）。为什么这样设置就行呢？因为排序后， 假设x1在下面出现次数最多，那么x1+1的出现次数也一定会等于x1的出现次数。大家可以画图试一试。这样就可以使用2个元素相交最多的区间了。
这是一个好题。可以总结很多东西。第一个是对于一维dp和多维dp掌握的不好，对于表格式的dp还可以。这道题是个一维dp。 第二点是对于回文串的判断，这道题就是标准答案了，以后就用这个模式求回文串，或者像leetcode5那样的题。
一维dp题， 单词划分，一遍过。总感觉这题做过，但竟然没有提交记录。
这个题自己做的不是贪心，就是一个哈希表就解决了，复杂度接近O2，看到网上用On做出来的。学习一下。 第一：先遍历一遍，用字典存储每个字符最后的位置。第二步：从第一个字符开始遍历，每获取一个字符就该字符最后一次出现的位置索引定为当前片段的最后位置， 在达到该位置之前，继续寻找更靠后的最后位置，若达到最后位置之前都没有发现更靠后的最后位置，则将当前最后位置作为一个片段的末尾。 这个思路很好，学习了！
现在世界真的好乱啊，英国已经开始采取群体免疫策略了。这也太疯狂了。我是真的怕了。发达国家莫不是有自己的一套模型？按说他们的科技水平和数学水平应该 比我们高啊？ 这道题实在不想debug了，有很多种做法。看了一个答案。非常妙！倒着dfs，也就是从边界的o开始dfs，凡是与边界的o相连的，都是不能被设置成x的，那就在这上面 插上旗子1.最后遍历整个map，为1的还是保持o，其他的都变为x。这是思路非常妙，都是有逆向思维在里面的，和上面那个题一样。学习了！！！
dp+dfs.思路和139题一样，只不过要记录当前dp[i]可以切分成字典里的单词的时候的位置，也就是使(dp[j]&&dict.find(s[j+1:pos]!=dict.end())成立的j的位置， 然后再用dfs去拼接单词就可以了。简单题。
一开始感觉很难，但一看数据范围。4-60哈哈哈，这啥算法都能跑通把。如果偏要叫他贪心的话，就是每一步移动都要凑成一对情侣牵手才行。而且可以证明 凑成任意一对即可，不会出现，在当前选择调换x1,x2时，调换x3，x2或者x3，x1会凑成更多地情侣牵手。所以直接for循环，每次凑成一对即可。
堆优化。看到这个题的第一个想法是01背包，但一看数据范围便作罢。比赛结束后，又想到会不会是最大矩形的题，但这个和最大矩形还不一样，因为底边长度不是 定值了，正确性就没办法保证了。后来一看题解，竟然这么简单。但自己想不到肯定是有原因的。思路在这：https://www.dreamwings.cn/leetcode1383/5576.html 自己叙述一遍：首先按照效率从大到小去排序，排序的目的就是为了后面保证当我处理当前效率时，效率比我大的就不用处理了，因为是从效率比我大的位置遍历过来的， 用到了一点记忆化的思想。排序后，从大到小遍历，将等于当前效率的工人的速度压进优先队列，这个时候队列里的个数可能会大于k，就把最小的数pop出去，直到等于k。 然后算这n次遍历的最大值，就是结果。复杂度就是，在n次的循环中，每次调整有限队列的时间是logn，所以是nlogn。我觉得想不出来的原因就是没有建模成那种矩形 题的形式。
这道题是dp，虽然做出来了，但是总感觉代码写的不够简洁。因为写的不对称，如果对于每一个元素无论正负，代码的结构都是一样的，就好了。 看了别人的答案，感觉更清晰。别人是划分最大值和最小值，并不区分这两个值的正负，而我设置的两个变量是最大正值，和最小负值。所以有一点麻烦。 maxDP[i + 1] = max(maxDP[i] * A[i + 1], A[i + 1],minDP[i] * A[i + 1]) minDP[i + 1] = min(minDP[i] * A[i + 1], A[i + 1],maxDP[i] * A[i + 1]) dp[i + 1] = max(dp[i], maxDP[i + 1]) 这是转移方程，对于0来说max和min都变成0，初值的max和min都设置成nums[0],从1开始遍历。我发现我非常纠结于变量的初值设置。如果算法过分依赖初值，那肯定 是算法不够好，以后要注意。
贪心。维护一个字母出现个数从大到小的优先队列。每次取出前两个，也就是每次都优先消耗出现次数最多的两个字母。如果消耗完后个数等于0，就不放入队列了， 成功返回条件是队列长度为0，当取不出两个时并且第一个剪完1后不为0时，就是不能互不相邻。这个要注意，排序的时候还要再排一下字母顺序，因为对于相同个数的 ，比如aaabbb，他会返回abbaab，所以要规定一下字母顺序就好处理了。 别人的思路：判断是否可以成功返回的条件是，最大的字母个数是否小于(字符串长度-1/2),也就是隔一个放一个字母时，会不会放下这个最大字母，比如aaaaabbb， 在奇数位上放置a，axaxaxax,下次再放就要放到第一个x上，就不能满足。如果小于，开一个和字符串相等大小的字符串长度，就先把字母都放在偶数位上，偶数位放满 再放到基数位上。
二维dp，一遍过。倒着dp就可以了，设置右下角的dp值为1就可以，没什么可以总结的。
暴力dfs，一遍过。
dp思路。不错的思路。总体思想是只关注一条链的两边，在连成线的序列的两边更新此链的长度即可。也想到过这个思路，但怎么定位到两边没想到o1的思路。dp的思想就可以做到。
直接dfs一遍过，碰到1就dfs，然后把所有的连着的1都变成0，然后结果加1。
dp。这道题思路和之前的很像。保存交易次数为k次的hold商品的值，和nothold商品的值，转移方程是dp[j][1] = max(dp[j][1],dp[j][0]-prices[i]); dp[j][0] = max(dp[j][0],dp[j-1][1]+prices[i]);dp[i][0] notholdMax after i times trades,dp[i][1]holdMax after i times trades 注意每次更新dp数组的第一维的范围应该是k和现在遍历的商品数目的最小值，因为进行交易的次数不会大于商品数。
贪心水题，无需总结。
dp水题，好像是北理的那道dp题。
dp。思路和上面很像，因为首尾不能同时选择，所以计算数组0-nums.size()-2中的最大值，在计算1-nums.size()-1中的最大值，然后取两者的最大值。
dp,算是一遍过。用的最大矩形的那个思路解题。首先先把map转化成当前位置向上连续的1的长度的二维数组。然后对于每一行，都用求最大矩形的思路去求。 只不过这个题是最大正方形。所以对于max的判断要改一下，当vector元素要出vector时，初始width=1 就是如果width<=vector里要处理的数字时，就可以更新ans = max(ans,width,width)，并把width++。 https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/ 这个思路简单也清晰，但我肯定想不到。
贪心，一遍过。先翻转行，如果最高位是1，就不翻转，因为翻转后肯定会变小，反之则翻转。然后翻转列，如果此列的0的个数小于1的个数，说明翻转后1的个数>0的个数 ，会令最终结果变大，翻转。否则不翻转。然后记录下此列的1所对应的2进制的和。
很早之前做过带权并查集的题，没想到一下子又拿起来了，很开心。 总的来说，带权并查集和并查集的区别就是在并查集的树的边的意义不在只是“相连”，而又多了 一个记录值的意义，而这个值是什么是根据题目来定的。 在这个题中，这个边的值的意义：e2->e1的边值代表e1/e2的结果。而带权并查集和普通并查集的 区别在于union操作和find操作（也可能只有union操作）。 首先来看find操作，find操作不仅进行了常规的压缩路径寻找父节点（如果压缩路径不知道的话，应该去做一下普通的并查集熟练一下），而且还利用回溯法更新了边值，比如a->b->c,压缩完路径后， 变成了a->c,b->c,那么a的那条边对应的边值一定会改变，就是b到c的边值a到b的边值(跟新的 规则依据题目来定，有的题是+)。 再来看union操作，也特殊在边值的更新上。，例如对于b/c=2,不仅要把c的父亲指向b的父亲， 还要设置c的父亲到b的父亲的边值，更新法则按以前我看的一篇回答的叫法称作“四边形法则”。
dp。挺简单，状态转移方程很好找。但是重点总是超时，后来发现，每次遍历完全平方数就可以了。
这道题是目前为止写的最有成就感的一题，这一题也说明我写这个总结真的对我有帮助。这个题一开始就是用贪心，先装最重的，如果还有余下的重量，就装可以装下的最大的那个人。 思路是这样，但是实现起来却超时了。因为大量的对于vector的erase和pop_back的操作很费时间。这个时候我想到了上个周末我卡我的最后一题，他是用了一个有限队列，去维护 了一些信息，优先队列的意义是可以和当前的right指向的人一起上船的人这个有限队列有这样的特点：对于当前大的数，比如limit=10，当前大的数为7，现在可以装下1,2,3, 这些可能已经在队列里了。等到下次遍历到的数为6时，这时候优先队列里的1,2,3照样是满足要求的（leetcode1383题），所以这个数据可以很好地维护这个题目要求的数据。如果当前的这个人的体重<limit,首先先把当前位置left向后的 体重小于等于limit-当前right的体重的加进去,然后取这个优先队列最大的体重即可。 最后一看这个优先队列的元素根本没用到，于是就把优先队列优化成了一个数就可以了，表示优先队列的大小。
基础并查集，一遍过。
n2复杂度的算法很容易想到。对于nlogn的算法，我的想法是对于内层循环维护一个优先队列，降序，然后找到第一个小于这次的数，对应的序列长度+1就是本次以这个数结尾的长度。 但是不仅要调整子优先队列，还会有出队列的操作，所以应该不是logn的复杂度。 官方题解的思路很好，可以去看看：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
二维矩阵dp，复习.这道题要复习，这个思路可能以后会用到。比较好用。详细题解官方题解方法3： https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/er-wei-qu-yu-he-jian-suo-ju-zhen-bu-ke-bian-by-lee/
dp，一遍过。一开始设置了nothold hold数组，意义是nothold[i]表示包含在i点卖出后的最大值，hold[i]表示包含在i点买入的最大值。 转移方程是 hold[i]=maxNothold-prices[i];nothold[i]=maxhold+prices[i]; 然后在更新，maxNothold=max(maxNothold,nothold[i-1]); maxhold=max(maxhold,hold[i]);这样就可以保证不连续卖出和买入。
贪心不会做。这个题要复习。关键是找出这个pivot，使得A数组变化后长度最小。也就是A[0:I] +k AND A[i+1..back]-k,遍历这个枢纽找到长度最下值。 正确性的保证是因为排好序之后的数组A，A[i]左边的数+k都会小于A[i]+k,右边同理。所以长度就会由四个数控制min(A[0]+k,A[i]-k),max(A[i-1]+k,A.back()-k).
并查集基础题。没难度。
是个好题。复习！与打家劫舍2一起复习。这个题可以转化成不相邻序列元素的最大和。因为去披萨，只要我去的披萨的个数为n/3，并且取得位置不相邻，那么一定 有一种取法可以把披萨取出来。所以转化成了不相邻序列元素最大和。核打家劫舍2不同的是，这个规定了取的次数，而那个题没有规定偷的次数，所以在写法上有区别。 这个题的dp用到了滚动数组的优化，每一次都要和上一次的dp前[0,i-2]的最大值结合，这样可以避免靠着。dp[j]在第i次循环里的意义是，取了i-1个披萨后，第i次一定取 第j个披萨的最大值。
最后忽然想到KMP算法。直接就是match的想法的应用。一遍过，不过还是得复习。
上午起床状态不行啊，这种题根本静不下心来写。下午清醒了一会就写完了。没难度，就是怎么实现比较代码比较好看。
找素数的方法： //oura查找 保存在prime中，N是查找的范围[0,N],REC初始为0数组 for (int i = 2; i < N; i++) { if (!rec[i]) prime.push_back(i),cout << i << endl; for (auto& p : prime) { if (ll(i) * p < N) rec[i * p] = 1; else break; } }
括号匹配。直接就是栈的思想。匹配右括号，栈空就要加+1.最后跳出循环后，栈不空还要+栈的长度。
这个题好难。不会做。思想可以先从分治开始想。倒着想，假设我们最后取得数是x，那么x左边的数和x右边的数就永远不会靠着，就可以把两者区分开，分成两个子问题。 而两边的值可以子问题的求解是相同步骤。对于选定的这个x的求法。应该是用nums[x]*nums[start-1]*nums[end+1]因为两边都选完后，start左边的数和end右边的数会和x碰到， 这是这个题比较难想的点。所以整体思路就是对于长度L为1到n的区间遍历，对于长度为L的每个区间，都选取这个区间内不同的数当做x枢纽，最大值既是所求。 最后返回dp[0][nums.size()-1]
这道分治如果谁可以做出来，我真的就给你跪了。太难了，不是我这个水平做的题。平时分治的题做得少，感觉这个算法很有魅力，以后要多做两道。好的题解看这个就行了。 这个里面我觉得最需要总结的就是：在分治的时候，right的设置，这个题里设置的是数组的长度。而一般准确二分查找的时候，都是设置长度-1.这个为什么直接不减1呢？ 解答的作者给出的理由是这个题要考虑到m位置的VALUE_MAX 这个数值，所以要把right设置为数组长度。我觉得这个可以接受。 完美题解位置：https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/ 这个答主热衷于写分治法的 题解。
分治。复习。n个链表22分组分别合并。合并链表注意空间不要浪费，记得delete。
2020.3.25 1：34 leetcode240.cpp 分治。把这个想象成一棵二叉树。从右上角遍历。小于就往左子树走，大于就往右子树走，而且不可以往回走。如果等于就返回true。
dp水题。一遍过。
dp水题，一遍过，记得要比较下dp[i]和i哪个大，哪个大用哪个。
用lowbit算法做的，一遍过。就是不知道两个数相互与，这个操作是不是O（1）。另一个人的做法是如果末尾不是1，此数1的个数等于右移次数1次的1的个数，否则就等于右移此数 一次的1的个数+1，这个思路也很巧妙。
用朴素o2的dp做了，一遍过。但显然有nlogn的算法。看了一个评论才恍然大雾。这就是一个彻头彻尾的二维最长上升子序列啊！因为套娃的每一维都满足最长上升子序列。那怎么 编码呢？首先对第一维升序，第二维降序sort。这时候只看第二维，去求第二维的最长上升子序列就可以了，因为第一维时一定满足的。因为对于第一维相等的情况例如【3，3】， 【3，4】的排序情况时【3，4】，【3，3】，这个时候的LCS是1不是2。 排序后等于把在二维(长、宽)上的最长递增子序列问题转换成一维(宽)上的最长递增子序列的查找, 因为对于长度来说已经满足递增, 只需要在宽度上也递增即为递增序列, 同长时按宽度降序排列的原因是避免同长时宽度小的也被列入递增序列中, 例如[3,3], [3,4]如果宽度也按升序来排列, [3,3]和[3,4]会形成递增序列, 而实际上不行.
这个题脑子瓦特了。对于处理前导0的问题，每次我们都从最高位开始选，而不是用C 或者A这样的排列组合的方式选择。每次先选最高位，有9中选择，而下面一位也有9种， 然后8种，以此类推。就可以避免掉前导0的麻烦。 dp[0] = 1; dp[1] = 9(原因是0不能作为首字母被选择,所以dp实际表示的有多少种不同排列的数字，而不是数字组合) dp[2] = 9x9 dp[3] = 9x9x8 dp[4] = 9x9x8x7 dp[5] = 9x9x8x7x6 dp[6] = 9x9x8x7x6x5 dp[7] = 9x9x8x7x6x5x4 dp[8] = 9x9x8x7x6x5x4x3 dp[9] = 9x9x8x7x6x5x4x3x2 dp[10] = 9x9x8x7x6x5x4x3x2x1
直接看的答案。先记录当前位置的连续和x，然后用x-k，如果之前的连续和中出现过x-k，则结果ans+1.
二维矩阵dp，复习。这个题我写了O（mmnn)复杂度的，思路和304题是一样的。另一个思路看的别人的答案。今天先写思路，明天编码。 思路就是把二维的数组压缩成一维，设置两个指针left，right，left和right的移动区间是[0,m],m是列数，这样是n2的复杂度，对于每一个区间的[left,right] 在设置一个这个区间里的指针t，求[left,t]的每一行的和，这样列就消失了，就压缩成了一维。然后遍历行的前缀和。然后用set保存这些前缀和。对于前缀和sum， 我们要找在这个位置之前的矩阵中是否有和小于等于k的，也就是是否存在前缀和大于等于sum-k的，用lower_bound查找一下如果可以找到，sum-
dp，一遍过。转移方程确定了就行了，对于一个里面所有数都互相可以整除的数组，如果另一个数x可以整除这个数组中的最大值，那他一定可以整除整个数组。
dp。复习。一开始看成了二分。但是仔细想了一下，二分的选择的时候每个选择的代价都是一样的，都是一次。但这个题显然不是相同的代价，但可以借用dp的思路。 dp[i][j]表示i到j的最小的钱数，dp[i][j]=min(dp[i][j],max(dp[i][mid-1],dp[mid+1][j])+mid).也就是说以前二分只选择中间的数，但现在我遍历这个枢纽点， 选择代价最小的那个枢纽点。 枢纽这个思想似乎经常用，在312,910题里都是中心思想，要一起复习。
dp,复习。这个题关键是在如何定义二维数组dp[i][j]的意义上.一开始我把dp[i][j]定义为以A[i]元素结尾的序列差值是j的最长长度，转移方程就是dp[i][diff] = dp[j][diff]+1 但这样有个问题，对2,2,3,4这样的序列他无法得到正确答案，因为在3的时候最长长度是2，但是却有2个长度是2的序列。 看了别人的解答后，把dp[i][diff]定义成以A[i]结尾等差是diff的序列的数量这样一来对于2,3,4这样的序列，扫描到4的时候，差值为1的序列数量有两个，一个是2，3,4，一个是 3,4，同样对于2,2,3,4，扫描到3的时候的差值为1的序列数量为2.等扫描到4的时候，发现dp[A[2]][1]的数量不等于0,，就说明加上我本身的4 长度一定能达到3，所以result就要 加上dp[A[2]][1] ，其他类似。 tips: 要注意 vector<unordered_map<long long, int>> dp(A.size()); 和 unordered_map<long long, int> dp[1001];的区别 推荐前者，后者容易栈溢出。
和上一个题思路一样，只不过这个题要求是等差数列在原数列里必须相连，所以，内层循环直接只查看左边一个数的情况就可以了。
这道题想复杂了，复习！这个的转移方程应该很好想到，dp[i][j]代表0..i数组的元素切分成j个子数组的最大和的最小值，dp[i][j] =min( dp[k][j-1]+(nums[k+1]+...+nums[j]) ) k的范围是j-1到i-1。还有求一维数组任意区间的和的复杂度是On,求每个位置的前缀和，然后前缀和相减即可。
dp。不难。看到k-1,k,k+1,就感觉很眼熟。定义dp[i][k]为i位置的石块，能不能通过前面的某一个石块，经过k步到达。dp[i][k]=dp[j][k]||dp[j][k+1]||dp[j][k-1]. 还要就是最关键的一点是，有的题不确定第二维的范围，往往被迫用map，但很多时候可能可以确定第二维的上限，比如这个题，k一定小于等于len，所以第二维最大是len+1。
dp是否是子序列。一遍过。
复习！这种找循环节的思想没有用到过。找循环节的思想关键是，谁是pattern，在那个穿上上找循环节。在这个题中，为了将S1变成S2，所以S2应该是pattern，在 n1个s1中寻找循环节。循环节的寻找方法就是：在遍历完第i个s1之后，看看他想匹配的s2中的字符的在s2中的位置，比如s1=abc，s2=abb,那遍历完第一个s1后，nextIdx[1]=2 当这个所期望的位置在nextidx数组之前出现过的话，就说明找到了循环节。假设之前出现过的位置是k，循环节的起始位置是[k+1,i],那么在S1中存在多少循环节呢？ 就是等于(n1-k)/(i-k+1-1),而这些循环节可以贡献多少个匹配成功的s2呢。那就看看每个循环节可以匹配成功多少个（算法就是每一次记录遍历完当前s1后匹配成功了多少个s2，记录在 repeatCnt里，然后repeatCnt[i]-repeatCnt[k]就是一个循环节可以匹配多少个s2），然后乘前面算出的个数。这个时候还剩下S1中的头和尾巴匹配的个数没算，这俩可以 合在一起算，要不太麻烦，先考虑前面的循环节开始之前匹配的个数就是nextIdx[k].考虑结尾构不成循环节的m个，他说可以带来的匹配个数不是单纯的但拎出来看可以匹配多少个s2. 因为前面的最后一个s1可能和后面的最前的s1组合匹配s2。所以最好的方法就是把后面多出来的m个s1的移到start后面来，和start一起算，正好等于repeatCnt[start + (n1 - start) % interval]
这道题不难。但思路有点巧妙。关键在于如何排除重复。每次都只记录a-z结尾的最长的链的长度，然后返回这些链的长度的和。为什么这样就是个数了呢？ 跟446题一样。关键在于在新引进一个字符后，个数的变化，增加的字符串一定以我新引进的字符为结尾。这样考虑的话，比如abc，在a的时候是1，因为新引进了a。 在b的时候新引进的是2，因为新引进了b，ab，在c新引进了c，bc，abc。所以对于这种计数的要注意，一定记录因为引入新字符而增加的串的个数。
这道题复习，是博弈题。dp[i][j]定义为数组下标i到j区间中，按照规则可以取得的最大值。转移方程： dp[i][i+length] = max(nums[i]-dp[i+1][i+length]+pre[i+length]-pre[i+1]+nums[i+1],nums[i+length]-dp[i][i+length-1]+pre[i+length-1]-pre[i]+nums[i]); 每次取值都有两种选择，取左边和右边。左边:左边的值加上剩下数组区间和-可取的最大值,右边：右边的值加上剩下数组区间和-可取最大值。取两种的max。
dp，一遍过。从这道题开始，要注意一下dp数组的规律，对于那些问题dp数组范围是固定从0开头的，悠悠哪些类型需要开头也不固定的。 这道题也可以转化为01背包来做，转化成了“一个数组中，存在给定目标值的不同元素和的组合数目”
dp，回文串，这个可以要求是子序列不是子串了，换汤不换药，一遍过。
这题不会做。考察的是抽象问题能力。要想办法把所求的结果，换成另一种形式表示出来，最重要的还是看到问题本质。 https://blog.csdn.net/weixin_39350124/article/details/91485753
leetcode的题的难度的标签肯定不合理。这道题肯定不是hard题，直接n3的复杂度一遍过。如果想优化可以到n2logn的，懒得弄了。
没用的水题。
复习。这种题就是考智商，可是智商不高。1的个数必须是3的整数倍 将1等分成3份 再根据最后一份末尾0的个数推导 前两份的最后一个坐标，最后判断3份去掉前导0 是不是一样
复习，错。我们要判断的是 (sum[j]−sum[i])%k 是否等于 0。 根据 modmod 运算的性质，我们知道 sum[j] - sum[i])%k = sum[j]%k - sum[i]%k 故若想 (sum[j]−sum[i])%k=0，则必有 sum[j]%k=sum[i]%k。
博弈，dp，和486的思路大致一样，一遍过。既然都是最优策略取值。那么每个人的剩余序列中所取的最大值dp[start:end] = max(nums[start]+sum[start+1:end]-dp[start+1:end]), (nums[start]+nums[start+1]+sum[start+2:end]-dp[start+2:end]),(nums[start]+nums[start+1]+nums[start+2]+sum[start+3:end]-dp[start+3:end])),把每一项的常数部分提出来 ，就变成了，dp[start:end] = max(-dp[start+1:end],-dp[start+2:end],-dp[start+3:end])+sum[start:end]。因为dp的第二维总是end，所以用On的复杂度就可以解决。
这个题一开始就想到了贪心，但我是以3个字母为单位贪心，其实每次都以一个字母为单位贪心就可以。每次都选剩余最多的字母，如果他前面有两个一样的，就选次多，否则就选次次多。
不会做，思路错了。这道题和312戳气球的题一起复习。记忆化搜索。整体思路是：对于每个区间的的最大值，有两个策略可能会得到最大值，dp[i][j][k]表示i，j区间的最大值 k表示i之前与box[i]数字一样的box的个数，第一个策略是直接取那么此时的值是res =(k+1)^2+removingbox(i+1,j,0),第二个策略是跟i,j范围内的box[i]结合，需要用一个for循环 遍历，如果有等于box[i]的，那这个时候的最大值就是res=max(res,removingbox(i,m-1,0)+removingbox(m,j,k+1))
总算用这题找回点信心。一遍过。要分情况讨论。首先要把不出现A的1-n的长度的数量算出来。对于每个长度length，设置两个变量，表示长度length的串 以p结尾的个数P和以l结尾的个数L。更新规则是：P=上一次的P+上一次的L。 L = 上一次的P+上上次的P。对于L的更新规则解释一下：若以L结尾，上一位是P的都可以满足，所以是第一项。 上一位是L的，那么上上位只能以P结尾才能满足，要不该3个L了。所以是 L = 上一次的P+上上次的P。 算完不带A的个数后，算带A的就很容易了。n长度有n个位置放A，每个位置可以得到左边长度满足的不带A的个数*右边长度满足不带A的个数。
dp，一遍过。dp[i][j][k]的含义是走到坐标ij时并且步数用了k步后，所有的路线数。k的变化范围设置成1~N-1，转移方程是dp[i][j][step] += dp[nowm][nown][step-1]; nowm，nown是上下左右四个方向的坐标。最后返回的结果就是最上面一行，最下面一行，最左一列，最右一列的第0步到N-1步的路线数的累加，因为再多走一步就可以出去了， 并且走的步数<=N。
算是一遍过把。dp，如果这个题改成二进制n个长度的数中1不相邻的数字的个数，那就是个普通的dp。但这个题给了一个数字大小的上限。首先求出n个长度中 1不相邻的个数，但这中间可能会存在超出题目给定数字大小的，比如给定8（1000），所求的答案中会包含1010和1001，显然我们要把他剔除。 那我们从从高位到低位遍历这个给定的数字，遍历过程中同时检查以下两个条件。 如果当前位是1上一位也是1，那么我们的答案里就不会存在大于这个数字的了，因为答案给出的一定是10或者01，都比11小，直接break。 如果当前0上一位也是0，那么我们的答案中会包含01这样的，会超过给定范围，就要减去之前dp数组中这个位置以1结尾的数字个数。 对于当前位置是0上一位置是1的，不用处理，因为不会超过范围。 对于当前位置是1，上一位置是0的也不用处理，因为也不会超过范围。
中序遍历还原树，挺简单，好像南大机考最后一题是这个。哎，突然觉得好简单啊。为了写代码方便，需要把-整合一下，我定义的是把---定义成_$3_，这样字符串操作比较好find。
这个题不会做。复习。之前也定义好了dp[i][k]的含义，但是没想好转移方程怎么写。dp[i][k]指的是1-i数字排列中有k个逆序对的个数。 假如当前的4个数字的排列方式为：xxxx 再往其中添加一个数字5有如下几种添加方式： xxxx5 多出0个逆序对，因此有： f1(5,k)=f(4,k) xxx5x 多出1个逆序对，因此有： f2(5,k+1)=f(4,k)=> f2(5,k)=f(4,k-1) xx5xx 多出1个逆序对，因此有： f3(5,k+2)=f(4,k)=> f3(5,k)=f(4,k-2) x5xxx 多出1个逆序对，因此有： f4(5,k+3)=f(4,k)=> f4(5,k)=f(4,k-3) 5xxxx 多出1个逆序对，因此有： f5(5,k+4)=f(4,k)=> f5(5,k)=f(4,k-4) 递推关系：dp[n][k] = dp[n - 1][k] + dp[n - 1][k - 1] + dp[n - 1][k - 2] + ... + dp[n - 1][k+1-n+1] + dp[n -1][k - n + 1] dp[n][k + 1] = dp[n - 1][k + 1] + dp[n - 1][k] + ... +dp[n - 1][k + 1 -n + 1]
因此： dp[n][k + 1] = dp[n - 1][k + 1] + dp[n][k] - dp[n - 1][k - n + 1]
由于dp[n][k]可能出现负数，因此dp[n][k] = dp[n][k] + MOD
回溯，复习。一般来说，回溯我应该都会写。这个遇到点困难。主要是，在考虑大礼包和单独买的时候，怎么去考虑，其实只要把ans初值设置成单独买的情况，就可以了。 因为设置成单独买，考虑树的最下面树一层，如果在当前的列表里我找不到一个大礼包可以买的，那就直接返回ans了。
N皇后问题。其实就是dfs枚举+剪枝。dfs枚举的意思是：比如输入3，那么dfs枚举的结果就是123,132,213,231,312, 321这6个结果。这6个结果已经可以保证不同行不同列， 但不可以保证斜着不连着。所以在每次dfs 的开始要剪一下枝，像12开头的已经连着了，后续就不可能有满足要求的答案了。 所以这个题就是在dfs枚举的基础上， 在dfs的开头加上一个特判，看看是否斜着也连着。
一维dp。比较简单。dp[i]的含义是前i位的解码个数。（因为只需要考虑新加进来的这一位的单独位所新增的和新加进来的和前面一维组合起来新增的，所以dp的含义只需要是 0-i维，而不需要二维，写这些的原因是前面好像说过总结什么时候要考虑dp[i:j],什么时候要考虑dp[0:i]）,这个题主要考虑三种情况，如果当前位置是*，（前面如果是*，前面是 0，前面是1或2，前面是>=3),如果当前位置是[1:9]，（前面是0，前面是*，前面是1,前面是2，前面是>=3）,如果当前位置是0，（前面是1或2，前面是*，前面是0或>=3) 这些不同的情况，对应不同的转移方程，但都很简单。
dp，一遍过，比较简单，也是dp[0:i]的形式。先排序，按第二维从小到大排序。目的是在算当前数对时，他只能可能链接第二维比自己第二维小的数对，所以要把他们提前算出来，他们是 子问题。转移方程是if(pairs[j][1] < pairs[i][0]) dp[i] = max(dp[i],dp[j]+1);
回文子串数目，dp，一遍过。很简单，只要掌握了判断回文串的转移方程，一般关于回文子串的题都会做了。
转移方程不太好想。dp[i][j]表示字符i到j位置打印出来的最小次数，对于一个新字符，要么我是自己被单独打印出来，要么我就是和前面某一个和我一样的字符一起打印出来(如果我和， 对于单独打印出来的值，等于dp[i][j-1]+1。如果是和前面的某个相同字符一起打出来的话，dp[left][i] = min(dp[left][k-1]+dp[k][i-1],dp[left][i]);其中s[k]=s[i] 其中当k等于left的时候需要特殊处理一下，因为没有k-1，所以变成dp[left][i] = min(dp[k][i-1],dp[left][i]);
dp，可以复习。让求最长子序列的个数。每个最长子序列的子问题肯定是一个子最长子序列加上当前字符。所以对于每个当前字符，遍历之前的字符，找到小于当前数字的 最长子序列的长度。讲这些有这些长度的子序列个数累加，就是以当前字符结尾的最长子序列的长度。
记忆话搜索。一遍过，这道题的dfs很美妙。一开始没有想到，每个dfs(N,message)的含义就是每个点的状态是(i,j,k)的状态下他在界内的概率。最后写完才发现，把我能到达的 界内的点的概率相加，也就是调用的dfs相加，最后除以8，就是结果。可是我推出这个结果不是这个思路推的。我是从，当前状态可以到达界内的概率，比如时2/8,下一步我将从 这两个点开始dfs，到达这两个点概率相同，所以要成1/2，然后就是每个点的dfs值相加，这样推出了上面的结论。虽然结果一样，但却是两种不同的思路。显然第一种更高级。 边界状态是，如果当前位置在界外时肯定返回0，如果当前k=0，如果此时在界内，返回1，在界外返回0.
本来这道题很简单，被记录路径搞得数据结构异常复杂。后来恍然大悟，回溯路径可以解决这个问题。再重新写一下代码把。
复习！这个01背包的思路我想出来了，但不知道怎么编码比较好，这是一个模板。对于这种状态压缩dp的题的背包写法。
记忆化搜索。当dp不好写的时候，用记忆化搜索很不错。这个其实也是状态压缩dp，和按上面那题一起复习。
扔鸡蛋题，非常经典，复习。我只会写KNN的复杂度的dp，但这样远远不够。参考这篇博客。 https://leetcode-cn.com/problems/super-egg-drop/solution/ji-ben-dong-tai-gui-hua-jie-fa-by-labuladong/ 要注意二分的写法，边界的设置。
这个问题我觉得看我的解释大家应该都能理解。 首先让左右指针指向数组头尾（为什么一开始要这样，有个比较漫长的分析过程，但不是重点，就不多说了）。 这时算出来一个数ans.这个时候假设height[left] < height[right],我们可以发现，如果我们把left当做左边，那这个时候最大值一定是现在这个ans了。 因为如果在right左边有大于height[right]的数，但是由于height[left]决定着下限，所以再大也没用。如果right左边有小于height[right]的数，那更不可能比当前ans大了。 所以这个时候只能移动left指针。对于height[left] >height[right]同理。 而且对于height[left] < height[right]这种情况来说，移动left指针， 如果移动到的数小于height[left] ，那也不可能比ans大，所以left下一次指向的数应该是比height[left]严格大的数。对于height[left] >height[right]同理。
复习，这题竟然想了这么久。经验是：如果对于自己的算法，初始状态需要特殊化处理的话，那么大概率这个算法还有细节上没考虑清楚的地方。 这个题是找并行的串。 1.对于是否返回-1的判断很好判断，因为要找croak，对于a看看是否前面还有没用过的o，roak同理。如果没有就返回-1。 对于c不需要判断，但要加一个processing++，对于k要加一个processing--，为的是像croakcro这样的情况，如果有没有处理完的串，那也返回-1. 2.关键是对于青蛙个数的判断。其实可以叫做贪心，对于当前串，我们尽可能的让他和前面的串一起出现，这样ans就不用+1.也就是如果前面已经有处理完的串， 我们就可以把它们安排到一个青蛙上，但是这个时候finished要-1，因为这个时候如果再出现一个c，比如croakcrocroakak，对于第3个c，不能和第一个串一起出现，因为 第一个和第二个c的串一起出现。所以finished记录的是完成的且没有在处理的个数。 网上精简的回答：思想就是维护croak的个数，如果遇到当前字母，则肯定是由前面字母过来，前面字母数-1。 如遇到r，则必是c->r，所以c-- k代表结尾，其实也是青蛙的起始（一次喊叫结束），所以遇到c的时候，先去消耗k，没有k了，需要新青蛙，答案+1
水题，一遍过。
这道题合最大子序列的类型题换汤不换药。区别仅是最大子序列相当于拿掉一个字母的代价是1，而这个题拿掉一个字母的代价是对应的ascii值。
这题是真的难！不会做！dp里面算是非常难的了。如果这题只要求回文子序列的个数（允许重复），那就是个水题，但他要求不重复的子序列的个数。这个题就是首先我对于不重复子序列的求法 就已经注定我这题做不出来了，但我每次dp[i][j]表示以i开始以j结尾的回文子串的个数，然后返回的时候是dp数组的累加。但这样好像行不通，没法派出重复。思路都在代码里了。 看的是一个评论的答案，写的很好。
这道题也是个好题。总结一下：我记得以前遇到过和一个数组两边状态有关系的，其实只去考虑一边就行了，假设只考虑删除左边元素，因为等到遍历到下一个元素时，下一个元素删除 左边的就等于上一个元素删除右边的了。 算法：对排序后的数组的每一位都设置两个状态，hold:从数组开始到目前数组元素的最大值切目前元素保留。nothold:从数组开始到目前元素最大值切目前元素不保留。 转移方程很简单，如果是当前元素和前一个元素差1，说明不能共存： lasthold = lastnothold+type[i]*number[i]; lastnothold = max(lastnothold,temp); 如果不是差1，说明可以共存：lasthold = max(lasthold,lastnothold)+type[i]*number[i]; lastnothold = max(lastnothold,temp);有的同学可能会有疑问：对于1,3,4这样的没有连着的，对于遍历到3位置应该不会出现nothold状态呀，会不会导致平白无故删掉一个元素？ 其实不会的，因为max会帮助我们取到最大值，这个时候3位置的nothold一定小于hold。而且等到遍历到4的时候，如果让4处于hold状态，那就需要知道3位置的nothold状态的最大值， 所以知道3位置的nothold状态是有必要的。 ps::!!!!有一个发现，我看到有人写直接从数字1--10000遍历，然后就不用对数组排序了，因为题目给了数字范围，没在数组中出现的就按0个来看。这样的话就提供了一个新思路， 也非常好，直接变成了打家劫舍问题，转移方程是dp[i] = max(dp[i-2]+dp[i]*i, dp[i-1]);果然简洁，而且下次如果再给数字范围，要朝“直接遍历数据范围”想一下，这样就不用 处理特殊的情况了，像nums[i]是否等于nums[i-1]。
这题太难了，不会做。不管是从优化空间代码编写还是思路上。要把这题转化成：两个人同时从起点到终点，所获得的最大樱桃数。“同时出发”保证了两个人一定在一个对角线上。 至于为什么要保证两个人同时出发，我觉得这才是这题难点所在。如果不保证同时出发，比如说(4*4)大小的grid，B点在1,2 A点在0,3，从右下角向左上角算，这样如果不同步 就会出现B走完的点，A点还会走，处理起来就会很麻烦，应该说是处理不了。所以只要保证了同时出发，就保证了一定在对角线上，也就保证了不会出现上面那种情况。 定义dp[i1][j1][i2][j2]为从A从A从i1，j1出发，B从i2 j2出发到达右下角的最大值。这样因为i1+j1=j2+i2=k，所以i1,i2,k唯一确定了两个点，所以可以优化成 dp[i1][j1][k]，然后k这一维其实也可以被删去，只要处理的时候把处理的顺序搞清楚就可以了。如果i1不等于i2，说明两个点不在同一点 dp[i1][i2][k] = grid[i1][k-i1]+grid[i2][k-i2]+max(dp[i1+1][i2][k+1],dp[i1][i2][k+1],dp[i1+1][i2+1][k+1],dp[i1][i2+1][k+1]),max里面的含义依次是，A B点在(i1+1,j1) (i2,j2+1) (i1,j1+1)(i2,j2+1) (i1+1,j1)(i2+1,j2) (i1,j1+1)(i2+1,j2) 到达右下角的最大值。 如果i1=i2，dp[i1][i2][k] = grid[i1][k-i1]+max(dp[i1+1][i2][k+1],dp[i1][i2][k+1],dp[i1+1][i2+1][k+1],dp[i1][i2+1][k+1])。如果处理每个k的时候可按照从右上处理到 左下的顺序，可以把k这一维省略。参考的是二维背包转一维背包。
这题不是用dp做的，直接统计每个1的点四个方向上连续1的个数的最小值，然后+1就是以这个点为中心的加号标志的大小。
感觉分弗洛伊德算法差不多，dp[j][i]代表源点到达j点至多中转i次的路费最小值。源点到达一个点的最小值，要么是直接到达，要么是利用另一个点当做跳板到达。 因为还有i步的限制，所以转移方程改成了，要么是直接到达，要么是在别的点上经过了最多i-1步之后，又从那个点经过了一步到达，所以转移方程是 dp[j][i] = min(dp[h][i-1]+Map[h][j],dp[j][i]);
dp。不难，就是找规律，比较墨迹。没有复习价值。
形象的说法：就是带着0的区间一直往下沉。因为0的区间的元素都是0，所以往下沉不用挨个交换，只需要把开头的0和不等于0的元素交换就行。比如00034,指向0的时候，把开头 0和3交换，这样变成了30004，就把0区间下沉了，等到遇到4，就和开头0交换，变成34000. 这题没有想到怎么做。两种方法，第一种是2次遍历。就是一个n长的数组，如果有m个非0元素，移动完后这些元素一定按顺序在前m个位置。所以设两个指针a，b，b表示 非零元素末尾位置+1，a用来遍历元素，当a指向的元素不等于0时，那么他应该放在b的位置，当a==b的时候就不用交换了直接把b后移即可。 当a>b时，num[b]=num[a],num[a]=0,b++,相当于把ab元素交换，然后让b后移。当a指向元素等于0的时候，b的位置应该不变。
这题真的学到了。二分一定要记住了。这题跟410题很像。我410题用的dp做的。但如果410用二分做，这题应该就有戏。二分的时候思路不要受限，不光是可以二分给定的数组， 关键是大多时候二分的时候选择的是这些元素的和，反正就是和数组内元素和有关系的二分。这个题，对于每个区间的和的最大值进行二分。一开始的二分区间是0和数组总和， 分别是l和h。然后判断在每组的和都小于等于mid的时候整个数组需要分成多少组，这个数字是cnt，如果cnt大于m，说明每一组和的数字要大一些，l=mid+1；else h=mid。 最后返回l。关键是如何编码"判断在每组的和都小于等于mid的时候整个数组需要分成多少组，"。对于这个题，意思是： long temp = 0; int cnt = 1;//初始值必须为1 long maxx = -0x3f3f3f; for(int i = 0 ; i < time.size() ;i++){ temp += time[i]; maxx = maxx <time[i] ? time[i] : maxx; if(temp-maxx>mid){//当去掉最大值之后还不可以装下时，就要新开一个组了，所以cnt++，因为当前元素装不进去，所以i要减1. i--; maxx = -0x3f3f3f3f; temp = 0; cnt++; } }
dp水题，de了一遍，然后过了。
这道题怪我，我非得想从正面角度结题，用数位dp，但可惜没做出来。还是逆命题的思路好做。 找出小等于N中至少一位重复的数字的个数，那就先找打小于等于N全都不重复的数字的个数m，然后N-m就是结果。 m的求法：首先求出小于等于N这个数字长度的(比如N=12345，找出数字长度是5的)不重复数字的个数，再减去其中大于N的，就是m。 求出N这个数字长度的不重复个数的求法：从固定长度为1的开始算，类加到固定长度为N的。固定长度为m的不重复的个数：9*A(9，m)。 求出比N大的不重复的数字的个数的求法：首先设置一个set，存入从数字最高位到当前前一位出现过的数字。 如果当前数字是m，那么m+1到9之间的数字只要之前没出出现过都要被减去。对应的代码是： for(int j = (number[i]-'0')+1 ; j <= 9 ; j++){if(exist.find(j) == exist.end()){sum -= A(10-exist.size()-1,number.size()-1-i);}} 算完这些后，开始检查，当前数字之前有没有出现过，如果出现过，比如123245，遍历到第二个2的时候，后面就不可能有不重复的了，因为2已经重复了，直接break。 否则就把当前数字加入set。最后返回N-m.
这题很简单。这种统计矩形个数的题要注意两个问题：1，基本思想都会涉及到这个：if (grid[i][j] == 1) f[i][j] = min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1; 这个思路很经典，之前不是很理解，现在理解很多了，参考https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/submissions/ 2.统计个数的时候，一般都要找到一种不重复统计的一次性统计好的方法，而不是统计完之后再减去重复个数。像这个题，统计思想是以grid[i][j]为右下角的矩形个数 。这样既可以统计完整，又不会出现重复。
这题也不难。中间我写了一个O（n^4）的复杂度的dp，后来一想中间有一维度没用，优化到了n3过了。 感觉现在写dp题确实是进步了，以前总想着去背这些题的特点，比如说dp开三维数组的有哪些特点，对于for遍历dp的含义是从0到j还是i到j等等。但现在就比较灵活了， 因为这些其实都是优化过来的。对于这个题，我一开始写了一个for的四层嵌套，分别是对k，对左指针，对右指针，对，左右指针在进行遍历。 但是这题仔细一想，最后的分割出来的串，一定有一个在右边界的位置（我的意思是比如aabbc，k=3，一定有一个c，被分割在了最右边的位置再比如说aabbcc， k=3的cc），那这样的话，就不用对左指针进行遍历了，因为从这个角度看，把除最右边的这个串S的剩下的串看成一个整体，分割S占了一次，剩下的串分割成回文用 剩下的k-1次次数就好了。 另外到底dp的含义到底需要怎样几个维度，for循环到底是几个嵌套，关键还是看转移方程。
https://leetcode-cn.com/problems/smallest-integer-divisible-by-k/solution/javajie-fa-yi-ji-zheng-ming-de-si-lu-by-jiangzk/ 这道题真难。不过这个解释的非常好。有理有据。
很简单。两遍dfs搜索。第一遍确定每个点及其儿子是否有苹果。第二遍dfs只去遍历儿子中有苹果的点就可以了。
这道题早就有思路了，而且思路还是对的。主要是忙着写论文，而且我debug太慢了。中间出的bug调了好久。 这道题其实不难，在dp里绝对不算难的。思路是这样的。dp[i][j][t]表示的是在由左上角是[i][j]到pizza的右下角，分给k个人的总方案数。 最终返回肯定是dp[0][0][k],转移方程是（对于dp[i][j][t],如果当前这一刀竖着切，那应该从第一个刀左边有苹果的位置开始切，一直切到最右边，这刀上边的分给1人， 下面的分给t-1人。如果第一刀横着切，那应该从第一刀上边有苹果的位置开始切，一直切到最下边，这刀上面的分给1人，下面的分给k-1人。 对应代码分别是： for(int m = up[i][j]; m < row ; m++)dp[i][j][t] += dp[m][j][t-1]; for(int m = left[i][j];m <col ; m++)dp[i][j][t] += dp[i][m][t-1];这里的up和left分别对应横着切和竖着切左上角为（i,j)时的行和列位置。这两个数组需要 O（n3）的复杂度预处理一下。
dp水题。还是说一下，自己之前写了个O（n3）的，但是是因为题看错了，看成了最小剪辑次数。如果是最小片段，两遍循环就够了。
这题是之前一道求等差数列的基础版，那道题要复习。
这道题逼着自己想了很多。想要优化到nlogn，因为自己n2的算法没过。后来真的不行了，看了答案才知道，原来我调用函数没加引用，导致函数调用频繁变慢很多。
这道题想了30min，不应该。而且虽然是dp，但不是最优化的dp，dp[i][j]表示用前j个price数值凑出i分来（前j个里面的数值不一定每个都要用） dp[i][j]+=dp[i-price[j]][j];dp[i][j] += dp[i][j-1]; 最后返回dp[n][3].
一遍过，水题dp。
普通写法很简单。评论区看到一个背包写法。很关键。文件中的代码对应的也是背包的写法。背包写法是外层枚举物品，内层枚举重量。完全背包和01背包就是内层 的遍历顺序区别。这题是这样抽象的：相当于装满重量为n的背包，这个背包里不能有大于n的线段（因为一定要剪一下）。所以外层i从1到n-1遍历，内层从i到n遍历。就可以满足所有限制。
这题上来肯定无脑dp。但是有贪心的思路。 先讲自己的dp思路。先排序。一开始dp[i]设定为前i个菜可以超出的最大价值，同时必须炒第i个菜。这样不合理，因为每次dp就会变了，起不到记忆化的效果了。 所以经过改进，dp[i]表示 炒i个菜的最大值，跟背包差不多了。这样每次都去改变dp[i]的值，转移方程是 dp[num-1]+satisfaction[i]num>dp[num]，就代表可以炒这个第i个菜来更新一共炒num个菜的值，并且注意遍历num的时候要从大到小遍历，否则就会重复炒一个菜。 贪心的思路很巧妙，用到了数学的证明，这个没想到。从大到小遍历，如果对于炒一个菜，肯定是s0,炒3个菜，当满足s1+2s0>s0时，就可以炒，整理一下是 s1+s0>0,第3个菜如果s2+2s1+3s0>s1+2*s0,就抄，整理一下是s1+s0+s2>0。可以看出，如果从目前的菜si到之前所有的菜的满意度之和大于0，就可以炒，如果小于0， 直接退出，因为后面的菜的满意度比si还要小，也肯定不会满足了。 贪心思路ps:https://leetcode-cn.com/problems/reducing-dishes/solution/zuo-cai-shun-xu-by-leetcode-solution/
这个题很难，不会做。dp[i]表示高度差为i时的最大高度。两层遍历，第一层对物品便利，第二层对可能的高度差遍历。对于每个高度差，当前 的物品有两个选择，要么加在长的那一段，要么加在短的一端，要么不加。不加不用处理，加在长的一端时，高度差变为 k = j + rods[i - 1]; 更新： dp1[k] = max(dp1[k], dp[j] + rods[i - 1]); 加在短的一端时，有两种情况：如果当前长度差大于等于当前物品长度，说明超不过去， int k = j-rods[i-1];dp1[k] = max(dp1[k],dp[j]);否则， int k = rods[i-1]-j; dp1[k] = max(dp1[k],dp[j]+k);
这道题也不会做，太菜了。但是有点收获。这个是利用之前所有数据状态来设立的dp含义，而不是单纯根据位置信息来设立。其实这点可以经过思考的来： 我们利用dp速度快的原因，就是因为没有枚举，而没有枚举的原因就是因为把一些相同的状态压缩到了一个，比如这种dp[i][j][k]表示的是前i个字母，，左手 在j字母上，右手在k字母上的最小距离。因为我们只需要最小的那个，所以dp数组只记录最小的那个数值即可，以后也可以从这个思路上定义dp数组。 正确性利用最有子结构性质也能证明。
这道题还是不会。一定要复习！！！！！！我发现一阵子不做题，脑子真的会锈住。不过这道题真的很难。 朴素的做法就是dfs枚举，通过设置visit来看这个帽子之前有没有被带过，以此来防止冲突。 但是这肯定过不了，因为这太慢了。网上的正确做法是，看到10，就要想到状态压缩dp。那为什么状态压缩呢？状态压缩之所以快的原因就是因为我只需要知道 之前这个人带没带过帽子，而至于他带的几号帽子，我不关心，所以会快。 这题的巧妙之处在于，遍历帽子，每次都只把帽子i分给某个人，下次再把i+1帽子分给某个人，这样就保证不会把一个帽子同时分给两个人。 ps：还有一个窍门：LeetCode还真是喜欢出状压的题目。还是老套路，看到某一个维度特别小（本题是1≤n≤10），就尝试在这一维进行状态压缩。