MySQL面试题

## 198. 打家劫舍

#动态规划

[198. 打家劫舍 - 力扣（LeetCode）](https://leetcode.cn/problems/house-robber/description/)

**思路分析**
- 题目要求不能连着偷，那么在递归中可以考虑各种路线中，在当前 i 位置时是去前-1个值更好，还是取前-2个值加当前 i 值更好
- 写出状态转移方程
$$
dfs[i] = max(dfs(i-1), dfs(i-2) + nums[i])
$$
我们可以将选的过程画成一颗二叉树，如下，其中0-4表示的是 i 的值，选与不选表示的是是否选择4这个节点
![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/5279e71cf972cf1046a573a62548fa39.png)

代码如下
```java
import java.util.*;

class Solution {
    private int[] nums;

    public int rob(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        return dfs(n - 1);
    }

    /**
     * 递归遍历房子
     * 
     * @param i
     * @return
     */
    private int dfs(int i) {
        // 如果i<0表示没有房子可选了，直接返回0
        if (i < 0) {
            return 0;
        }
        // 使用状态转移方程表示获取的最大值
        /*
         * dfs(i-1)表示在当前位置i不选，因为 “如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。”
         * dfs(i - 2) + nums[i] 表示在当前位置i选
         * 使用max则可选出这两种操作哪种得到的值最大
         */
        int res = Math.max(dfs(i - 1), dfs(i - 2) + this.nums[i]);
        return res;
    }
}
```

显然，答案**超时**了，我们需要优化代码，我们注意到搜索树，它有一些重复的地方，我们可以进行**剪枝**操作

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/ac20489dc0542d4b7090951cef908ead.png)

**优化一**
- 我们使用一个 memo 数组记录每次计算的值，然后在递归中判断是否进行过计算，如果 memo 数组中有值，则直接返回

```java
import java.util.*;

class Solution {
    private int[] nums;
    private int[] memo;

    public int rob(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        this.memo = new int[n];
        Arrays.fill(this.memo, -1);
        return dfs(n - 1);
    }

    /**
     * 递归遍历房子
     * 
     * @param i
     * @return
     */
    private int dfs(int i) {
        // 如果i<0表示没有房子可选了，直接返回0
        if (i < 0) {
            return 0;
        }
        // 如果当前值计算过了，那么直接返回
        if (this.memo[i] != -1) {
            return this.memo[i];
        }
        // 使用状态转移方程表示获取的最大值
        /*
         * dfs(i-1)表示在当前位置i不选，因为 “如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。”
         * dfs(i - 2) + nums[i] 表示在当前位置i选
         * 使用max则可选出这两种操作哪种得到的值最大
         */
        int res = Math.max(dfs(i - 1), dfs(i - 2) + this.nums[i]);
        this.memo[i] = res;
        return res;
    }
}
```

这样算法的复杂度就优化到了 $O(n)$

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/e0b7689c5e7f93119bdf55c7d8d3c527.png)

**优化二**
- 对于剪枝后的搜索树，我们还可以将其转为递推的方式
- 由于我们知道每个数它的前一个数应该是多少，因此我们可以直接从0开始计算

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/eb7064028fd27f33f2e096386d02e67e.png)

代码如下
```java
import java.util.*;

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 2];
        for (int i = 0; i < n; i++) {
            f[i + 2] = Math.max(f[i + 1], f[i] + nums[i]);
        }
        return f[n - 1 + 2];
    }
}
```

此时的时间复杂度是 $O(n)$，空间复杂度也是 $O(n)$

**优化三**
- 对于 f 数组，我们知道 $当前=max(上一个+上上一个+nums[i])$
- 于是我们可以将 f 数组改成三个变量即可
$$
newF = max(f_{1}, f_{0}+nums[i])
$$
计算完后更新 $f_{1}$ 和 $f_{0}$ 即可
$$
\begin{align}
f_{0}&=f_{1} \\
f_{1}&=newF
\end{align}
$$
代码如下

```java
import java.util.*;

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int f0 = 0, f1 = 0, newF = 0;
        for (int i = 0; i < n; i++) {
            newF = Math.max(f1, f0 + nums[i]);
            f0 = f1;
            f1 = newF;
        }
        return newF;
    }
}
```

这时的事件复杂度是 $O(n)$，空间复杂度就是 $O(1)$ 了

## 494. 目标和

#动态规划 #0-1背包问题

[494. 目标和 - 力扣（LeetCode）](https://leetcode.cn/problems/target-sum/description/)

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/526ae1931f51f3876fb6daf16802e6a4.png)

得到 `0-1背包` 代码

