1.分治

本质上就是一种递归

找问题重复性，分解问题，组合每个子问题结果

递归状态树

1.1 分治 Divide & Conquer

1.2 分治代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def divide_conquer(problem, param1, param2, ...):
  # 1.recursion terminator (递归终止条件)
  if problem is None:
    print_result
    return
  
  # 2.prepare data (拆分问题)
  data = prepare_data(problem)
  subproblems = split_problem(problem, data)
  
  # 3.conquer subproblems (调字问题的递归函数)
  subresult1 = self.divide_conquer(subproblems[0], p1, ...)
  subresult1 = self.divide_conquer(subproblems[0], p1, ...)
  subresult1 = self.divide_conquer(subproblems[0], p1, ...)
  ...
  
  # 4.process and generate the final result (合并结果)
  result = process_result(subresult1, subresult2, subresult3, ...)
  
  # 5.revert the current level status (回复当前层状态)

泛型递归代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def recursion(level, param1, param2, ...):
  # 1.recursion terminator (递归终止条件)
  if level > MAX_LeVEL:
    process_result
    return

  # 2.process logic in current level (处理当前层逻辑)
  process(level, data, ...)
  
  # 3.drill down (下探到下一层)
  self.recursion(level + 1, p1, ...)
  
  # 4.reverse the current level status if needed (清理当前层)

2.回溯

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。

回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

  • 找到一个可能存在的正确的答案
  • 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

最典型应用：八皇后、数独

3.实战题目

3.1 pow(x, n)

https://leetcode.cn/problems/powx-n/

（1）暴力 O(n)

1
2
3
4
result = 1;
for (int i = 0; i < n; i++) {
  result *= x;
}

（2）分治

1
2
3
4
5
6
template:
  1. terminator
  2. process (split your big problem)
  3. drill down (subproblems), merge(subresult)
  4. reverse states

x^n → 2^10 → 2^5 → (2^2)*2

1
2
3
4
5
6
7
8
9
10
pow(x, n):
  subproblem : subresult = power(x, n/2)

merge:
  if (n % 2 == 1) {
    result = subresult * subresult * x;
  } else {
    result = subresult * subresult;
  }

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    // 分治，递归
    // 2^10 --> 2^5  -> (2^2) * 2
    double fast_pow(double x, int n) {
        if (n == 0)
            return 1.0;
        double sub_result = fast_pow(x, n/2);
        return n % 2 == 0 ? sub_result * sub_result : sub_result * sub_result * x;
    }

    // 分治递归处理
    double myPow(double x, int n) {
        long long N = n;
        // 如果n是负数，特殊处理
        return N >= 0 ? fast_pow(x, N) : fast_pow(1/x, -N);
    }
};

（3）牛顿迭代法

3.2 子集

78. 子集 - 力扣（LeetCode）

（1）递归

类似爬楼梯，可选可不选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    void dfs(std::vector<std::vector<int>>& ans, std::vector<int>& nums, vector<int> list, int idx) {
        // terminator
        if (idx == nums.size()) {
            ans.push_back(list);
            return;
        }

        // not pick the number at this idx
        this->dfs(ans, nums, list, idx + 1);

        // pick the number at this idx
        list.push_back(nums[idx]);
        this->dfs(ans, nums, list, idx + 1);
        list.pop_back();

    }
    vector<vector<int>> subsets(vector<int>& nums) {
        std::vector<std::vector<int>> ans;
        std::vector<int> list;
        if (nums.empty())
            return ans;

        this->dfs(ans, nums, list, 0);

        return ans;
    }
};

（2）迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    # []

    # [1]

    # [2]
    # [1, 2]

    # [3]
    # [1, 3]
    # [2, 3]
    # [1, 2, 3]
    def subsets(self, nums: List[int]) -> List[List[int]]:
        results = [[]]

        for num in nums:
            new_sets = []
            for subset in results:
                new_subset = subset + [num]
                new_sets.append(new_subset)
            results.extend(new_sets)

        return results

3.3 众数

https://leetcode-cn.com/problems/majority-element/description/ （简单、但是高频）

