349. 兩個(gè)數(shù)組的交集，387. 字符串中的第一個(gè)唯一字符，394. 字符串解碼，每題做詳細(xì)思路梳理，配套Python&Java雙語(yǔ)代碼， 2024.04.02?可通過(guò)leetcode所有測(cè)試用例。
目錄
349. 兩個(gè)數(shù)組的交集
解題思路
完整代碼
Python
Java
387. 字符串中的第一個(gè)唯一字符
解題思路
完整代碼
Python
Java
394. 字符串解碼
解題思路
完整代碼
Python
Java
349. 兩個(gè)數(shù)組的交集
給定兩個(gè)數(shù)組?
nums1?和?nums2?，返回?它們的?交集
?。輸出結(jié)果中的每個(gè)元素一定是? 唯一?的。我們可以? 不考慮輸出結(jié)果的順序?。示例 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] 也是可通過(guò)的提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
解題思路
-
使用兩個(gè)哈希集合：一個(gè)集合
set1存儲(chǔ)nums1中的元素，另一個(gè)集合set2用來(lái)存儲(chǔ)nums2中的元素。 -
填充第一個(gè)集合：遍歷數(shù)組
nums1，將其中的元素加入set1。哈希集合會(huì)自動(dòng)處理重復(fù)元素，確保set1中的元素唯一。 -
查找交集：遍歷數(shù)組
nums2，檢查每個(gè)元素是否已存在于set1中。如果存在，說(shuō)明該元素是兩個(gè)數(shù)組的交集的一部分，將其加入set2。這樣做的原因是set2此時(shí)用于存儲(chǔ)交集結(jié)果，也能自動(dòng)去重。 -
轉(zhuǎn)換結(jié)果：最后，將
set2中的元素轉(zhuǎn)換成數(shù)組形式返回，這些元素就是兩個(gè)數(shù)組的交集。
完整代碼
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<>();
// 填充第一個(gè)集合
for (int num : nums1) {
set1.add(num);
}
// 查找交集
for (int num : nums2) {
if (set1.contains(num)) {
resultSet.add(num);
}
}
// 轉(zhuǎn)換結(jié)果
int[] result = new int[resultSet.size()];
int i = 0;
for (int num : resultSet) {
result[i++] = num;
}
return result;
}
}
387. 字符串中的第一個(gè)唯一字符
給定一個(gè)字符串?
s?，找到?它的第一個(gè)不重復(fù)的字符，并返回它的索引?。如果不存在，則返回?-1?。示例 1：
輸入: s = "leetcode" 輸出: 0示例 2:
輸入: s = "loveleetcode" 輸出: 2示例 3:
輸入: s = "aabb" 輸出: -1
解題思路
-
統(tǒng)計(jì)字符頻率：遍歷字符串
s一次，使用哈希表（如 Python 中的字典或 Java 中的 HashMap）來(lái)統(tǒng)計(jì)每個(gè)字符出現(xiàn)的次數(shù)。 -
找到第一個(gè)不重復(fù)字符：再次遍歷字符串
s，使用之前構(gòu)建的哈希表來(lái)檢查每個(gè)字符的頻率。第一個(gè)頻率為 1 的字符就是我們要找的第一個(gè)不重復(fù)字符，此時(shí)返回它的索引。 -
處理未找到的情況：如果遍歷結(jié)束仍未找到頻率為 1 的字符，則說(shuō)明沒有不重復(fù)的字符，返回 -1。
完整代碼
Python
class Solution:
def firstUniqChar(self, s: str) -> int:
# 使用哈希表統(tǒng)計(jì)每個(gè)字符的頻率
charCount = {}
for char in s:
charCount[char] = charCount.get(char, 0) + 1
# 查找第一個(gè)不重復(fù)的字符
for i, char in enumerate(s):
if charCount[char] == 1:
return i
# 如果沒有不重復(fù)的字符，返回-1
return -1Java
class Solution {
public int firstUniqChar(String s) {
// 使用哈希表統(tǒng)計(jì)每個(gè)字符的頻率
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);
}
// 查找第一個(gè)不重復(fù)的字符
for (int i = 0; i < s.length(); i++) {
if (charCount.get(s.charAt(i)) == 1) {
return i;
}
}
// 如果沒有不重復(fù)的字符，返回-1
return -1;
}
}394. 字符串解碼
給定一個(gè)經(jīng)過(guò)編碼的字符串，返回它解碼后的字符串。
編碼規(guī)則為:?
k[encoded_string]，表示其中方括號(hào)內(nèi)部的?encoded_string?正好重復(fù)?k?次。注意?k?保證為正整數(shù)。你可以認(rèn)為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號(hào)總是符合格式要求的。
此外，你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字，所有的數(shù)字只表示重復(fù)的次數(shù)?
k?，例如不會(huì)出現(xiàn)像?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"
解題思路
-
創(chuàng)建兩個(gè)棧：一個(gè)用于保存數(shù)字（即重復(fù)次數(shù)），另一個(gè)用于保存字符串。
-
遍歷輸入字符串：對(duì)每個(gè)字符進(jìn)行處理：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-844682.html
- 如果遇到數(shù)字，解析整個(gè)數(shù)字（因?yàn)閿?shù)字可能超過(guò)一位），并將其壓入數(shù)字棧。
- 如果遇到字母，將其添加到當(dāng)前字符串中。
- 如果遇到
'['，表示一個(gè)新的編碼字符串的開始，因此需要將當(dāng)前字符串壓入字符串棧，然后重置當(dāng)前字符串。 - 如果遇到
']'，表示一個(gè)編碼字符串的結(jié)束，此時(shí)應(yīng)從數(shù)字棧中彈出一個(gè)數(shù)字，表示重復(fù)次數(shù)，并從字符串棧中彈出字符串（如果有的話），將當(dāng)前字符串重復(fù)指定次數(shù)后，與彈出的字符串連接起來(lái)，更新當(dāng)前字符串。
-
返回解碼后的字符串：遍歷完成后，當(dāng)前字符串即為解碼后的字符串。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-844682.html
完整代碼
Python
class Solution:
def decodeString(self, s: str) -> str:
numStack = [] # 存儲(chǔ)重復(fù)次數(shù)
strStack = [] # 存儲(chǔ)字符串
currentNum = 0
currentStr = ''
for char in s:
if char.isdigit():
currentNum = currentNum * 10 + int(char) # 構(gòu)建多位數(shù)
elif char == '[':
# 遇到 '['，將當(dāng)前數(shù)字和字符串分別壓棧，然后重置
numStack.append(currentNum)
strStack.append(currentStr)
currentNum, currentStr = 0, ''
elif char == ']':
# 遇到 ']'，彈出棧頂數(shù)字，重復(fù)當(dāng)前字符串，并與棧頂字符串連接
num = numStack.pop()
prevStr = strStack.pop()
currentStr = prevStr + num * currentStr
else:
currentStr += char # 構(gòu)建字符串
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 == '[') {
// 遇到 '['，將當(dāng)前數(shù)字和字符串分別壓棧，然后重置
numStack.push(currentNum);
strStack.push(currentStr);
currentNum = 0;
currentStr = "";
} else if (ch == ']') {
// 遇到 ']'，彈出棧頂數(shù)字，重復(fù)當(dāng)前字符串，并與棧頂字符串連接
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;
}
}到了這里，關(guān)于力扣熱門算法題 349. 兩個(gè)數(shù)組的交集，387. 字符串中的第一個(gè)唯一字符，394. 字符串解碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
