Skip to content

Latest commit

 

History

History
927 lines (706 loc) · 26.4 KB

回溯.md

File metadata and controls

927 lines (706 loc) · 26.4 KB
Raw

回溯法总结

路径总和III

LeetCode中文

解答：记忆化搜索 + 回溯 https://leetcode.cn/problems/path-sum-iii/solutions/596361/dui-qian-zhui-he-jie-fa-de-yi-dian-jie-s-dey6/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long, int> mp; // key: 前缀和 value: 前缀和等于key的节点数量
        long prefix_sum = 0;
        return pathSumImpl(root, targetSum, mp, prefix_sum);
    }
    int pathSumImpl(TreeNode* root, int target, unordered_map<long, int>& mp, long prefix_sum) {
        if (root == nullptr) return 0;
        int res = 0;
        prefix_sum += root->val;
        if (prefix_sum == target) res += 1;
        if (mp.find(prefix_sum - target) != mp.end()) {
            res += mp[prefix_sum - target];
        }
        mp[prefix_sum]++;
        res += pathSumImpl(root->left, target, mp, prefix_sum);
        res += pathSumImpl(root->right, target, mp, prefix_sum);
        mp[prefix_sum]--;
        return res;
    }
};

子集

LeetCode中文

LeetCode英文

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解答

大体思路是将数组nums遍历走一遍，对于数组nums的每一个元素都可以选择加入或者不加入，这样就构成了数组的所有子集。可以用递归来实现这个过程，利用临时数组tmp来存放每一子集。第i层递归到达数组的第i个元素nums[i]，在这一层递归可以选择将nums[i]加入或者不加入，然后进入下一层递归。递归结束条件为i到达数组的末尾，此时将tmp加入结果，然后返回上一层递归。

例如，数组[1,2,3]，递归过程如下所示：

                       []        
                   /          \        
                  /            \     
                 /              \
              [1]                []
           /       \           /    \
          /         \         /      \        
       [1 2]       [1]       [2]     []
      /     \     /   \     /   \    / \
  [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []
  • 时间复杂度：O(2n)
  • 空间复杂度：O(n)
class Solution {
public:
    void recursion(vector<int>& vec,vector<vector<int>>& res,vector<int>& tmp,int n)
    {
        if(n == vec.size())
        {
            res.push_back(tmp);
            return;
        }

        recursion(vec,res,tmp,n+1);
        
        tmp.push_back(vec[n]);
        recursion(vec,res,tmp,n+1);
        tmp.pop_back();
    }
    
    
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> tmp;
        
        if(nums.empty())
            return res;
        
        recursion(nums,res,tmp,0);
        
        return res;
    }
};

子集II

LeetCode中文

LeetCode英文

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

解答

思路和 子集 基本一样，但是由于数组有可能存在重复元素，为避免递归过程中得到重复的子集，需要有所调整。这里我们举例说明，对于数组[1,2,2]，在处理到第二个2时，由于前面已经处理了一次2，这次我们只在添加过2的[2] 和 [1 2]后面添加2，其他的都不添加，那么这样构成的二叉树如下图所示：

                        []        
                   /          \        
                  /            \     
                 /              \
              [1]                []
           /       \           /    \
          /         \         /      \        
       [1 2]       [1]       [2]     []
      /     \     /   \     /   \    / \
  [1 2 2] [1 2]  X   [1]  [2 2] [2] X  []

递归函数代码只需在原有的基础上增加一句话：

while(n+1 < vec.size() && vec[n] == vec[n+1]) n++;

这句话的作用是跳过树中为X的叶节点，因为它们是重复的子集，应被抛弃。

  • 时间复杂度：O(2n)
  • 空间复杂度：O(n)
class Solution {
public:
    void recursion(int n,vector<int>& vec,vector<vector<int>>& res,vector<int>& path)
    {
        if(n == vec.size())
        {
            res.push_back(path);
            return;
        }
        
        path.push_back(vec[n]);
        recursion(n+1,vec,res,path);
        path.pop_back();
        
        while(n+1 < vec.size() && vec[n] == vec[n+1]) n++;
        recursion(n+1,vec,res,path);
        
    }
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        if(nums.empty())
            return vector<vector<int>>();
        
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        vector<int> path;
        recursion(0,nums,res,path);
        
