挑战100天 AI In LeetCode Day04（热题+面试经典150题）

柔光的暖阳◎ 2024-02-19 09:22 142阅读 0赞

#### 挑战100天 AI In LeetCode Day04（热题+面试经典150题） ####

*  一、LeetCode介绍
 *  二、LeetCode 热题 HOT 100-6
 *   *  2.1 题目
     *  2.2 题解
 *  三、面试经典 150 题-6
 *   *  3.1 题目
     *  3.2 题解

## 一、LeetCode介绍 ##

![在这里插入图片描述][580331538fd84f08a8132dbc87c1bd8a.png]

LeetCode是一个在线编程网站，提供各种算法和数据结构的题目，面向程序员、计算机科学专业学生和技术爱好者等人群，旨在帮助他们提高算法和编程技能。LeetCode上的问题通常来自各种技术公司的面试题目，因此它也是程序员面试准备的重要资源之一。

LeetCode上的问题涵盖了各种难度级别，从入门级到专家级都有不同难度的题目可供练习。用户可以选择使用不同的编程语言提交答案，LeetCode能够对结果进行评估并返回测试结果。

除了题目外，LeetCode还提供了讨论区、排行榜等社区功能，用户可以在这里交流学习心得、解决疑难问题，并与其他用户比较自己的做题成绩。

**挑战100天 AI In LeetCode**是基于LeetCode题库，借助AI的能力进行解题、并学习其解题过程。

## 二、LeetCode 热题 HOT 100-6 ##

### 2.1 题目 ###

**正则表达式匹配**

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
    
    '.' 匹配任意单个字符
    '*' 匹配零个或多个前面的那一个元素
    所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
    
     
    示例 1：
    
    输入：s = "aa", p = "a"
    输出：false
    解释："a" 无法匹配 "aa" 整个字符串。
    示例 2:
    
    输入：s = "aa", p = "a*"
    输出：true
    解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
    示例 3：
    
    输入：s = "ab", p = ".*"
    输出：true
    解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
     
    
    提示：
    
    1 <= s.length <= 20
    1 <= p.length <= 20
    s 只包含从 a-z 的小写字母。
    p 只包含从 a-z 的小写字母，以及字符 . 和 *。
    保证每次出现字符 * 时，前面都匹配到有效的字符

### 2.2 题解 ###

时间复杂度为 O(mn)，其中 m 和 n 分别为字符串 s 和模式 p 的长度；空间复杂度为 O(mn)，使用了一个二维数组来存储状态。

**解题思路：**

这个题目可以使用动态规划来解决。我们可以定义一个二维数组 dp，其中 dp\[i\]\[j\] 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否能匹配。

接下来，我们来考虑如何更新这个二维数组。对于 dp\[i\]\[j\] 而言，有以下几种情况：

1.  如果 p\[j-1\] 是普通字符（即非’.‘和’\*'），则当前字符必须匹配，即 s\[i-1\] == p\[j-1\]，并且前面的字符也必须匹配，即 dp\[i-1\]\[j-1\] 必须为 true。
2.  如果 p\[j-1\] 是’.'，则当前字符可以匹配任意字符，所以只需要前面的字符匹配，即 dp\[i-1\]\[j-1\] 必须为 true。
3.  如果 p\[j-1\] 是’\*'，则有两种情况：
    
     *  ‘’ 匹配零个前面的字符，即去掉 ‘’ 和它之前的字符，看是否匹配，即 dp\[i\]\[j-2\] 必须为 true。
     *  ‘\*’ 匹配一个或多个前面的字符，即当前字符必须匹配，并且前面的字符串也必须匹配，即 s\[i-1\] == p\[j-2\] 或者 p\[j-2\] 是’.'，并且 dp\[i-1\]\[j\] 必须为 true。

基于以上分析，我们可以得到状态转移方程：

if (p.charAt(j-1) == ‘\*’) \{  
dp\[i\]\[j\] = dp\[i\]\[j-2\] || (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == ‘.’) && dp\[i-1\]\[j\];  
\} else \{  
dp\[i\]\[j\] = (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == ‘.’) && dp\[i-1\]\[j-1\];  
\}

