LeetCode-Day41

172. 阶乘后的零

给定一个整数 n，返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

思路：能产生0的情况只有5 * 2 = 10，其他情况分解后也是这个，2的数目要远多于5，所以问题就转变为求5的个数

比如25! = 1 * 2 * 3 * ... * 24 * 25

• 去掉无法产生0的，5 * 10 * 15 * 20 * 25
• 再分解，1*5 * 2*5 * 3*5 * 4*5 * 5*5
• 那些5的倍数的都能构造出2*5，而25有两层5
• 所以只要n /= 5就能得到第一层的5的个数，剩下1 * 2 * 3 * 4 * 5
• 上面的结果再除以5就是下一层的5的个数
• 最终5 + 1 = 6

class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        while(n >= 5) {
            n /= 5;
            ans += n;
        }    
        return ans;     
    }
};

179. 最大数

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210
示例 2:

输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

思路：

其实想了好久才突然明白一件事情…

就是在作为排序条件的时候，如何判断a > b

一开始一直在想长度不相等的话怎么办，后来才发现自己的判断依据其实一直是a + b 是否大于 b + a(这里的相加指的是字符串的相加)

所以判断依据就是上面这个，然后排个序穿起来就行了，但是要注意全零的情况，此时只需要返回0

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        if(nums.size() == 0) {
            return "0";
        }
        int index = 0;
        while(index < nums.size()) {
            if(nums[index] != 0) {
                break;
            }
            index++;
        }
        if(index == nums.size()) {
            return "0";
        }
        sort(nums.begin(), nums.end(), [](int& a, int& b) {
            string stra = to_string(a), strb = to_string(b);
            string str1 = stra + strb, str2 = strb + stra;
            return str1 > str2;  
        });
        string res = "";
        for(int num : nums) {
            res += to_string(num);
        }
        return res;
    }
};

130. 被围绕的区域

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例:

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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

思路：这个问题很容易就能想到DFS，所以照着思路写代码就可以了

简单总结dfs和bfs：

• bfs:递归。可以想象二叉树中如何递归进行层序遍历
• bfs:非递归，一般用队列存储
• dfs:递归，最常用，如二叉树的先序遍历
• dfs:非递归，一般用stack

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.size() == 0) {
            return ;
        }
        int m = board.size(), n = board[0].size();
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                // 从边缘第一个是O开始搜索
                bool isEdge = (i == 0 || i == m - 1 || j == 0 || j == n - 1);
                if(isEdge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                if(board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if(board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    void dfs(vector<vector<char>>& board, int i,int j) {
        int m = board.size(), n = board[0].size();
        stack<pair<int, int>> st;
        st.push({i, j});
        board[i][j] = '#';
        while(!st.empty()) {
            pair<int, int> current = st.top();
            if(current.first >= 1 && board[current.first - 1][current.second] == 'O') {
                st.push({current.first - 1, current.second});
                board[current.first - 1][current.second] = '#';
                continue;
            } 
            if(current.first + 1 < m && board[current.first + 1][current.second] == 'O') {
                st.push({current.first + 1, current.second});
                board[current.first + 1][current.second] = '#';
                continue;
            } 
            if(current.second >= 1 && board[current.first][current.second - 1] == 'O') {
                st.push({current.first, current.second - 1});
                board[current.first][current.second - 1] = '#';
                continue;
            } 
            if(current.second + 1 < n && board[current.first][current.second + 1] == 'O') {
                st.push({current.first, current.second + 1});
                board[current.first][current.second + 1] = '#';
                continue;
            } 
            st.pop();
        }
    }
};

200. 岛屿数量

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000
输出: 1

示例 2:

输入:
11000
11000
00100
00011
输出: 3

思路：与上一题很类似

class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
    if(grid.size() == 0) {
        return 0;
    }
    int m = grid.size(), n = grid[0].size();
    int sum = 0;
    for(int i = 0;i < m;i++) {
        for(int j = 0;j < n;j++) {
            if(grid[i][j] == '1') {
                DFS(grid, i, j);
                sum += 1;
            }
        }
    }
    return sum;
}

void DFS(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    stack<pair<int, int>> st;
    st.push({i, j});
    grid[i][j] = '#';
    while(!st.empty()) {
        pair<int, int> current = st.top();
        if(current.first >= 1 && grid[current.first - 1][current.second] == '1') {
            st.push({current.first - 1, current.second});
            grid[current.first - 1][current.second] = '#';
            continue;
        }
        if(current.first + 1 < m && grid[current.first + 1][current.second] == '1') {
            st.push({current.first + 1, current.second});
            grid[current.first + 1][current.second] = '#';
            continue;
        }
        if(current.second >= 1 && grid[current.first][current.second - 1] == '1') {
            st.push({current.first, current.second - 1});
            grid[current.first][current.second - 1] = '#';
            continue;
        }
        if(current.second + 1 < n && grid[current.first][current.second + 1] == '1') {
            st.push({current.first, current.second + 1});
            grid[current.first][current.second + 1] = '#';
            continue;
        }
        st.pop();
    }
}
};