Leetcode求职题目（21）
1.戳气球
方法一：
class Solution {
public int[][] rec; // 记忆化数组，记录子问题的结果
public int[] val; // 扩展后的数组，前后各加一个1
public int maxCoins(int[] nums) {
int n = nums.length;
val = new int[n + 2]; // 扩展数组，前后各加一个1
for (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) {
// 如果区间内没有气球，返回0
if (left >= right - 1) {
return 0;
}
// 如果已经计算过，直接返回结果
if (rec[left][right] != -1) {
return rec[left][right];
}
// 枚举最后一个被戳破的气球 k
for (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，那么问题可以分解为：-
戳破区间
(left, k)内的气球。 -
戳破区间
(k, right)内的气球。 -
戳破气球
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) {
// 创建新数组，首尾添加1
int 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;
}
}