Leetcode_14 天算法入门_day11

Posted on | Edited on | In ,
| 5.3k | 44 mins.

今天是 3 道中等题，有点难度？？？

今天的主题依然是递归跟回溯。

77. Combinations

Analysis

这个题看着挺简单的，其实不是个简单的题目...
最直观的思路，应该是先挑出 1，然后从剩余大于 1 的数中挑选出 k - 1 个数，依次挑选即可。按照这种思路，写了一下，越写感觉越不对劲。只凭单纯的循环，可能并不能完美的表达出这种过程，还需要一点思考，还是先按照常规的思路来吧。

Code

backtracking

这个题其实是个经典的回溯法应用题，对于每一个数字只有选与不选两种可能，当选出的数的个数等于 k 时，就找到解，可以返回了，注意大于 n 的数字不能选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* dfs */
class Solution {
public:
    vector<int> tmp;
    void dfs(int cur, int n, int k, vector<vector<int>>& ret) {
        if(tmp.size() == k) {
            ret.push_back(tmp);
            return;
        }
        if(cur == n + 1) return;
        tmp.push_back(cur);
        dfs(cur + 1, n, k, ret);
        tmp.pop_back();
        dfs(cur + 1, n, k, ret);
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        dfs(1, n, k, ret);
        return ret;
    }
};

但是为什么总感觉递归用的这么别扭呢？
接下来，可以修改下代码，“剪掉”某些情况，比如当 tmp 的大小与剩余数字之和小于 k 时，此时不论怎样都是无解的，这样就没有必要继续递归下去了，这样就可以写成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* dfs */
class Solution {
public:
    vector<int> tmp;
    void dfs(int cur, int n, int k, vector<vector<int>>& ret) {
        if(tmp.size() + (n - cur + 1) < k) return;
        if(tmp.size() == k) {
            ret.push_back(tmp);
            return;
        }
        if(cur == n + 1) return;
        tmp.push_back(cur);
        dfs(cur + 1, n, k, ret);
        tmp.pop_back();
        dfs(cur + 1, n, k, ret);
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        dfs(1, n, k, ret);
        return ret;
    }
};

按照 Leetcode 给的测试样例，速度的提升很明显。
实际上，当cur == n + 1时，tmp 的大小与剩余数字之和一定是小于等于 k 的，这样就会被第一个或第二个 if 返回了，所以，最终的代码可以写成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* dfs: tmp.size + (n - cur + 1) < k */
class Solution {
public:
    vector<int> tmp;
    void dfs(int cur, int n, int k, vector<vector<int>>& ret) {
        if(tmp.size() + (n - cur + 1) < k) return;
        if(tmp.size() == k) {
            ret.push_back(tmp);
            return;
        }
        tmp.push_back(cur);
        dfs(cur + 1, n, k, ret);
        tmp.pop_back();
        dfs(cur + 1, n, k, ret);
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        dfs(1, n, k, ret);
        return ret;
    }
};

iteration

这里不得不在提到一下使用循环（迭代）的方法，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* iteration */
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        int i = 0;
        vector<int> tmp(k, 0);
        while(i >= 0) {
            tmp[i]++;
            if(tmp[i] > n) i--;
            else if(i == k - 1) ret.push_back(tmp);
            else {
                i++;
                tmp[i] = tmp[i - 1];
            }
        }
        return ret;
    }
};

这个解法其实并没有单纯的利用循环，反而有一点动态规划的影子在里面，又有一点回溯的影子在里面。

46. Permutations

Analysis

看到这个题，直接就想到了 next_permutation 这个函数，果断直接用。

Code

next_permutation()

1
2
3
4
5
6
7
8
9
10
11
12
/* next_permutation */
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        do{
            ret.push_back(nums);
        } while(next_permutation(nums.begin(), nums.end()));
        return ret;
    }
};

这里有个问题，一开始没有对 nums 进行排序，提交是无法通过的。百度了一下，发现 next_permutation 在生成排列的时候是按照当前顺序生成下一个排列，直到数字序列是降序为止。也就是说，如果数字序列一开始不是严格的升序序列，那么就可能会漏掉可能存在的排列组合，所以要先排序，不过题目也不是每个样例都是无序序列，当然了，直接排序还无脑一点。

backtracking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* dfs */
class Solution {
public:
    void dfs(vector<vector<int>>& ret, vector<int>& nums, int first, int len) {
        if(first == len) {
            ret.push_back(nums);
            return;
        }
        for(int i = first; i < len; i++) {
            swap(nums[i], nums[first]);
            dfs(ret, nums, first + 1, len);
            swap(nums[i], nums[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        dfs(ret, nums, 0, nums.size());
        return ret;
    }
};

虽然是回溯的入门题，但感觉不是很好想啊...

784. Letter Case Permutation

Analysis

这个题算是上面这个题的变式，复杂度差不多。

Code

直接按照上面的思路来做，注意对每一个字母，需要转换大小写后再选择，然后还需要还原（回溯的思想），但数字就不用了。

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
class Solution {
public:
    string tmp;
    void dfs(vector<string>& ret, string s, int first, int length) {
        if(first == length) {
            ret.push_back(s);
            return;
        }
        if(isupper(s[first])) {
            s[first] += 32;
            dfs(ret, s, first + 1, length);
            s[first] -= 32;
        } else if(islower(s[first])) {
            s[frist] -= 32;
            dfs(ret, s, first + 1, length);
            s[first] += 32;
        }
        dfs(ret, s, first + 1, length);
    }
    vector<string> letterCasePermutation(string s) {
        vector<string> ret;
        if(s.length() > 0) dfs(ret, s, 0, s.length());
        return ret;
    }
};

Summary

今天是 3 道考察回溯算法的题，难度不是很大，但是其中蕴含的思想要好好体会。

Buy me a coffee ? :)
0%