刷题-搜索

发表于 | 更新于 | 评论数：
本文字数： 40k | 阅读时长 ≈ 36 分钟

1. [Leetcode 200] 岛屿的个数

  • 解法：

    • DFS：一次遍历，遇到1则进行深搜，遍历过的1设为2，遇到非1或者越界则深搜停止，统计深搜的次数，即为岛屿数量。(这里采用)
    • BFS: 循环遍历每个点，如果该点是0，则跳过，如果是1，岛屿数目加1，并加入队列，并将该点改为0，避免重复访问，然后进行广搜，取出队首元素，搜索该点周围四个点，如果有1就加入队列，并将1改为0，否则就跳过，当队列空时，一块岛屿搜索完毕，进入下一块搜索。(代码可参考：岛屿的个数 BFS)
    • 并查集: 将二维数组重新编号，从0开始，从左到右，从上到下，直到n*m-1（其中n为行数，m为列数），对于位置(i,j)则编号为i*m+j，那么相邻（左右，上下）的为同一个值，则认为他们相通。那么最终只要统计一下father[i]==i且对应值为1的个数即可。(代码可参考: 岛屿的个数 Disjoint Set)

  • 代码：

    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
    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            if(grid.empty()) return 0;

            int res = 0;
            
            for(int i = 0; i < grid.size(); i++){
                for(int j = 0; j < grid[0].size(); j++){
                    if(grid[i][j] == '1'){
                        dfs(grid, i, j);
                        res++;
                    }
                }
            }
            return res;
        }
        
        void dfs(vector<vector<char>>& grid, int row, int col){
            if(row < 0 || col < 0 || row >= grid.size() || col >= grid[0].size() || grid[row][col] == '0' || grid[row][col] == '2')
                return;
            
            if(grid[row][col] == '1') grid[row][col] = '2';
            
            dfs(grid, row-1, col);
            dfs(grid, row+1, col);
            dfs(grid, row, col-1);
            dfs(grid, row, col+1);
                    
        }
        
       
    };

2. [Leetcode 77] 组合

  • 模板题：重点在于dfs中的startPos=i+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
    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            vector<vector<int>> res;
            vector<int> inRes;
            if(n<=0 || k<=0) return {};
            
            
            dfs(res, inRes, n, k, 1);
            return res;
        }
        
        void dfs(vector<vector<int>> &res, vector<int> &inRes, int n, int k, int startPos){
            if(inRes.size()==k){
                res.emplace_back(inRes);
                return;
            }
                
            
            for(int i = startPos; i<=n; i++){
                inRes.emplace_back(i);
                dfs(res, inRes, n, k, i+1); //重点在于i+1
                inRes.pop_back();
            }
        }
    };

3. [Leetcode 39] 组合总和(可重复选取数字)

  • 基于模板加一些改动即可，由于可重复选择数字，将startPos=i+1 改成startPos=i，判停条件满足目标和就可以了,(前提是有序数组，先拍下序)
  • 代码：
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
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        if(candidates.size() <= 0) return {};
        vector<vector<int>> res;
        vector<int> tmp;
        sort(candidates.begin(), candidates.end()); //保证有序
        dfs(res, target, tmp, candidates, 0);
        return res;
    }
    
    void dfs(vector<vector<int>> &res,int target, vector<int> tmp, vector<int>& candidates, int startPos)
    {
        int sum = 0;
        for(auto i : tmp) 
            sum += i;
        
        if (sum > target)
        {
            return;
        }
        
        if (sum == target) //求和判停
        {
            res.emplace_back(tmp);
            return;
        }
        
        for(int i = startPos; i < candidates.size(); i++)
        {
            tmp.emplace_back(candidates[i]);
            dfs(res, target, tmp, candidates, i);
            tmp.pop_back();
        }
    }
};

4. [Leetcode 40] 组合总和 II (不重复)

  • 解法：在上一题的基础上使用Set进行去重

  • 代码:

    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
    class Solution {
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            if (candidates.size() <= 0) return {};
            set<vector<int>> res;
            vector<int> curr;

            
            sort(candidates.begin(), candidates.end());
            dfs(res, target, 0, curr, candidates);
            return vector<vector<int>>(res.begin(), res.end());
        }
        
        void dfs(set<vector<int>> &res, int target, int s, vector<int> curr, vector<int>& candidates)
        {
            if(target == 0) 
            {
                res.insert(curr);
                return;
            }
            
            for(int i = s; i < candidates.size(); i++)
            {
                if(target - candidates[i] < 0) break;
                curr.emplace_back(candidates[i]);
                dfs(res, target - candidates[i], i+1, curr, candidates);
                curr.pop_back();
            }
        }
    };

