22. Generate Parentheses

思路:

正确的迭代方式是,从左到右的遍历中,每一个正确序列都有左括号的数量大于等于右括号的数量。而每一处符号要么是左括号,要么是右括号,后者符号都有选择的生成即可。

如何便可以递归生成所有符合题意的括号。

Read more

81. Search in Rotated Sorted Array II

81. Search in Rotated Sorted Array II

思路:

这题好像是33题的follow up。

增添了各个元素可能相等的条件。

没做出来。

如果考虑在上一题的思路,先寻找找出二分点,在二分两端数字。如果遇到 nums[mid]==nums[l]那就需要遍历确定哪边是相等的,巴拉巴拉……,多了一堆条件设置和条件判断。

跳出这层,能不能直接在二分搜索呢?

Read more

39. Combination Sum

39. Combination Sum

在dfs搜索题中,形象化一个dfs搜索树是一个非常有趣的,形象的描述方法。比如下面这个没有剪枝的dfs搜索树。也可以比较一下,下面两种解法的dfs搜索树的不同之处。

img

Read more

130. Surrounded Regions

130. Surrounded Regions

思路:

如果用普通dfs搜索所有区域是速度有点慢的。

但只是反过来思考,如果只所搜索所有不被包围的O并标记,同时翻转所有剩下的X,最后把所有的P翻转回来是不是会更快。

不搞特例的话,一般都是后者快。

Read more

126. Word Ladder II

126. Word Ladder II

思路:

这次的bugs很少,开心。

这题核心就是BFS(DFS)的基础上加上剪枝优化。或者TBFS

建立搜索树BFS搜索结果即可。

最好用邻接矩阵优化BFS搜索数量,同时显然的,你没法通过绕一个小弯找到最短路,这可以剪枝。

Read more

51. N-Queens

51. N-Queens

思路:

八皇后问题,经典问题。回溯解决。

代码:

class Solution {
public:
    
    void generate(vector<vector<string>> &outs, vector<int> &chess, vector<int> &hashorpos, int depth, int n){
        if(n == depth){
            
            vector<string> res(n, string(n, '.'));
            for(int i = 0; i < n; ++i){
                res[i].replace(chess[i], 1, "Q"); 
                //  cout << chess[i] << ' ' ;
            }
            // cout << endl;
            outs.emplace_back(res);
            return;
        }
    
        for(int i = 0; i < n; ++i){
            int flag = 1;
            if(!hashorpos[i]){
                #这部分判断代码可以优化,但是很麻烦,可以用hasverpos代表一层中被禁止的位置,需要标记左右方向,很麻烦。考虑到n的数量直接遍历就行,可以当做一个不变量。
                for(int j = 1; j <= depth ; ++j){
                    if(chess[depth - j] == i - j || chess[depth - j] == i + j){
                        flag = 0;
                        break;
                    }                                        
                }
                if(!flag) continue;

                chess[depth] = i;
                hashorpos[i] = 1;
                
                generate(outs, chess, hashorpos, depth + 1, n);
                                
                chess[depth] = -1;
                hashorpos[i] = 0;
                
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> outs;
        vector<int> chess(n, -1), hashorpos(n, 0);
        generate(outs, chess, hashorpos, 0, n);
        return outs;
    }
};

4. Median of Two Sorted Arrays

4. Median of Two Sorted Arrays - 第K大 + 二刷

思路:

将查找中位数扩大为更广义的解法:求解第$K$位的数字。每次在A,B两个数组中划分出两个k/2个元素,并排除划分出的最后一个数字比较小的数组,然后减去对应的排除的数组的数字个数,更新$K$值。直到$K==1$,或者其中一个数组为空。

详细题解如下

Read more

81. Search in Rotated Sorted Array II

81. Search in Rotated Sorted Array II

思路:

这题好像是33题的follow up。

增添了各个元素可能相等的条件。

没做出来。

如果考虑在上一题的思路,先寻找找出二分点,在二分两端数字。如果遇到 nums[mid]==nums[l]那就需要遍历确定哪边是相等的,巴拉巴拉……,多了一堆条件设置和条件判断。

跳出这层,能不能直接在二分搜索呢?

Read more