前言

? ? ? ? 今天開始刷面試算法題，雖然之前在藍橋杯、程序設計天梯賽中拿過兩個省一和一個國三，但是基本靠的都是我對 Java 語言的熟悉，至于算法我只會基本的雙指針、快慢指針、差分數組等，最擅長的其實還是暴力。但是自認為應付面試還是遠遠不夠的，所以今天開始是該好好修煉一下算法了。

leetcode 編號	完成時間	復習時間
1. 兩數之和	2024-06-30
2. 兩數相加	2024-06-30
3. 無重復字符的最長子串	2024-06-30
4. 尋找兩個正序數組的中位數	2024-07-01
5. 最長回文串	2024-07-01
6.?
7.
8.?
9. 回文數	2024-07-02
10.?

1、兩數之和（哈希）

1.1、暴力法?

• 思路💡：雙重遍歷，確保數組中每兩個數字都進行過一次求和，直到找到 nums[i] + nums[j] = target 的兩個目標索引
• 時間復雜度🕖：?O(n2)

class Solution {public int[] twoSum(int[] nums, int target) {int[] res = new int[2];for(int i=0;i<nums.length-1;i++){for(int j=i+1;j<nums.length;j++){if(nums[i]+nums[j]==target){res[0]=i;res[1]=j;return res;}}}return nums;}
}

1.2、哈希表

• 思路💡：使用一個哈希表來存儲遍歷過的元素，每次插入元素前判斷是否存在 target - nums[i]
• 時間復雜度🕖：因為哈希表的插入和查詢操作的復雜度是 O(1)，所以總的時間復雜度是 O（n）

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

2、兩數相加（模擬）

?2.1、模擬算法

• 思路💡：模擬普通列式計算的過程，用變量 t 代表當前位的計算和，則 t%10 為當前位的結果，t/10 作為下一輪計算的加數
• 時間復雜度🕖：O（n）

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(-1); // 首節點ListNode cur = dummy; // 當前節點（負責穿針引線，將每位的結果連起來）int t = 0; // 每位的計算和while(l1 !=null || l2 !=null || t!=0){if(l1!=null){t += l1.val;l1 = l1.next;}if(l2!=null){t += l2.val;l2 = l2.next;}cur.next = new ListNode(t % 10);t /= 10;cur = cur.next;}return dummy.next;} 
}

3、無重復字符的最長子串（雙指針——前后指針）

3.1、暴力法

• 思路💡：雙重循環，遍歷每一種沒有重復字符的字符串組合
• 時間復雜度🕖：O（n2）

class Solution {public int lengthOfLongestSubstring(String s) {if(s.length()==0 || s.length()==1) return s.length();char[] arr = s.toCharArray();int max = Integer.MIN_VALUE;for(int i=0;i<arr.length-1;i++){Map<Character,Integer> map = new HashMap<>();map.put(arr[i],1);for(int j=i+1;j<arr.length;j++){if(map.containsKey(arr[j])) break;else map.put(arr[j],1);}max = Math.max(max,map.size());}return max;}
}

3.2、前后指針?

• 思路💡：指針 j 負責在前面探索，當哈希表中存在索引 j 的元素時，指針 i 開始移動，直到區間內沒有重復元素
• 時間復雜度🕖：由于 i,j 均最多增加n次，且哈希表的插入和更新操作的復雜度都是 O(1)
  ，因此，總時間復雜度 O(n)

class Solution {public int lengthOfLongestSubstring(String s) {char[] arr = s.toCharArray();Map<Character,Integer> map = new HashMap<>();int res = 0;for(int i=0,j=0;j<arr.length;j++){map.put(arr[j],map.getOrDefault(arr[j],0)+1);while(map.get(arr[j]) > 1){map.put(arr[i],map.get(arr[i++])-1);}res = Math.max(res,j - i + 1);}return res;}
}

4、尋找兩個正序數組的中位數（歸并排序）

