😍😍😍 相知

刷題不要一上來就直接干，先看題，明白題說的什么意思，然后想一下用什么現成的算法和數據結構可以快速解決，如果還是無從下手，建議先去看視頻，不要直接翻評論或官方代碼實現，看完視頻，自己在idea中模擬敲幾遍代碼，如果跑通了，先別急著上leetcode黏貼，而是再回顧一下要點，然后確定自己完全懂了后，在leetcode中手敲，注意是手敲下來！！！ 目前我就是采用的這種方法，雖然慢，但是可以維持一周忘不掉它，如果要想長期不忘，只能隔段時間就review一下了，就算是大牛，知道方法，長時間不碰，也不可能保證一次到位把代碼敲完一遍過！！！

這是我上一篇博客的，也希望大家多多關注！

1. 《劍指Offer》筆記&題解&思路&技巧&優化 Java版本——新版leetcode_Part_1
2. 《劍指Offer》筆記&題解&思路&技巧&優化 Java版本——新版leetcode_Part_2
3. 《劍指Offer》筆記&題解&思路&技巧&優化 Java版本——新版leetcode_Part_3
4. 《劍指Offer》筆記&題解&思路&技巧&優化 Java版本——新版leetcode_Part_4
5. 《劍指Offer》筆記&題解&思路&技巧&優化 Java版本——新版leetcode_Part_5

🙌🙌🙌 相識

根據題型可將其分為這樣幾種類型：

1. 結構概念類（數組，鏈表，棧，堆，隊列，樹）
2. 搜索遍歷類（深度優先搜索，廣度優先搜索，二分遍歷）
3. 雙指針定位類（快慢指針，指針碰撞，滑動窗口）
4. 排序類（快速排序，歸并排序）
5. 數學推理類（動態規劃，數學）

😢😢😢 開始刷題

🟡1.LCR 168. 丑數—— 丑數

題目跳轉：https://leetcode.cn/problems/chou-shu-lcof/description/

class Solution {public int nthUglyNumber(int n) {if (n <= 0)return -1;int[] dp = new int[n];dp[0] = 1;int id2 = 0, id3 = 0, id5 = 0;for (int i = 1; i < n; i++) {dp[i] = Math.min(dp[id2] * 2, Math.min(dp[id3] *3, dp[id5] * 5));// 這里不用else if的原因是有可能id2(3) * 2 == id3(2) * 3// 這種情況兩個指針都要后移if (dp[id2] * 2 == dp[i])id2 += 1;if (dp[id3] * 3 == dp[i])id3 += 1;if (dp[id5] * 5 == dp[i])id5 += 1; }return dp[n - 1];}
}

---

🟢2. LCR 169. 招式拆解 II——第一個只出現一次的字符

題目跳轉：https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/description/

class Solution {public char dismantlingAction(String arr) {if(arr.length()==0) return ' ';if(arr.length()==1) return arr.charAt(0);int [] array =new int[26];for(int i = 0;i<arr.length();i++){array[arr.charAt(i)-'a']++;}for(int i = 0;i<arr.length();i++){if(array[arr.charAt(i)-'a']==1)return arr.charAt(i);}return ' ';}
}

---

🔴3. LCR 170. 交易逆序對的總數——數組中的逆序對

題目跳轉：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

冒泡排序

每檢查一次交換一次 就可以產生一次逆序對

歸并排序

class Solution {public int reversePairs(int[] nums) {if(nums == null || nums.length <= 1){return 0;}return mergeSort(nums, 0, nums.length - 1);}int mergeSort(int[] nums, int left, int right){if(left >= right){return 0;}int mid = (right - left) / 2 + left;int x1 = mergeSort(nums, left, mid);int x2 = mergeSort(nums, mid + 1, right);int x3 = merge(nums, left, mid, mid+1, right);return x1 + x2 + x3;}int merge(int[] nums, int l1, int r1, int l2, int r2){int[] temp = new int[r2 - l1 + 1];int count = 0;int i = l1, j = l2, k = 0;while(i <= r1 && j <= r2){if(nums[i] > nums[j]){count = count + (l2 - i);temp[k++] = nums[j++];}else{temp[k++] = nums[i++];}}while(i <= r1) temp[k++] = nums[i++];while(j <= r2) temp[k++] = nums[j++];// 把臨時數組復制回原數組k = 0;for(i = l1; i <= r2; i++){nums[i] = temp[k++];}return count;}
}

---

🟢4. LCR 171. 訓練計劃 V——兩個鏈表的第一個公共節點

題目跳轉：https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/description/

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
class Solution {ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA==null||headB==null)return null;ListNode tempA = headA;ListNode tempB = headB;boolean a = false;boolean b = false;while(tempA!=tempB){if(tempA.next==null){tempA = headB;if(a)return null;a = true;}else{tempA = tempA.next;}if(tempB.next==null){tempB = headA;if(b)return null;b = true;}else{tempB = tempB.next;}}return tempA;}
}

原來不會死循環

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode h1 = headA, h2 = headB;while (h1 != h2) {h1 = h1 == null ? headB : h1.next;h2 = h2 == null ? headA : h2.next;}return h1;  }