        return res;
    }
};

括号生成

LeetCode中文

LeetCode英文

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解答

括号的对数为n，生成括号的过程可以想象成走2n步，每一步可以选择左括号或者右括号，利用递归来模拟每一步的选择，那么就需要剔除那些无效的括号组合，我们定义两个变量l和r分别对左括号和右括号进行计数，要求的括号对数为n，那么在递归过程中，如果l > n或者r > n或者l < r，则出现无效的括号组合，返回；如果l == r == n，则出现有效的括号组合，加入结果。

class Solution {
public:
    void recursion(const int n,int l,int r,vector<string>& res,string str)
    {
        if(l > n || r > n || l < r)
            return;
        if(l == r && l == n)
        {
            res.push_back(str);
            return;
        }
        
         recursion(n,l + 1,r,res,str + '(');
         recursion(n,l,r + 1,res,str + ')');
    }
    
    vector<string> generateParenthesis(int n) {
        if(n <= 0) return vector<string>();
        
        string str;
        vector<string> res;
        recursion(n,0,0,res,str);
        
        return res;
    }
};

电话号码的字母组合

LeetCode中文

LeetCode英文

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

1

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:

尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解答

先用哈希表mp建立数字（按键）到对应字母之间的映射。例如，数字1，则建立映射mp['2'] = "abc"。定义数组res保存最终的结果，同时定义一个临时数组tmp存放每一个字母组合。然后递归来遍历输入字符串的每个字母元素，在第n层递归遍历到字母str[n]，如果str[n]在哈希表mp中存在(str[n]在'2'~'9'之间)，得到它映射的字符串s = mp[str[n]]，穷举s的每一个字母元素s[i]，然后放入tmp，进入下一层递归。递归结束条件是n == str.size()，此时遍历到字符串末尾，则将tmp加入结果res。

class Solution {
public:
    void recursion(unordered_map<char,string>& mp,int n,string& str,vector<string>& res,string& tmp)
    {
        if(n == str.size())
        {
            res.push_back(tmp);
        }
        
        if(mp.find(str[n]) != mp.end())
        {
            string s = mp[str[n]];
            for(int i=0;i<s.size();i++)
           {
                tmp.push_back(s[i]);
                recursion(mp,n + 1,str,res,tmp);
                tmp.pop_back();
            }
        }
    }
    
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return vector<string>();
        unordered_map<char,string> mp;
        mp['2'] = "abc";
        mp['3'] = "def";
        mp['4'] = "ghi";
        mp['5'] = "jkl";
        mp['6'] = "mno";
        mp['7'] = "pqrs";
        mp['8'] = "tuv";
        mp['9'] = "wxyz";
        
        vector<string> res;
        string tmp;
        recursion(mp,0,digits,res,tmp);
        return res;
    }
};

全排列

LeetCode中文

LeetCode英文

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解答

方法1

利用全排列的原理，设nums大小为n，想象有n个空位排成一排，从左往右，每一次都从数组选择一个数nums[i]放入空位，后面的空位就不能选择nums[i]，每一个空位都有多种选择，这样n个空位的选择组合在一起，就得到了所有可能的全排列。这个过程用递归来实现，定义bool类型数组vis来记录访问过的数字，定义数组res存放结果，每一步递归循环访问nums中所有未被访问的元素nums[i]，并加入临时数组tmp，同时在vis中记录(令vis[i] = true)，然后进入下一层递归。定义变量idx记录递归层数，那么递归结束条件是idx == nums.size()，此时tmp中已经存放了数组序列的全排列之一，将tmp加入结果数组res，然后返回。最后，所有递归过程结束之后，数组res就存放了所有的全排列。

  • 时间复杂度：O(n!)
  • 空间复杂度：O(n) (忽略存放结果的数组占用的内存)
