leetcode刷题记录22（2023-09-11）【两数相除(二分、翻倍的思想) | 有效的数独(遍历) | 通配符匹配(动态规划、贪心) | 加一(进位、模拟)】

小鱼儿 2024-03-03 07:01 6阅读 0赞

## 29. 两数相除 ##

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的 商 。

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是  \[ − 2 31 , 2 31 − 1 \] \[−2^\{31\}, 2^\{31\} − 1\] \[−231,231−1\] 。本题中，如果商 严格大于  2 31 − 1 2^\{31\} − 1 231−1 ，则返回  2 31 − 1 2^\{31\} − 1 231−1 ；如果商 严格小于  − 2 31 -2^\{31\} −231 ，则返回  − 2 31 -2^\{31\} −231 。

示例 1:

输入: dividend = 10, divisor = 3  
输出: 3  
解释: 10/3 = 3.33333… ，向零截断后得到 3 。

示例 2:

输入: dividend = 7, divisor = -3  
输出: -2  
解释: 7/-3 = -2.33333… ，向零截断后得到 -2 。

提示：

− 2 31 < = d i v i d e n d , d i v i s o r < = 2 31 − 1 -2^\{31\} <= dividend, divisor <= 2^\{31\} - 1 −231<=dividend,divisor<=231−1  
 d i v i s o r ! = 0 divisor != 0 divisor!=0

除数的本质就是减法，但是，我们不能每次都减去 divisor，会超时，需要利用二分的思想，将 divisor 不断地增大。

#include <vector>
    #include <climits>
    #include <iostream>
    using namespace std;
    
    class Solution
    {
        
    public:
        int divide(int dividend, int divisor)
        {
        
            if (dividend == INT_MIN)
            {
        
                if (divisor == 1)
                    return INT_MIN;
                if (divisor == -1)
                    return INT_MAX;
            }
            if (divisor == INT_MIN)
            {
        
                return dividend == INT_MIN ? 1 : 0;
            }
    
            if (dividend == 0)
                return 0;
    
            bool rev = false;
            if (dividend > 0)
            {
        
                dividend = -dividend;
                rev = !rev;
            }
            if (divisor > 0)
            {
        
                divisor = -divisor;
                rev = !rev;
            }
    
            vector<int> candidates = {
        divisor};
            while (candidates.back() >= dividend - candidates.back())
            {
        
                // 主要通过翻倍的操作来降低复杂度
                candidates.push_back(candidates.back() + candidates.back());
            }
            int res = 0;
            for (int i = candidates.size() - 1; i >= 0; i--)
            {
        
                if (candidates[i] >= dividend)
                {
        
                    res += (1 << i);
                    dividend -= candidates[i];
                }
            }
            return rev ? -res : res;
        }
    };
    
    int main()
    {
        
        Solution sol;
        int res = sol.divide(5, 2);
        cout<<res;
        return 0;
    }

## 36. 有效的数独 ##

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。  
数字 1-9 在每一列只能出现一次。  
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。  
只需要根据以上规则，验证已经填入的数字是否有效即可。  
空白格用 ‘.’ 表示。

示例 1：

![在这里插入图片描述][0d5c792255fa47e5ae424353f8286fea.png]

输入：board =  
\[\[“5”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”\]  
,\[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”\]  
,\[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”\]  
,\[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”\]  
,\[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”\]  
,\[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”\]  
,\[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”\]  
,\[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”\]  
,\[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”\]\]  
输出：true

示例 2：

输入：board =  
\[\[“8”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”\]  
,\[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”\]  
,\[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”\]  
,\[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”\]  
,\[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”\]  
,\[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”\]  
,\[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”\]  
,\[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”\]  
,\[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”\]\]  
输出：false  
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

board.length == 9  
board\[i\].length == 9  
board\[i\]\[j\] 是一位数字（1-9）或者 ‘.’

三次遍历，第一次是判断每一行，第二次是判断每一列，第三次是判断每一个box。

#include <vector>
    #include <iostream>
    
    using namespace std;
    
    class Solution
    {
        
    public:
        bool isValidSudoku(vector<vector<char>> &board)
        {
        
            for (int i = 0; i < 9; i++)
            {
        
                vector<bool> vec(9);
                for (int j = 0; j < 9; j++)
                {
        
                    if (board[i][j] == '.')
                        continue;
                    else if (vec[board[i][j] - '0' - 1] == true)
                    {
        
                        return false;
                    }
                    else
                    {
        
                        vec[board[i][j] - '0' - 1] = true;
                    }
                }
            }
    
            for (int j = 0; j < 9; j++)
            {
        
                vector<bool> vec(9);
                for (int i = 0; i < 9; i++)
                {
        
                    if (board[i][j] == '.')
                        continue;
                    else if (vec[board[i][j] - '0' - 1] == true)
                    {
        
                        return false;
                    }
                    else
                    {
        
                        vec[board[i][j] - '0' - 1] = true;
                    }
                }
            }
    
            for (int i = 0; i < 3; i++)
            {
        
                for (int j = 0; j < 3; j++)
                {
        
                    vector<bool> vec(9);
                    for (int m = i * 3; m < i * 3 + 3; m++)
                    {
        
                        for (int n = j * 3; n < j * 3 + 3; n++)
                        {
        
                            if (board[m][n] == '.')
                                continue;
                            else if (vec[board[m][n] - '0' - 1] == true)
                            {
        
                                return false;
                            }
                            else
                            {
        
                                vec[board[m][n] - '0' - 1] = true;
                            }
                        }
                    }
                }
            }
    
            return true;
        }
    };
    
    int main()
    {
        
        vector<vector<char>> board = {
        
            {
        '5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {
        '6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {
        '.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {
        '8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {
        '4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {
        '7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {
        '.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {
        '.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {
        '.', '.', '.', '.', '8', '.', '.', '7', '9'}};
    
        Solution sol;
        bool res = sol.isValidSudoku(board);
    
        cout << res;
    }

