如何做网站写手/如何建网址

其他:

今日总结
往期打卡

---

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;}
}

---

总结

今天学习了回文数以及二叉树应用双指针跨节点操作

往期打卡

代码随想录算法训练营第十五天

代码随想录算法训练营第十四天

代码随想录算法训练营第十三天

代码随想录算法训练营第十二天

代码随想录算法训练营第十一天

代码随想录算法训练营周末二

代码随想录算法训练营第十天

代码随想录算法训练营第九天

代码随想录算法训练营第八天

代码随想录算法训练营第七天

代码随想录算法训练营第六天

代码随想录算法训练营第五天

代码随想录算法训练营周末一

代码随想录算法训练营第四天

代码随想录算法训练营第三天

代码随想录算法训练营第二天

代码随想录算法训练营第一天