Leetcode求职题目（21）

1.戳气球

方法一：

class Solution {public int[][] rec; // 记忆化数组，记录子问题的结果public int[] val;   // 扩展后的数组，前后各加一个1public int maxCoins(int[] nums) {int n = nums.length;val = new int[n + 2]; // 扩展数组，前后各加一个1for (int i = 1; i <= n; i++) {val[i] = nums[i - 1]; // 复制原始数组}val[0] = val[n + 1] = 1; // 边界值设为1// 初始化记忆化数组，-1表示未计算过rec = new int[n + 2][n + 2];for (int i = 0; i <= n + 1; i++) {Arrays.fill(rec[i], -1);}// 调用递归函数，计算区间 (0, n+1) 的最大硬币数return solve(0, n + 1);}// 递归函数，计算区间 (left, right) 的最大硬币数public int solve(int left, int right) {// 如果区间内没有气球，返回0if (left >= right - 1) {return 0;}// 如果已经计算过，直接返回结果if (rec[left][right] != -1) {return rec[left][right];}// 枚举最后一个被戳破的气球 kfor (int i = left + 1; i < right; i++) {// 计算戳破气球 i 的硬币数int sum = val[left] * val[i] * val[right];// 递归计算左右两个区间的最大硬币数sum += solve(left, i) + solve(i, right);// 更新当前区间的最大硬币数rec[left][right] = Math.max(rec[left][right], sum);}// 返回当前区间的最大硬币数return rec[left][right];}
}

解题思路

分治法

将问题分解为子问题：假设最后一个被戳破的气球是 k，那么问题可以分解为：
1. 戳破区间 (left, k) 内的气球。
2. 戳破区间 (k, right) 内的气球。
3. 戳破气球 k。
通过递归解决子问题，最终合并结果。

记忆化搜索

使用一个二维数组 rec 记录已经计算过的子问题的结果，避免重复计算。

代码流程

初始化

创建一个新数组 val，在原始数组前后各添加一个 1，方便处理边界条件。
初始化记忆化数组 rec，所有值设为 -1，表示未计算过。

递归函数 `solve`

参数：left 和 right 表示当前区间的左右边界。

终止条件：如果区间内没有气球（left >= right - 1），返回 0。

记忆化检查：如果 rec[left][right] 已经计算过，直接返回结果。

枚举最后一个戳破的气球：

遍历区间 (left + 1, right - 1)，假设最后一个戳破的气球是 i。

计算戳破气球 i 的硬币数：val[left] * val[i] * val[right]。

递归计算左右两个区间的最大硬币数：solve(left, i) 和 solve(i, right)。

更新当前区间的最大硬币数：rec[left][right] = max(rec[left][right], sum)。

返回结果：返回 rec[left][right]。

另一种方法：

class Solution {public int maxCoins(int[] nums) {// 创建新数组，首尾添加1int n = nums.length;int[] points = new int[n + 2];points[0] = 1;points[n + 1] = 1;for (int i = 0; i < n; i++) {points[i + 1] = nums[i];}// 创建dp数组int[][] dp = new int[n + 2][n + 2];// 开始dp：len表示开区间长度for (int len = 1; len <= n; len++) {// i表示开区间左端点for (int i = 0; i <= n - len; i++) {int j = i + len + 1; // 开区间右端点// k为最后一个被戳破的气球for (int k = i + 1; k < j; k++) {// 状态转移方程dp[i][j] = Math.max(dp[i][j],dp[i][k] + dp[k][j] + points[i] * points[k] * points[j]);}}}// 返回整个区间的最大值return dp[0][n + 1];}
}

解题思路：

2.去除重复字母

这道题是2024年华为面试题

关键策略

贪心选择：尽可能选择更小的字符作为前导
延迟删除：当发现更优选择时，只有确定后续还能找到当前字符时才删除前面的字符

逐步解析

预处理阶段：

使用lastOccurrence数组记录每个字符最后一次出现的索引位置

示例：对于"bcabc"

b最后出现位置：1

c最后出现位置：4

a最后出现位置：2

主处理阶段：

遍历每个字符时进行以下判断：

跳过条件：当前字符已经在结果栈中（保证唯一性）

优化条件（同时满足时执行栈顶弹出）：

当前字符 < 栈顶字符（有机会获得更小字典序）

栈顶字符后续还会出现（删除后有机会重新获取）

栈维护：

始终保证栈中字符保持递增顺序（除非后续没有机会再调整）

每次添加新字符时更新使用标记

class Solution {public String removeDuplicateLetters(String s) {// 记录每个字符最后一次出现的位置int[] lastOccurrence = new int[26];// 标记字符是否已存在于结果栈中boolean[] used = new boolean[26];// 用StringBuilder模拟栈结构StringBuilder stack = new StringBuilder();// Step 1: 预处理每个字符的最后出现位置for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);lastOccurrence[c - 'a'] = i; // 记录字符c的最后位置}// Step 2: 遍历字符串构建结果for (int i = 0; i < s.length(); i++) {char currentChar = s.charAt(i);int charIndex = currentChar - 'a';// 如果当前字符已经在栈中，跳过if (used[charIndex]) continue;// Step 3: 贪心移除可以优化的前导字符while (stack.length() > 0 && currentChar < stack.charAt(stack.length()-1) // 当前字符更小&& lastOccurrence[stack.charAt(stack.length()-1)-'a'] > i) { // 栈顶字符后续还会出现// 移除栈顶字符并更新使用标记char removedChar = stack.charAt(stack.length()-1);used[removedChar - 'a'] = false;stack.deleteCharAt(stack.length()-1);}// Step 4: 将当前字符入栈stack.append(currentChar);used[charIndex] = true;}return stack.toString();}
}

3.最大单词长度乘积

解题思路：

**1. 预处理阶段（时间复杂度 O(n*L)，L为单词平均长度）**

目标：将每个单词的字符存在性快速记录下来
实现：
- 使用 boolean[n][26] 数组，chars[i][k] = true 表示第i个单词包含字符 (char)('a' + k)
- 遍历每个单词的每个字符，填充布尔数组

**计算阶段（时间复杂度 O(n²*26)）**

目标：检查所有单词对，找出无公共字符的最大乘积
实现：
- 双重循环遍历所有单词对 (i, j)（i < j）
- 内层循环检查两单词是否有公共字符：
  - 若存在任意一个字符同时存在于两个单词中，标记为有公共字符
- 若无公共字符，计算两单词长度的乘积，更新最大值

    class Solution {public int maxProduct(String[] words) {int maxProduct = 0;int n = words.length;boolean[][] chars = new boolean[n][26];  // 记录每个单词包含的字符// 预处理所有单词的字符组成for (int i = 0; i < n; i++) {for (char c : words[i].toCharArray()) {chars[i][c - 'a'] = true;}}// 检查每对单词for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {boolean hasCommon = false;// 检查是否有公共字符for (int k = 0; k < 26; k++) {if (chars[i][k] && chars[j][k]) {hasCommon = true;break;}}if (!hasCommon) {maxProduct = Math.max(maxProduct, words[i].length() * words[j].length());}}}return maxProduct;}}