class Solution {
public:
    void recursion(vector<vector<int>>& res,vector<bool>& vis,const vector<int>& nums,vector<int>& tmp,int idx)
    {
        if(idx == nums.size())
        {
            res.push_back(tmp);
        }
        
        for(int i=0;i<nums.size();i++)
        {
            if(!vis[i])
            {
                vis[i] = true;
                tmp.push_back(nums[i]);
                recursion(res,vis,nums,tmp,idx + 1);
                vis[i] = false;
                tmp.pop_back();
            }
        }
        
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        if(nums.empty()) return vector<vector<int>>();
        
        vector<bool> vis(nums.size(),false);
        vector<int> tmp;
        vector<vector<int>> res;
        
        recursion(res,vis,nums,tmp,0);
        
        return res;
    }
};

方法2

同样是递归的方法，处理过程和方法1不一样，在第n层递归中，循环过程，分别将数组nums中索引 n~nums.size()-1 的元素与nums[n]交换，然后进入下一层递归。整个递归结束后，就得到了所有的全排列。

  • 时间复杂度：O(n!)
  • 空间复杂度：O(1) (忽略存放结果的数组占用的内存)
class Solution {
public:
    void recursion(int n,vector<int>& vec)
    {
        if(n == vec.size())
        {
            res.push_back(vec);
            return;
        }
        
        for(int i=n;i<vec.size();i++)
        {
            swap(vec[n],vec[i]);
            recursion(n + 1,vec);
            swap(vec[n],vec[i]);
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        if(nums.empty()) return res;
        recursion(0,nums);
        return res;
    }
    
private:
    vector<int> tmp;
    vector<vector<int>> res;
};

格雷编码

LeetCode中文

LeetCode英文

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

示例 1:

输入: 2
输出: [0,1,3,2]

解释:

00 - 0
01 - 1
11 - 3
10 - 2

对于给定的 n，其格雷编码序列并不唯一。例如，[0,2,3,1] 也是一个有效的格雷编码序列。

00 - 0
10 - 2
11 - 3
01 - 1

示例 2:

输入: 0
输出: [0]

解释:

我们定义格雷编码序列必须以 0 开头。给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。

因此，当 n = 0 时，其格雷编码序列为 [0]。

解答

方法1

可以找出规律，n 位的格雷码可以由 n-1 位的格雷码获得

一位格雷码：0,1
两位格雷码：00,01;11,10
三位格雷码：000,001,011,010;110,111,101,100
四位格雷码：0000,0001,0011,0010,0110,0111,0101,0100;1100,1101,1111,1110,1010,1011,1001,1000

通过上面的枚举可以发现，格雷码的实现其实是一个递归过程。

例如：三位格雷码的前四位是把两位格雷码按从左到右的顺序在每一个格雷码前面加0实现的，后面四位是把两位格雷码按照从右到左的顺序在每一位格雷码前面加一实现的，大家按照这个方法推一下格雷码，应该能理解这段话的意思。

注意：在前面加0，格雷码对应的值不会改变，前面加1会让格雷码的值增加 2n-1 ( n 为格雷码的位数)

  • 时间复杂度：O(2n)
  • 空间复杂度：O(1) (忽略存放结果的数组占用的内存)
class Solution {
public:
    void recursion(vector<int>& vec,const int n,int idx)
    {
        if(idx > n) return;
        else if(idx == 1)
        {
            vec = {0,1};
            recursion(vec,n,idx + 1);
        }
        else{
            int len = vec.size();
            for(int i=len-1;i>=0;i--)
            {
                vec.push_back(vec[i]);
            }
            
            for(int j=len;j<vec.size();j++)
            {
                vec[j] += pow(2,idx-1);
            }
            
            recursion(vec,n,idx + 1);
        }
    }
    
    vector<int> grayCode(int n) {
        if(n == 0) return {0};
        
        vector<int> res;
        recursion(res,n,1);
        return res;
    }
};

方法2

二进制的格雷码是有转换公式的，对于数字num，它的格雷编码为a = num ^ (num >>1)，也就是将num与num右移一位的结果进行异或。

