【代碼隨想錄】刷題筆記—

242. 有效的字母異位詞

349. 兩個數組的交集

202. 快樂數

1. 兩數之和

454. 四數相加 II

383. 贖金信

15. 三數之和

18. 四數之和

242. 有效的字母異位詞

思路

代碼

class Solution {public boolean isAnagram(String s, String t) {if (s.length() != t.length()) return false;int[] cnt = new int[26];for (int i = 0;i < s.length();i++) {cnt[s.charAt(i) - 'a']++;}for (int i = 0;i < t.length();i++) {cnt[t.charAt(i) - 'a']--;}for (int i = 0;i < cnt.length;i++) {if (cnt[i] > 0) return false;}return true;}
}

API：

字符串求length：s.length()?

數組求length：cnt.length

取出 i 位置的元素：s.charAt(i)

代碼（排序）

class Solution {public boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}char[] str1 = s.toCharArray();char[] str2 = t.toCharArray();Arrays.sort(str1);Arrays.sort(str2);return Arrays.equals(str1, str2);}
}

API：

字符串轉字符數組：s.toCharArray()

比較兩字符數組：Arrays.equals(str1, str2)

349. 兩個數組的交集

思路

先把 nums1 改成 HashSet 形式，對 nums2 篩選出在 nums1 中的元素，并考慮對 nums2 中的元素去重，放入一個新的 HashSet 中，最后轉為答案要求的形式。

代碼（數組表示哈希表，有->1 ，無->0）

class Solution {public int[] intersection(int[] nums1, int[] nums2) {int[] temp = new int[1000];int index = 0;//存在不存在的問題int[] map = new int[1001];for (int i = 0;i < nums1.length;i++) {map[nums1[i]] = 1;}for (int i = 0;i < nums2.length;i++) {if (map[nums2[i]] == 1) {temp[index] = nums2[i];map[nums2[i]] = 0;index++;}}int[] result = Arrays.copyOfRange(temp,0,index);return result;}
}

代碼（Set集合去重）

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<>();for (int num : nums1) {set1.add(num);}Set<Integer> set2 = new HashSet<>();for (int num : nums2) {if (set1.contains(num)) {set2.add(num);}}int[] result = new int[set2.size()];int index = 0;for (int num : set2) {result[index++] = num;}return result;}
}

Collection集合的遍歷方式

//1.使用增強for遍歷集合
for(String s: c){System.out.println(s); 
}

//2. 使用lambda表達式,結合forEach方法
c.forEach(s->System.out.println(s));

202. 快樂數

思路

題目中說了會?無限循環，那么也就是說求和的過程中，sum會重復出現，這對解題很重要！

當我們遇到了要快速判斷一個元素是否出現集合里的時候，就要考慮哈希法了。

所以這道題目使用哈希法，來判斷這個sum是否重復出現，如果重復了就是return false，否則一直找到sum為1為止。

判斷sum是否重復出現就可以使用set集合。

還有一個難點就是求和的過程，如果對取數值各個位上的單數操作不熟悉的話，做這道題也會比較艱難。

代碼

class Solution {public boolean isHappy(int n) {Set<Integer> set = new HashSet<>();while(true) {int temp = getSum(n);if (temp == 1) return true;if (!set.contains(temp)) {set.add(temp);n = temp;}else {return false;}}}//計算每個位置上的數字的平方和private int getSum(int n) {int sum = 0;while (n > 0) {sum += (n%10) * (n%10);n /= 10;}return sum;}
}

新增的方法不能寫到默認的public方法里

代碼（官方）

class Solution {public boolean isHappy(int n) {Set<Integer> record = new HashSet<>();while (n != 1 && !record.contains(n)) {record.add(n);n = getNextNumber(n);}return n == 1;}private int getNextNumber(int n) {int res = 0;while (n > 0) {int temp = n % 10;res += temp * temp;n = n / 10;}return res;}
}

1. 兩數之和

思路

代碼

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();int[] result = new int[2];for (int i = 0;i < nums.length;i++) {int key = target - nums[i];if (map.containsKey(key)) {result[0] = i;result[1] = map.get(key);break;}map.put(nums[i],i);}return result;}
}

