算法筆記總結

一般不考慮空間復雜度，能降低時間復雜度就降低復雜度

時間復雜度排列順序

常見的算法時間復雜度由小到大依次為：

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<…<O(2n)<O(n!)

暴力算法

暴力算法適用于沒有思路情況下第一會想到的，一般是幾成for循環搭配使用。

例如：

在一個長度為 n 的數組 nums 里的所有數字都在 0～n-1 的范圍內。數組中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次。請找出數組中任意一個重復的數字。來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。 class Solution {public int findRepeatNumber(int[] nums) {int ans=0;for(int i=0;i<nums.length-1;i++){for(int j=i+1;j<nums.length;j++){if(nums[i]==nums[j]){ans=nums[i];return ans;}}}return ans;} }

哈希

HashSet

在一個長度為 n 的數組 nums 里的所有數字都在 0～n-1 的范圍內。數組中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次。請找出數組中任意一個重復的數字。來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。class Solution {public int findRepeatNumber(int[] nums) {int ans=0;Set<Integer> set=new HashSet<Integer>();for(int i=0;i<nums.length;i++){if(set.contains(nums[i])){ans=nums[i];return ans;}set.add(nums[i]);}return ans;} }

貪心

貪心算法又稱貪婪算法，貪心算法是指在不考慮整體上最優，算法是在某種意義上的局部最優解。

貪心算法采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇，就將所求問題簡化為一個規模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優解。雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以貪心算法不要回溯。

算法思路

一、建立數學模型。

二、把問題分成若干個子問題。

三、對子問題求解，得到子問題局部最優解。

四、把局部最優解合成合成原問題的解。

使用條件

1、貪心選擇的性質

一個問題的整體最優解可通過一系列局部的最優解的選擇達到，并且每次的選擇可以依賴以前作出的選擇，但不依賴于后面要作出的選擇。

2、最優子結構性質

