算法篇-----回溯1

什么是回溯呢？

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解
条件时，就“回溯”返回，尝试别的路径。 其实呢
常见的回溯有 DFS —深度优先搜索（一条路走到黑）， 类似于二叉树的前序遍历，本质就算 全排列 或者是 组合
BFS—广度优先搜素 （一石激起千层浪）， 类似于二叉树的层序遍历（这个广度优先搜索放在后面的博客）

DFS：
例如 ： 假设我们有 A, B , C ， D 这4张扑克牌， 放入3个盒子里面
如果是全排列呢？

void DFS(vector<char>& board, vector<bool>& book, string& poker, int cur)
{
	if (cur == 3)  //下标3 表示第4个盒子了
	{
		for (auto e : board)
			cout << e << " " ;

		cout << endl;

		return;
	}

	for (int i = 0; i < poker.size(); i++)
	{
		if (book[i] == false)
		{
			board[cur] = poker[i];  //把没用过的牌放入盒子
			book[i] = true;         //标记为用过
			DFS(board, book, poker, cur + 1);
			book[i] = false;      //回溯的时候没有用过
		}
	}

}

int main()
{

	//扑克牌 ABCDEFG
	string poker = "ABCD";
	//5个盒子
	vector<char> board(3, 0);
	//标记扑克牌的使用情况, false 表示没有使用过的
	vector<bool> book(poker.size(), false);
	//0表示当前盒子
	DFS(board, book, poker, 0);

	return 0;
}

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

如果是组合呢？

力扣690-----员工的重要性（中等）

题目链接

class Solution {
public:
    int DFS(int id,unordered_map<int , Employee*>& m, int curImportance)
    {
        curImportance = m[id]->importance;  //这个curImportance 算的是当前员工的所有直系员工
        for(auto& e : m[id]->subordinates)
        {
            curImportance += DFS(e, m, curImportance);
        }
        
        return curImportance;
    }

    int getImportance(vector<Employee*> employees, int id) 
    {
        unordered_map<int , Employee*> m;
        for(auto& e : employees)  
        {
            m[e->id] = e;
        }

        return DFS(id, m, 0);  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

力扣733-----图像渲染（简单）

力扣链接

//向四个方向探索
const int arr[4][2] = {{-1,0}, {1,0}, {0,-1}, {0, 1}};
class Solution {
public:
    void DFS(vector<vector<int>>& image, int x, int y, int oldcolor, int newcolor, int row, int col)
    {
         image[x][y] = newcolor; 

         for(int i = 0; i < 4; i++)
         {
             int newx = x + arr[i][0];
             int newy = y + arr[i][1];

             if(newx < 0 || newx >= row || newy < 0 || newy >= col)
                      continue;

             if(image[newx][newy] == oldcolor)
                    DFS(image, newx, newy, oldcolor, newcolor, row, col);
         }
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
    {
        if(image[sr][sc] == color) //old 和new一样不用玩了
             return image;

        int row = image.size();
        int col = image[0].size();

        DFS(image, sr, sc, image[sr][sc], color, row, col);

        return image;
    }
};
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

力扣463-----岛屿的周长（简单)

力扣题链接

这个题目和上面一个题目类似， 就不写深度搜索了， 就直接简单的遍历也是可以的。

const int arr[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid)
    {
        int row = grid.size();
        int col = grid[0].size();

        int ans = 0;
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (grid[i][j] == 1)    //表明当前是陆地
                {
                    int cnt = 0;
                    for (int k = 0; k < 4; k++)
                    {
                        int newx = i + arr[k][0];
                        int newy = j + arr[k][1];

                        if (newx < 0 || newx >= row || newy < 0 || newy >= col
                            || !grid[newx][newy])     //如果是边界或者是水路就 + 1
                        {
                            cnt += 1;
                        }
                    }

                    ans += cnt;
                }
            }
        }

        return ans;
    }
};
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

力扣130------被围绕的区域（中等）

