1、删除倒数第 n 个节点

1.1、题目描述

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

进阶:你能尝试使用一趟扫描实现吗?

1.2、解题思路

  • 创建一个虚拟头节点,令这个虚拟头节点的 next 域指向真实的头节点

  • 创建一个 sentinel 节点,这个节点指向虚拟头节点

  • 创建一个 fast 节点,这个节点指向真实头节点

image-20210913235146399

此时原问题与查询链表倒数第 n 个节点的问题一致,让 sentinel 指针和 fast 指针每次走一步,当 fast == null 时,sentinel 的下一个节点就是待删除节点,此时让 sentinel.next = sentinel.next.next ,然后返回虚拟头节点的 next 即可。

1.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode removeNthFromEnd(ListNode head, int n) {
//1 指定一个虚拟头节点
ListNode virtualHead = new ListNode(-1);
// 让虚拟节点的 next 指向真实的头节点
virtualHead.next = head;
//2 令 fast 节点从真实头节点开始,哨兵节点从虚拟头节点开始
ListNode fast = head;
ListNode sentinel = virtualHead;
//3 让 fast 指针先走 n 步
for (int i = 0; i < n; i++) {
fast = fast.next;
}
//4 每次让 sentinel 和 fast 往前走一步,当 fast 为空时, sentinel 的下一个节点就是待删除节点
while (fast != null) {
fast = fast.next;
sentinel = sentinel.next;
}
//5 退出时,删除 sentinel 的 next 即可
sentinel.next = sentinel.next.next;
return virtualHead.next;
}

2、数字在升序数组中出现的次数

2.1、题目描述

统计一个数字在升序数组中出现的次数。

  • 输入:[1,2,3,3,3,3,4,5],3

  • 返回值:4

2.2、解题思路

对于升序数组,我们第一想到的就是二分查找法,在查询到第一个符合条件的 mid 后,向左向右进行查找,统计所有符合条件的个数

2.3、解题代码

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
public int GetNumberOfK(int [] array , int k) {
if (array == null || array.length == 0) {
return 0;
}
int left = 0;
int right = array.length - 1;
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (k < array[mid]) {
right = mid - 1;
} else if (k > array[mid]) {
left = mid + 1;
} else {
// 使用一个 index 指向 mid
int index = mid;
// 统计下标在 [0, mid] 中元素 == k 的个数
while (index >= 0 && array[index] == k) {
result++;
index--;
}
// 将 index 重置为 mid + 1,然后统计下标在 [mid + 1, array.length - 1] 中元素 == k 的个数
index = mid + 1;
while (index <= array.length - 1 && array[index] == k) {
result++;
index++;
}
return result;
}
}
return 0;
}

3、验证 IP 地址

3.1、题目描述

编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址

3.2、解题思路

  • IPv4

一个合法的 IPv4 地址可以根据 . 分割为 4 组,且分割后每组元素都不为空,且每组的长度均 <= 3,每组大小在 0 - 255 之间,每组不包含前导 0 ,除非本身为 0

  • IPv4

一个合法的 IPv4 地址可以根据 : 分割为 8 组,且分割后每组均不为空,每组长度 <= 4,组中的字符范围为:0~9 || a~f || A~F

3.3、解题代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
public String solve (String IP) {
// write code here
if (IP == null || "".trim().equals(IP) || IP.length() == 0) {
return "Neither";
}
if (isIPv4(IP)) {
return "IPv4";
} else if (isIPv6(IP)) {
return "IPv6";
} else {
return "Neither";
}
}

private boolean isIPv6(String ip) {
if (!ip.contains(":")) {
return false;
}
String[] ipv6Group = ip.split(":");
if (ipv6Group.length != 8) {
return false;
}
for (String item : ipv6Group) {
if (!isIpv6Item(item)) {
return false;
}
}
return true;
}

private boolean isIpv6Item(String item) {
if (item == null || "".trim().equals(item) || item.length() > 4) {
return false;
}
for (int i = 0 ; i < item.length(); i++) {
if (!('0' <= item.charAt(i) && item.charAt(i) <= '9' || 'a' <= item.charAt(i) && item.charAt(i) <= 'f' || 'A' <= item.charAt(i) && item.charAt(i) <='F')) {
return false;
}
}
return true;

}