```java
class Solution {
    private int[] w;
    private int[] v;
    private int[] memo;

    /**
     * 背包问题
     * 
     * @param capacity 背包容量
     * @param w        n个物品的体积
     * @param v        n个物品的价值
     * @return 所选物品在不超过capacity的情况下的最大价值
     */
    private int zeroOneKnapsack(int capacity, int[] w, int[] v) {
        int n = w.length;
        this.w = w;
        this.v = v;
        this.memo = new int[n];
        Arrays.fill(this.memo, -1);
        return dfs(n - 1, capacity);
    }

    /**
     * 遍历
     * 
     * @param i 第i个元素
     * @param c 背包容量
     * @return
     */
    private int dfs(int i, int c) {
        if (i < 0) {
            return 0;
        }
        if (this.memo[i] != -1) {
            return this.memo[i];
        }
        if (c < this.w[i]) {
            return dfs(i - 1, c);
        }
        // 选(dfs(i - 1, c - this.w[i]) + this.v[i])或者不选(dfs(i - 1, c))
        int res = Math.max(dfs(i - 1, c), dfs(i - 1, c - this.w[i]) + this.v[i]);
        this.memo[i] = res;
        return res;
    }
}
```

**目标和思路分析**
- 设 $p$ 为所有+号的数之和，那么 $(s-p)$ 就是所有-号的数之和
- 可得

$$
\begin{align}
p-(s-p)&=target \\
2p&=target+s \\
p&=\frac{target+s}{2}
\end{align}
$$
- 变成了规定 target 求 p 的动态规划
代码
```java
import java.util.*;

class Solution {
    private int[] nums;
    private int[][] memo;

    public int findTargetSumWays(int[] nums, int target) {
        // p: nums中的+数
        // ng: s-p nums中的-数 注意，这里不是负数，而是不带-的数的和
        // 可得 p-(s-p)=target
        // 2p=target+s
        // p=(target+s)/2 我们需要求p，计算哪些条件下p是可以满足的
        // (target+s)为偶数 且不为负数(为什么要判断是否为负数，因为target可能为负数，而sum+target可能小于0，则不可能取得结果)
        this.nums = nums;
        target += Arrays.stream(nums).sum();
        if (target < 0 || (target % 2 == 1)) {
            return 0;
        }
        // 除以2去计算p
        target /= 2;

        // 01背包
        int n = nums.length;
        this.memo = new int[n][target + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(this.memo[i], -1);
        }
        return dfs(n - 1, target);
    }

    /**
     * 遍历
     * 
     * @param i 第i个元素
     * @param c 背包容量
     * @return
     */
    private int dfs(int i, int c) {
        if (i < 0) {
            // c == 0表示这些数加起来等于target
            if (c == 0) {
                return 1; // 表示这组合可以 返回1
            }
            // c != 0 表示这些数加起来不等于target
            if (c != 0) {
                return 0; // 表示这组合不行 返回0
            }
        }
        if (this.memo[i][c] != -1) {
            return this.memo[i][c];
        }
        if (c < this.nums[i]) {
            return dfs(i - 1, c);
        }
        // 这里计算了
        int res = dfs(i - 1, c) + dfs(i - 1, c - this.nums[i]);
        this.memo[i][c] = res;
        return res;
    }
}
```

2024-4-27 力扣刷题记录

## 209. 长度最小的子数组

#同向双指针 #滑动窗口 

