Skip to content

Latest commit

 

History

History
457 lines (390 loc) · 14.8 KB

进阶班03_知乎.md

File metadata and controls

457 lines (390 loc) · 14.8 KB
Raw

进阶班第3节

一、暴力递归

  1. 汉诺塔问题

    属于是很经典的递归问题，最早接触编程、接触递归的时候就是这个例子，但是自己独立完成依然不熟悉，这里重新整理思路。

    首先，脑海中要有一个正确的递归过程（假设3个柱子分别是left，mid，right）：

    1. 从left将n-1个盘子移动到mid；

    2. 从left将1个盘子移动到right；

    3. 从mid将n-1个盘子移动到right；

    于是，我们可以进行递归过程，这里的递归过程中，变化的是left，mid，right这3个柱子的角色，否则是不能够动起来；在第1步中移动盘子，mid和right的身份就发生了变化，mid变成了目的地，而right变成了中转站，这就是精髓所在。

    接下是题目：面试题 08.06. 汉诺塔问题

    代码：

   class Solution {
   public:
       void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
           recur(A.size(), A, C, B);
       }
       void recur(int size, vector<int>& start, vector<int>& end, vector<int>& temp) {
           if (size == 1) {
               int last = start.back();
               start.pop_back();
               end.emplace_back(last);
               return;
           }
           // 将size-1个盘子从start移动到temp
           recur(size-1, start, temp, end);
           int last = start.back();
           start.pop_back();
           end.emplace_back(last);
           // 将size-1个盘子从temp移动到end
           recur(size-1, temp, end, start);
       }
   };

  1. 字符串的全部子序列

    首先要分清楚子串和子序列的区别：子串是去掉原字符串首位若干元素构成的字符串，而子序列是可以去掉任意元素构成的字符串。所以数组和字符串都有其对应的子数组和子串，对于子序列没有名字上的区别，都叫子序列。

    子序列和排列是不一样的，排列可以改变元素间的相对位置关系，而子序列不可以。如果是子串的话，直接双循环，就可以枚举出所有的结果。

    因为不含有重复元素的子集和子序列可以等效，所以找了力扣相似的题目。

    题目：78. 子集

    思路1：其实就是一个最简单的回溯，每次遇到当前元素可以取或者不取

    代码：

   class Solution {
   public:
       vector<vector<int>> subsets(vector<int>& nums) {
           backtrack(0, nums);
           return res;
       }
       void backtrack(int i, vector<int>& nums) {
           if (i == nums.size()) {
               res.emplace_back(path);
               return;
           }
           backtrack(i+1, nums);
           path.emplace_back(nums[i]);
           backtrack(i+1, nums);
           path.pop_back();
           // 这里换成以下顺序也可以，但是子集Ⅱ不可以，原因见后
           // path.emplace_back(nums[i]);
           // backtrack(i+1, nums);
           // path.pop_back();
           // backtrack(i+1, nums);
       }
   private:
       vector<vector<int>> res;
       vector<int> path;
   };

思路2：因为是全部的子序列，而且没有重复元素，所以可以使用位运算，即用掩码来标识某一位取或者不取，逐一枚举掩码的值，即得到每个子序列