private boolean isIPv4(String ip) {
if (!ip.contains(".")) {
return false;
}
String[] ipv4Group = ip.split("\\.");
if (ipv4Group.length != 4) {
return false;
}
for (String item : ipv4Group) {
if (!isIpv4Item(item)) {
return false;
}
}
return true;
}

/**
* 判断这个 ipv4 的 item 是否合法
* @param item
* @return
*/
private boolean isIpv4Item(String item) {
if (item == null || "".trim().equals(item) || item.length() > 3) {
return false;
}
for (int i = 0; i < item.length(); i++) {
char ch = item.charAt(i);
if (!(ch >= '0' && ch <= '9')) {
return false;
}
}
try {
int intItem = Integer.parseInt(item);
// 如果 item 小于0或大于 255 或是第一个字符为0且item长度大于1
if (intItem < 0 || intItem > 255 || (item.charAt(0) == '0' && item.length() > 1)) {
return false;
}
} catch (NumberFormatException e) {
return false;
}
return true;
}

4、相交链表

4.1、题目描述

给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null

图示两个链表在节点 c1 开始相交,题目数据 保证 整个链式结构中不存在环。

img

4.2、解题思路

  • 使用 HashSet

先将一条链表中的数据全部 “注册” 到 HashSet 中,然后遍历另外一条链表,如果发现已经有存在的元素就直接返回该元素。

  • 追赶法

先获取两条链表的长度,设长的那条链表长度为 a ,短的那条长度为 b ,让长的那条先走 a - b 步,然后两条链表一起走,如果二者有交集,那么一定会相遇,此时返回第一个相遇节点即可。

4.3、解题代码

  • 使用 HashSet
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> set = new HashSet<>();
while (headA != null) {
set.add(headA);
headA = headA.next;
}
while (headB != null) {
if (!set.add(headB)) {
return headB;
}
headB = headB.next;
}
return null;
}
  • 使用追赶法
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
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
int sizeA = getLinkedListSize(headA);
int sizeB = getLinkedListSize(headB);
if (sizeA > sizeB) {
int diff = sizeA - sizeB;
for (int i = 0; i < diff; i++) {
headA = headA.next;
}
} else {
int diff = sizeB - sizeA;
for (int i = 0; i < diff; i++) {
headB = headB.next;
}
}
while (headA != null && headB != null) {
if (headA == headB) return headA;
headA = headA.next;
headB = headB.next;
}
return null;
}

private int getLinkedListSize (ListNode head) {
if (head == null) return 0;
if (head.next == null) return 1;
int size = 0;
ListNode cur = head;
while (cur != null) {
size++;
cur = cur.next;
}
return size;
}

5、插入排序链表

5.1、题目描述

对链表进行插入排序

5.2、解题思路

插入排序将链表分为两部分,第一部分是已经有序的链表序列,第二部分是无序的链表序列,我们对链表进行遍历,每次将链表中的一个节点加入到左边有序链表的合适位置中。

遍历链表时,如果当前节点的值小于等于它的下一个节点的值,那么我们认为这两个节点有序,直接跳过进行下一次遍历。

如果当前节点的值大于它的下一个节点的值,那么将这个节点从链表中删除,然后为这个节点找到一个合适的位置,插入

  • 创建一个虚拟头节点,让这个头节点的 next 指针指向 head

为什么要有虚拟头节点?因为在排序过程中 head 可能被排到其他节点后面,如果有虚拟头节点,那么即使 head 在之后的排序中被排到后面,最终结果也可以使用虚拟节点获取。

  • 创建一个 prev 节点,这个节点初始指向虚拟头节点,在每一次为节点查找插入位置时,都必须让它从虚拟头节点开始遍历
  • 创建一个 temp 节点,这个节点用于保存要进行插入排序的节点

