剑指offer55-Ⅰ 二叉树的深度【DFS】

题目描述

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。

例如:

给定二叉树 [3,9,20,null,null,15,7]

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回它的最大深度 3 。

提示:

  1. 节点总数 <= 10000
Read more

剑指offer54 二叉搜索树的第k大节点【DFS】

题目描述

给定一棵二叉搜索树,请找出其中第k大的节点。

示例 1:

1
2
3
4
5
6
7
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4

示例 2:

1
2
3
4
5
6
7
8
9
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4

限制:

1 ≤ k ≤ 二叉搜索树元素个数

Read more

剑指offer53-Ⅱ 0到n-1中缺失的数字【二分查找、数学】

剑指 Offer 53 - II. 0~n-1中缺失的数字

题目描述

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

示例 1:

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

示例 2:

1
2
输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制:

1
1 <= 数组长度 <= 10000
Read more

剑指offer52 两个链表的第一个公共节点【双指针】

题目描述

输入两个链表,找出它们的第一个公共节点。

如下面的两个链表

img

在节点 c1 开始相交。

示例 1:

img

1
2
3
输入: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 个节点。

示例 2:

img

1
2
3
4
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
解释:这两个链表不相交,因此返回 null。

注意:

  • 如果两个链表没有交点,返回 null.
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
Read more

剑指offer51 数组中的逆序对【分治、归并】

剑指 Offer 51. 数组中的逆序对

题目描述

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例 1:

1
2
输入: [7,5,6,4]
输出: 5

限制:

1
0 <= 数组长度 <= 50000
Read more

排序算法 归并排序

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
private static void mergeSort(int[] nums, int left, int right, int[] temp) {
if (left == right) {
return;
}
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid, temp);
mergeSort(nums, mid + 1, right, temp);
merge(nums, left, mid, right, temp);
}

private static void merge(int[] nums, int left, int mid, int right, int[] temp) {
int i = left, j = mid + 1;
for (int k = left; k <= right; k++) {
if (i == mid + 1) {
temp[k] = nums[j++];
} else if (j == right + 1) {
temp[k] = nums[i++];
} else if (nums[i] <= nums[j]) {
temp[k] = nums[i++];
} else {
temp[k] = nums[j++];
}
}
for (int k = left; k <= right; k++) {
nums[k] = temp[k];
}
}


public static void main(String[] args) {
int[] num = {7,5,6,4,8,9,6,7,4,5,9,0,7,3};
System.out.println("未排序");
System.out.println(Arrays.toString(num));
int[] temp = new int[num.length];
mergeSort(num, 0, num.length - 1, temp);
System.out.println("排序后");
System.out.println(Arrays.toString(num));
}


剑指offer49 丑数【双指针】

题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。

示例:

1
2
3
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

  1. 1 是丑数。
  2. n 不超过1690。
Read more

剑指offer48 最长不重复字符的子字符串【哈希表、双指针】

题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

提示:

  • s.length <= 40000
Read more