代码随想录训练营第33天|休息日 小结

• 组合总和
  这题有两个点，一是给出的元素无重复，二是每个元素可以多次使用。无重复元素，所以不用考虑去重问题；每个可多次使用，因此遍历的下一个元素仍然是当前元素。其他按照回溯套路来做就可以了。
• 组合总和II
  这一题的难点是在去重，组合问题的求救过程可以抽象为遍历一个树形结构，因为得到的组合不能重复，而组合内部是可以有重复元素的，因此去重是在树层上，在每一层上之前 使用过的元素就不能在使用了，这个是去重的关键。
• 分割回文串
  把切割分题和组合问题关联起来，于字符串abcdef：
  组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…
  切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…
  在遍历过程中，只保留子串都是回文串的切割方法。
• 复原IP地址
  这个题和分割回文串类似，但这个题只能分割成四段，且每一段都要满足IP地址的要求
• 子集
  这个题反而是很简单的，因为得到所有的子集，所以要保存的是树形结构所有的节点，而之前是只保存叶子节点
• 子集II
  这个题在上一个题的基础之上要考虑去重问题，去重思路和前面的组合II一样，都是在同一树层上不能使用已经使用过的元素
• 递增子序列
  这个题涉及三个点，递增，子集和去重，递增不难，别的两个点也做过，但是不能使用一样的方法去重，因为这个题不能改变原来的数组的元素顺序，因为需要用哈希来判断一个元素是否使用过，（判断一个元素是否出现就用哈希），这里最高效的是使用数组。
• 全排列
  相比于组合，全排列中for循环的i每次都要从0开始，且需要一个数组来标记某一个元素是否使用过。i那次都从0开始是和组合区别很大的一点。
• 全排列II
  这个是全排列的去重问题，全排列的去重可以在树枝上也可以在树层上，但是在树层上去重效率更高。
• 分发饼干
  将饼干大小和胃口值都进行排序，然后大饼干优先满足胃口值较大的。
• 摆动序列
  因为差值要正负连续出现，可以转化为求递增和递减区间，每个区间对应着两个点，而中间的一个点是两个区间共用的，因此最后的点树要等于区间数加1。
• 最大子序和
  从前往后遍历求和，每当当前和为负数的时候就重置和为0，重新求和。这样做的原因是负数加上任意一个数都会是这个数更小。
• 买卖股票的最佳时机II
  最简单的想法是在最低点买入，在最高点卖出，因此可以转化为求极值点的问题。其实可以简化问题，利润是可以分解的，某一天相比于前一天的利润为正，就加入到总利润中，也就是说只关心利润为正的情况，这就是贪心所贪的地方。
  +跳跃游戏
  这个题问的是能不能跳到最后，因此我们不需要关心具体怎么跳，而只需要知道能在当前位置能跳的范围，最终只需要判断跳跃的范围有没有包含最后一个位置即可。