[209. 长度最小的子数组 - 力扣（LeetCode）](https://leetcode.cn/problems/minimum-size-subarray-sum/description/)


```java
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int ans = n + 1; // 用于比较min值，所以需要是n+1
        int s = 0; // 用于计算从left到right的数组和
        int l = 0; // 左指针
        for (int r = 0; r < n; r++) {
            int x = nums[r];
            s += x;
            // 如果num[r]是大于target的，将左指针右移缩小范围
            while (s >= target) {
                // 更新答案
                ans = Math.min(ans, r - l + 1);// r-l+1 计算的是子数组的长度，需要加1
                s -= nums[l]; // 减去左边的值
                l++; // 移动指针
            }
        }
        // 如果循环结束后ans还是等于n+1则相当于没有答案返回0
        if (ans == n + 1) {
            return 0;
        } else {
            return ans;
        }
    }
}
```

**复杂度分析**
- 时间复杂度：$O(n)$，对于本题，虽然有两层循环，但是 $l$ 至多可以加 $n$ 次，而不是一般双层循环的可以加 $n^2$ 次，所以是 $O(n)$
- 空间复杂度：$O(1)$，没有使用额外变量数组之类的，故为 $O(1)$

## 713. 乘积小于 K 的子数组

#同向双指针 #滑动窗口 

[713. 乘积小于 K 的子数组 - 力扣（LeetCode）](https://leetcode.cn/problems/subarray-product-less-than-k/description/)

```java
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // 判断k是否小于1
        if (k <= 1) {
            return 0;
        }
        int n = nums.length;
        int ans = 0;
        float prod = 1; // 用于计算从left到right的数组和
        int l = 0; // 左指针
        for (int r = 0; r < n; r++) {
            int x = nums[r];
            prod *= x;
            // 如果num[r]是大于target的，将左指针右移缩小范围
            while (prod >= k) {
                // 更新答案
                prod /= nums[l]; // 减去左边的值
                l++; // 移动指针
            }
            ans += r - l + 1;
        }
        return ans;
    }
}
```

**复杂度分析**
- 时间复杂度: $O(n)$
- 空间复杂度：$O(1)$


## 3. 无重复字符的最长子串

#同向双指针 #滑动窗口

[3. 无重复字符的最长子串 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/)

```java
import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        int n = s.length();
        Map<String, Integer> cnt = new HashMap<>();
        int l = 0;
        for (int r = 0; r < n; r++) {
            String rKey = String.valueOf(s.charAt(r));
            cnt.put(rKey, cnt.getOrDefault(rKey, 0) + 1); // 遍历过一个字符，则在哈希表中记录下来
            // ==2说明遇到相同的字符了
            while (cnt.get(rKey) == 2) {
                String lKey = String.valueOf(s.charAt(l));
                cnt.put(lKey, cnt.getOrDefault(lKey, 0) - 1); // 让其左端点减1
                l++;
            }
            ans = Math.max(ans, r - l + 1); // 统计碰到的最大子串长度
        }
        return ans;
    }
}
```

使用 Java 包装类 HashMap 实现性能不是最优，可考虑 ASCII 字符只有128个，构建一个128字符数组记录字符出现字符即可

```java
import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        int n = s.length();
        int[] lastIndex = new int[128]; // 存储ASCII字符(128)个，数组的每个值表示字符出现次数
        Arrays.fill(lastIndex, -1); // 初始化数组的每个值都为-1
        int l = 0;
        for (int r = 0; r < n; r++) {
            char c = s.charAt(r);
            l = Math.max(l, lastIndex[c] + 1); // 移动到该字符出现次数的下一个位置
            ans = Math.max(ans, r - l + 1); // 这样就得到了一段无重复字符的字符串 r-l+1是字符串的长度
            lastIndex[c] = r; // 记录字符位置
        }
        return ans;
    }
}
```

这样耗时和内存占用就更小了

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/7c2be47c65068a833aabec7d5f0b6908.png)

**复杂度分析**
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$，字符总共只能出现128个，所以并不是 n，而 cnt 就不会是 n 的复杂度



## 2958. 最多 K 个重复元素的最长子数组

#同向双指针 #滑动窗口 

[2958. 最多 K 个重复元素的最长子数组 - 力扣（LeetCode）](https://leetcode.cn/problems/length-of-longest-subarray-with-at-most-k-frequency/description/)

```java
import java.util.*;

class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        int l = 0;
        // 创建一个数组，记录数字的出现次数
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int r = 0; r < n; r++) {
            int x = nums[r];
            // 遍历数字一次，将其加1
            cnt.merge(x, 1, Integer::sum);
            while (cnt.get(x) > k) {
                int y = nums[l];
                cnt.merge(y, -1, Integer::sum);
                l++;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}
```

**复杂度分析**
- 时间复杂度：$O(n)$，同向双指针的共同点
- 空间复杂度：$O(n)$，使用了一个 HashMap 存储数字出现次数

## 2730. 找到最长的半重复子字符串

#相向双指针 #滑动窗口 

[2730. 找到最长的半重复子字符串 - 力扣（LeetCode）](https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring/description/)

```java
class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        // 转换为字符数组
        char[] ch = s.toCharArray();
        int n = s.length();
        int ans = 1;
        int l = 0;
        int same = 0;
        for (int r = 1; r < n; r++) {
            // 需要比较与前一个数是否相同
            if (ch[r] == ch[r - 1]) {
                same++;
            }
            // 表示出现了两次
            if (same > 1) {
                l++;
                while (ch[l] != ch[l - 1]) {
                    l++;
                }
                same = 1;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}
```

**复杂度分析**
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$，使用了 ch 存储将字符串 s 转换为字符数组的变量，直接使用 String 的 charAt 即可减少空间复杂度

2024-4-25 力扣刷题记录

Redis面试题

2024-4-24 力扣刷题记录

首页

分类

时间线

友链

关于我

我的项目