5.3、解题代码

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
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null) return head;
// 创建 4 个节点
ListNode virtualHead = new ListNode(Integer.MIN_VALUE);
virtualHead.next = head;
ListNode current = head;
ListNode prev = null;
ListNode temp = null;
while (current != null && current.next != null) {
// 如果当前节点值小于后一个节点的值,证明这两个节点有序
// 所以只需要遍历下一个节点即可。
if (current.val <= current.next.val) {
current = current.next;
} else {
// 如果进入这里,代表当前节点的值大于下一个节点的值
// 使用一个 temp 保存当前节点的后续链表,避免丢失
temp = current.next;
// 相当于删除了 current 的下一个节点
current.next = current.next.next;
prev = virtualHead;
// 为 current.next 找到一个合适的位置插入
while (prev.next.val <= temp.val) {
prev = prev.next;
}
// 退出循环后,pre 的下一个位置就是待插入位置
temp.next = prev.next;
prev.next = temp;
}
}
// 这里需要返回虚拟头节点的下一个节点,不能返回 head
return virtualHead.next;
}

6、删除数组中的重复元素

6.1、题目描述

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。


  • 函数声明
1
public int removeDuplicates(int[] nums);

其中返回值为数组中最后一个不重复元素的下标,如 int len = removeDuplicates(nums);

那么下标从 0 到 len - 1 这几个元素就是 nums 数组中不重复的所有元素

  • 示例
1
2
3
输入:nums = [1,1,2]
输出:2, nums = [1,2]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

6.2、使用双指针

  • 我们定义两个指针,其中快指针用于扫描数组中的非重复元素,慢指针用于指向可以插入的位置

  • 快慢指针都必须从第二个元素,即下标 1 开始,因为 nums[0] 本身是一个合法的不重复元素

  • 当 nums[fast] == nums[fast - 1] 时,表示当前快指针指向的是一个重复元素,此时让快指针后移,慢指针不动

  • 当 nums[fast] != nums[fast - 1] 时,表示当前快指针找到的是一个之前数组中没有出现过的新元素,此时让 nums[slow] = nums[fast] ,将当前快指针指向的这个元素插入到慢指针所指向的,可以插入的位置中。

  • 最后返回 slow (由于 slow 指向的是可以插入的位置,那么在遍历结束后,它的位置就是最后一个不重复元素的下一个位置。)

6.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) return 0;
// 快慢指针的下标都从 1 开始,这是因为 nums[0] 一定是不重复的
int slow = 1 , fast = 1;
// slow 指针指向可以插入的位置,fast 用于遍历整个数组
while (fast < nums.length) {
if (nums[fast - 1] != nums[fast]) {
// 如果 fast 指针指向的元素不等于它的前一个元素,那么证明这个元素是第一个不重复元素
// 此时让 nums[slow] = nums[fast]
// 同时让 slow 后移,指向下一个可插入位置
nums[slow++] = nums[fast];
}
// 不管如何, fast 都必须后移
fast++;
}
return slow;
}

7、矩阵置 0

7.1、题目描述

给定一个 m * n 的矩阵,如果有一个元素是 0,就把该元素所在的行和列上的元素全置为 0

7.2、解题思路

  • HashSet 解法

扫描两次矩阵,第一次扫描记录矩阵中 0 元素的行号和列号,并将其加入到两个 HashSet 中;第二次遍历矩阵,如果循环中的行号或列号在集合中,那么将该行和该列都置为 0

  • 标记位法

这种解法的关键思想是将第一行第一列作为标记位,用于标记该行该列是否有 0 ,我们需要对第一行第一列的元素进行判断,防止第一行第一列的元素有 0

  1. 第一行、第一列有 0 的进行标记(使用一个标记位,第一行有 0 时,将该标记位置为 true,第一列同理)
  2. 从第二行第二列开始,如果有元素为 0 ,那么将元素所在的行首和列首元素置为 0
  3. 如果第一行有 0 (标记位为 true )那么整行都为 0,如果第一列有 0 (标记位为 true ),那么整列都为 0