當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/can-place-flowers/ 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {int count = 0;int m = flowerbed.length;int prev = -1;for (int i = 0; i < m; i++) {if (flowerbed[i] == 1) {if (prev < 0) {count += i / 2; //計算第一次左邊可以種植花的次數} else {count += (i - prev - 2) / 2; //距離上次的花的位置之間可以種植的花的次數}prev = i;}}if (prev < 0) {count += (m + 1) / 2;//全是0的情況，及總長度可以種植的次數} else {count += (m - prev - 1) / 2; //計算總長度和上次花的位置之間可以種植的次數}return count >= n;} }

滑動窗口最大值

暴力破解

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/sliding-window-maximum/ 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。//當數值很多的時候會時間超時，不可取。 class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int len=nums.length;int[] ans=new int[len-k+1];for(int i=0;i<len-k+1;i++){int tmp=nums[i];for(int j=1;j<k;j++){int t=nums[i+j];if(tmp<t){tmp=t;}}ans[i]=tmp;}return ans;} }

單調隊列

作者：LeetCode-Solution 鏈接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;Deque<Integer> deque = new LinkedList<Integer>();for (int i = 0; i < k; ++i) {while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) { //獲取元素但不刪除deque.pollLast();//獲取元素并刪除}deque.offerLast(i); //隊尾增加元素}int[] ans = new int[n - k + 1];ans[0] = nums[deque.peekFirst()];for (int i = k; i < n; ++i) {while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);while (deque.peekFirst() <= i - k) {deque.pollFirst();}ans[i - k + 1] = nums[deque.peekFirst()];}return ans;} }

雙指針

作者：LeetCode-Solution 鏈接：https://leetcode-cn.com/problems/sliding-window-median/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class Solution {public double[] medianSlidingWindow(int[] nums, int k) {int len=nums.length;double[] ans=new double[len-k+1];int r=0;int l=0;int[] t=new int[k];int count=0;while(r<=len){int countk=0; if(r-l+1>k){for(int j=l;j<r;j++){t[countk]=nums[j];countk++;}l++;//開始Arrays.sort(t);if(k%2==0){ans[count]=(double)(t[(k/2)-1])/2 +(double)(t[k/2])/2;}else{ans[count]=t[k/2];}count++;}r++;}return ans;} } 作者：LeetCode-Solution 鏈接：https://leetcode-cn.com/problems/get-equal-substrings-within-budget/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class Solution {public int equalSubstring(String s, String t, int maxCost) {int len=s.length();//首先總開銷應當小于等于該預算int cost=0;int l=0,r=0;//雙指針用法滑窗while(r<len){cost+=Math.abs(s.charAt(r)-t.charAt(r));//差值r++;if(cost>maxCost){cost-=Math.abs(s.charAt(l)-t.charAt(l));l++;}}return r-l;} } 作者：LeetCode-Solution 鏈接：https://leetcode-cn.com/problems/subarrays-with-k-different-integers/submissions/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class Solution {public int subarraysWithKDistinct(int[] A, int K) {return getNum(A,K)-getNum(A,K-1);}public int getNum(int[] A,int K){int len = A.length;int[] freq = new int[len+1];int left = 0;int right = 0;// [left, right) 里不同整數的個數int count = 0;int res = 0;// [left, right) 包含不同整數的個數小于等于 Kwhile (right < len) {System.out.println("right="+right+" A[right]="+A[right]+" freq[A[right]]="+freq[A[right]]);if (freq[A[right]] == 0) { //不包含重復元素count++;}freq[A[right]]++;System.out.println("====>"+"right="+right+" A[right]="+A[right]+" freq[A[right]]="+freq[A[right]]);right++;System.out.println("count=="+count);while (count > K) {freq[A[left]]--;System.out.println("<<===="+"left="+left+" A[left]="+A[left]+" freq[A[left]]="+freq[A[left]]);if (freq[A[left]] == 0) {count--;}left++;}// [left, right) 區間的長度就是對結果的貢獻System.out.println(right+" - "+left+"\n");res += right - left;//System.out.println("res="+res);}return res;} } 哈希表+雙指針作者：LeetCode-Solution 鏈接：https://leetcode-cn.com/problems/degree-of-an-array/submissions/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class Solution {public int findShortestSubArray(int[] nums) {int len =nums.length;//先統計元素的最大頻數// nums的值 對應的個數Map<Integer,Integer> map = new HashMap<Integer,Integer>();for (int i = 0; i <len; i++) {if(map.containsKey(nums[i])) {map.put(nums[i], map.get(nums[i])+1);}else {map.put(nums[i], 1);}}int maxCount=-1;int maxKey=-1;for(Integer key : map.keySet()){Integer value = map.get(key);if(value>=maxCount){maxCount=value;}}int l=0,r=0;int res=Integer.MAX_VALUE;for(Integer key : map.keySet()){Integer value = map.get(key);if(value==maxCount){maxKey=key;int lcount=1;for(int i=0;i<len;i++){if(lcount==1 && nums[i]==maxKey){lcount=0;l=i;}if(nums[i]==maxKey){r=i;}}res=Math.min(res,r-l+1);}}return res;} }

二分法

作者：LeetCode-Solution 鏈接：https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class Solution {public int maxScore(int[] cardPoints, int k) {int ans=0;int len=cardPoints.length;int sum=0;for(int i=0;i<k;i++){sum+=cardPoints[i];}ans=sum;for(int i=0;i<k;i++){sum+=cardPoints[len-i-1];sum-=cardPoints[k-i-1];ans=Math.max(ans,sum);}return ans;} } 作者：Y6blNU1L 鏈接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class Solution {public boolean search(int[] nums, int target) {boolean ans=false;int n = nums.length;if (nums== null || n == 0) {return false;}if (n == 1) {return nums[0] == target;}Arrays.sort(nums);int l=0,r=n-1,mid=0;while (l <= r) {mid = l + (r - l) / 2;if (nums[mid] == target) {return true;}if (nums[l] == nums[mid]) {l++;continue;}if (nums[l] < nums[mid]) {if (nums[mid] > target && nums[l] <= target) {r = mid - 1;} else {l = mid + 1;}} else {if (nums[mid] < target && nums[r] >= target) {l = mid + 1;} else {r = mid - 1;}}}return ans;} }

單鏈表

單鏈表基礎：https://www.cnblogs.com/whgk/p/6589920.html

• 頭結點：有時，在鏈表的第一個結點之前會額外增設一個結點，結點的數據域一般不存放數據（有些情況下也可以存放鏈表的長度等信息），此結點被稱為頭結點。

若頭結點的指針域為空（NULL），表明鏈表是空表。頭結點對于鏈表來說，不是必須的，在處理某些問題時，給鏈表添加頭結點會使問題變得簡單。
首元結點：鏈表中第一個元素所在的結點，它是頭結點后邊的第一個結點。

• 頭指針：永遠指向鏈表中第一個結點的位置（如果鏈表有頭結點，頭指針指向頭結點；否則，頭指針指向首元結點）。
• 頭結點和頭指針的區別：頭指針是一個指針，頭指針指向鏈表的頭結點或者首元結點；頭結點是一個實際存在的結點，它包含有數據域和指針域。兩者在程序中的直接體現就是：頭指針只聲明而沒有分配存儲空間，頭結點進行了聲明并分配了一個結點的實際物理內存。

單鏈表中可以沒有頭結點，但是不能沒有頭指針！

ListNode list=new ListNode(0) 初始化一個節點值為0的空節點，最常用最正規寫法

class Solution {public ListNode partition(ListNode head, int x) {ListNode small = new ListNode(0);ListNode smallHead = small;ListNode large = new ListNode(0);ListNode largeHead = large;while (head != null) {if (head.val < x) {small.next = head;small = small.next;} else {large.next = head;large = large.next;}head = head.next;}large.next = null;small.next = largeHead.next;//合并一條return smallHead.next;} }作者：LeetCode-Solution 鏈接：https://leetcode-cn.com/problems/partition-list/solution/fen-ge-lian-biao-by-leetcode-solution-7ade/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

優先隊列

隊列的核心思想就是先進先出，在優先級隊列中，數據按關鍵詞有序排列，插入新數據的時候，會自動插入到合適的位置保證隊列有序。（順序有兩種形式：升序或者是降序），優先級隊列底層的數據結構其實是一顆二叉堆。Java中PriorityQueue通過二叉小頂堆實現。

PriorityQueue是基于優先堆的一個無界隊列，這個優先隊列中的元素可以默認自然排序或者通過提供的Comparator（比較器）在隊列實例化的時排序。要求使用Java Comparable和Comparator接口給對象排序，并且在排序時會按照優先級處理其中的元素。

二叉堆有以下特征：

（1）二叉堆是一個完全二叉樹

（2）根節點總是大于左右子節點（大頂堆），或者是小于左右子節點（小頂堆）。

方法：

• add：插入一個元素，不成功會拋出異常
• offer：插入一個元素，不能被立即執行的情況下會返回一個特殊的值（true 或者 false）
• remove：刪除一個元素，如果不成功會返回false。
• poll：刪除一個元素，并返回刪除的元素
• **peek：獲取首元素但不刪除 **
• indexOf(Object o)：查詢對象o的索引
• contain(Object o)：判斷是否容納了元素

實例

PriorityQueue<Integer>q=new PriorityQueue<Integer>();q.offer(5);q.offer(7);q.offer(6);q.offer(4);q.offer(8);q.remove(8);//升序后刪除 刪除的是元素的值，若為空則刪除排序后的首元素System.out.println(q.peek());//獲取升序后的首元素但不刪除System.out.println(q);System.out.println(q.poll());//獲取升序后的首元素但刪除System.out.println(q);//獲取升序后的首元素但刪除 的排列順序 作者：LeetCode-Solution 鏈接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class KthLargest {PriorityQueue<Integer>que;int k;public KthLargest(int k, int[] nums) {this.k=k;que=new PriorityQueue<Integer>();for(int n: nums){add(n);}}public int add(int val) {que.offer(val);//增加元素if(que.size() >k){que.poll();//獲取首元素并刪除}return que.peek();//獲取首元素不刪除} }/*** Your KthLargest object will be instantiated and called as such:* KthLargest obj = new KthLargest(k, nums);* int param_1 = obj.add(val);*/

動態規劃

數組求和

思路： 原數組內增加長度1，出數組從索引 i 到 j（i ≤ j）范圍內元素的總和，包含 i、j兩點

// 0 --> 0 //1 0 0 --> 0 -2 -> -2 --> 表示nums中第1個數前值和 //2 1 1 --> -2 0 -> -2 --> 表示nums中第2個數前值和 //3 2 2 --> -2 3 -> 1 --> 表示nums中第3個數前值和class NumArray {int[] sum;public NumArray(int[] nums) {int len =nums.length;sum=new int[len+1];for(int i=0;i<len;i++){sum[i+1]=sum[i]+nums[i];}}public int sumRange(int i, int j) {return sum[j+1]-sum[i];} }作者：LeetCode-Solution 鏈接：https://leetcode-cn.com/problems/range-sum-query-immutable/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

一維前綴和

同上同理，只是二維數組轉成一維數組進行計算。

作者：LeetCode-Solution 鏈接：https://leetcode-cn.com/problems/range-sum-query-2d-immutable/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class NumMatrix {int[][]arr;public NumMatrix(int[][] matrix) {int r=matrix.length;if(r==0) return ;int c=matrix[0].length;arr=new int[r][c+1];for(int i=0;i<r;i++){for(int j=0;j<c;j++){arr[i][j+1]=arr[i][j]+matrix[i][j];}}}public int sumRegion(int row1, int col1, int row2, int col2) {int sum=0;for(int i=row1;i<=row2;i++){sum+=arr[i][col2+1]-arr[i][col1];}return sum;} }

二維前綴和

詳細具體參考：https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/ru-he-qiu-er-wei-de-qian-zhui-he-yi-ji-y-6c21/

作者：LeetCode-Solution 鏈接：https://leetcode-cn.com/problems/range-sum-query-2d-immutable/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class NumMatrix {/*** 二維前綴和*/int[][]arr;public NumMatrix(int[][] matrix) {int r=matrix.length;if(r==0) return ;int c=matrix[0].length;arr=new int[r+1][c+1];for(int i=0;i<r;i++){for(int j=0;j<c;j++){arr[i+1][j+1]=arr[i][j+1]+arr[i+1][j]-arr[i][j]+matrix[i][j];}}}public int sumRegion(int r1, int c1, int r2, int c2) {return arr[r2+1][c2+1] - arr[r1][c2+1]- arr[r2+1][c1] + arr[r1][c1];} }

動態規劃 + 回溯算法

我們只需要以首個字符為起點，枚舉以其開頭所有的回文串方案，加入集合，然后對剩下的字符串部分繼續爆搜。就能做到以任意字符作為回文串起點進行分割的效果了。

剩下的問題是，我們如何快速判斷連續一段 [i, j] 是否為回文串，因為爆搜的過程每個位置都可以作為分割點，復雜度為 O(2^n)O(2
n) 的。

因此我們不可能每次都使用雙指針去線性掃描一遍 [i, j] 判斷是否回文。

一個直觀的做法是，我們先預處理除所有的 f[i][j]，f[i][j] 代表 [i, j] 這一段是否為回文串。

預處理 f[i][j] 的過程可以用遞推去做。

要想 f[i][j] == true ，必須滿足以下兩個條件：

一、f[i + 1][j - 1] == true
二、s[i] == s[j]
由于狀態 f[[i][j]依賴于狀態 f[i + 1][j - 1]，因此需要我們左端點 i 是從大到小進行遍歷；而右端點 j 是從小到大進行遍歷。

因此，我們的遍歷過程可以整理為：右端點 j 一直往右移動（從小到大），在 j 固定情況下，左端點 i 在 j 在左邊開始，一直往左移動（從大到小）

鏈接：https://leetcode-cn.com/problems/palindrome-partitioning/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class Solution {public List<List<String>> partition(String s) {int n = s.length();char[] cs = s.toCharArray();// f[i][j] 代表 [i, j] 這一段是否為回文串boolean[][] f = new boolean[n][n];for (int j = 0; j < n; j++) {for (int i = j; i >= 0; i--) {// 當 [i, j] 只有一個字符時，必然是回文串if (i == j) {f[i][j] = true;} else {// 當 [i, j] 長度為 2 時，滿足 cs[i] == cs[j] 即回文串if (j - i + 1 == 2) {f[i][j] = cs[i] == cs[j];// 當 [i, j] 長度大于 2 時，滿足 (cs[i] == cs[j] && f[i + 1][j - 1]) 即回文串} else {f[i][j] = cs[i] == cs[j] && f[i + 1][j - 1];}}}}List<List<String>> ans = new ArrayList<>();List<String> cur = new ArrayList<>();dfs(s, 0, ans, cur, f);return ans;}/*** s: 要搜索的字符串* u: 以 s 中的那一位作為回文串分割起點* ans: 最終結果集* cur: 當前結果集* f: 快速判斷 [i,j] 是否為回文串*/void dfs(String s, int u, List<List<String>> ans, List<String> cur, boolean[][] f) {int n = s.length();if (u == n) ans.add(new ArrayList<>(cur));for (int i = u; i < n; i++) {if (f[u][i]) {cur.add(s.substring(u, i + 1));dfs(s, i + 1, ans, cur, f);cur.remove(cur.size() - 1);}}} }

動態轉移方程方程思想

思想：抽出動態規劃里非常重要的兩個概念：狀態和狀態轉移方程。

動態規劃算法通常基于一個遞推公式及一個或多個初始狀態。當前子問題的解將由上一次子問題的解推出。使用動態規劃來解題只需要多項式時間復雜度，因此它比回溯法、暴力法等要快許多。

鏈接：https://leetcode-cn.com/problems/distinct-subsequences/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class Solution {public int numDistinct(String s, String t) {int m = s.length(), n = t.length();if (m < n) {return 0;}int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {dp[i][n] = 1;}for (int i = m - 1; i >= 0; i--) {char sChar = s.charAt(i);for (int j = n - 1; j >= 0; j--) {char tChar = t.charAt(j);if (sChar == tChar) {dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];} else {dp[i][j] = dp[i + 1][j];}}}return dp[0][0];} } 鏈接：https://leetcode-cn.com/problems/longest-common-subsequence/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。詳解參考: https://leetcode-cn.com/problems/longest-common-subsequence/solution/fu-xue-ming-zhu-er-wei-dong-tai-gui-hua-r5ez6/class Solution {public int longestCommonSubsequence(String text1, String text2) {int m=text1.length(),n=text2.length();int dp[][]=new int[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(text1.charAt(i-1) == text2.charAt(j-1) ){dp[i][j] = dp[i-1][j-1] +1;}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return dp[m][n];} }

棧

Stack是棧；特點是：先進后出。

E push(E item) // 把項壓入堆棧頂部。E pop() //移除堆棧頂部的對象，并作為此函數的值返回該對象。 E peek() //查看堆棧頂部的對象，但不從堆棧中移除它。 boolean empty() //測試堆棧是否為空。 int search(Object o) // 返回對象在堆棧中的位置，以 1 為基數。 import java.util.Stack;public class StackX {public static void main(String[] args) {stackMethod();}//stack operatepublic static void stackMethod(){//定義一個Integer泛型的StackStack<Integer> stack = new Stack<Integer>();System.out.println("新建棧stack是否為空 : "+(stack.empty() ? "空" : stack.size()));//push : 把項壓入堆棧頂部，返回值泛型指定的類型//此處將1到5壓入棧中stack.push(1);stack.push(2);stack.push(3);stack.push(4);stack.push(5);System.out.println("將1到5按順序壓入棧中后為："+stack);//empty : 測試堆棧是否為空，size() == 0，返回值booleanSystem.out.println("值為1~5的棧中stack是否為空 : "+(stack.empty() ? "空" : stack.size()));//search : 返回對象在堆棧中的位置，以 1 為基數，參數：search(Object o) ，返回值intint oStack = stack.search(3);System.out.println("查找棧stack中對象3的位置elementId為 : "+oStack);//peek : 查看堆棧頂部的對象，但不從堆棧中移除它，返回值泛型指定的類型int topElement =stack.peek();System.out.println("查看stack的棧頂元素為 : "+topElement);System.out.println("peek操作stack后為 : "+stack);//pop : 移除堆棧頂部的對象，并作為此函數的值返回該對象，返回值泛型指定的類型int oRemove = stack.pop();System.out.println("移除stack棧頂的元素為 : "+oRemove);System.out.println("pop操作移除stack棧頂元素后為 : "+stack);} }輸出為:新建棧stack是否為空 : 空 將1到5按順序壓入棧中后為：[1, 2, 3, 4, 5] 值為1~5的棧中stack是否為空 : 5 查找棧stack中對象3的位置elementId為 : 3 查看stack的棧頂元素為 : 5 peek操作stack后為 : [1, 2, 3, 4, 5] 移除stack棧頂的元素為 : 5 pop操作移除stack棧頂元素后為 : [1, 2, 3, 4]//自定義獲取棧的的值 class Solution {public boolean isValidSerialization(String preorder) {Deque<String> stack = new LinkedList<>();for (String s : preorder.split(",")) {stack.push(s);while (stack.size() >= 3&& ((LinkedList<String>) stack).get(0).equals("#")&& ((LinkedList<String>) stack).get(1).equals("#")&& !((LinkedList<String>) stack).get(2).equals("#")) {stack.pop();stack.pop();stack.pop();stack.push("#");}}return stack.size() == 1 && stack.pop().equals("#");} }

隊列

隊列是線性表的一種，在操作數據元素時，和棧一樣，有自己的規則：使用隊列存取數據元素時，數據元素只能從表的一端進入隊列，另一端出隊列。特點是先進先出。

Deque

Deque是Queue的子接口。

Deque有兩個比較重要的類：ArrayDeque和LinkedList

建議 使用棧時，用ArrayDeque的push和pop方法；

使用隊列時，使用ArrayDeque的add和remove方法。

三種用途

• 普通隊列(一端進另一端出):
  Queue queue = new LinkedList()或Deque deque = new LinkedList()
• 雙端隊列(兩端都可進出)
  Deque deque = new LinkedList()
• 堆棧
  Deque deque = new LinkedList()

Java官方推薦使用Deque替代Stack使用。Deque堆棧操作方法：push()、pop()、peek()。

詳細參考：https://blog.csdn.net/devnn/article/details/82716447

實例

作者：Y6blNU1L 鏈接：https://leetcode-cn.com/problems/basic-calculator-ii/solution/227-ji-ben-ji-suan-qi-ii-javayong-dequed-zci2/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。class Solution {public int calculate(String s) {//Deque堆棧操作Deque<Integer> stack = new LinkedList<Integer>();char sign = '+';int num = 0;int n = s.length();for (int i = 0; i < n; ++i) {if (Character.isDigit(s.charAt(i))) {//為數字num = num * 10 + s.charAt(i) - '0';}if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {//為字符switch (sign) {case '+':stack.push(num);// System.out.println("+"+stack);break;case '-':stack.push(-num);// System.out.println("-"+stack);break;case '*':stack.push(stack.pop() * num);// System.out.println("*"+stack);break;default:stack.push(stack.pop() / num);// System.out.println("/"+stack);}sign = s.charAt(i);num = 0;}}int ans = 0;while (!stack.isEmpty()) {ans += stack.pop();}return ans;} }

Queue

Queue是java中實現隊列的接口，它總共只有6個方法，我們一般只用其中3個就可以了。Queue的實現類有LinkedList和PriorityQueue。最常用的實現類是LinkedList。

Queue的6個方法分類：

壓入元素(添加)：add()、offer()
相同：未超出容量，從隊尾壓入元素，返回壓入的那個元素。
區別：在超出容量時，add()方法會對拋出異常，offer()返回false

彈出元素(刪除)：remove()、poll()
相同：容量大于0的時候，刪除并返回隊頭被刪除的那個元素。
區別：在容量為0的時候，remove()會拋出異常，poll()返回false

獲取隊頭元素(不刪除)：element()、peek()
相同：容量大于0的時候，都返回隊頭元素。但是不刪除。
區別：容量為0的時候，element()會拋出異常，peek()返回null。

詳細參考：https://blog.csdn.net/devnn/article/details/82591349

public class QueueTest {public static void main(String[] args) {Queue<String> queue = new LinkedList();queue.offer("元素A");queue.offer("元素B");queue.offer("元素C");queue.offer("元素D");queue.offer("元素E");while (queue.size() > 0) {String element = queue.poll();System.out.println(element);}} }輸出:元素A 元素B 元素C 元素D 元素E

二叉樹

• 根（Root）：樹中最頂端的節點，根沒有父節點。
• 子節點（Child）：節點所擁有子樹的根節點稱為該節點的子節點。
• 父節點（Parent）：如果節點擁有子節點，則該節點為子節點的父節點。
• 兄弟節點（Sibling）：與節點擁有相同父節點的節點。
• 子孫節點（Descendant）：節點向下路徑上可達的節點。
• 葉節點（Leaf）：沒有子節點的節點。
• 內節點（Internal Node）：至少有一個子節點的節點。
• 度（Degree）：節點擁有子樹的數量。
• 邊（Edge）：兩個節點中間的鏈接。
• 路徑（Path）：從節點到子孫節點過程中的邊和節點所組成的序列。
• 層級（Level）：根為 Level 0 層，根的子節點為 Level 1 層，以此類推。
• 高度（Height）/深度（Depth）：樹中層的數量。比如只有 Level 0,Level 1,Level 2 則高度為 3。

二叉搜索樹

二叉搜索樹是一種節點值之間具有一定數量級次序的二叉樹，對于樹中每個節點：

• 若其左子樹存在，則其左子樹中每個節點的值都不大于該節點值；
• 若其右子樹存在，則其右子樹中每個節點的值都不小于該節點值。

觀察二叉搜索樹結構可知，二叉樹節點個數確定的情況下，整顆樹的高度越低，節點的查詢復雜度越低。

遍歷樹

遍歷指的是按照某種特定的次序來訪問二叉搜索樹中的每個節點，主要有三種遍歷的方法：

前序遍歷，“根左右”

中序遍歷，“左根右”

后續遍歷，“左右根”

上面的口訣“中左右”表示的含義是，先訪問根節點，再訪問左子，最后訪問右子。舉個例子：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-UzQlNmla-1618277790358)(https://z3.ax1x.com/2021/04/13/cruyVJ.jpg)]

• 前序遍歷：39 24 23 30 64 53 60
• 中序遍歷：23 24 30 39 53 60 64
• 后序遍歷：23 30 24 60 53 64 39

詳細參考博客： https://www.cnblogs.com/yahuian/p/10813614.html

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 來源：力扣（LeetCode） 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。/*** 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 {int pre;int ans;public int minDiffInBST(TreeNode root) {ans = Integer.MAX_VALUE;pre = -1;dfs(root);return ans;}public void dfs(TreeNode root) {if (root == null) {return;}//中序遍歷dfs(root.left);if (pre == -1) {pre = root.val;} else {ans = Math.min(ans, root.val - pre);pre = root.val;}dfs(root.right);} }

總結

以上是生活随笔為你收集整理的算法笔记总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。