代码：

   class Solution {
   public:
       vector<vector<int>> subsets(vector<int>& nums) {
           int mask = 0;
           int end = 1 << nums.size();
           while (mask < end) {
               path.clear();
               for (int i = 0; i < nums.size(); ++i) {
                   if ((1 << i) & mask) {
                       path.emplace_back(nums[i]);
                   }
               }
               res.emplace_back(path);
               mask++;
           }
           return res;
       }
   private:
       vector<vector<int>> res;
       vector<int> path;
   };

  1. 字符串的全部子序列（结果不含有重复子序列）

    最简单直观的思路就是，直接在上面的版本中加上集合去重即可，代码如下：

   // vector对象不能哈希，转化成string
   string t(path.begin(), path.end());
   if (!vis.count(t) {
       vis.insert(t);
       res.emplace_back(path);
   }

力扣上面，与上面相关的题目和这里的要求还略有不同，因为含有重复元素的子集并不等同于含有重复元素的子序列的情况。这里单独将力扣题目放在这里，对比用。

总体思路：排序后进行去重

题目：90. 子集 II

思路1：对照上面问题的思路1的版本

代码：

   class Solution {
   public:
       vector<vector<int>> subsetsWithDup(vector<int>& nums) {
           sort(nums.begin(), nums.end());
           backtrack(0, nums, false);
           return res;
       }
       void backtrack(int i, vector<int>& nums, bool choosePre) {
           if (i == nums.size()) {
               res.emplace_back(path);
               return;
           }
           backtrack(i+1, nums, false);
           if (!choosePre && i > 0 && nums[i] == nums[i-1]) {
               return;
           }
           path.emplace_back(nums[i]);
           backtrack(i+1, nums, true);
           path.pop_back();
       }
   private:
       vector<vector<int>> res;
       vector<int> path;
       bool choosePre;
   };

思路2：对照上面问题的思路2的版本，choosePre其实就是((1 << (i-1)) & mask) == 1

代码：

   class Solution {
   public:
       vector<vector<int>> subsetsWithDup(vector<int>& nums) {
           sort(nums.begin(), nums.end());
           int mask = 0;
           int end = 1 << nums.size();
           while (mask < end) {
               path.clear();
               bool flag = true;
               for (int i = 0; i < nums.size(); ++i) {
                   if ((1 << i) & mask) {
                       // 判断当前位置的元素能否取到，break照应递归版本的return
                       // 当前字母和上一个相等 and 前一次没有取
                       // 还可以是 ((1 << (i-1)) & mask) == 0
                       if (i > 0 && nums[i] == nums[i-1] && (mask >> (i-1) & 1) == 0) {
                           flag = false;
                           break;
                       }
                       path.emplace_back(nums[i]);
                   }
               }
               if (flag) {
                   res.emplace_back(path);
               }
               mask++;
           }
           return res;
       }
   private:
       vector<vector<int>> res;
       vector<int> path;
   };

思考：

  1. 问：为什么顺序不能变？

    答：因为在Ⅱ中，添加元素与否取决于当前的状态，而不添加元素一定是可行的一种情况，所以先进行不添加的递归，再进行判断，是否进行添加元素的递归。

  2. 问：为什么不能用全局变量表示choosePre？

    即代码为以下为什么不能通过：

      class Solution {
      public:
          vector<vector<int>> subsetsWithDup(vector<int>& nums) {
              sort(nums.begin(), nums.end());
              backtrack(0, nums);
              return res;
          }
          void backtrack(int i, vector<int>& nums) {
              if (i == nums.size()) {
                  res.emplace_back(path);
                  return;
              }
              choosePre = false;
              backtrack(i+1, nums);
              if (!choosePre && i > 0 && nums[i] == nums[i-1]) {
                  return;
              }
              path.emplace_back(nums[i]);
              choosePre = true;
              backtrack(i+1, nums);
              path.pop_back();
          }
      private:
          vector<vector<int>> res;
          vector<int> path;
          bool choosePre;
      };

答：用例[1,2,2]，将每一次进入回溯的choosePre变量都打印出来，可以发现：

      全局变量：0 0 0 0 1 0 1 0 0 1 0
      局部变量：0 0 0 0 1 0 1 1 0 0 1 0 1

虽然在前期是一致的，但是在回溯的过程中，局部变量是真的带着前一个元素已选择这样的信息进行下一次递归的，而全局变量则是忽略了此次递归的信息，机械的进行2种情况的处理。

我自己也不是特别清晰，如果有更好的解释欢迎指点！

补充：

      // 当前位置i choosePre
      // 全局变量
      0 0
      1 0
      2 0
      3 0
      2 1
      3 0
      1 1
      2 0
      3 0
      2 1
      3 0
      // 局部变量
      0 0
      1 0
      2 0
      3 0
      2 1
      3 0
      3 1  // 在第2次执行的过程中，选择了当前元素，所以在i==3时不应该return
           // 而全局变量在进入i==3时先执行了choosePre=false的操作，所以return
      1 1
      2 0
      3 0
      2 1
      3 0
      3 1

暂时先解释这么多，感觉应该是解释清楚了

  1. 字符串的全排列

    不含重复的情况是最简单的情况，和上面考虑要不要当前元素不一样，要考虑的问题有下面这几个：

    • 循环从什么位置开始？因为每个位置的元素都有机会加入path的下一个位置，所以是0

    • 为什么需要去重？当前回溯轮中，当前位置的元素只能加入path一次。例：比如当前层1加入了，之后深层的backtrack中就不能再加入1了，不属于同一层去重，实际是利用了元素不重复的特性，在一条路上面不出现重复的，这个和后面的有区别，需要注意

    首先是普通的回溯，需要借助哈希表去重：

   class Solution {
       vector<vector<int>> res;
       vector<int> path;
       unordered_set<int> vis;
   public:
       vector<vector<int>> permute(vector<int>& nums) {
           // 普通回溯
           backtrack(nums, 0);
           return res;
       }
       void backtrack(vector<int>& nums, int start) {
           if (start == nums.size()) {
               res.emplace_back(path);
               return;
           }
           for (int i = 0; i < nums.size(); ++i) {
               if (vis.count(nums[i])) {
                   continue;
               }
               vis.insert(nums[i]);
               path.emplace_back(nums[i]);
               backtrack(nums, start+1);
               vis.erase(nums[i]);
               path.pop_back();
           }
       }
   };

然后是交换法，需要体会和普通回溯的区别：

   class Solution {
       vector<vector<int>> res;
       vector<int> path;
   public:
       vector<vector<int>> permute(vector<int>& nums) {
           // 交换法回溯
           backtrack(nums, 0);
           return res;
       }
       void backtrack(vector<int>& nums, int start) {
           if (start == nums.size()) {
               res.emplace_back(path);
               return;
           }
           // 1.循环从什么位置开始？交换法前面的元素固定了，只能和自己及后面元素交换
           //   所以加入的也是start而不是i，因为start是被固定的元素
           // 2.为什么不需要去重？因为每层回溯不会重复枚举同一个位置，
           //   所以当前遇到的元素一定是未见过的，本质是在考虑每个位置的情况
           for (int i = start; i < nums.size(); ++i) {
               swap(nums[start], nums[i]);
               path.emplace_back(nums[start]);
               backtrack(nums, start+1);
               swap(nums[start], nums[i]);
               path.pop_back();
           }
       }
   };

  1. 字符串的全排列（结果不含有重复排列）

    加入了重复元素两种方法都有了不同，即添加了各自的约束条件：

    • 普通回溯：提前排序+哈希（保存索引）去重

    • 交换法：同一层哈希（保存数字）去重

    造成这样问题的原因是普通回溯要保证排序后同一个位置不能重复添加，或者不在同一个位置但是相同的元素也不能添加，所以是这个判断条件：

   if (vis.count(i) || (i > 0 && !vis.count(i-1) && nums[i] == nums[i-1])) {
       continue;
   }

而交换法的实质是保证当前位置不出现重复元素即可，不需要出现过的不能再出现，所以只在同一层创建哈希表即可，以下是2种方法：

普通回溯：

   class Solution {
       vector<vector<int>> res;
       vector<int> path;
       unordered_set<int> vis;
   public:
       vector<vector<int>> permuteUnique(vector<int>& nums) {
           // 普通回溯
           sort(nums.begin(), nums.end());
           backtrack(nums, 0);
           return res;
       }
       void backtrack(vector<int>& nums, int start) {
           if (start == nums.size()) {
               res.emplace_back(path);
               return;
           }
           // 变化1：if语句的判断条件（重点记忆）
           // 变化1：vis记录的不是元素，而是每个位置，否则一定会有重复元素
           //   （相当于Ⅰ中已经遇到了重复元素，就不会继续回溯），即有重复元素就枚举位置
           for (int i = 0; i < nums.size(); ++i) {
               if (vis.count(i) || (i > 0 && !vis.count(i-1) && nums[i] == nums[i-1])) {
                   continue;
               }
               vis.insert(i);
               path.emplace_back(nums[i]);
               backtrack(nums, start+1);
               vis.erase(i);
               path.pop_back();
           }
       }
   };

交换法：

   class Solution {
       vector<vector<int>> res;
       vector<int> path;
   public:
       vector<vector<int>> permuteUnique(vector<int>& nums) {
           // 交换法回溯
           // 变化3：不需要排序，因为不需要判断相邻位置元素的关系
           backtrack(nums, 0);
           return res;
       }
       void backtrack(vector<int>& nums, int start) {
           if (start == nums.size()) {
               res.emplace_back(path);
               return;
           }
           // 变化1：在单次回溯中去重，即每轮回溯里，每个位置不能交换到同样的元素
           // 哈希表添加的和path一样，都是start位置的元素
           // 变化2：不需要删除！
           unordered_set<int> vis;
           for (int i = start; i < nums.size(); ++i) {
               if (vis.count(nums[i])) {
                   continue;
               }
               swap(nums[start], nums[i]);
               vis.insert(nums[start]);
               path.emplace_back(nums[start]);
               backtrack(nums, start+1);
               swap(nums[start], nums[i]);
               path.pop_back();
           }
       }
   };