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