## 44. 通配符匹配 ##

给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘\*’ 匹配规则的通配符匹配：  
‘?’ 可以匹配任何单个字符。  
‘\*’ 可以匹配任意字符序列（包括空字符序列）。  
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 1：

输入：s = “aa”, p = “a”  
输出：false  
解释：“a” 无法匹配 “aa” 整个字符串。

示例 2：

输入：s = “aa”, p = “\*”  
输出：true  
解释：‘\*’ 可以匹配任意字符串。

示例 3：

输入：s = “cb”, p = “?a”  
输出：false  
解释：‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。

提示：

0 <= s.length, p.length <= 2000  
s 仅由小写英文字母组成  
p 仅由小写英文字母、‘?’ 或 ‘\*’ 组成

参考题解：[https://leetcode.cn/problems/wildcard-matching/][https_leetcode.cn_problems_wildcard-matching]

动态规划：dp\[i\]\[j\]表示，s中的前i个是否和p中的前j个匹配

class Solution
    {
        
    public:
        bool isMatch(string s, string p)
        {
        
            int m = s.size();
            int n = p.size();
            vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
    		
    		// p为空，只有党s也为空的情况才能满足
            dp[0][0] = true;
            // p为空的其它情况全为 false
            // s为空，只有p前几个全为'*'的字符才能满足
            for (int j = 1; j <= n; j++)
            {
        
                if (p[j - 1] == '*')
                {
        
                    dp[0][j] = true;
                }
                else
                {
        
                    break;
                }
            }
    
            for (int i = 1; i <= m; i++)
            {
        
                for (int j = 1; j <= n; j++)
                {
        
                    if (p[j - 1] == '*')
                    {
        
                        dp[i][j] = dp[i][j - 1] | dp[i - 1][j];
                    }
                    else if (p[j - 1] == '?' || s[i - 1] == p[j - 1])
                    {
        
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
    
            return dp[m][n];
        }
    };

贪心：相当于在s中找到所有’\*'划分的p的子串

class Solution
    {
        
        bool charMatch(char u, char v)
        {
        
            return u == v || v == '?';
        }
    
    public:
        bool isMatch(string s, string p)
        {
        
            while (s.size() && p.size() && p.back() != '*')
            {
        
                if (charMatch(s.back(), p.back()))
                {
        
                    s.pop_back();
                    p.pop_back();
                }
                else
                {
        
                    return false;
                }
            }
            if (p.empty())
            {
        
                return s.empty();
            }
            int sIndex = 0, pIndex = 0;
            // 两个字符串 匹配 开始的地方
            int sRecord = -1, pRecord = -1;
            // p 中的所有子串都要在 s 中出现
            while (sIndex < s.size() && pIndex < p.size())
            {
        
                if (p[pIndex] == '*')
                {
        
                    pIndex++;
                    sRecord = sIndex;
                    pRecord = pIndex;
                }
                else if (charMatch(s[sIndex], p[pIndex]))
                {
        
                    sIndex++;
                    pIndex++;
                }
                // 如果出现不匹配，sRecord向后移，然后继续匹配
                else if (sRecord != -1 && sRecord + 1 < s.size())
                {
        
                    sRecord++;
                    sIndex = sRecord;
                    pIndex = pRecord;
                }
                else
                {
        
                    return false;
                }
            }
            for (int i = pIndex; i < p.size(); i++)
            {
        
                if (p[i] != '*')
                {
        
                    return false;
                }
            }
            return true;
        }
    };

## 66. 加一 ##

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = \[1,2,3\]  
输出：\[1,2,4\]  
解释：输入数组表示数字 123。

示例 2：

输入：digits = \[4,3,2,1\]  
输出：\[4,3,2,2\]  
解释：输入数组表示数字 4321。

示例 3：

输入：digits = \[0\]  
输出：\[1\]

提示：

1 <= digits.length <= 100  
0 <= digits\[i\] <= 9

主要采用了模拟的思想，记录每一位 +1 后的进位

#include <vector>
    
    using namespace std;
    
    class Solution
    {
        
    public:
        vector<int> plusOne(vector<int> &digits)
        {
        
            int plus = 1;
            for (auto it = digits.rbegin(); it != digits.rend(); it++)
            {
        
                *it += plus;
                if (*it >= 10)
                {
        
                    plus = 1;
                    *it = *it % 10;
                    if (it == digits.rend() - 1)
                    {
        
                        digits.insert(digits.cbegin(), 0);
                        digits[0] += plus;
                        plus = 0;
                        break;
                    }
                }
                else
                {
        
                    break;
                }
            }
            return digits;
        }
    };

答案的做法，更加简洁：

class Solution
    {
        
    public:
        vector<int> plusOne(vector<int> &digits)
        {
        
            for (int i = digits.size() - 1; i >= 0; i--)
            {
        
                digits[i]++;
                digits[i] = digits[i] % 10;
                if (digits[i] != 0)
                    return digits;
            }
            digits = vector<int>(digits.size() + 1);
            // 999 + 1 必然是 1000，所以只需要考虑第一位
            digits[0] = 1;
            return digits;
        }
    };

[0d5c792255fa47e5ae424353f8286fea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/23e977cc366d4b67b2b01929a510ab51.png
[https_leetcode.cn_problems_wildcard-matching]: https://leetcode.cn/problems/wildcard-matching/