7.3、解题代码

  • HashSet 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void setZeroes(int[][] matrix) {
if (matrix == null || matrix.length == 0) return;
int rows = matrix.length;
int cols = matrix[0].length;
// 创建两个 HashSet ,分别用于保存 0 元素的行号和列号
Set<Integer> rowSet = new HashSet<>();
Set<Integer> colSet = new HashSet<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
rowSet.add(i);
colSet.add(j);
}
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (rowSet.contains(i) || colSet.contains(j)) {
matrix[i][j] = 0;
}
}
}
}
  • 标记位解法
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
41
42
43
44
45
46
47
48
49
public void setZeroes(int[][] matrix) {
boolean rowFlag = false, colFlag = false;
int rows = matrix.length;
int cols = matrix[0].length;
for (int i = 0; i < rows; i++) {
if (matrix[i][0] == 0) {
// 如果第一列中有 0 元素,那么将符号位 colFlag 置为 true
colFlag = true;
break;
}
}

for (int i = 0; i < cols; i++) {
if (matrix[0][i] == 0) {
rowFlag = true;
break;
}
}

// 这里从下标 1 开始遍历这个二维数组
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][j] == 0) {
// 将元素所在标记位置为 0
matrix[i][0] = matrix[0][j] = 0;
}
}
}
// 进行置 0 操作,如果标记位为 0 ,那么置为空
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// 如果第一行有 0 ,那么第一行都为 0
if (rowFlag) {
for (int i = 0; i < cols; i++) {
matrix[0][i] = 0;
}
}
// 如果第一列有 0 ,那么第一列均为 0
if (colFlag) {
for (int i = 1; i < rows; i++) {
matrix[i][0] = 0;
}
}
}

8、实现二叉树先序,中序和后序遍历

8.1、题目描述

分别按照二叉树先序,中序和后序打印所有的节点。

8.2、解题思路

分别对传入的树进行前中后序遍历,将遍历结果分别加入到 list 集合中,然后使用一个二维数组合并集合中的数据

8.3、解题代码

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
41
42
43
44
45
46
47
48
49
50
List<Integer> preOrderList = new ArrayList<>();
List<Integer> infixOrderList = new ArrayList<>();
List<Integer> postOrderList = new ArrayList<>();
/**
* 分别按照二叉树先序,中序和后序打印所有的节点。
*/
public int[][] threeOrders (TreeNode root) {
getPreOrderList(root);
getInfixOrderList(root);
getPostOrderList(root);
int[] preResult = copyElementFromListToArray(preOrderList);
int[] infixResult = copyElementFromListToArray(infixOrderList);
int[] postResult = copyElementFromListToArray(postOrderList);
int[][] res = new int[3][];
res[0] = preResult;
res[1] = infixResult;
res[2] = postResult;
return res;
}

private void getPreOrderList(TreeNode root) {
if (root == null) return;
preOrderList.add(root.val);
if (root.left != null) getPreOrderList(root.left);
if (root.right != null) getPreOrderList(root.right);
}

private void getInfixOrderList(TreeNode root) {
if (root == null) return;
if (root.left != null) getInfixOrderList(root.left);
infixOrderList.add(root.val);
if (root.right != null) getInfixOrderList(root.right);
}

private void getPostOrderList(TreeNode root) {
if (root == null) return;
if (root.left != null) getPostOrderList(root.left);
if (root.right != null) getPostOrderList(root.right);
postOrderList.add(root.val);
}

private int[] copyElementFromListToArray (List<Integer> list) {
if (list == null || list.size() == 0) return null;
int size = list.size();
int[] result = new int[size];
for (int i = 0; i < size; i++) {
result[i] = list.get(i);
}
return result;
}

9、两个链表生成相加链表

9.1、题目描述

假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。

给定两个这种链表,请生成代表两个整数相加值的结果链表。

例如:链表 1 为 9->3->7,链表 2 为 6->3,最后生成新的结果链表为 1->0->0->0。

9.2、解题思路

  • 将两个需要进行加法的链表翻转过来
  • 对翻转后的链表进行加法计算
  • 最后将得到的链表再次翻转,即可得到解

9.3、解题代码

