wy的leetcode刷题记录_Day25

wy的leetcode刷题记录_Day25

130. 被围绕的区域

130. 被围绕的区域

题目介绍

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例 1：

输入：board =[[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]]
输出：[[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的
‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：
输入：board = [[“X”]]
输出：[[“X”]]

思路

首先根据题目意思，我们先找到边界上为0的位置，然后根据这几个位置进行DFS搜索，将与边界相连的内部0的位置做上标记，最后我们遍历整个地域，如果遍历到0并且没有标记我们就将其变为X，否则仍变为0.

代码

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        //先对边界点进行判断 找到边界上的O 然后dfs搜寻内部的相连的O
        int n=board.size();
        int m=board[0].size();
        
        for(int i=0;i<m;i++)
        {
            if(board[0][i]=='O')
                dfs(board,0,i);
             if(board[n-1][i]=='O')
                dfs(board,n-1,i);           
        }
        for(int i=0;i<n;i++)
        {
            if(board[i][0]=='O')
                dfs(board,i,0);
             if(board[i][m-1]=='O')
                dfs(board,i,m-1);           
        }

        //dfs搜寻完之后  遍历整个board 把剩余的O给填上
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(board[i][j]=='O')
                    board[i][j]='X';
                else if(board[i][j]=='1')
                   board[i][j]='O';
            }
        }

       // return board;

    }
    void dfs(vector<vector<char>>& board,int x,int y)
    {
        if(x<0||y<0||x>=board.size()||y>=board[0].size()||board[x][y]!='O')
            return ;
        board[x][y]='1';
        dfs(board,x+1,y);
        dfs(board,x,y+1);
        dfs(board,x-1,y);
        dfs(board,x,y-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
43
44
45
46
47
48
49
50

收获

又是一道DFS的题，一般在图、数等复杂数据结构中有相连问题或者搜索问题时一定会用到DFS或者BFS。

583. 两个字符串的删除操作

583. 两个字符串的删除操作

题目介绍

1. 给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
2. 每步 可以删除任意一个字符串中的一个字符。

示例 1：
输入: word1 = “sea”, word2 = “eat”
输出: 2
解释: 第一步将 “sea” 变为 “ea”，第二步将 "eat "变为 “ea”

示例 2:
输入：word1 = “leetcode”, word2 = “etco”
输出：4

思路

1. 确定dp数组的含义：dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素
   的最少次数。（也就是把俩个字符串分解从0开始看起）
2. 确定dp数组的递推公式：这里也是俩种情况：1）新加入的字符匹配，这样的话dp[i][j]=dp[i-1][j-1]。2）新加入的字符不匹配，这样的情况要么删除word1的子串的最后一个字符，要么删除word2的子串的最后一个字符，要么俩个都删 （最后发现这个条件不要好像也能成立？？？为什么我也不清楚。。。），最后得出dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+2));
3. 初始化：从递推公式可以看出我们的dp二维数组的边界是肯定要初始化的，根据dp数组的定义我们得出：

vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
1
2
3

代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n=word1.size();
        int m=word2.size();
        
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        
        for(int i=0;i<=n;i++)
        {
            dp[i][0]=i;
        }

        for(int i=0;i<=m;i++)
        {
            dp[0][i]=i;
        }
        dp[0][0]=0;
        for(int i =1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(word1[i-1]==word2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1];
                }
                else
                {
                    //dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+2));
                    dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
                }
            }
        }
        return dp[n][m];
    }
};
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

收获

观察题目确定设立的dp数组的含义，然后推导状态转移公式，然后确定初始化情况和遍历顺序，基本上就能完成题目了，最后一定要举例推导。