---

🟢5. LCR 172. 統計目標成績的出現次數——在排序數組中查找數字

題目跳轉：https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/description/

二分查找

class Solution {public int countTarget(int[] scores, int target) {int left = 0;int right = scores.length-1;int mid = 0;int conut = 0;while(left<right){mid = (right-left)/2+left;if(target <= scores[mid]) right = mid;else left = mid+1;}while(left<scores.length&&scores[left++]==target)conut++;return conut;}
}

---

🟢6. LCR 173. 點名——0~ n-1中缺失的數字

題目跳轉：https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/

位運算

class Solution {public int takeAttendance(int[] records) {if(records[records.length-1]==records.length-1) return records.length;int result = 0;for(int i = 0;i<records.length;i++){result ^=records[i];result ^=i;}result^=records.length;return result;}
}

二分查找

class Solution {public int takeAttendance(int[] records) {if(records[records.length-1]==records.length-1) return records.length;int left = 0;int right =records.length-1;while(left<right){int mid = (right-left)/2 +left;if(records[mid]==mid){left = mid+1;}else{right = mid;}}return left;}
}

---

🟢7. LCR 174. 尋找二叉搜索樹中的目標節點——二叉搜索樹的第k大節點

題目跳轉：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/description/
作為一個普通人，我來分析下這題。

1. 假設，你花了點時間，練習了二叉樹的三種遍歷方式： a. 前序遍歷 b. 中序遍歷 c. 后續遍歷
2. 你也學習了二叉搜索樹，深入研究了二叉樹搜索樹的特性，并且深刻知道二叉搜索樹的一個特性：通過中序遍歷所得到的序列，就是有序的。

好，有了以上兩點知識，我認為你必須能想到（如果想不到，以上兩點知識肯定沒有學扎實）：中序遍歷二叉搜索樹，遍歷的同時，把遍歷到的節點存到一個可變數組里（Java的話，可以用ArrayList)。 思路轉化為代碼，如下：

class Solution {public int findTargetNode(TreeNode root, int cnt) {if(root==null)return -1;if(root.left==null&root.right==null)return root.val;ArrayList<Integer> list = new ArrayList<>();dfs(root,list);return list.get(list.size()-cnt);}public void dfs(TreeNode root,ArrayList<Integer> list){if(root==null)return;if(root.left==null&root.right==null){list.add(root.val);return ;}if(root.left!=null)dfs(root.left,list);list.add(root.val);if(root.right!=null)dfs(root.right,list);}
}

class Solution {public int findTargetNode(TreeNode root, int cnt) {if(root==null)return -1;if(root.left==null&root.right==null)return root.val;ArrayList<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode temp = stack.peek();if(temp==null){stack.pop();list.add(stack.pop().val);}else{stack.pop();if(temp.right!=null) stack.push(temp.right);stack.push(temp);stack.push(null);if(temp.left!=null)stack.push(temp.left);}}return list.get(list.size()-cnt);}
}

---

🟢8. LCR 175. 計算二叉樹的深度——二叉樹的深度

題目跳轉：https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/description/