这部分代码在牛客中无法通过测试用例

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
41
42
43
44
45
46
47
48
49
50
public ListNode reverseList (ListNode head) {
if(head == null || head.next == null) {
//如果进入这个if块中,证明当前head与其之后结点形成的链表不需要反转
//例如1-2-3-4中的4不需要反转,直接返回该节点即可
return head;
}
//如果链表长度大于等于2,进行递归
ListNode reverseNode = reverseList(head.next);
//将当前节点下一个节点的next指针域指向自己
head.next.next = head;
//将当前节点的next指针域置空
head.next = null;
return reverseNode;
}

public ListNode addInList (ListNode head1, ListNode head2) {
//1 反转两个链表
head1 = reverseList(head1);
head2 = reverseList(head2);
ListNode result = new ListNode(Integer.MIN_VALUE);
ListNode current = result;
// 这个值存放当前节点的值的进位
int temp = 0;
while (head1 != null || head2 != null) {
int param1 = head1 == null ? 0 : head1.val;
int param2 = head2 == null ? 0 : head2.val;
// 当前这一个节点的总值,为 a 节点的值 + b 节点的值 + 后一位的进位值
int sum = param1 + param2 + temp;
// 计算当前节点下一位的进位值
temp = sum / 10;
// 构造该节点的下一个节点
ListNode tempNode = new ListNode(sum % 10);
// 进行插入
current.next = tempNode;
current = current.next;
// 由于循环条件是 head1 != null || head2 != null
// 所以在将指针向后移时需要进行判断
if (head1 != null) {
head1 = head1.next;
}
if (head2 != null) {
head2 = head2.next;
}
}
// 如果退出循环后 temp > 0,证明我们还需要向前进一位
if (temp > 0) {
current.next = new ListNode(temp);
}
return reverseList(result.next);
}

10、反转字符串

10.1、题目描述

写出一个程序,接受一个字符串,然后输出该字符串反转后的字符串。(字符串长度不超过1000)

10.2、解题思路

  • 使用 Java 自带的 API 进行翻转
  • 使用双指针进行翻转

使用一个指针 i 指向字符串末尾,一个指针 j 指向新数组头部,循环将 i 指向的字符赋给 j 即可,然后让指针 i 前移,指针 j 后移。

10.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
public String solve (String str) {
if (str == null || str.length() == 0 || "".equals(str.trim())) return str;
char[] strArray = str.toCharArray();
char[] result = new char[strArray.length];
// 初始化
int j = 0;
for (int i = str.length() - 1; i >= 0; i--) {
result[j++] = strArray[i];
}
return new String(result);
}

11、删除链表的中间节点

11.1、题目描述

给你一个不知道头节点的链表,实现算法来删除单链表中的中间节点(只知道指向该节点(中间节点)的指针)。

  • 函数声明
1
void deleteNode (ListNode node);

其中 node 为待删除节点

11.2、解题思路

单链表中,如果我们要删除一个节点,那么必须找到被删除节点的上一个节点,但这里没有给头节点,所以不能以普通方法解决,我们可以找到待删除节点的下一个节点 node.next ,然后将待删除节点的值赋给待删除节点 (node.val = node.next.val),然后删去待删除节点的下一个节点。

这样就完成了对 node 节点的“删除”。

11.3、解题代码

1
2
3
4
5
6
void deleteNode (ListNode node) {
ListNode temp = node.next;
node.val = temp.val;
node.next = temp.next;
temp = null;
}

12、在二叉树中找到两个节点的最近公共祖先

12.1、题目描述

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2,请找到 o1 和 o2 的最近公共祖先节点。

注:本题保证二叉树中每个节点的val值均不相同。

  • 给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

img

结点 5 和结点 1 的最近公共祖先为 3 ;结点 5 和 4 的最近公共祖先为 5 ,因为根据定义,最近公共祖先可以是自己。

12.2、解题思路

  • 递归
  1. 如果 root 是 o1 和 o2 的最近公共祖先,那么只可能有以下三种情况

o1 和 o2 在 root 的子树中,且分列在 root 的异侧(一个在左一个在右)

