Java每日一练(20230318)

创始人

2025-05-30 04:01:15

0次

1. 只出现一次的数字 🌟

2. 不同的二叉搜索树 🌟🌟

3. 寻找两个正序数组的中位数 🌟🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

1. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

代码：

class Solution {public int singleNumber(int[] nums){int res = 0;for (int num : nums){res ^= num;}return res;}
};

2. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

代码：

class Solution {public int numTrees(int n){if (n < 2){return 1;}int[] count = new int[n + 1];count[0] = 1;count[1] = 1;for (int i = 2; i <= n; i++){int sum = 0;for (int root = 1; root <= i; root++){sum += count[root - 1] * count[i - root];}count[i] = sum;}return count[n];}
};

二叉搜索树

若它的左子树不空，则左子树上所有结点的值均小于它根结点的值。
若它的右子树不空，则右子树上所有结点的值均大于它根结点的值。
它的左、右树又分为二叉排序树

构建二叉排序树

假设有以下数据，按从左到右的顺序来构建二叉排序树。

二叉排序树构建过程：

首先，将8作为根节点
插入3，由于3小于8，作为8的左子树
插入10，由于10大于8，作为8的右子树
插入1，由于1小于8，进入左子树3，1又小于3，则1为3的左子树
插入6，由于6小于8，进入左子树3，6又大于3，则6为3的右子树
插入14，由于14大于8，进入右子树10，14又大于10，则14为10的右子树
插入4，由于4小于8，进入左子树3，4又大于3，进入右子树6，4还小于6，则4为6的左子树
插入7，由于7小于8，进入左子树3，7又大于3，进入右子树6，7还大于于6，则7为6的右子树
插入13，由于13大于8，进入右子树10，又13大于10，进入右子树14,13小于14，则13为14的左子树

只要左子树为空，就把小于父节点的数插入作为左子树
只要右子树为空，就把大于父节点的数插入作为右子树
如果不为空，就一直往下去搜索，直到找到合适的插入位置

任意一树二叉搜索树的水平投影都是有序的，也就是中序遍历的结果是有序的。

3. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

代码：

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int nums1Size = nums1.length;int nums2Size = nums2.length;int na = nums1Size + nums2Size;int[] ns = new int[4 * na];int i = 0, j = 0, d = 0;int m = na / 2 + 1;while (d < m) {int n = 0;if (i < nums1Size && j < nums2Size) {n = (nums1[i] < nums2[j]) ? nums1[i++] : nums2[j++];} else if (i < nums1Size) {n = nums1[i++];} else if (j < nums2Size) {n = nums2[j++];}ns[d++] = n;}if (na % 2 == 1) {return ns[d - 1];}return (ns[d - 1] + ns[d - 2]) / 2.0;}
}