下一个排列

  • 多背多练。

组合

  • 记得枝剪提升效率

全排列II

  • 如何去重 -> 排序 + 保存一个vis的boolean数组
    • if (i > 0 && nums[i] == nums[i-1] && !vis[i-1]) continue
    • 原理
        1. 限制出现顺序，比如说a1 a2 a3，就只会按照a1 a2 a3的顺序出现
        1. 同一层的去重，如果vis[i-1]=false，表示 nums[i]和nums[i-1]在同一层的递归里面，也就是index相同，所以要去重。

77. 组合（Done）

答案

  • 回溯+支剪

    46. 全排列（Done）

    答案

  • 回溯+保留一个全局变量数组来控制每个位置可以选择的数字

    • index之前的是已经用掉的数字，后面的（包括index）是可以选择的范围，这个数组的顺序会根据每一步选择的元素发生变动

      47. 全排列 II（不熟练）

      重复数字如何处理重复解
      官方答案看不懂。。。，用我自己的
      答案:

  • hashmap统计频次+根据剩余频次来判断剩下那些元素可以选择


  • 31. 下一个排列（Done）

    直接背答案
    答案：
    image.png
    五步走：
    1. 从后往前找到第一个单调递减的值x记录index为i
    2. 从后往前找到第一个大于x的值y
    3. 交换x和y
    4. 翻转i之后的元素来进行升序排列（不包括i）
    5. 记得处理从后往前全升序情况




    267. 回文排列 II

    我自己做的超时了，测试用例18/26
    答案：

  • 第一步判断是否可以构成回文串

  • 第二步，只回溯枚举前一半的回文串，节约时间。