最终的答案就是 dp\[s.length()\]\[p.length()\]。

public boolean isMatch(String s, String p) {
        
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
        
            for (int j = 1; j <= n; j++) {
        
                if (p.charAt(j - 1) == '*') {
        
                    dp[i][j] = dp[i][j - 2] || (i > 0 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') && dp[i - 1][j]);
                } else {
        
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
                }
            }
        }
        return dp[m][n];
    }

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

## 三、面试经典 150 题-6 ##

> 数组 / 字符串

### 3.1 题目 ###

\*\* 轮转数组\*\*

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
    
     
    
    示例 1:
    
    输入: nums = [1,2,3,4,5,6,7], k = 3
    输出: [5,6,7,1,2,3,4]
    解释:
    向右轮转 1 步: [7,1,2,3,4,5,6]
    向右轮转 2 步: [6,7,1,2,3,4,5]
    向右轮转 3 步: [5,6,7,1,2,3,4]
    示例 2:
    
    输入：nums = [-1,-100,3,99], k = 2
    输出：[3,99,-1,-100]
    解释: 
    向右轮转 1 步: [99,-1,-100,3]
    向右轮转 2 步: [3,99,-1,-100]
     
    
    提示：
    
    1 <= nums.length <= 105
    -231 <= nums[i] <= 231 - 1
    0 <= k <= 105
     
    
    进阶：
    
    尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
    你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

### 3.2 题解 ###

空间复杂度为 O(1)。

**解题思路：**

这三种方法分别使用了**额外数组、环状替换和数组反转来实现数组的右移操作**。其中，方法三使用了空间复杂度为 O(1) 的原地算法解决了这个问题。

1.  对于方法一，我们创建了一个额外的数组来存储旋转后的元素，在最后再将其拷贝回原数组中。这种方法的时间复杂度为 O(n)，空间复杂度为 O(n)。
2.  方法二使用了环状替换的思想，通过多次交换元素来实现数组的右移操作，时间复杂度为 O(n)，空间复杂度为 O(1)。
3.  方法三则使用了数组反转的思想，先将整个数组反转，然后分别反转前 k 个元素和后 n-k 个元素，从而实现数组的右移操作。该方法的时间复杂度为 O(n)，空间复杂度为 O(1)。

**方法一：使用额外数组**

public void rotate(int[] nums, int k) {
        
        int n = nums.length;
        int[] temp = new int[n];
        for (int i = 0; i < n; i++) {
        
            temp[(i + k) % n] = nums[i];
        }
        System.arraycopy(temp, 0, nums, 0, n);
    }

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

**方法二：使用环状替换**

public void rotate(int[] nums, int k) {
        
        int n = nums.length;
        k = k % n;
        int count = 0;
        for (int start = 0; count < n; start++) {
        
            int current = start;
            int prev = nums[start];
            do {
        
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }
    }

![在这里插入图片描述][75199236cabd42d59ad3954d1f19b85d.png]

**方法三：使用反转数组**

public void rotate(int[] nums, int k) {
        
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    
    private void reverse(int[] nums, int start, int end) {
        
        while (start < end) {
        
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

![在这里插入图片描述][7f1b574db87f4686a5db526b466a18ae.png]

**至此，挑战100天 AI In LeetCode Day04（热题+面试经典150题）完成，后续会持续调整；查阅过程中若遇到问题欢迎留言或私信交流。**

[580331538fd84f08a8132dbc87c1bd8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/87f547a0a75f40f4b6f9f1d117ed2b5c.png
[a8b2c0cc1c2b46c786dba385e1cce95a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/3f7bead1d4a7422783293f8bf7adc136.png
[d6a6074ad7bd4fa19efa6333144dd22f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/13721b49cc4e45f5bd70d145c26b0372.png
[75199236cabd42d59ad3954d1f19b85d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/2035ed43bee147a083ccf47feec3955d.png
[7f1b574db87f4686a5db526b466a18ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/5c9eff6dcb6342f59a08acd607533a21.png