（1）哈希表

我们使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。

我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后，我们遍历哈希映射中的所有键值对，返回值最大的键。我们同样也可以在遍历数组 nums 时候使用打擂台的方法，维护最大的值，这样省去了最后对哈希映射的遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    // 哈希表映射法
    int majorityElement(vector<int>& nums) {
        std::unordered_map<int, int> counts;
        int majority = 0;
        int max_cnt = 0;

        for (int num : nums) {
            counts[num]++;
            if (counts[num] > max_cnt) {
                majority = num;
                max_cnt = counts[num];
            }
        }

        return majority;
    }
};

3.3 电话号码的字母组合

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

1
2
3
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) {
            return {};
        }
        std::vector<std::string> ans;

        std::unordered_map<char, std::string> map{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };

        this->search("", digits, 0, ans, map);

        return ans;
    }

private:
    void search(std::string s, std::string& digits,  int i,
        std::vector<std::string>& ans, 
        std::unordered_map<char, std::string> map) {
        // terminator
        if (i == digits.size()) {
            ans.push_back(s);
            return;
        }

        // process
        std::string letters = map.at(digits[i]);
        for (int j = 0; j < letters.size(); j++) {
            // drill down
            this->search(s+letters[j], digits, i+1, ans, map);
        }
    }
};

3.4 N皇后

51. N 皇后 - 力扣（LeetCode）

1
2
3
4
5
6
7
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if n < 1:
            return []
        
        self.result = []

        # 之前的皇后所占的位置 (列, pie, na)
        self.cols = set()
        self.pie = set()
        self.na = set()

        self.dfs(n, 0, [])

        return self._generate_result(n)


    def dfs(self, n, row, curr_state):
        # 终止条件
        if row >= n:
            self.result.append(curr_state)
            return

        # 当前层处理
        for col in range(n):
            if col in self.cols or row + col in self.pie or row - col in self.na:
                # 不能放
                continue
            
            # 更新标志位
            self.cols.add(col)
            self.pie.add(row + col)
            self.na.add(row - col)

            self.dfs(n, row + 1, curr_state + [col])

            self.cols.remove(col)
            self.pie.remove(row + col)
            self.na.remove(row - col)

    def _generate_result(self, n):
        board = []
        for res in self.result:
            for i in res:
                board.append("." * i + "Q" + "." * (n - i - 1))
        
        return [board[i : i + n] for i in range(0, len(board), n)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        std::vector<std::string> curr_state(n, std::string(n, '.'));
        this->dfs(curr_state, 0, n);

        return m_ans;
    }

private:
    std::vector<std::vector<std::string>> m_ans;

    void dfs(std::vector<std::string>& curr_state, int row, int n) {
        // 终止条件
        if (row == n) {
            m_ans.push_back(curr_state);
            return;
        }

        // 循环每列，
        for (int col = 0; col < n; col++) {
            if (this->is_valid(curr_state, row, col)) {
                // doing
                curr_state[row][col] = 'Q';
                // 下一行
                this->dfs(curr_state, row + 1, n);
                // reverse
                curr_state[row][col] = '.';
            }
        }
    }

    bool is_valid(const std::vector<std::string>& curr_state, int row, int col) {
        int n = curr_state.size();

        // 上
        for (int i = 0; i < n; i++) {
            if (curr_state[i][col] == 'Q') {
                return false;
            }
        }

        // 左上
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (curr_state[i][j] == 'Q') {
                return false;
            }
        }

        // 右上
        for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
            if (curr_state[i][j] == 'Q') {
                return false;
            }
        }

        // 其他方向都是未放过皇后的，不可能为false
        return true;
    }

};

写的很好的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    # 写的很好的python代码
    def solveNQueens(self, n: int) -> List[List[str]]:
        def dfs(queens, xy_dif, xy_sum):
            p = len(queens)
            if p == n:
                result.append(queens)
                return None
            for q in range(n):
                if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
                    dfs(queens + [q], xy_dif+[p-q], xy_sum+[p+q])
        result = []
        dfs([], [], [])
        return [["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]