• 思路💡：使用歸并算法將兩個數組合并
• 時間復雜度🕖：O（ n + m ）n 和 m 分別是兩個數組的長度

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int m = nums1.length;int n = nums2.length;int[] nums = new int[m+n];// 如果nums1為空,則直接返回nums2的中位數if (m == 0) {if (n % 2 == 0) {return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;} else {return nums2[n / 2];}}// 如果nums2為空,則直接返回nums1的中位數if (n == 0) {if (m % 2 == 0) {return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;} else {return nums1[m / 2];}}int count = 0; // 合并后的數組的索引int i = 0,j = 0; // nums1 和 nums2 的索引while(count != (m+n)){if(i == m){ // 如果數組 nums1 的元素合并完畢while(j != n){nums[count++] = nums2[j++];}break;}if(j == n){while(i != m){nums[count++] = nums1[i++];}break;}if(nums1[i] < nums2[j]){nums[count++] = nums1[i++];}else{nums[count++] = nums2[j++];}}// 到這里已經合并結束了 count=nums.lengthreturn count%2==0?(nums[count/2-1] + nums[count/2])/2.0:nums[count/2];}
}

?5、最長回文子串

5.1、雙指針 + 暴力

• 思路💡：使用雙指針判斷字符串是否是回文串，然后使用雙重循環枚舉出每一種子串
• 時間復雜度🕖：O（ n3 ）

class Solution {public String longestPalindrome(String s) {String longest = "";for(int i=0;i<s.length();i++){for(int j=i+1;j<s.length()+1;j++){String sub = s.substring(i,j);if(isPalindrome(sub)){longest = sub.length()>longest.length()?sub:longest;}}}return longest;}/*** 雙指針判斷回文串*/public boolean isPalindrome(String str){int i = 0,j = str.length()-1;while(str.charAt(i) == str.charAt(j)){if(i >= j) return true;i++;j--;}return false;}
}

5.2、 中心擴散法

• 思路💡：暴力枚舉所有回文串的中心，然后使用中心擴散計算回文串的長度
  • 首先尋找邊界，因為回文串的中心可能不是一個字符（比如 "abba"，或者 "abbba" ，這種可以統一將右指針移動到邊界）
  • 此時，左右指針都指向相同的字符，然后左右指針開始同時擴散，找到該中心最長的回文串
  • 長度 =? 右指針 - 左指針 + 1
• 時間復雜度🕖：O（N2）

class Solution {public String longestPalindrome(String s) {int left=0,right=0;int max = 0; // 最長for(int i=0;i<s.length();i++){int subLeft = i,subRight = i;// 尋找右邊界while(subRight<s.length()-1 && s.charAt(i)==s.charAt(subRight+1)){subRight++;}// 左右擴散while(subRight<s.length()-1 && subLeft-1>=0 && s.charAt(subLeft-1)==s.charAt(subRight+1)){subLeft--;subRight++;}int len = subRight - subLeft + 1;if(len > max){left = subLeft;right = subRight;max = len;}}return s.substring(left,right+1);}
}

?6、Z 字形變換

感覺這種題對面試沒意義，跳過

7、整數反轉

純數學題，跳過

8、字符串轉換整數

純模擬題，這類題做太多了，基本通過了，剩下個別一兩個用例懶得寫了，意義不大。

這里寫一下從中學到的一點，從來沒相關在算法里 try-catch 不過還挺好用的：

        try{if(Long.parseLong(sb.toString())< Integer.MIN_VALUE){return Integer.MIN_VALUE;}else if(Long.parseLong(sb.toString()) > Integer.MAX_VALUE){return Integer.MAX_VALUE;}}catch(Exception e){return 0;}

9、回文數

• 思路💡：雙指針
• 時間復雜度🕖：O（N）

class Solution {public boolean isPalindrome(int x) {String s = String.valueOf(x);int i = 0,j = s.length()-1;while(s.charAt(i) == s.charAt(j)){if(i>=j)    return true;i++;j--;}return false;}
}

10、正則表達式

• 思路💡沒有思路，純模擬，而且是最難的模擬
• 時間復雜度🕖：

果斷放棄，之后有思路了 再來