力扣热门算法题 349. 两个数组的交集，387. 字符串中的第一个唯一字符，394. 字符串解码

349. 两个数组的交集，387. 字符串中的第一个唯一字符，394. 字符串解码，每题做详细思路梳理，配套Python&Java双语代码， 2024.04.02 可通过leetcode所有测试用例。

目录

349. 两个数组的交集

解题思路

完整代码

Python

Java

387. 字符串中的第一个唯一字符

解题思路

完整代码

Python

Java

394. 字符串解码

解题思路

完整代码

Python

Java

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 <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

解题思路

1. 使用两个哈希集合：一个集合 set1 存储 nums1 中的元素，另一个集合 set2 用来存储 nums2 中的元素。

2. 填充第一个集合：遍历数组 nums1，将其中的元素加入 set1。哈希集合会自动处理重复元素，确保 set1 中的元素唯一。

3. 查找交集：遍历数组 nums2，检查每个元素是否已存在于 set1 中。如果存在，说明该元素是两个数组的交集的一部分，将其加入 set2。这样做的原因是 set2 此时用于存储交集结果，也能自动去重。

4. 转换结果：最后，将 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

解题思路

1. 统计字符频率：遍历字符串 s 一次，使用哈希表（如 Python 中的字典或 Java 中的 HashMap）来统计每个字符出现的次数。

2. 找到第一个不重复字符：再次遍历字符串 s，使用之前构建的哈希表来检查每个字符的频率。第一个频率为 1 的字符就是我们要找的第一个不重复字符，此时返回它的索引。

3. 处理未找到的情况：如果遍历结束仍未找到频率为 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 -1

Java

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"

解题思路

1. 创建两个栈：一个用于保存数字（即重复次数），另一个用于保存字符串。

2. 遍历输入字符串：对每个字符进行处理：

   • 如果遇到数字，解析整个数字（因为数字可能超过一位），并将其压入数字栈。
   • 如果遇到字母，将其添加到当前字符串中。
   • 如果遇到'['，表示一个新的编码字符串的开始，因此需要将当前字符串压入字符串栈，然后重置当前字符串。
   • 如果遇到']'，表示一个编码字符串的结束，此时应从数字栈中弹出一个数字，表示重复次数，并从字符串栈中弹出字符串（如果有的话），将当前字符串重复指定次数后，与弹出的字符串连接起来，更新当前字符串。

3. 返回解码后的字符串：遍历完成后，当前字符串即为解码后的字符串。

完整代码

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 currentStr

Java

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;
    }
}