力扣链接

const int arr[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

class Solution
{
public:
    void DFS(vector<vector<char>>& board, int x, int y, int row, int col)
    {
        if(board[x][y] == 'A' || board[x][y] == 'X')
             return;

        board[x][y] = 'A';
        for(int i = 0; i < 4; i++)
        {
            int newx = x + arr[i][0];
            int newy = y + arr[i][1];

            if(newx < 0 || newx >= row || newy < 0 || newy >= col)
                      continue;

            if(board[newx][newy] == 'O')
                 DFS(board, newx, newy, row, col);
        }
    }

    void solve(vector<vector<char>>& board) 
    {
        int row = board.size();
        int col = board[0].size();
        
        //遍历边界的两列
        for(int i = 0; i < row; i++)
        {
             DFS(board, i, 0, row, col);
             DFS(board, i, col-1, row, col);
        }
        
        //遍历边界上的两条行
        for(int i = 0; i < col; i++)
        {
            DFS(board, 0, i, row, col);
            DFS(board, row-1, i, row, col);
        }

        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(board[i][j] == 'O')
                      board[i][j] = 'X';                
                else if(board[i][j] == 'A')
                      board[i][j] = 'O';
            }
        }

    }
};
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

给一些相关的类似题， 都和这些题目的思想基本一致
力扣200，岛屿数量
我只用从遍历这个二维数组， 然后将岛屿变为海水 ， 通过DFS将上下左右都变为海水。
看最终需要变几次海水就可以了

const int arr[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
    void _numIslands(vector<vector<char>>& grid, int row, int col, int x, int y)
    {
        grid[x][y] = '0';
        for(int i = 0; i < 4; i++)
        {
            int newx = x + arr[i][0];
            int newy = y + arr[i][1];

            if(newx < 0 || newx >= row || newy < 0 || newy >= col)
               continue;

            if(grid[newx][newy] == '1')
              _numIslands(grid, row, col, newx, newy);
        }
    }

    int numIslands(vector<vector<char>>& grid) 
    {
        int row = grid.size();
        int col = grid[0].size();

        int ans = 0;
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(grid[i][j] == '1')
                {
                    ans++;
                    _numIslands(grid, row, col, i, j);
                }
            }
        }
        
        return ans;
    }
};
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

力扣695， 岛屿的最大面积
类似于， 渲染多少次。 找到渲染次数最大的那一次就行。

const int arr[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static int g_val = 0;
class Solution {
public:
     void _numIslands(vector<vector<int>>& grid, int row, int col, int x, int y)
    {
        grid[x][y] = 0;
        for(int i = 0; i < 4; i++)
        {
            int newx = x + arr[i][0];
            int newy = y + arr[i][1];

            if(newx < 0 || newx >= row || newy < 0 || newy >= col)
               continue;

            if(grid[newx][newy] == 1)
            {
                g_val++;
                _numIslands(grid, row, col, newx, newy);
            }
        }

    }

    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        int row = grid.size();
        int col = grid[0].size();

        int ans = 0;
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(grid[i][j] == 1)
                {
                     _numIslands(grid, row, col, i, j);
                     ans = max(ans, g_val + 1);
                     g_val = 0;
                }
            }
        }

        return ans;
    }
};
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

力扣17--------电话号码的组合 （中等）

力扣17

vector<string> number= {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv"
,"wxyz"};
class Solution {
public:
    void DFS(const string& digits,vector<string>& ans, string str, int i)
    {
        if(str.size() == digits.size())
        {
            ans.push_back(str);
            return;
        }

        int num = digits[i] - '0'; //拿到一个号码
        for(const auto& e : number[num])
        {
            DFS(digits, ans, str + e, i + 1);
        }
    }

    vector<string> letterCombinations(string digits) 
    {
        if(digits.empty())
             return  vector<string>();
             
        vector<string> ans;
        string str;
 
        DFS(digits, ans, str, 0);   
        return ans;
    }
};
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