class Solution {int max = 0;public int calculateDepth(TreeNode root) {int deep = 0;max = dfs(root,deep);return max;}public int dfs(TreeNode root,int num){if(root==null)return num;if(root.left==null&root.right==null){return num+1;}if(root.left!=null) max = Math.max(max,dfs(root.left,num+1));if(root.right!=null) max = Math.max(max,dfs(root.right,num+1));return max;}
}

class Solution {public int calculateDepth(TreeNode root) {int max = 0;if(root ==null)return 0;if(root.left == null&&root.right == null)return 1;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);queue.add(null);while(!queue.isEmpty()){TreeNode temp = queue.poll();if(temp==null){max++;if(!queue.isEmpty())queue.add(null);}else{if(temp.right!=null) queue.add(temp.right);if(temp.left!=null)queue.add(temp.left);}}return max;}
}

---

🟢9. LCR 176. 判斷是否為平衡二叉樹——平衡二叉樹

題目跳轉：https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/description/

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isBalanced(TreeNode root) {if(root==null) return true;if(root.left==null&&root.right==null)return true;if(Math.abs(getHigh(root.left)-getHigh(root.right))<=1){return isBalanced(root.left)&&isBalanced(root.right);}return false;}public int getHigh(TreeNode root){if(root==null) return 0;return Math.max(getHigh(root.left),getHigh(root.right))+1;}
}

---

🟡10. LCR 177. 撞色搭配——數組中數字出現的次數I

題目跳轉：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/description/

相同的數異或為0，不同的異或為1。0和任何數異或等于這個數本身。

所以，數組里面所有數異或 = 目標兩個數異或 。 由于這兩個數不同，所以異或結果必然不為0。

假設數組異或的二進制結果為10010，那么說明這兩個數從右向左數第2位是不同的

那么可以根據數組里面所有數的第二位為0或者1將數組劃分為2個。

這樣做可以將目標數必然分散在不同的數組中，而且相同的數必然落在同一個數組中。

這兩個數組里面的數各自進行異或，得到的結果就是答案

class Solution {public int[] sockCollocation(int[] nums) {int x = 0; // 用于記錄 A B 的異或結果/** 得到A^B的結果 基于異或運算的以下幾個性質 1. 交換律 2. 結合律 3. 對于任何數x，都有x^x=0，x^0=x */for (int val : nums) x ^= val;// x & (-x)本身的作用是得到最低位的1，int flag = x & (-x); // 而我們所需要的做到的是：利用這個1來進行分組，也就是做到將A和B區分開// 前面已經知道，x是我們需要的結果數A和B相異或的結果，也就是說，x的二進制串上的任何一個1，都能成為區分A和B的條件// 因此我們只需要得到x上的任意一個1，就可以做到將A和B區分開來int res = 0; // 用于記錄A或B其中一者// 分組操作for (int val : nums) {// 根據二進制位上的那個“1”進行分組// 需要注意的是，分組的結果必然是相同的數在相同的組，且還有一個結果數// 因此每組的數再與res=0一路異或下去，最終會得到那個結果數A或B// 且由于異或運算具有自反性，因此只需得到其中一個數即可if ((flag & val) != 0) {res ^= val;}}// 利用先前的x進行異或運算得到另一個，即利用自反性return new int[] {res, x ^ res};}
}

---

🟡11. LCR 178. 訓練計劃 VI——數組中數字出現的次數II

題目跳轉：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/description/

排序

class Solution {public int trainingPlan(int[] actions) {int n = actions.length;Arrays.sort(actions);for(int i = 0;i<n-1;i = i+3){if(actions[i]!=actions[i+2]){return actions[i];}}return  actions[n-1];}
}

哈希表

class Solution {public int singleNumber(int[] actions) {HashMap<Integer, Integer> map = new HashMap<>();for (int number : actions) map.put(number, map.getOrDefault(number, 0) + 1);for (int number : map.keySet()) if (map.get(number) == 1) return number;return 0;}
}

class Solution {public int singleNumber(int[] nums) {int[] res = new int[32];int m = 1;int sum = 0;for(int i = 0; i < 32; i++){for(int j = 0; j < nums.length; j++){if((nums[j] & m) != 0){res[i]++;}}res[i] = res[i] % 3;sum = sum + res[i] * m;m = m << 1;}return sum;}
}

---