题026复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
解法：
首先想到的第一步： 复制每个节点，让后用next连接起来 第二部 设置随机指针 需要从头部找
每个随即指针都需要O(n） 所以复杂度为O(n^)
- 复制每一个节点，使得复制后的节点都在当前节点的下一个节点
- 原生链表的节点的指向任意节点，使复制的节点也都指向某一任意节点
- 重新连接节点，把原生节点重新连接起来，把克隆后的节点连接起来
class Solution {
public Node copyRandomList(Node pHead) {
if (pHead == null)
return null;
// 插入新节点
Node cur = pHead;
while (cur != null) {
Node clone = new Node(cur.val); //复制当前节点
clone.next = cur.next; //复制节点指向下一个节点
cur.next = clone; //当前节点指向复制节点
cur = clone.next; //当前节点 变为下个节点
}
// 建立 random 链接
cur = pHead;
while (cur != null) {
Node clone = cur.next;
if (cur.random != null)
clone.random = cur.random.next;
cur = clone.next; //当前节点 变为下个节点
}
// 拆分
cur = pHead;
Node pCloneHead = pHead.next;
while (cur.next != null) {
Node next = cur.next;
cur.next = next.next;
cur = next;
}
return pCloneHead;
}
}
题027二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
解法：
二叉搜索树得中序遍历为递增序列
class Solution {
Node head, pre;
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
dfs(root);
head.left = pre; // 首尾指针指针相连
pre.right = head;
return head;
}
void dfs(Node cur) {
if (cur == null) {
return;
}
dfs(cur.left);
if (pre != null) {
pre.right = cur;
} else {
head = cur;
}
cur.left = pre; // pre 是否为 null无影响
pre = cur; // pre指向当前cur
dfs(cur.right);
}
}
题028字符串得排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
class Solution {
List<String> res = new LinkedList<>();
char[] c;
public String[] permutation(String s) {
c = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
void dfs(int x) {
if(x == c.length - 1) { //结束条件 达到第三层
res.add(String.valueOf(c)); // 添加排列方案
return;
}
HashSet<Character> set = new HashSet<>();
for(int i = x; i < c.length; i++) {
if(set.contains(c[i])) continue; // 重复，因此剪枝
set.add(c[i]);
swap(i, x); // 交换，将 c[i] 固定在第 x 位
//返回时交换回来，这样保证到达第1层的时候，一直都是abc。这里捋顺一下，开始一直都是abc，那么第一位置总共就3个位置
//分别是a与a交换，这个就相当于 x = 0, i = 0;
// a与b交换 x = 0, i = 1;
// a与c交换 x = 0, i = 2;
//就相当于上图中开始的三条路径
//第一个元素固定后，每个引出两条路径,
// b与b交换 x = 1, i = 1;
// b与c交换 x = 1, i = 2;
//所以，结合上图，在每条路径上标注上i的值，就会非常容易好理解了
dfs(x + 1); // 开启固定第 x + 1 位字符
swap(i, x); // 恢复交换 回溯
}
}
void swap(int a, int b) {
char tmp = c[a];
c[a] = c[b];
c[b] = tmp;
}
}
举一反三
按照一定要求摆放若干个数字，先求出这些数字的所有排列，然后再一一判断每个排列是否满足
复杂问题： 画图 举例子 分解 能够帮助解决复杂问题
题029 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
解法一： 哈希表
public int majorityElement(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
//如果已经存在key，将值+1
int cnt = map.get(nums[i]) + 1;
if ((cnt * 2) > nums.length) {
return nums[i];
}
map.put(nums[i], cnt);
} else {
map.put(nums[i], 1);
}
}
return 0;
}
解法二：摩尔投票法
若一个数字出现的次数超过数组长度的一半，则该数字减去其他数字个数必定大于0，根据这个原理，使用摩尔法投票法，记录一个数字，遍历数组，若是该数，票数加一，不是减一，为零下次出现什么都投一票，记录值变为下次出现的值。最后，记录中必定是出现过半的数字！
核心理念为 “正负抵消” ；时间和空间复杂度分别为 O(N) 和 O(1)
public int majorityElement(int[] nums) {
int x = 0, votes = 0; //众数 统计票数
for (int num : nums) {
if (votes == 0) {
x = num; //如果票数为0 则当前数为众数
}
int vote = num == x ? 1 : -1; //如果为众数,加一 否则减一
votes = votes + vote;
}
return x;
}
题030最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
对于经典TopK问题，本文给出 4 种通用解决方案。
解法一：使用快排切分思想 当我们可以修改输入数组可用
不需要对整个数组进行他O(nlogn)的排序
时间复杂度O(n)
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 找前k个 最后一个下标为k -1 即基准的下标
return quick(arr, 0, arr.length - 1, k - 1);
}
private static int[] quick(int[] arr, int left, int right, int k) {
//如果k == j 就返回 j 及 j左边所有的数
int j = partition(arr, left, right);
if (k == j) {
return Arrays.copyOf(arr, j + 1);
}
// 否则根据j 与 k的关系来决定 继续切分 左段 和 右端
return j > k ? quick(arr, left, j - 1, k) : quick(arr, j + 1, right, k);
}
private static int partition(int[] a, int low, int high) {
//取每个序列的第一个值作为基准值
int pivotkey = a[low];
while (low < high) {
//从序列的右边开始往左遍历，直到找到小于基准值的元素
while (high > low && a[high] >= pivotkey) {
high--;
}
//将元素直接赋予给左边第一个，即pivotkey所在的位置
a[low] = a[high];
//从序列的左边边开始往右遍历，直到找到大于基准值的元素
while (high > low && a[low] <= pivotkey) {
low++;
}
//此时的a[high]<pivotkey,已经被赋予到左边，所以可以将元素赋予给a[high]
a[high] = a[low];
}
//最后的low是基准值所在的位置
a[low] = pivotkey;
return low;
}
解法二：堆 大根堆(前 K 小) / 小根堆（前 K 大) O(NlogK) 海量数据
本题是求前 K 小，因此用一个容量为 K 的大根堆，每次 poll 出最大的数，那堆中保留的就是前 K 小啦（注意不是小根堆！小根堆的话需要把全部的元素都入堆，那是 O(NlogN)，就不是 O(NlogK)啦～～）
class Solution {
// 保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
// 1. 若目前堆的大小小于K，将当前数字放入堆中。
// 2. 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；
// 反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 默认是小根堆，实现大根堆需要重写一下比较器。
Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
for (int num: arr) {
if (pq.size() < k) {
pq.offer(num);
} else if (num < pq.peek()) {
pq.poll();
pq.offer(num);
}
}
// 返回堆中的元素
int[] res = new int[pq.size()];
int idx = 0;
for(int num: pq) {
res[idx++] = num;
}
return res;
}
}
**解法三：二叉搜索树O(NlogK) 海量数据 **
与前两种方法相比，最大的好处是前k大的数字是有序的
因为有重复的数字，所以用的是 TreeMap 而不是 TreeSet
TreeMap的key 是数字，value 是该数字的个数。 我们遍历数组中的数字，维护一个数字总个数为 K 的 TreeMap： 1.若目前 map 中数字个数小于 K，则将 map 中当前数字对应的个数 +1； 2.否则，判断当前数字与 map 中最大的数字的大小关系：若当前数字大于等于 map 中的最大数字，就直接跳过该数字；若当前数字小于 map 中的最大数字，则将 map 中当前数字对应的个数 +1，并将 map 中最大数字对应的个数减 1
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// TreeMap的key是数字, value是该数字的个数。
// cnt表示当前map总共存了多少个数字。
TreeMap<Integer, Integer> map = new TreeMap<>();
int cnt = 0;
for (int num : arr) {
// 1. 遍历数组，若当前map中的数字个数小于k，则map中当前数字对应个数+1
if (cnt < k) {
map.put(num, map.getOrDefault(num, 0) + 1);
cnt++;
continue;
}
// 2. 否则，取出map中最大的Key（即最大的数字), 判断当前数字与map中最大数字的大小关系：
// 若当前数字比map中最大的数字还大，就直接忽略；
// 若当前数字比map中最大的数字小，则将当前数字加入map中，并将map中的最大数字的个数-1。
Map.Entry<Integer, Integer> entry = map.lastEntry();
if (entry.getKey() > num) {
map.put(num, map.getOrDefault(num, 0) + 1);
if (entry.getValue() == 1) {
map.pollLastEntry();
} else {
map.put(entry.getKey(), entry.getValue() - 1);
}
}
}
// 最后返回map中的元素
int[] res = new int[k];
int idx = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int freq = entry.getValue();
while (freq-- > 0) {
res[idx++] = entry.getKey();
}
}
return res;
}
}
解法四：数据范围有限时直接计数排序就行了：O(N)
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 统计每个数字出现的次数
int[] counter = new int[10001];
for (int num: arr) {
counter[num]++;
}
// 根据counter数组从头找出k个数作为返回结果
int[] res = new int[k];
int idx = 0;
for (int num = 0; num < counter.length; num++) {
while (counter[num]-- > 0 && idx < k) {
res[idx++] = num;
}
if (idx == k) {
break;
}
}
return res;
}
}
题031连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
动态规划
/**
* 考虑到在dp列表中，dp[i]只和dp[i-1]有关,
* 所以用两个参数存储循环过程中的dp[i]和dp[i-1]的值即可
*/
public int maxSubArray(int[] nums) {
int max = nums[0];
int former = 0;//用于记录dp[i-1]的值，对于dp[0]而言，其前面的dp[-1]=0
int cur = nums[0];//用于记录dp[i]的值
for (int num : nums) {
cur = num;
//如果dp[i-1]即former大于0 则dp[i] = dp[i-1] + num[i] 否则为num[i]
if (former > 0) {
cur += former;
}
//记录最大值 返回
if (cur > max) {
max = cur;
}
former = cur;
}
return max;
}
题032 1~n整数中1出现的次数
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12
输出：5
解法：找规律
class Solution {
public int countDigitOne(int n) {
int digit = 1, res = 0;
int high = n / 10, cur = n % 10, low = 0;
while (high != 0 || cur != 0) {
if (cur == 0) {
res += high * digit;
} else if (cur == 1) {
res += high * digit + low + 1;
} else {
res += (high + 1) * digit;
}
low += cur * digit;
cur = high % 10;
high /= 10;
digit *= 10;
}
return res;
}
}
题033把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [3,30,34,5,9]
输出: "3033459"
解法：
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
fastSort(strs, 0, strs.length - 1);
StringBuilder res = new StringBuilder();
for (String s : strs) {
res.append(s);
}
return res.toString();
}
private String[] fastSort(String[] arr, int left, int right) {
if (left < right) { //left right一直变化 直到left <right递归结束
int partitionIndex = partition(arr, left, right);
fastSort(arr, left, partitionIndex - 1);
fastSort(arr, partitionIndex + 1, right);
}
return arr;
}
private int partition(String[] a, int low, int high) {
//取每个序列的第一个值作为基准值
String pivotkey = a[low];
while (low < high) {
//从序列的右边开始往左遍历，直到找到小于基准值的元素
while (high > low && (a[high] + pivotkey).compareTo(pivotkey + a[high]) >= 0) {
high--;
}
//将元素直接赋予给左边第一个，即pivotkey所在的位置
a[low] = a[high];
//从序列的左边边开始往右遍历，直到找到大于基准值的元素
while (high > low && (a[low] + pivotkey).compareTo(pivotkey + a[low]) <= 0) {
low++;
}
//此时的a[high]<pivotkey,已经被赋予到左边，所以可以将元素赋予给a[high]
a[high] = a[low];
}
//最后的low是基准值所在的位置
a[low] = pivotkey;
return low;
}
}
题034丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
解法：动态规划
一个丑数乘以 2， 3， 5 之后， 一定还是一个丑数。
并且如果从丑数序列首个元素开始 *2 *3 *5 来计算， 丑数序列也是不会产生漏解的。
丑数的排列 假设当前存在 3 个数组 nums2, nums3, nums5 分别代表丑数序列从 1 开始分别乘以 2, 3, 5 的序列， 即
nums2 = {1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2...}
nums3 = {1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3...}
nums5 = {1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5...}
注意 7 不是丑数.
2, 3, 5 这前 3 个丑数一定要乘以其它的丑数， 所得的结果才是新的丑数， 所以上例中没有出现 72, 73, 7*5
那么， 最终的丑数序列实际上就是这 3 个有序序列对的合并结果， 计算丑数序列也就是相当于 合并 3 个有序序列。
合并 3 个有序序列 合并 3 个有序序列， 最简单的方法就是每一个序列都各自维护一个指针， 然后比较指针指向的元素的值， 将最小的放入最终的合并数组中， 并将相应指针向后移动一个元素。 这也就是：
class Solution {
public:
int nthUglyNumber(int n) {
// ....
dp[i] = min(min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5);
if (dp[i] == dp[p2] * 2)
p2++;
if (dp[i] == dp[p3] * 3)
p3++;
if (dp[i] == dp[p5] * 5)
p5++;
// ......
};
合并过程中重复解的处理 nums2, nums3, nums5 中是存在重复的解的， 例如 nums2[2] == 32, nums3[1] == 23 都计算出了 6 这个结果， 所以在合并 3 个有序数组的过程中， 还需要跳过相同的结果， 这也就是为什么在比较的时候， 需要使用 3 个并列的 if… if… if… 而不是 if… else if… else 这种结构的原因。 当比较到元素 6 时， if (dp[i] == dp[p2] * 2)…if (dp[i] == dp[p3] * 3)… 可以同时指向 nums2, nums3 中 元素 6 的下一个元素。
代码
public int nthUglyNumber(int n) {
int a = 0, b = 0, c = 0;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
dp[i] = Math.min(Math.min(n2, n3), n5);
if (dp[i] == n2) {
a++;
}
if (dp[i] == n3) {
b++;
}
if (dp[i] == n5) {
c++;
}
}
return dp[n - 1];
}
题035第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例:
s = "abaccdeff"
返回 "b"
s = ""
返回 "
解法一：哈希表
public char firstUniqChar(String s) {
HashMap<Character, Boolean> dic = new HashMap<>();
char[] sc = s.toCharArray();
for (char c : sc) {
dic.put(c, !dic.containsKey(c));
}
for (char c : sc) {
if (dic.get(c)) {
return c;
}
}
return ' ';
}
解法二：有序哈希表
Map<Character, Boolean> dic = new LinkedHashMap<>();
char[] sc = s.toCharArray();
for(char c : sc)
dic.put(c, !dic.containsKey(c));
for(Map.Entry<Character, Boolean> d : dic.entrySet()){
if(d.getValue()) return d.getKey();
}
return ' ';
复杂度分析： 时间和空间复杂度均与 “方法一” 相同，而具体分析时间复杂度：
方法一 O(2N) ： N 为字符串 s 的长度；需遍历 s 两轮； 方法二 O(N) ：遍历 s 一轮，遍历 dic 一轮。
当字符串很长（重复字符很多）时，方法二则效率更高。
空间复杂度 O(N) ： HashMap 需存储 N个字符的键值对，使用 O(N) 大小的额外空间。
题036数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
解法一：分治思想 （归并排序 ）
合并两个有序数组时，利用数组的部分有序性，一下子计算出一个数之前或者之后元素的逆序的个数。
两者不能同时计算，否则会计算重复。
class Solution {
public int reversePairs(int[] nums) {
int len = nums.length;
if (len < 2) {
return 0;
}
return sort(nums, 0, len - 1);
}
public int sort(int[] arr, int left, int right) {
// 递归终止条件
if (left >= right) {
return 0;
}
// 获取 left right 之间的中间位置
int mid = left + ((right - left) / 2);
// 分治递归
int leftCount = sort(arr, left, mid);
int rightCount = sort(arr, mid + 1, right);
int mergeCount = merge(arr, left, mid, right);
return leftCount + rightCount + mergeCount;
}
// 合并数据
public int merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
int count = 0;
// 比较左右两部分的元素，哪个小，把那个元素填入temp中
while (p1 <= mid && p2 <= right) {
if (arr[p1] <= arr[p2]) {
temp[i++] = arr[p1++];
} else {
temp[i++] = arr[p2++];
count += (mid - p1 + 1);
}
}
// 上面的循环退出后，把剩余的元素依次填入到temp中
// 以下两个while只有一个会执行
while (p1 <= mid) {
temp[i++] = arr[p1++];
}
while (p2 <= right) {
temp[i++] = arr[p2++];
}
// 把最终的排序的结果复制给原数组
for (i = 0; i < temp.length; i++) {
arr[left + i] = temp[i];
}
return count;
}
}
题037两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
双指针法，浪漫相遇
我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode node1 = headA;
ListNode node2 = headB;
while (node1 != node2) {
node1 = node1 != null ? node1.next : headB;
node2 = node2 != null ? node2.next : headA;
}
return node1;
}
题038数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
解法：二分
代码：
public int search(int[] nums, int target) {
//target的有边界 减去 target-1的右边界
return helper(nums, target) - helper(nums, target - 1);
}
int helper(int[] nums, int tar) {
int i = 0, j = nums.length - 1;
while (i <= j) {
int m = (i + j) / 2;
if (nums[m] <= tar) { //等于的时候 找到右边界
i = m + 1;
} else {
j = m - 1;
}
}
return i;
}
题039二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3
树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）；
常见的 DFS ： 先序遍历、中序遍历、后序遍历； 常见的 BFS ： 层序遍历（即按层遍历）。 求树的深度需要遍历树的所有节点，本文将介绍基于 后序遍历（DFS） 和 层序遍历（BFS） 的两种解法。
深度优先遍历（DFS）
树的后序遍历 / 深度优先搜索往往利用 递归 或 栈 实现，本文使用递归实现
public int maxDepth(TreeNode root) {
//终止条件 最后返回0
if (root == null) {
return 0;
}
//每层回溯时加1 并判断左右子树最大的返回
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
复杂度： 时间复杂度O(N) 空间复杂度O(N)
广度优先遍历（BFS）
- 特例处理： 当
root为空，直接返回 深度 00 。 - 初始化： 队列
queue（加入根节点root），计数器res = 0。 - 循环遍历： 当
queue为空时跳出
- 初始化一个空列表 tmp ，用于临时存储下一层节点；
- 遍历队列： 遍历 queue 中的各节点 node ，并将其左子节点和右子节点加入 tmp；
- 更新队列： 执行 queue = tmp ，将下一层节点赋值给 queue；
- 统计层数： 执行 res += 1 ，代表层数加 11
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
List<TreeNode> queue = new LinkedList<>() , tmp;
int res = 0;
while (!queue.isEmpty()) {
tmp = new LinkedList<>();
for (TreeNode node : queue) {
if (node.left != null) {
tmp.add(node.left);
}
if (node.right != null) {
tmp.add(node.right);
}
}
queue = tmp;
res++;
}
return res;
}
题040数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
解法：分组异或
相同两个数字异或结果为0
由于数组中存在着两个数字不重复的情况，我们将所有的数字异或操作起来，最终得到的结果是这两个数字的异或结果：(相同的两个数字相互异或，值为0)) 最后结果一定不为0，因为有两个数字不重复。
演示：
4 ^ 1 ^ 4 ^ 6 => 1 ^ 6
6 对应的二进制： 110
1 对应的二进制： 001
1 ^ 6 二进制： 111
此时我们无法通过 111（二进制），去获得 110 和 001。 那么当我们可以把数组分为两组进行异或，那么就可以知道是哪两个数字不同了。 我们可以想一下如何分组：
- 重复的数字进行分组，很简单，只需要有一个统一的规则，就可以把相同的数字分到同一组了。例如：奇偶分组。因为重复的数字，数值都是一样的，所以一定会分到同一组！
- 此时的难点在于，对两个不同数字的分组。 此时我们要找到一个操作，让两个数字进行这个操作后，分为两组。 我们最容易想到的就是 & 1 操作， 当我们对奇偶分组时，容易地想到 & 1，即用于判断最后一位二进制是否为 1。来辨别奇偶。 你看，通过 & 运算来判断一位数字不同即可分为两组，那么我们随便两个不同的数字至少也有一位不同吧！ 我们只需要找出那位不同的数字mask，即可完成分组（ & mask ）操作。
由于两个数异或的结果就是两个数数位不同结果的直观表现，所以我们可以通过异或后的结果去找 mask！ 所有的可行 mask 个数，都与异或后1的位数有关。
num1: 101110 110 1111
num2: 111110 001 1001
num1^num2: 010000 111 0110
可行的mask: 010000 001 0010
010 0100
100
为了操作方便，我们只去找最低位的mask:
代码：
public int[] singleNumbers(int[] nums) {
//xor用来计算nums的异或和
int xor = 0;
// 计算异或和 并存到xor
// e.g. [2,4,2,3,3,6] 异或和：(2^2)^(3^3)^(4^6)=2=010
for (int num : nums) {
xor ^= num;
}
int mask = 1;
// & operator只有1&1时等于1 其余等于0
// 用上面的e.g. 4和6的二进制是不同的 我们从右到左找到第一个不同的位就可以分组 4=0100 6=0110
// 根据e.g. 010 & 001 = 000 = 0则 mask=010
// 010 & 010 != 0 所以mask=010
// 之后就可以用mask来将数组里的两个数分区分开
//拉去最低位的mask 用于分组 只要有一位为1表明当前位不相同 可以用来区分
while ((xor & mask) == 0) {
mask <<= 1;
}
//两个只出现一次的数字
int a = 0, b = 0;
for (int num : nums) {
//根据&是否为0区分将两个数字分区，并分别求异或和
if ((num & mask) == 0) {
a ^= num;
} else {
b ^= num;
}
}
return new int[] {a, b};
}
}
题041和为s的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
解法一：哈希
hash表方法是遍历我们的数组，然后存到hash表中，这样我们可以在o(1)时间取出，但是我们要维护一个hash表的空间，以及o(n)的时间复杂度。
参考LeetCode001两数之和
class Solution {
public int[] twoSum(int[] nums, int target) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
int temp = target - nums[i];
//算出差值 看看map里是否有 有的话返回[之前的索引，现在索引] 否则放入map中
if (set.contains(temp)) {
return new int[] {temp, nums[i]};
}
set.add(nums[i]);
}
return new int[] {-1, -1};
}
}
解法二：双指针（最高效）
计算和 s = nums[i] + nums[j]； 若 s > target，则指针 j 向左移动，即执行 j = j - 1； 若 s < target，则指针 i 向右移动，即执行 i = i + 1； 若 s = target ，立即返回数组 [nums[i], nums[j]；
public int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while (i < j) {
int s = nums[i] + nums[j];
if (s < target) {
i++;
} else if (s > target) {
j--;
} else {
return new int[] {nums[i], nums[j]};
}
}
return new int[0];
}
解法三：二分法
e = target - nums[i] 再使用二分查找
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; ++i) {
int left = i + 1, right = nums.length - 1, e = target - nums[i];
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == e) {
return new int[] {nums[i], nums[mid]};
} else if (nums[mid] > e) {
right = mid - 1;
} else if (nums[mid] < e) {
left = mid + 1;
}
}
}
return new int[] {};
}
题042翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
解法：双指针
- 倒序遍历字符串 ss ，记录单词左右索引边界 i , j ；
- 每确定一个单词的边界，则将其添加至单词列表 res ；
- 最终，将单词列表拼接为字符串，并返回即可。
public String reverseWords(String s) {
s = s.trim(); // 删除首尾空格
int j = s.length() - 1, i = j;
StringBuilder res = new StringBuilder();
while (i >= 0) {
while (i >= 0 && s.charAt(i) != ' ') {
i--; // 搜索首个空格
}
res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
while (i >= 0 && s.charAt(i) == ' ') {
i--; // 跳过单词间空格
}
j = i; // j 指向下个单词的尾字符
}
return res.toString().trim(); // 转化为字符串并返回
}
题043n个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
解法：动态规划
单纯使用递归时间复杂度为6^n,会造成超时错误，因为存在重复子结构
使用动态规划解决问题一般分为三步：
1.表示状态
2.找出状态转移方程
3.边界处理
表示状态
分析问题的状态时，不需要分析整体，只需要分析最后一个阶段即可！因为动态规划问题都是划分为多个阶段的，各个阶段的状态表示都是一样，而我们的最终答案在就是在最后一个阶段。
通过题目我们知道一共投掷 nn 枚骰子，那最后一个阶段很显然就是：当投掷完 n枚骰子后，各个点数出现的次数。
找出了最后一个阶段，那状态表示就简单了。
-
首先用数组的第一维来表示阶段，也就是投掷完了几枚骰子。
-
然后用第二维来表示投掷完这些骰子后，可能出现的点数。
-
数组的值就表示，该阶段各个点数出现的次数。
所以状态表示就是这样的：
dp[i][j]，表示投掷完 i 枚骰子后，点数 j的次数。
找出状态转移方程
找状态转移方程也就是找各个阶段之间的转化关系，同样我们还是只需分析最后一个阶段，分析它的状态是如何得到的。
单单看第 n 枚骰子，它的点数可能为 1 , 2, 3, … , 6，因此投掷完 n 枚骰子后点数 j 出现的次数，可以由投掷完 n-1 枚骰子后，对应点数 j-1, j-2, j-3, … , j-6 出现的次数之和转化过来。
当前n个骰子出现的点数之和等于前一次出现的点数之和加上这一次出现的点数
for (第n枚骰子的点数 i = 1; i <= 6; i ++) {
dp[n][j] += dp[n-1][j - i]
}
边界处理
这里的边界处理很简单，只要我们把可以直接知道的状态初始化就好了。
我们可以直接知道的状态是啥，就是第一阶段的状态：投掷完 1 枚骰子后，它的可能点数分别为 1, 2, 3, … , 6，并且每个点数出现的次数都是 1.
for (int i = 1; i <= 6; i ++) {
dp[1][i] = 1;
}
代码：
public double[] twoSum(int n) {
int dp[][] = new int[n + 1][6 * n + 1];//表示i个骰子掷出s点的次数
for (int i = 1; i <= 6; i++) {
dp[1][i] = 1;//边界值 表示一个骰子掷出i点的次数为1
}
//第一层循环表示骰子的个数
for (int i = 2; i <= n; i++) {
//第二层循环表示可能会出现的点数之和
for (int j = i; j <= 6 * i; j++) {
//三层循环是为了找到能得到这种可能和时，对于少一个色子时的所有可能情况，相加即是当前可能总和
for (int k = 1; k <= 6; k++) {
if (i - 1 >= 0 && j - k >= 0) {
dp[i][j] += dp[i - 1][j - k];//当前n个骰子出现的点数之和等于前一次出现的点数之和加上这一次出现的点数
}
}
}
}
double total = Math.pow((double) 6, (double) n);//掷出n次点数出现的所有情况、
//1个筛子和 1-6 6个
//2个筛子和 2-12 11个
//3个筛子和 3-18 16个 得出和的总数5*n+1
double[] ans = new double[5 * n + 1];//因为最大就只会出现5*n+1中点数
for (int i = n; i <= 6 * n; i++) {
ans[i - n] = ((double) dp[n][i]) / total;//第i小的点数出现的概率
}
return ans;
}
题044扑克牌的顺子
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
解题思路：
根据题意，此 5 张牌是顺子的 充分条件 如下：
除大小王外，所有牌 无重复 ；
设此 5 张牌中最大的牌为 max ，最小的牌为 min （大小王除外），则需满足：
max - min < 5
方法一：Set + 遍历
public boolean isStraight(int[] nums) {
Set<Integer> repeat = new HashSet<>();
int max = 0, min = 14;
for (int num : nums) {
if (num == 0) {
continue; // 跳过大小王
}
max = Math.max(max, num); // 最大牌
min = Math.min(min, num); // 最小牌
if (repeat.contains(num)) {
return false; // 若有重复，提前返回 false
}
repeat.add(num); // 添加此牌至 Set
}
return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
复杂度分析： 时间复杂度 O(N) = O(5) = O(1) ： 其中 N为 nums 长度，本题中N≡5 ；遍历数组使用 O(N) 时间。 空间复杂度 O(N) = O(5) = O(1) ： 用于判重的辅助 Set 使用 O(N) 额外空间。
方法二：排序+遍历
public boolean isStraight(int[] nums) {
int joker = 0;
Arrays.sort(nums); // 数组排序
for(int i = 0; i < 4; i++) {
if(nums[i] == 0) joker++; // 统计大小王数量
else if(nums[i] == nums[i + 1]) return false; // 若有重复，提前返回 false
}
return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
复杂度分析： 时间复杂度 O(N log N) = O(5log 5) = O(1) ： 其中 N 为 nums 长度，本题中 N≡5 ；数组排序使用 )O(NlogN) 时间。 空间复杂度 O(1) ： 变量 joker 使用 O(1) 大小的额外空间。
题045圆圈中最后剩下的数字
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
解法一：模拟链表O(n^2)
假设当前删除的位置是 idx，下一个删除的数字的位置是 idx + m 。但是，由于把当前位置的数字删除了，后面的数字会前移一位，所以实际的下一个位置是 idx + m - 1。由于数到末尾会从头继续数，所以最后取模一下，就是 (idx + m - 1) (mod n)。
LinkedList 虽然删除指定节点的时间复杂度是 O(1)的，但是在 remove 时间复杂度仍然是 O(n)的，因为需要从头遍历到需要删除的位置。那 ArrayList 呢？索引到需要删除的位置，时间复杂度是 O(1)，删除元素时间复杂度是 O(n)（因为后续元素需要向前移位）， remove 整体时间复杂度是 O(n)的
ArrayList 的 remove 操作在后续移位的时候，其实是内存连续空间的拷贝的！所以相比于LinkedList大量非连续性地址访问性能更好。
代码：
public int lastRemaining(int n, int m) {
ArrayList<Integer> list = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
list.add(i);
}
int idx = 0;
while (n > 1) {
idx = (idx + m - 1) % n;
list.remove(idx);
n--;
}
return list.get(0);
}
解法二：约瑟夫O(n)
这个问题实际上是约瑟夫问题，这个问题描述是
N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
既然约塞夫问题就是用人来举例的，那我们也给每个人一个编号（索引值），每个人用字母代替
下面这个例子是N=8 m=3的例子
我们定义F(n,m)表示最后剩下那个人的索引号，因此我们只关系最后剩下来这个人的索引号的变化情况即可
反推
现在我们知道了G的索引号的变化过程，那么我们反推一下 从N = 7 到N = 8 的过程
如何才能将N = 7 的排列变回到N = 8 呢？
我们先把被杀掉的C补充回来，然后右移m个人，发现溢出了，再把溢出的补充在最前面
神奇了 经过这个操作就恢复了N = 8 的排列了！
因此我们可以推出递推公式f(8,3) = [f(7, 3) + 3] % 8
进行推广泛化，即f(n,m) = [f(n-1, m) + m] % n
代码：
public int lastRemaining(int n, int m) {
int pos = 0; // 最终活下来那个人的初始位置
for (int i = 2; i <= n; i++) {
pos = (pos + m) % i; // 每次循环右移
}
return pos;
}
题046求1+2+…+n
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3
输出: 6
解法一：递归 （ 利用短路与的特性）
public int sumNums(int n) {
//当n不大于0 直接返回n 不执行后边的递归
boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
return n;
}
复杂度分析：
时间复杂度：O(n)。递归函数递归 n 次，每次递归中计算时间复杂度为 O(1)，因此总时间复杂度为 O(n)。 空间复杂度：O(n)。递归函数的空间复杂度取决于递归调用栈的深度，这里递归函数调用栈深度为 O(n)，因此空间复杂度为 O(n)。
解法二：快速乘
int ans = 0;
while (b > 0) {
if ((b & 1) != 0) {
ans += a;
}
b >>= 1;
a <<= 1;
}
回到本题，由等差数列求和公式我们可以知道等价于 n(n+1)/2 => n(n+1)»1
乘法可以使用俄罗斯算法
因为题目数据范围 n 为 [1,10000]，所以 n 二进制展开最多不会超过 14 位，我们手动展开 14层代替循环即可
public int sumNums(int n) {
int ans = 0, A = n, B = n + 1;
boolean flag;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
return ans >> 1;
}
题047不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2
解法：位运算
本题考察对位运算的灵活使用，即使用位运算实现加法。 设两数字的二进制形式 a, ba,b ，其求和 s = a + bs=a+b ，a(i)a(i) 代表 aa 的二进制第 ii 位，则分为以下四种情况：
| a(i) | b(i) | 无进位和 n(i) | 进位 c(i+1) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
观察发现，无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）。因此，无进位和 n与进位 c的计算公式如下；
s=a+b⇒s=n+c 循环求n和c 直到进位为0
代码：
public int add(int a, int b) {
while (b != 0) { // 当进位为 0 时跳出
int c = (a & b) << 1; // c = 进位
a ^= b; // a = 非进位和
b = c; // b = 进位
}
return a;
}
题049把字符串转化为整数
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
解法：
-
首部空格： 删除之即可；
-
符号位： 三种情况，即 ‘’+’’ , ‘’-‘’ , ‘‘无符号” ；新建一个变量保存符号位，返回前判断正负即可。
-
非数字字符： 遇到首个非数字的字符时，应立即返回。
-
数字字符： 字符转数字： “此数字的 ASCII 码” 与 “ 0 的 ASCII 码” 相减即可； 数字拼接： 若从左向右遍历数字，设当前位字符为 c ，当前位数字为 x ，数字结果为 res ，则数字拼接公式为：
res = 10 *res + x
代码：
public int strToInt(String str) {
char[] c = str.trim().toCharArray();
if (c.length == 0) {
return 0;
}
int res = 0, bndry = Integer.MAX_VALUE / 10;
int i = 1, sign = 1;
//符号处理 如果无正负符号从0开始
if (c[0] == '-') {
sign = -1;
} else if (c[0] != '+') {
i = 0;
}
for (int j = i; j < c.length; j++) {
//不是数字
if (c[j] < '0' || c[j] > '9') {
break;
}
// 判断是否超过边界
if (res > bndry || res == bndry && c[j] > '7') {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
//字符串转化为数字
res = res * 10 + (c[j] - '0');
}
return sign * res;
}
题050二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
本题给定了两个重要条件：① 树为 二叉搜索树 ，② 树的所有节点的值都是 唯一 的。根据以上条件，可方便地判断 p,q与 root 的子树关系，即：
若 root.val < p.val ，则 p 在 root 右子树 中；
若 root.val > p.val ，则 p 在 root 左子树 中；
若 root.val = p.val，则 p 和 root 指向 同一节点 。
解法一：迭代 时间复杂度 O(N) ： 其中 N为二叉树节点数；每循环一轮排除一层，二叉搜索树的层数最小为logN （满二叉树），最大为 N （退化为链表）。 空间复杂度 O(1) ： 使用常数大小的额外空间。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p.val > q.val) { // 保证 p.val < q.val
TreeNode tmp = p;
p = q;
q = tmp;
}
while (root != null) {
if (root.val < p.val) // p,q 都在 root 的右子树中
{
root = root.right; // 遍历至右子节点
} else if (root.val > q.val) // p,q 都在 root 的左子树中
{
root = root.left; // 遍历至左子节点
} else {
break;
}
}
return root;
}
解法二：递归
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
}
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
}
return root;
}