o1 = root ,且 o2 在 root 的左或右子树中

o2 = root ,且 o1 在 root 的左或右子树中

  1. 终止条件:

当越过叶子节点时,直接返回 null

当 root 等于 o1 或 o2 结点时,返回 root

  1. 递推工作

开启递归左子节点,返回值记为 left

开启递归右子节点,返回值记为 right

  1. 返回值

根据 left 和 right,可以分为以下四种情况

a. 当 left 与 right 同时为空时,说明 root 的左 / 右子树都不包含 o1,o2 ,直接返回 null

b. 当 left 与 right 同时不为空时,此时说明 o1,o2 分布在 root 的异侧,此时 root 就是最近公共祖先,返回 root

c. 当 left 为空,right 不为空时,o1 o2 都不在 root 的左子树中,此时直接返回 right

d. 当 right 为空,left 不为空时,o1 o2 都不在 root 的右子树中,此时直接返回 left

  • 使用散列表存储父节点

12.3、解题代码

  • 递归
1
2
3
4
5
6
7
8
9
10
11
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 如果 p q 中有一个结点为根节点,那么直接返回根节点即可
if (root == null || p.val == root.val || q.val == root.val) return root;
// 往左子树中搜寻
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
if (left == null) return right;
if (right == null) return left;
return root;
}
  • 使用散列表

13、数组中的第K个最大元素

13.1、题目描述

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

13.2、解题思路

  • 使用最小堆解决

维护一个只有 k 个元素的最小堆,然后遍历数组,将数组中的元素加入到最小堆中,每次加入时我们需要进行判断:

  1. 加入元素后,如果此时最小堆中的元素个数小于 k ,那么此时不做任何事

  2. 加入元素后,如果此时最小堆中的元素个数大于 k ,那么我们依次从最小堆中 pop 出一个元素(删除堆顶元素,即去除堆中最小的元素),直到堆中元素个数为 k

在遍历完整个数组之后,此时堆中的元素就是这个数组中最大的 k 个元素,根据最小堆的特性,堆顶元素就是这些元素中最小的一个,也就是数组中第 k 大的元素。

  • 使用快排思路解决
  1. 随机取一个数(它的下标假设为 index),由于我们需要找第 k 个大的数,所以是降序排序,故将大于这个数的值放在左边,将小于这个数的值放在右边。
  2. 由于数组的索引是从 0 开始,所以对于一个降序排序的数组,索引为 K - 1 的元素即为第 K 大元素
  3. 在一次快速排序后,我们进行判断,如果 index = k - 1,那么证明 arr[index] 就是我们要找的数,如果 index > k - 1 ,那么证明我们要找的数在 index 的左边,此时向左递归查找即可
  4. 如果 index < k - 1,那么证明我们要找的数在 index 的右边,此时向右递归查找即可

13.3、解题代码

  • 使用最小堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findKthLargest(int[] nums, int k) {
//1 创建一个大小为 k 的小顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
//2 循环遍历数组元素
for (int i = 0; i < nums.length; i++) {
minHeap.add(nums[i]);
// 添加元素后,需要检查当前最小堆中元素是否大于 k ,如果是,需要去掉堆顶元素
if (minHeap.size() > k) {
minHeap.poll();
}
}
// 在退出循环后,我们就得到了一个长度为 k 的小顶堆,此时我们可以直接返回其中的最小元素即可
return minHeap.peek();
}

14、数组中的逆序对

14.1、题目描述

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

14.2、解题思路

使用归并排序的思想来解这道题,在将多个组的元素合并到一个组时,此时用 i 指向 left ,j 指向 mid + 1,此时我们判断 i 和 j 指向元素的大小关系,如果

  • arr[i] <= arr[j] ,那么证明前面的元素小于等于后面的元素,构不成逆序数组
  • arr[i] > arr[j],那么证明前面的元素大于后面的元素,此时构成逆序组。

使用归并排序的思想如下,在我们将一个无序组变为一个递增数组的过程中,只要存在一次交换(将前面大的元素放到小的元素后面),那么就 count++,其中 count 为逆序对个数