  • 时间复杂度：O(2n)
  • 空间复杂度：O(1) (忽略存放结果的数组占用的内存)
class Solution {
public:
    vector<int> grayCode(int n) {
        int len = 1 << n;
        vector<int> res;
        for(int i=0;i<len;i++)
        {
            int a = i ^ (i >> 1);
            res.push_back(a);
        }
        
        return res;
    }
};

累加数

LeetCode中文

LeetCode英文

累加数是一个字符串，组成它的数字可以形成累加序列。

一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

给定一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。

说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

示例 1:

输入: "112358"
输出: true 
解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

示例 2:

输入: "199100199"
输出: true 
解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

进阶:

你如何处理一个溢出的过大的整数输入?

解答

回溯法的思想，递归来处理，在每一层递归中，对字符串idx~len-1之间字母组成的字符串进行划分，注意是子串划分而不是子序列，所以划分的子串tmp有len-idx种可能，其中tmp = substr(idx,i - idx + 1)(idx <= i < len)，同时用一个临时数组res来存放每一步划分的子串，为避免int类型的溢出，需将tmp转换成long long 类型，而且由于INT_MAX位数为10，所以i - idx + 1不应该超过10。递归结束条件为idx == num.size() - 1，此时如果res.size() >= 3，则返回true。

在划分为子串tmp之后，首先判断tmp是否为符合要求的字符串(不是0开头的字符串)：

  1. 如果不符合要求，则跳过，进行下一次划分；
  2. 如果符合要求，则首先判断数组res的长度：
    • 如果长度小于2，则将tmp加入res，如果下一层递归的结果为true，则这一层递归也返回true；如果下一层递归的结果为false，则从res尾部删除tmp(回溯)，进行下一次划分；
    • 如果长度不小于2，则取出res的最后两个数字res[len - 1]和res[len - 2]。
      • 如果tmp == res[len - 1] + res[len - 2]，则将tmp加入res，同时判断：如果下一层递归的结果为true，则这一层递归也返回true；如果下一层递归的结果为false，则从res尾部删除tmp(回溯)，进行下一次划分；
      • 如果tmp != res[len - 1] + res[len - 2]，则跳过，进行下一次划分。

在回溯的过程中，只要出现满足条件的累加序列则返回true，每一层递归的bool返回结果基于它的下一层bool返回结果，所以第一层递归的bool返回结果即为所求。

注意：如果原字符串的长度小于3，则直接返回false。

class Solution {
public:
    bool inValid(const string& str)
    {
        if(str.size() == 1)
            return false;
        if(str.size() > 1)
        {
            if(str[0] == '0')
                return true;
        }
        
        return false;
    }
    
    long long Stol(string str)
    {
        long long res = 0;
        for(int i=0;i<str.size();i++)
        {
            res = 10 * res + (str[i] - '0'); 
        }
        
        return res;
    }
    
    bool recursion(int idx,string& num,vector<long long>& res)
    {
        int len = num.size();
        if(idx == len && res.size() >= 3) return true;
        
        for(int i = idx;i < len && i - idx <= 9;i++)
        {
            string str = num.substr(idx,i - idx + 1);
            if(inValid(str)) break;//01 02、、
            
            long long tmp = Stol(str);
            
            if(res.size() < 2) 
            {
                res.push_back(tmp);
                if(recursion(i + 1,num,res))
                    return true;
                res.pop_back();
            }
            else{
                int len1 = res.size();
                if(tmp == res[len1 - 1] + res[len1 - 2])
                {
                    res.push_back(tmp);
                    if(recursion(i + 1,num,res))
                        return true;
                    res.pop_back();
                }
            }
        }
        
        return false;
    }
    
    bool isAdditiveNumber(string num) {
        if(num.size() < 3) return false;
        
        vector<long long> res;
        return recursion(0,num,res);
    }
};

将数组拆分成斐波那契序列

LeetCode中文

LeetCode英文

定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。

形式上，斐波那契式序列是一个非负整数列表 F，且满足：

