開始前：
選擇leetcode-hot100。要求每日1道，并且需要親自二刷昨天的題目（每一種解法），要做解題筆記并發布CSDN，做完立刻二刷。做題時間為每日12：50起，不拖延，這是學習成長的機會，堅持下去就會變得很厲害很強。當然，學習是一個持續的過程，開學之后每日JAVA做的算法題就是leetcode面試經典150題。變強。努力提升算法和工程能力。
力扣hot100
哈希
1.兩數之和
return new int[0]?表示返回一個長度為 0 的 int 類型數組
暴力枚舉：
class Solution {
? ? public int[] twoSum(int[] nums, int target) {
? ? ? ? for(int i = 0;i<nums.length;i++){
? ? ? ? ? ? for(int j=i+1;j<nums.length;j++){
? ? ? ? ? ? ? ? if(nums[j]==(target-nums[i])){
? ? ? ? ? ? ? ? ? ? int[] arr = new int[]{i,j};
? ? ? ? ? ? ? ? ? ? return arr;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return new int[0];
? ? }
}
哈希表：
復習代碼隨想錄的哈希表理論基礎
(代碼隨想錄)
一般選擇3種數據結構來做哈希：數組、set（集合）、map（映射）
C++：“當我們要使用集合來解決哈希問題的時候，優先使用unordered_set，因為它的查詢和增刪效率是最優的，如果需要集合是有序的，那么就用set，如果要求不僅有序還要有重復數據的話，那么就用multiset。”
JAVA中哈希法涉及的數據結構：
1.?HashMap（最常用的哈希表實現）
- 特點：基于哈希表實現，允許存儲?null?鍵和?null?值，無序（鍵值對的存儲順序與插入順序無關）。
- 底層結構：JDK 1.8 后采用「數組 + 鏈表 + 紅黑樹」結構：
- 數組（哈希桶）：每個索引對應一個鏈表或紅黑樹。
- 鏈表：解決哈希沖突（不同鍵映射到同一索引），當鏈表長度超過 8 時轉為紅黑樹（提高查詢效率）。
- 核心方法：
- put(key, value)：插入鍵值對（若鍵已存在則覆蓋值）。
- get(key)：根據鍵獲取值（不存在返回?null）。
- containsKey(key)：判斷是否包含指定鍵。
- remove(key)：刪除指定鍵的鍵值對。
- 適用場景：
- 需快速通過鍵查找值（如緩存、計數統計）。
- 解決兩數之和、子數組和等算法問題（通過鍵存儲目標值，值存儲索引）。
2.?HashSet（基于?HashMap?的集合）
- 特點：底層通過?HashMap?實現（將元素作為?HashMap?的鍵，值為固定常量），不允許重復元素，無序，允許?null?元素。
- 核心方法：
- add(element)：添加元素（若已存在則返回?false）。
- contains(element)：判斷元素是否存在。
- remove(element)：刪除元素。
- 適用場景：
- 需要去重或快速判斷元素是否存在（如查找交集、判斷是否包含重復元素）。
- 替代數組或鏈表做查找操作（時間復雜度從 O (n) 降至 O (1)）。
Map:因為要用元素值去找匹配的元素，最后返回的是下標，所以元素值作為key（用于哈希查找），下標作為value。
JAVA map,set學習鏈接：
(https://blog.csdn.net/qq_47980550/article/details/148064851)
(https://blog.csdn.net/qq_47980550/article/details/148085987)
哈希法：
class Solution {
? ? public int[] twoSum(int[] nums, int target) {
? ? Map<Integer,Integer> map = new HashMap<Integer,Integer>();
? ? ? ? for(int i=0;i<nums.length;i++){
? ? ? ? ? ? if(map.containsKey(target-nums[i])){
? ? ? ? ? ? ? ? int[] arr = new int[]{i,map.get(target-nums[i])};
? ? ? ? ? ? ? ? return arr;
? ? ? ? ? ? }
? ? ? ? ? ? else map.put(nums[i],i);
? ? ? ? }
? ? ? ? return new int[0];
? ? }
}
MAP用于記錄遍歷過的。
?
2. 字母異位詞分組
題意：要做的還是遍歷一遍，過程中用MAP存遍歷，找。題目返回的類型是List需要先學習List:
(https://blog.csdn.net/qq_47980550/article/details/148012216)
回顧做過的題：242.有效的字母異位詞。
該題（242.有效的字母異位詞）哈希：
class Solution {
??? public boolean isAnagram(String s, String t) {
??????? // 首先判斷長度是否相等，不等直接返回false
??????? if (s.length() != t.length()) {
??????????? return false;
??????? }
???????
??????? // 手動創建計數數組，存儲每個字母的出現次數
??????? int[] count = new int[26];
???????
??????? // 手動遍歷字符串s，統計每個字符出現次數
??????? for (int i = 0; i < s.length(); i++) {
??????????? // 手動計算字符對應的索引（'a'-'z'對應0-25）
??????????? char c = s.charAt(i);
??????????? int index = 0;
??????????? // 不使用減法運算，手動計算索引（鍛煉基礎邏輯）
??????????? for (char ch = 'a'; ch <= 'z'; ch++) {
??????????????? if (ch == c) {
??????????????????? break;
??????????????? }
??????????????? index++;
??????????? }
??????????? count[index]++;
??????? }
???????
??????? // 手動遍歷字符串t，減少對應字符的計數
??????? for (int i = 0; i < t.length(); i++) {
??????????? char c = t.charAt(i);
??????????? int index = 0;
??????????? for (char ch = 'a'; ch <= 'z'; ch++) {
??????????????? if (ch == c) {
??????????????????? break;
??????????????? }
??????????????? index++;
??????????? }
??????????? count[index]--;
???????????
??????????? // 如果出現負數，說明t包含s沒有的字符
??????????? if (count[index] < 0) {
??????????????? return false;
??????????? }
??????? }
???????
??????? // 檢查所有計數是否為0
??????? for (int i = 0; i < 26; i++) {
??????????? if (count[i] != 0) {
??????????????? return false;
??????????? }
??????? }
???????
??????? return true;
??? }
}
該題（242.有效的字母異位詞）暴力解法：
public class AnagramChecker {
??? public static boolean isAnagram(String s, String t) {
??????? // 首先檢查長度是否相同
??????? if (s.length() != t.length()) {
??????????? return false;
??????? }
???????
??????? // 自定義方法將字符串轉換為字符數組
??????? char[] sChars = stringToCharArray(s);
??????? char[] tChars = stringToCharArray(t);
???????
??????? // 使用冒泡排序對字符數組排序
??????? bubbleSort(sChars);
??????? bubbleSort(tChars);
???????
??????? // 比較排序后的字符數組
??????? for (int i = 0; i < sChars.length; i++) {
??????????? if (sChars[i] != tChars[i]) {
??????????????? return false;
??????????? }
??????? }
???????
??????? return true;
??? }
???
??? // 自定義方法：將字符串轉換為字符數組
??? private static char[] stringToCharArray(String str) {
??????? // 創建與字符串長度相同的字符數組
??????? char[] arr = new char[str.length()];
??????? // 逐個提取字符并放入數組
??????? for (int i = 0; i < str.length(); i++) {
??????????? arr[i] = str.charAt(i);
??????? }
??????? return arr;
??? }
???
??? // 冒泡排序實現
??? private static void bubbleSort(char[] arr) {
??????? int n = arr.length;
??????? for (int i = 0; i < n - 1; i++) {
??????????? for (int j = 0; j < n - i - 1; j++) {
??????????????? if (arr[j] > arr[j + 1]) {
??????????????????? // 交換元素
??????????????????? char temp = arr[j];
??????????????????? arr[j] = arr[j + 1];
??????????????????? arr[j + 1] = temp;
??????????????? }
??????????? }
??????? }
??? }
???
??? public static void main(String[] args) {
??????? // 測試示例
??????? System.out.println(isAnagram("anagram", "nagaram")); // 輸出: true
??????? System.out.println(isAnagram("rat", "car"));???????? // 輸出: false
??? }
}
冒泡排序：核心邏輯是（重復地比較兩個相鄰的元素，如果他們是逆序，就交換他們，知道整個序列排序完成）
(三分鐘學會冒泡排序_嗶哩嗶哩_bilibili)
private static void bubbleSort(char[] arr) {
??? int n = arr.length;? // 獲取數組長度
??? // 外層循環：控制需要進行多少輪比較
??? // 每一輪都會將當前未排序部分的最大元素"浮"到末尾
??? for (int i = 0; i < n - 1; i++) {
??????? // 內層循環：進行每一輪的相鄰元素比較
??????? // n - i - 1：因為每輪結束后，最后i個元素已經排好序，不需要再比較
??????? for (int j = 0; j < n - i - 1; j++) {
??????????? // 如果當前元素大于下一個元素，說明順序錯誤，需要交換
??????????? if (arr[j] > arr[j + 1]) {
??????????????? // 交換元素（借助臨時變量temp）
??????????????? char temp = arr[j];
??????????????? arr[j] = arr[j + 1];
??????????????? arr[j + 1] = temp;
??????????? }
??????? }
??? }
}
接下來做49.字母異位詞分組
把排序后的字符串作為鍵，將原字符串集合作為VALUE
JAVA ArrayList
(Java中ArrayList常用方法_java arraylist方法-CSDN博客)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class AnagramGrouper {
???
??? // 主方法：將字符串數組中的異位詞分組
??? public List<List<String>> groupAnagrams(String[] strs) {
??????? // 創建一個HashMap，用于存儲分組結果
??????? // 鍵：字符串的特征編碼（如"a3b2c1"）
??????? // 值：具有相同特征編碼的字符串列表（即異位詞組）
??????? Map<String, List<String>> groups = new HashMap<>();
???????
??????? // 遍歷輸入的每個字符串
??????? for (String str : strs) {
??????????? // 1. 計算當前字符串的字符計數數組
??????????? int[] counter = new int[26];? // 26個位置對應a-z 26個字母
??????????? for (int i = 0; i < str.length(); i++) {
??????????????? // 獲取當前字符，計算它在數組中的索引（a->0, b->1, ..., z->25）
??????????????? char c = str.charAt(i);
??????????????? int index = c - 'a';
??????????????? // 對應位置的計數加1
??????????????? counter[index]++;
??????????? }
???????????
??????????? // 2. 將計數數組轉換為字符串編碼（如[0,2,1] -> "b2c1"）
??????????? StringBuilder sb = new StringBuilder();
??????????? for (int i = 0; i < 26; i++) {
??????????????? // 只處理出現過的字符，減少編碼長度
??????????????? if (counter[i] != 0) {
??????????????????? // 添加字符（如i=0對應'a'，i=1對應'b'）
??????????????????? sb.append((char) ('a' + i));
??????????????????? // 添加該字符出現的次數
??????????????????? sb.append(counter[i]);
??????????????? }
??????????? }
??????????? String code = sb.toString();? // 得到編碼字符串
???????????
??????????? // 3. 將當前字符串添加到對應的分組中
??????????? // 如果該編碼不存在于map中，先創建一個新列表
??????????? if (!groups.containsKey(code)) {
??????????????? groups.put(code, new ArrayList<>());
??????????? }
??????????? // 將當前字符串添加到對應的列表中
??????????? groups.get(code).add(str);
??????? }
???????
??????? // 4. 將map中的所有值（即分組列表）轉換為List并返回
??????? return new ArrayList<>(groups.values());
??? }
???
??? // 測試方法
??? public static void main(String[] args) {
??????? AnagramGrouper solution = new AnagramGrouper();
??????? String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
??????? List<List<String>> result = solution.groupAnagrams(strs);
???????
??????? // 打印結果
??????? for (List<String> group : result) {
??????????? System.out.println(group);
??????? }
??????? // 輸出應該是：
??????? // [eat, tea, ate]
??????? // [tan, nat]
??????? // [bat]
??? }
}
排序：由于互為字母異位詞的兩個字符串包含的字母相同，因此對兩個字符串分別進行排序之后得到的字符串一定是相同的，故可以將排序之后的字符串作為哈希表的鍵。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
??? public List<List<String>> groupAnagrams(String[] strs) {
??????? // 創建一個哈希表，用于存儲分組結果
??????? // 鍵：排序后的字符串（例如"aet"）
??????? // 值：具有相同排序結果的字符串列表（即異位詞分組）
??????? Map<String, List<String>> map = new HashMap<String, List<String>>();
???????
??????? // 遍歷數組中的每個字符串
??????? for (String str : strs) {
??????????? // 1. 將字符串轉換為字符數組
??????????? // 例如 "eat" 會變成 ['e', 'a', 't']
??????????? char[] array = str.toCharArray();
???????????
??????????? // 2. 對字符數組進行排序
??????????? // 排序后 ['e', 'a', 't'] 會變成 ['a', 'e', 't']
??????????? Arrays.sort(array);
???????????
??????????? // 3. 將排序后的字符數組轉換回字符串
??????????? // 這里就是你不理解的 String key = new String(array);
??????????? // 作用：把排序后的字符數組['a', 'e', 't']變成字符串"aet"
??????????? // 互為異位詞的字符串排序后會得到相同的key
??????????? String key = new String(array);
???????????
??????????? // 4. 這是你不理解的getOrDefault方法
??????????? // 作用：嘗試從map中獲取key對應的列表
??????????? // 如果存在，就直接使用這個列表；如果不存在，就創建一個新的空列表
??????????? List<String> list = map.getOrDefault(key, new ArrayList<String>());
??????????? /*
map.getOrDefault(key, new ArrayList<String>())這是 Map 接口的一個便捷方法，等價于下面的代碼：
List<String> list;
if (map.containsKey(key)) {
?? ???????? ?// 如果map中已經有這個key，就獲取已有的列表
?? ??????? list = map.get(key);
} else {
? ? ??????? // 如果map中沒有這個key，就創建一個新的空列表
?? ??????? list = new ArrayList<String>();
}
?????????? */
??????????? // 5. 將當前字符串添加到對應的列表中
??????????? list.add(str);
???????????
??????????? // 6. 將更新后的列表放回map中
??????????? map.put(key, list);
??????? }
???????
??????? // 7. 將map中所有的值（即所有分組）轉換為List并返回
??????? return new ArrayList<List<String>>(map.values());
??? }
}
3.最長連續序列
我想要做暴力法：冒泡排序+算法。但是有很多考慮不周全的地方，其實還要多練，加油。
問題分析
- 最后一段連續序列未被統計
循環結束后，最后一段連續序列的長度（cnt）沒有與結果（res）比較，導致如果最長序列在數組末尾，會被遺漏。 - flag變量的邏輯混亂
flag的存在使得重復元素的處理變得復雜，尤其是當重復元素出現在連續序列的起始位置時，會錯誤地重置計數。 - 重復元素處理不當
當遇到重復元素（nums[i] == nums[i+1]）時，無論是否在連續序列中，都應該直接跳過（不影響連續長度），但你的代碼中flag的判斷導致了錯誤的分支進入。
class Solution {
??? public int longestConsecutive(int[] nums) {
??????? if (nums.length == 0) return 0;
???????
??????? // 先排序
??????? mysort(nums);
???????
??????? int maxLen = 1;? // 最長連續序列長度
??????? int currentLen = 1;? // 當前連續序列長度
???????
??????? for (int i = 0; i < nums.length - 1; i++) {
??????????? // 情況1：當前元素與下一個元素相等（重復元素），不影響連續長度，直接跳過
??????????? if (nums[i] == nums[i+1]) {
??????????????? continue;
??????????? }
??????????? // 情況2：下一個元素是當前元素+1，屬于連續序列，長度+1
??????????? else if (nums[i+1] == nums[i] + 1) {
??????????????? currentLen++;
??????????? }
??????????? // 情況3：不連續，更新最長長度，并重置當前長度
??????????? else {
??????????????? maxLen = Math.max(maxLen, currentLen);
??????????????? currentLen = 1;
??????????? }
??????? }
???????
??????? // 最后一次比較（處理數組末尾的連續序列）
??????? maxLen = Math.max(maxLen, currentLen);
???????
??????? return maxLen;
??? }
???
??? // 冒泡排序（保持不變）
??? private void mysort(int[] nums) {
??????? for (int i = 0; i < nums.length - 1; i++) {
??????????? for (int j = 0; j < nums.length - i - 1; j++) {
??????????????? if (nums[j] > nums[j+1]) {
??????????????????? int temp = nums[j];
??????????????????? nums[j] = nums[j+1];
??????????????????? nums[j+1] = temp;
??????????????? }
??????????? }
??????? }
??? }
}
這樣顯然不符合題目o(n)的要求。下面學習哈希法：
哦其實不用排序，直接哈希查數一直查，是否有x,x+1,…。為什么不用排序：為了避開在子序列上找答案，只要保證該序列不是子序列，也就是要保證枚舉的數x在原數組中一定不存在前驅的x-1。并且set是自動去重的。
import java.util.HashSet;
import java.util.Set;
class Solution {
??? public int longestConsecutive(int[] nums) {
??????? // 1. 創建哈希集合存儲所有數字，實現O(1)時間復雜度的查詢
??????? // 哈希集合的特性：自動去重，且查詢元素是否存在時效率極高
??????? Set<Integer> numSet = new HashSet<Integer>();
??????? for (int num : nums) {
??????????? numSet.add(num); // 將數組中所有數字添加到集合中
??????? }
??????? // 用于記錄最長連續序列的長度，初始化為0
??????? int longestStreak = 0;
??????? // 2. 遍歷集合中的每個數字
??????? for (int num : numSet) {
??????????? // 關鍵判斷：只有當當前數字是一個序列的起點時，才開始計算連續長度
??????????? // 什么是序列的起點？即當前數字的前一個數字（num-1）不在集合中
??????????? // 這樣可以避免重復計算（例如序列1,2,3，只會從1開始計算，不會從2或3開始）
??????????? if (!numSet.contains(num - 1)) {
??????????????? int currentNum = num; // 當前正在檢查的數字
??????????????? int currentStreak = 1; // 當前連續序列的長度，至少為1（包含自身）
??????????????? // 3. 不斷檢查下一個數字是否存在于集合中，擴展連續序列
??????????????? // 例如當前數字是1，檢查2是否存在，存在則繼續檢查3，以此類推
??????????????? while (numSet.contains(currentNum + 1)) {
??????????????????? currentNum += 1; // 移動到下一個數字
??????????????????? currentStreak += 1; // 連續長度加1
??????????????? }
??????????????? // 4. 更新最長連續序列的長度
??????????????? longestStreak = Math.max(longestStreak, currentStreak);
??????????? }
??????? }
??????? // 返回最長連續序列的長度
??????? return longestStreak;
??? }
}
明天一定要二刷，能力欠缺，需要多學多練，深入地練習掌握。
)