14.3、解题代码

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
41
42
43
44
45
public int InversePairs(int [] array) {
sort (array);
return count;
}

int count = 0;
private int[] assist;
private void sort(int[] arr) {
if (arr == null || arr.length == 0) return;
assist = new int[arr.length];
sort(arr, 0, arr.length - 1);
}

private void sort(int[] arr, int low, int high) {
if (low >= high) return;
int mid = low + (high - low) / 2;
sort(arr, low, mid);
sort(arr, mid + 1, high);
merge(arr, low, mid, high);
}

private void merge(int[] arr, int low, int mid, int high) {
int leftPoint = low;
int assistPoint = low;
int rightPoint = mid + 1;
while (leftPoint <= mid && rightPoint <= high) {
if (arr[leftPoint] < arr[rightPoint]) {
// 此时不是一个逆序对
assist[assistPoint++] = arr[leftPoint++];
} else {
// 此时是一个逆序对
count = (count + mid - leftPoint + 1) % 1000000007;
assist[assistPoint++] = arr[rightPoint++];
}
}
while (leftPoint <= mid) {
assist[assistPoint++] = arr[leftPoint++];
}
while (rightPoint <= high) {
assist[assistPoint++] = arr[rightPoint++];
}
for (int index = low; index <= high; index++) {
arr[index] = assist[index];
}
}

15、长度最小的子数组

15.1、题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

15.2、解题思路

  • 暴力破解
  1. 假设现在数组的长度为 n ,那么这道题的答案可能为 0 - n ,我们先假设长度为 1 的情况,此时遍历数组,判断其中是否有单个元素的值大于等于 target 值,如果有,直接返回 1 即可。

  2. 如果数组中没有单个元素的值大于等于 target 值,那么将子数组长度设为 2 ,查看有没有长度为 2 的子数组之和大于等于 target ,以此类推

  • 双指针法

这里以 nums = {2,3,1,2,4,3} ,target = 7 为例

  1. 定义一个指针 i 与指针 j ,程序开始时, i,j 均指向数组中的第一个元素,再定义一个值 total ,这个值初始化为 nums[i] ,表示当前指针 i 与指针 j 形成的子数组的值的总和。
  2. 当 total < target 时,我们移动 j 指针,i 不动,即扩张子数组,当 total >= target ,此时数组 {nums[i], nums[i + 1], nums[i + 2], …, nums[j]} 为问题的一个解
  3. 当 total >= target 时, j 保持不动,然后让 i 向后移,然后减去 i 的指向元素的前一个值

在这里,我们又需要判断 target 与 当前 total 的关系,如果 total < target ,那么还需要将 j 后移,然后将 nums[j] 加入到 total 中

15.3、解题代码

  • 暴力法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 使用暴力法进行破解
*/
public int minSubArrayLen(int target, int[] nums) {
if (nums == null || nums.length == 0) return 0;
//1 遍历数组,如果发现数组中存在元素的值大于等于 target ,那么返回 1
int size = 1;
//2 查看长度为 2 的子数组之和有没有大于等于 target
//3 以此类推,查看长度为 3 4 ... 的子数组
while (size <= nums.length) {
for (int i = 0; i < nums.length - size + 1; i++) {
int total = 0;
for (int j = i; j < i + size; j++) {
total += nums[j];
}
if (total >= target) {
return size;
}
}
size++;
}
return 0;
}
  • 双指针法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int minSubArrayLen(int target, int[] nums) {
if (nums == null || nums.length == 0) return 0;
//1 定义一个左指针、右指针和总值 total
int left = 0, right = 0, result = nums.length + 1, total = 0;
while (right < nums.length) {
total += nums[right];
right++;
// 当 total 大于等于 target 时,证明此时找到了一个解,我们将当前左边界的值记录下来,然后移动左指针
// 这是为了在这个解中找到一个更优的解
while (total >= target) {
result = Math.min(result, right - left);
total -= nums[left];
left++;
}
}
return result == nums.length + 1 ? 0 : result;
}