代碼（官方）

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; ++i) {if (hashtable.containsKey(target - nums[i])) {return new int[]{hashtable.get(target - nums[i]), i};}hashtable.put(nums[i], i);}return new int[0];}
}

454. 四數相加 II

思路

代碼

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int cnt = 0;Map<Integer,Integer> map = new HashMap<>();//1. 把nums1 nums2相加的所有可能值存到hashmapfor (int i = 0;i < nums1.length;i++) {for (int j = 0;j < nums2.length;j++) {int temp = nums1[i] + nums2[j];if (map.containsKey(temp)) {int a = map.get(temp);map.remove(temp);map.put(temp,a + 1);}else {map.put(temp,1);}}}//2. 遍歷nums3 和 nums4，對相加的所有結果判斷hashmap中是否存在for (int i = 0;i < nums3.length;i++) {for (int j = 0;j < nums4.length;j++) {int temp2 = 0 - nums3[i] - nums4[j];if (map.containsKey(temp2)) {cnt += map.get(temp2);}}}return cnt;}
}

代碼（官方）

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0;Map<Integer, Integer> map = new HashMap<Integer, Integer>();//統計兩個數組中的元素之和，同時統計出現的次數，放入mapfor (int i : nums1) {for (int j : nums2) {int sum = i + j;map.put(sum, map.getOrDefault(sum, 0) + 1);}}//統計剩余的兩個元素的和，在map中找是否存在相加為0的情況，同時記錄次數for (int i : nums3) {for (int j : nums4) {res += map.getOrDefault(0 - i - j, 0);}}return res;}
}

Map集合API補充

// 遍歷鍵
for (String key : map.keySet()) {System.out.println(key);
}// 遍歷值
for (Integer value : map.values()) {System.out.println(value);
}// 獲取默認值（若鍵不存在）
Integer defaultValue = map.getOrDefault("apple", 0); // 返回 0// 合并操作（Java 8+）
map.merge("apple", 5, Integer::sum); // 若鍵不存在則添加，存在則合并值

Java 8+ 新增默認方法

方法簽名說明
V getOrDefault(Object key, V defaultValue) 安全獲取值（鍵不存在時返回默認值）
V putIfAbsent(K key, V value) 鍵不存在時才插入
boolean remove(Object key, Object value) 僅當鍵值都匹配時才移除
boolean replace(K key, V oldValue, V newValue) 鍵值都匹配時才替換為新值
V replace(K key, V value) 鍵存在時替換值
void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) 批量替換所有值
void forEach(BiConsumer<? super K, ? super V> action) 遍歷所有鍵值對
V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) 動態計算新值（可刪除或更新）
V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) 鍵不存在時計算新值并插入
V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) 鍵存在時計算新值
V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) 合并新舊值（常用于計數）

方法簽名	說明
`V getOrDefault(Object key, V defaultValue)`	安全獲取值（鍵不存在時返回默認值）
`V putIfAbsent(K key, V value)`	鍵不存在時才插入
`boolean remove(Object key, Object value)`	僅當鍵值都匹配時才移除
`boolean replace(K key, V oldValue, V newValue)`	鍵值都匹配時才替換為新值
`V replace(K key, V value)`	鍵存在時替換值
`void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)`	批量替換所有值
`void forEach(BiConsumer<? super K, ? super V> action)`	遍歷所有鍵值對
`V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)`	動態計算新值（可刪除或更新）
`V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)`	鍵不存在時計算新值并插入
`V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)`	鍵存在時計算新值
`V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)`	合并新舊值（常用于計數）

383. 贖金信

代碼

class Solution {public boolean canConstruct(String ransomNote, String magazine) {Map<Character,Integer> map = new HashMap<>();for (char s: ransomNote.toCharArray()) {map.merge(s,1,Integer::sum);}for (char m: magazine.toCharArray()) {if (map.containsKey(m)) {map.merge(m,1,(oldValue,newValue) -> oldValue - newValue);}}for (Integer v: map.values()) {if (v > 0) {return false;}}return true;}
}

