数组中的逆序对
剑指 Offer 51. 数组中的逆序对 - 力扣（Leetcode）
题目要求
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
例子：
提示：
0 <= 数组长度 <= 50000
思路分析
归并排序
通过i和j进行比较，将小的合并到原始数组，当遇到j小于i合并回去的情况时，需要记录逆序个数，为i指向的部分剩余的元素个数；例如下图：j指向的1小于i指向的2，就将1合并回去，因为i指向的部分还存在2，3，5，7四个数字，并且都和1构成逆序队，因此直接加4；
而当j大于i的情况下，将i指向的数字进行合并即可；
代码实现
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
| class Solution {
public int reversePairs(int[] nums) {
if(nums == null || nums.length <= 0){
return 0;
}
return mergeSort(nums,0,nums.length-1);
}
int mergeSort(int[] nums,int left,int right){
if(left >= right){
return 0;
}
int mid = (right - left)/2 + left;
int x1 = mergeSort(nums,left,mid);
int x2 = mergeSort(nums,mid+1,right);
int x3 = merge(nums,left,mid,mid+1,right);
return x1+x2+x3;
}
int merge(int[] nums,int l1,int r1,int l2,int r2){
int [] temp = new int[r2-l1+1];
int count = 0;
int i=l1,j=l2,k=0;
while(i<=r1 && j<=r2){
if(nums[i] > nums[j]){
count += (l2 - i);
temp[k++] = nums[j++];
}else{
temp[k++] = nums[i++];
}
}
while(i <= r1) temp[k++] = nums[i++];
while(j <= r2) temp[k++] = nums[j++];
k = 0;
for(i=l1; i<=r2; i++){
nums[i] = temp[k++];
}
return count;
}
}
|
两个链表的第一个公共节点
剑指 Offer 52. 两个链表的第一个公共节点 - 力扣（Leetcode）
题目要求
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
例子：
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 个节点。
|
提示：
- 如果两个链表没有交点，返回
null.
- 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
思路分析
双指针
假设两条链表分别为A和B，使用两个指针node1和node2，node1指向A的头节点，node2指向B的头节点，然后node1和node2同时向后走，当node1指针走到null时，下一次回到B链表的头节点开始继续向后走；当node2指针走到null时，下一次回到A链表的头节点开始继续向后走，直到node1和node2相遇，即找到了它们的第一个公共节点；
代码实现
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
|
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode node1 = headA,node2 = headB;
while(node1!=node2){
node1 = node1 == null ? headB : node1.next;
node2 = node2 == null ? headA : node2.next;
}
return node1;
}
}
|
在排序数组中查找数字
剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（Leetcode）
题目要求
统计一个数字在排序数组中出现的次数。
例子：
1
2
3
4
5
| 输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
|
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums 是一个非递减数组-109 <= target <= 109
思路分析
二分查找思想
例如target=8，那么我们先找第一个8的位置，用left指向它，再找到最后一个8的位置，用right指向它，最后将(right-left)+1返回即可；
代码实现
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
| class Solution {
public int search(int[] nums, int target) {
int left = binarySearch(nums,target,true);
int right = binarySearch(nums,target,false) - 1;
if(left <= right && right < nums.length && nums[left] == target && nums[right] == target){
return right-left +1;
}
return 0;
}
public int binarySearch(int[] nums,int target,boolean flag){
int left = 0,right = nums.length-1,len = nums.length;
while(left <= right){
int mid = left+(right - left) /2;
if(nums[mid] > target ||(flag && nums[mid] >= target)){
right = mid-1;
len = mid;
}else{
left = mid+1;
}
}
return len;
}
}
|
0~n-1中缺失的数字
剑指 Offer 53 - II. 0～n-1中缺失的数字 - 力扣（Leetcode）
题目要求
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
例子：
1
2
3
4
5
| 输入: [0,1,3]
输出: 2
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
|
提示：
1 <= 数组长度 <= 10000
思路分析
二分查找
因为是从0开始到n-1，那么如果不是缺失的数，它的值和下标是相对应的；通过判断mid值是否和下标相等，不断的缩小查找的范围，直到最后剩下一个值，就是我们要找的；
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int missingNumber(int[] nums) {
int left = 0,right = nums.length-1;
while(left<right){
int mid = left + (right-left)/2;
if(nums[mid] == mid){
left = mid + 1;
}else{
right = mid;
}
}
return nums[left] == left ? left + 1 : left;
}
}
|
二叉搜索树的第k大节点
剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣（Leetcode）
题目要求
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
例子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4
|
提示
1 ≤ k ≤ 二叉搜索树元素个数
思路分析
使用中序遍历的顺序为左子树->根节点->右子树，但是该题需要找第 k 大的节点，那我们把中序遍历顺序改为右子树->根节点->左子树，每次遍历打印根节点时让k-1(根节点实际不打印)，直到k=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
|
class Solution {
int k = 0;
int target = 0;
public int kthLargest(TreeNode root, int k) {
this.k = k;
rightRootLeft(root);
return target;
}
public void rightRootLeft(TreeNode root){
if(root == null || k <= 0) return;
rightRootLeft(root.right);
k--;
if(k == 0){
target = root.val;
}
rightRootLeft(root.left);
}
}
|
