其他:

今日總結
往期打卡

---

530. 二叉搜索樹的最小絕對差

跳轉: 530. 二叉搜索樹的最小絕對差

學習: 代碼隨想錄公開講解

問題:

給你一個二叉搜索樹的根節點 root ，返回 樹中任意兩不同節點值之間的最小差值 。

差值是一個正數，其數值等于兩值之差的絕對值。

思路:

已知,二叉搜索樹中序遍歷是非遞減序列,所以只需要中序遍歷一一求差值,并記錄最小即可.
因為涉及到兩步操作,所以可以先獲得數組再操作數組,或者使用雙指針.

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$(不計遞歸棧占用)

代碼(雙指針):

class Solution {int pre=-1;int min=Integer.MAX_VALUE;public void getDiff(TreeNode root){if(root==null) return ;getDiff(root.left);if(pre!=-1) min = Math.min(root.val-pre,min);pre = root.val;getDiff(root.right);}public int getMinimumDifference(TreeNode root) {getDiff(root);return min;}
}

---

501. 二叉搜索樹中的眾數

跳轉:501. 二叉搜索樹中的眾數

學習: 代碼隨想錄公開講解

問題:

給你一個含重復值的二叉搜索樹（BST）的根節點 root ，找出并返回 BST 中的所有 眾數（即，出現頻率最高的元素）。

如果樹中有不止一個眾數，可以按 任意順序 返回。

假定 BST 滿足如下定義：

• 結點左子樹中所含節點的值 小于等于 當前節點的值
• 結點右子樹中所含節點的值 大于等于 當前節點的值
• 左子樹和右子樹都是二叉搜索樹

思路:

這題還是利用二叉搜索樹的性質,非遞減序列可以方便統計,每次統計的結尾部分做一次比較判斷集合添加與清空即可;
設計前后比較,還是可以使用雙指針一遍遍歷解決.

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(n)$

代碼雙指針:

class Solution {int max = 0;int curFrequency = 0;int pre = -100001;int[] maximumNodeValues;int count = 0;void traverse(TreeNode root) {if (root == null)return;traverse(root.left);if (root.val == pre)curFrequency++;else {if (curFrequency > max) {max = curFrequency;maximumNodeValues = new int[10000];count = 0;}if (curFrequency == max) {maximumNodeValues[count++] = pre;}curFrequency = 1;pre = root.val;}traverse(root.right);}public int[] findMode(TreeNode root) {maximumNodeValues = new int[10000];traverse(root);if (curFrequency > max) {max = curFrequency;maximumNodeValues = new int[10000];count = 0;}if (curFrequency == max) {maximumNodeValues[count++] = pre;}int[] ans = new int[count];System.arraycopy(maximumNodeValues, 0, ans, 0, count);return ans;}
}

---

236. 二叉樹的最近公共祖先

跳轉:236. 二叉樹的最近公共祖先

學習: 代碼隨想錄公開講解

問題:

給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”

思路:

返回第一次左右節點分別包含q,p或者上層的q或p
所以這題使用后序遍歷比較合適

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$

代碼:

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) {return root;}TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);if(left==null&&right==null) return null;if(left!=null&&right==null) return left;if(right!=null&&left==null) return right;return root;}
}

---

3272. 統計好整數的數目(每日一題)

跳轉: 3272. 統計好整數的數目

學習: 靈茶山艾府公開講解

問題:

給你兩個 正 整數 n 和 k 。

如果一個整數 x 滿足以下條件，那么它被稱為 k 回文 整數 。

• x 是一個 回文整數 。
• x 能被 k 整除。

如果一個整數的數位重新排列后能得到一個 k 回文整數 ，那么我們稱這個整數為 好 整數。比方說，k = 2 ，那么 2020 可以重新排列得到 2002 ，2002 是一個 k 回文串，所以 2020 是一個好整數。而 1010 無法重新排列數位得到一個 k 回文整數。

請你返回 n 個數位的整數中，有多少個 好 整數。

注意 ，任何整數在重新排列數位之前或者之后 都不能 有前導 0 。比方說 1010 不能重排列得到 101 。

思路:

回文子串可以用左半邊遍歷的方式獲得

題目中的好整數是調整之后的,為了不重復,需要哈希記錄等價的值,可以按各位數字排序后記錄字符串

每一個回文數會有多種排序,其排序的公式如下
cntn是數字n的個數

復雜度:

• 時間復雜度: $O(nlogn)$
• 空間復雜度: $O(n)$

代碼:

class Solution {public long countGoodIntegers(int n, int k) {int[] factorial = new int[n+1];factorial[0] = 1;for(int i=1;i<=n;i++){factorial[i] = factorial[i-1]*i;}long ans = 0;Set<String> vis = new HashSet<>();int base = (int)Math.pow(10,(n-1)/2);for(int i = base;i<base*10;i++){String s = Integer.toString(i);s += new StringBuilder(s).reverse().substring(n%2);if(Long.parseLong(s)%k>0) continue;char[] sortedS = s.toCharArray();Arrays.sort(sortedS);if(!vis.add(new String(sortedS))) continue;int[] cnt = new int[10];for(char c:sortedS){cnt[c-'0']++;}int res = (n-cnt[0])*factorial[n-1];for(int c:cnt){res /= factorial[c];}ans+=res;}return ans;}
}

---

總結

今天學習了回文數以及二叉樹應用雙指針跨節點操作

往期打卡

代碼隨想錄算法訓練營第十五天

代碼隨想錄算法訓練營第十四天

代碼隨想錄算法訓練營第十三天

代碼隨想錄算法訓練營第十二天

代碼隨想錄算法訓練營第十一天

代碼隨想錄算法訓練營周末二

代碼隨想錄算法訓練營第十天

代碼隨想錄算法訓練營第九天

代碼隨想錄算法訓練營第八天

代碼隨想錄算法訓練營第七天

代碼隨想錄算法訓練營第六天

代碼隨想錄算法訓練營第五天

代碼隨想錄算法訓練營周末一

代碼隨想錄算法訓練營第四天

代碼隨想錄算法訓練營第三天

代碼隨想錄算法訓練營第二天

代碼隨想錄算法訓練營第一天