map.merge(s,1,Integer::sum);? ? ? ?//相當于舊值 + 1

map.merge(m,1,(oldValue,newValue) -> oldValue - newValue);? //?//相當于舊值 -?1

代碼（官方）

class Solution {public boolean canConstruct(String ransomNote, String magazine) {// shortcutif (ransomNote.length() > magazine.length()) {return false;}// 定義一個哈希映射數組int[] record = new int[26];// 遍歷for(char c : magazine.toCharArray()){record[c - 'a'] += 1;}for(char c : ransomNote.toCharArray()){record[c - 'a'] -= 1;}// 如果數組中存在負數，說明ransomNote字符串中存在magazine中沒有的字符for(int i : record){if(i < 0){return false;}}return true;}
}

15. 三數之和

思路

代碼（官方）

class Solution {//定義三個指針，保證遍歷數組中的每一個結果//畫圖，解答public List<List<Integer>> threeSum(int[] nums) {//定義一個結果集List<List<Integer>> res = new ArrayList<>();//數組的長度int len = nums.length;//當前數組的長度為空，或者長度小于3時，直接退出if(nums == null || len <3){return res;}//將數組進行排序Arrays.sort(nums);//遍歷數組中的每一個元素for(int i = 0; i<len;i++){//如果遍歷的起始元素大于0，就直接退出//原因，此時數組為有序的數組，最小的數都大于0了，三數之和肯定大于0if(nums[i]>0){break;}//去重，當起始的值等于前一個元素，那么得到的結果將會和前一次相同if(i > 0 && nums[i] == nums[i-1]) continue;int l = i +1;int r = len-1;//當 l 不等于 r時就繼續遍歷while(l<r){//將三數進行相加int sum = nums[i] + nums[l] + nums[r];//如果等于0，將結果對應的索引位置的值加入結果集中if(sum==0){// 將三數的結果集加入到結果集中res.add(Arrays.asList(nums[i], nums[l], nums[r]));//在將左指針和右指針移動的時候，先對左右指針的值，進行判斷//如果重復，直接跳過。//去重，因為 i 不變，當此時 l取的數的值與前一個數相同，所以不用在計算，直接跳while(l < r && nums[l] == nums[l+1]) {l++;}//去重，因為 i不變，當此時 r 取的數的值與前一個相同，所以不用在計算while(l< r && nums[r] == nums[r-1]){r--;} //將 左指針右移，將右指針左移。l++;r--;//如果結果小于0，將左指針右移}else if(sum < 0){l++;//如果結果大于0，將右指針左移}else if(sum > 0){r--;}}}return res;}
}

Arrays.asList()?和?List.of()?
// 使用 List.of()（推薦）
List<Integer> immutableList = List.of(1, 2, 3); // 不可變// 使用 Arrays.asList()
List<Integer> fixedSizeList = Arrays.asList(1, 2, 3); // 大小固定但元素可變// 若需要可變列表，建議顯式轉換
List<Integer> mutableList = new ArrayList<>(Arrays.asList(1, 2, 3));
mutableList.add(4); // 允許添加元素
場景推薦方法
創建不可變列表 List.of()
需要存儲?null Arrays.asList()
需修改元素（不增減大小） Arrays.asList()
Java 8 及以下版本 Arrays.asList()

場景	推薦方法
創建不可變列表	`List.of()`
需要存儲?`null`	`Arrays.asList()`
需修改元素（不增減大小）	`Arrays.asList()`
Java 8 及以下版本	`Arrays.asList()`

18. 四數之和

代碼（官方）

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();if (nums == null || nums.length < 4) {return quadruplets;}Arrays.sort(nums);int length = nums.length;for (int i = 0; i < length - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break;}if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {continue;}for (int j = i + 1; j < length - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break;}if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {continue;}int left = j + 1, right = length - 1;while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum == target) {quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) {left++;}left++;while (left < right && nums[right] == nums[right - 1]) {right--;}right--;} else if (sum < target) {left++;} else {right--;}}}}return quadruplets;}
}