349. 两个数组的交集，387. 字符串中的第一个唯一字符，394. 字符串解码，每题做详细思路梳理，配套Python&Java双语代码， 2024.04.02 可通过leetcode所有测试用例。
目录
349. 两个数组的交集
给定两个数组
nums1和nums2，返回 它们的交集
。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
解题思路
-
使用两个哈希集合：一个集合
set1存储nums1中的元素，另一个集合set2用来存储nums2中的元素。 -
填充第一个集合：遍历数组
nums1，将其中的元素加入set1。哈希集合会自动处理重复元素，确保set1中的元素唯一。 -
查找交集：遍历数组
nums2，检查每个元素是否已存在于set1中。如果存在，说明该元素是两个数组的交集的一部分，将其加入set2。这样做的原因是set2此时用于存储交集结果，也能自动去重。 -
转换结果：最后，将
set2中的元素转换成数组形式返回，这些元素就是两个数组的交集。
完整代码
Python
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
set1 = set(nums1)
set2 = set()
for num in nums2:
if num in set1:
set2.add(num)
return list(set2)Java
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
Set<Integer> resultSet = new HashSet<>();
// 填充第一个集合
for (int num : nums1) {
set1.add(num);
}
// 查找交集
for (int num : nums2) {
if (set1.contains(num)) {
resultSet.add(num);
}
}
// 转换结果
int[] result = new int[resultSet.size()];
int i = 0;
for (int num : resultSet) {
result[i++] = num;
}
return result;
}
}
387. 字符串中的第一个唯一字符
给定一个字符串
s，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回-1。示例 1：
输入: s = "leetcode" 输出: 0示例 2:
输入: s = "loveleetcode" 输出: 2示例 3:
输入: s = "aabb" 输出: -1
解题思路
-
统计字符频率：遍历字符串
s一次，使用哈希表（如 Python 中的字典或 Java 中的 HashMap）来统计每个字符出现的次数。 -
找到第一个不重复字符：再次遍历字符串
s，使用之前构建的哈希表来检查每个字符的频率。第一个频率为 1 的字符就是我们要找的第一个不重复字符，此时返回它的索引。 -
处理未找到的情况：如果遍历结束仍未找到频率为 1 的字符，则说明没有不重复的字符，返回 -1。
完整代码
Python
class Solution:
def firstUniqChar(self, s: str) -> int:
# 使用哈希表统计每个字符的频率
charCount = {}
for char in s:
charCount[char] = charCount.get(char, 0) + 1
# 查找第一个不重复的字符
for i, char in enumerate(s):
if charCount[char] == 1:
return i
# 如果没有不重复的字符，返回-1
return -1Java
class Solution {
public int firstUniqChar(String s) {
// 使用哈希表统计每个字符的频率
HashMap<Character, Integer> charCount = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}
// 查找第一个不重复的字符
for (int i = 0; i < s.length(); i++) {
if (charCount.get(s.charAt(i)) == 1) {
return i;
}
}
// 如果没有不重复的字符，返回-1
return -1;
}
}394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为:
k[encoded_string]，表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数
k，例如不会出现像3a或2[4]的输入。示例 1：
输入：s = "3[a]2[bc]" 输出："aaabcbc"示例 2：
输入：s = "3[a2[c]]" 输出："accaccacc"示例 3：
输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef"示例 4：
输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz"
解题思路
-
创建两个栈：一个用于保存数字（即重复次数），另一个用于保存字符串。
-
遍历输入字符串：对每个字符进行处理：
- 如果遇到数字，解析整个数字（因为数字可能超过一位），并将其压入数字栈。
- 如果遇到字母，将其添加到当前字符串中。
- 如果遇到
'['，表示一个新的编码字符串的开始，因此需要将当前字符串压入字符串栈，然后重置当前字符串。 - 如果遇到
']'，表示一个编码字符串的结束，此时应从数字栈中弹出一个数字，表示重复次数，并从字符串栈中弹出字符串（如果有的话），将当前字符串重复指定次数后，与弹出的字符串连接起来，更新当前字符串。
-
返回解码后的字符串：遍历完成后，当前字符串即为解码后的字符串。
完整代码
Python
class Solution:
def decodeString(self, s: str) -> str:
numStack = [] # 存储重复次数
strStack = [] # 存储字符串
currentNum = 0
currentStr = ''
for char in s:
if char.isdigit():
currentNum = currentNum * 10 + int(char) # 构建多位数
elif char == '[':
# 遇到 '['，将当前数字和字符串分别压栈，然后重置
numStack.append(currentNum)
strStack.append(currentStr)
currentNum, currentStr = 0, ''
elif char == ']':
# 遇到 ']'，弹出栈顶数字，重复当前字符串，并与栈顶字符串连接
num = numStack.pop()
prevStr = strStack.pop()
currentStr = prevStr + num * currentStr
else:
currentStr += char # 构建字符串
return currentStrJava
class Solution {
public String decodeString(String s) {
Stack<Integer> numStack = new Stack<>();
Stack<String> strStack = new Stack<>();
String currentStr = "";
int currentNum = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
currentNum = currentNum * 10 + (ch - '0');
} else if (ch == '[') {
// 遇到 '['，将当前数字和字符串分别压栈，然后重置
numStack.push(currentNum);
strStack.push(currentStr);
currentNum = 0;
currentStr = "";
} else if (ch == ']') {
// 遇到 ']'，弹出栈顶数字，重复当前字符串，并与栈顶字符串连接
StringBuilder tempStr = new StringBuilder(strStack.pop());
int repeatTimes = numStack.pop();
for (int i = 0; i < repeatTimes; i++) {
tempStr.append(currentStr);
}
currentStr = tempStr.toString();
} else {
currentStr += ch;
}
}
return currentStr;
}
}