5.[Leetcode 216] 组合总和 III

  • 解法:
  • 代码
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:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> nums;
        vector<vector<int>> res;
        vector<int> curr;
        for(int i = 0; i < 9; i++)
            nums.emplace_back(i+1);
        dfs(res, k, n, 0, 0, curr, nums);
        return res;
    }
    
    void dfs(vector<vector<int>> &res, int k, int target, int s, int depth, vector<int> curr, vector<int>& nums)
    {
        if(target == 0 && depth == k)
        {
            res.emplace_back(curr);
            return;
        }
        
        for(int i = s; i < nums.size(); i++)
        {
            if(target - nums[i] < 0) break;
            curr.emplace_back(nums[i]);
            dfs(res, k, target - nums[i], i+1 , depth+1 , curr, nums);
            curr.pop_back();
        }
    }
};

6.[Leetcode 131] 分割回文串

  • 解法:

    按解组合的方式解，解的过程中判断回文串，组合的元素集合是按照从子串的第一个元素开始，到第i个元素截断作为一个新子串进行回文判断，

  • 代码：

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
62
63
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string >> res;
        vector<string> tmp;
        
        dfs(res, tmp, 0, s.length()-1, s);
        return res;
    }
    
    void dfs(vector<vector <string> >& res, vector<string >& tmp, int startPos, int endPos, string &s){
        //当原字符串都遍历完成后，结束一次搜索。
        if(startPos > endPos){
            res.emplace_back(tmp);
            return;
        }
        //遍历子串，从0~1，0~2 ... 到0~n, 递归的起始位置为截断后的第一位
        for(int i =1; i <= endPos-startPos+1; i++){
            if(isPalindrome(s.substr(startPos, i))){
                tmp.emplace_back(s.substr(startPos, i));
                //递归的起始位置为截断后的第一位
                dfs(res, tmp, startPos+i, endPos, s);
                tmp.pop_back();
            }
            
        }
    }
    
    // 判断回文串，这里用的是可解决大小写字母，数字的，过滤其他符号。
    bool isPalindrome(string s) {
        int pStart = 0;
        int pEnd = s.length()-1;
        while(pStart < pEnd){
            while (!checkChar(s[pStart]) && pStart < pEnd)
				pStart++;
			while (!checkChar(s[pEnd]) && pStart < pEnd)
				pEnd--;

			toLower(s[pStart]);
			toLower(s[pEnd]);
           
            if(s[pStart] == s[pEnd]){
                pStart ++;
                pEnd--;
            }else{
                return false;
            }
               
        }
        return true;
    }
    
    void toLower(char& s){
        if(s >= 'A' && s <= 'Z')
            s = s+32;
    }
    
	bool checkChar(const char& s){
		if ((s >= 'a' && s <= 'z') || (s >= '0' && s <= '9') || (s >= 'A' && s <= 'Z'))
			return true;
		return false;
	}
};

7.机器人运动范围

  • 规规矩矩没啥说的, 主要注意边界条件

  • 代码:

    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
    class Solution {
    public:
        int movingCount(int threshold, int rows, int cols)
        {
            int res = 0;
            vector<vector<int>> visited (rows, vector<int>(cols, 0));
            Dfs(threshold, rows, cols, 0, 0, res, visited);
            return res;
        }
        
        void Dfs(const int& threshold, const int& rows, const int& cols, int rowIdx, int colIdx, int& res, vector<vector<int>>& visited){
            if (JudgeOverThreshold(threshold, rowIdx, colIdx) || JudgeOutside(rows, cols, rowIdx, colIdx) || visited[rowIdx][colIdx] )
                return;
            visited[rowIdx][colIdx] = 1;
            res ++;
            Dfs(threshold, rows, cols, rowIdx+1, colIdx, res, visited);
            Dfs(threshold, rows, cols, rowIdx, colIdx+1, res, visited);
            Dfs(threshold, rows, cols, rowIdx-1, colIdx, res, visited);
            Dfs(threshold, rows, cols, rowIdx, colIdx-1, res, visited);
        }
        
        bool JudgeOverThreshold(const int& threshold, int rowIdx, int colIdx){
            int sum = 0;
            while(rowIdx){
                sum += rowIdx%10;
                rowIdx /= 10;
            }
            
            while(colIdx){
                sum += colIdx%10;
                colIdx /= 10;
            }
            if(sum > threshold) return true;
            else return false;
        }
        
        bool JudgeOutside(const int& rows, const int& cols, const int& rowIdx, const int& colIdx){
            if(rowIdx < 0 || rowIdx > rows-1 || colIdx < 0  || colIdx > cols-1) return true;
            else return false;
        }
    };
一分钱也是爱，mua~