  • 0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；
  • F.length >= 3；
  • 对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。

另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。

返回从 S 拆分出来的所有斐波那契式的序列块，如果不能拆分则返回 []。

示例 1：

输入："123456579"
输出：[123,456,579]

示例 2：

输入: "11235813"
输出: [1,1,2,3,5,8,13]

示例 3：

输入: "112358130"
输出: []
解释: 这项任务无法完成。

示例 4：

输入："0123"
输出：[]
解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。

示例 5：

输入: "1101111"
输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受。

提示：

  1. 1 <= S.length <= 200
  2. 字符串 S 中只含有数字。

解答

思路同 累加数，这里需要返回从 S 拆分出来的所有斐波那契式的序列块，所以返回临时数组res。

注意：由于0 <= F[i] <= 2^31 - 1，所以在每一层递归划分子串之前，如果res的最后两个数字之和已经大于INT_MAX，则这一层递归直接返回false。

class Solution {
public:
    long long Stol(const string& str)
    {
        long long res = 0;
        for(int i=0;i<str.size();i++)
        {
            res = res * 10 + (str[i] - '0');
        }
        
        return res;
    }
    
    bool inValid(const string& str)
    {
        if(str.size() > 1 && str[0] == '0')
        {
            return true;
        }
        
        return false;
    }
    
    bool recursion(int idx,string& S,vector<int>& res)
    {
        if(idx == S.size() && res.size() >= 3)
            return true;
        
        int len = res.size();
        if(len >= 2 && (long long)res[len - 1] + (long long)res[len - 2] > INT_MAX) return false;
        
        for(int i=idx;i<S.size() && i-idx <= 9;i++)
        {
            string str = S.substr(idx,i - idx + 1);
            if(inValid(str)) break;
            
            long long tmp = Stol(str);
            
            if(tmp > INT_MAX) break;
            
            if(res.size() < 2)
            {
                res.push_back((int)tmp);
                if(recursion(i + 1,S,res)) return true;
                res.pop_back();
            }
            else{
                if(tmp == res[len - 1] + res[len - 2])
                {
                    res.push_back((int)tmp);
                    if(recursion(i + 1,S,res)) return true;
                    res.pop_back();
                }
            }
        }
        
        return false;
    }
    
    vector<int> splitIntoFibonacci(string S) {
        vector<int> res;
        if(S.size() < 3) return res;
        
        if(recursion(0,S,res))
            return res;
        
        return res;
    }
};

解数独

LeetCode中文

LeetCode英文

解答

Python代码

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def _remove_num(val: int, i: int, j: int, block_i: int):
            row_list[val][i] -= 1
            col_list[val][j] -= 1
            block_list[val][block_i] -= 1
            board[i][j] = '.'

        def _add_num(val: int, i: int, j: int, block_i: int):
            row_list[val][i] += 1
            col_list[val][j] += 1
            block_list[val][block_i] += 1
            board[i][j] = str(val)

        def _place_next_num(i: int, j: int):
            if i == 8 and j == 8:
                return True
            elif j == 8:
                if _dfs(i + 1, 0):
                    return True
            elif _dfs(i, j + 1):
                return True
            return False

        def _get_block(i: int, j: int):
            return (i // 3) * 3 + j // 3
        
        def _dfs(i: int, j: int) -> bool:
            if board[i][j] != '.':
                if _place_next_num(i, j):
                    return True
            else:
                for val in range(1, 10):
                    block_i = _get_block(i, j)
                    if row_list[val][i] > 0 or col_list[val][j] > 0 \
                            or block_list[val][block_i] > 0:
                        continue
                    _add_num(val, i, j, block_i)
                    if _place_next_num(i, j):
                        return True
                    _remove_num(val, i, j, block_i)
            return False

        row_list = [[0 for i in range(9)] for i in range(10)]
        col_list = [[0 for i in range(9)] for i in range(10)]
        block_list = [[0 for i in range(9)] for i in range(10)]
        for i in range(0, 9):
            for j in range(0, 9):
                val = board[i][j]
                if val != '.':
                    row_list[int(val)][i] += 1
                    col_list[int(val)][j] += 1
                    block_i = _get_block(i, j)
                    block_list[int(val)][block_i] += 1
        _dfs(0, 0)