力扣labuladong——一刷day35

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

就这么说吧，所有递归的算法，你甭管它是干什么的，本质上都是在遍历一棵（递归）树，然后在节点（前中后序位置）上执行代码，你要写递归算法，本质上就是要告诉每个节点需要做什么

一、力扣912. 排序数组

class Solution {
    public int[] sortArray(int[] nums) {
        Merge.sort(nums);
        return nums;
    }
}
class Merge{
    public static int[] temp;
    public static void sort(int[] nums){
        temp = new int[nums.length];
        sort(nums, 0, nums.length-1);
    }
    public static void sort(int[] nums, int low, int high){
        if(low == high){
            return;
        }
        int mid = low + (high-low)/2;
        sort(nums, low, mid);
        sort(nums,mid+1,high);
        merge(nums,low,high,mid);
    }
    public static void merge(int[] nums, int low, int high, int mid){
        for(int a = low; a <= high; a ++){
            temp[a] = nums[a];
        }
        int i = low, j = mid+1, k = low;
        for(; i <= mid && j <= high;){
            if(temp[i] < temp[j]){
                nums[k++] = temp[i++];
            }else{
                nums[k++] = temp[j++];
            }
        }
        while(i <= mid){
            nums[k++] = temp[i++];
        }
        while(j <= high){
            nums[k++] = temp[j++];
        }
    }
}
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

二、力扣 315. 计算右侧小于当前元素的个数

class Solution {
    private class Pair{
        int id;
        int val;
        public Pair(int id, int val){
            this.id = id;
            this.val = val;
        }
    }
    Pair[] temp;
    int[] count;
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        temp = new Pair[n];
        Pair[] arr = new Pair[n];
        for(int i = 0; i < n; i ++){
            arr[i] = new Pair(i,nums[i]);
        }
        count = new int[n];
        sort(arr,0,n-1);
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < n; i ++){
            res.add(count[i]);
        }
        return res;
    }
    public void sort(Pair[] 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,high,mid);
    }
    public void merge(Pair[] arr, int low, int high, int mid){
        for(int i = low; i <= high; i ++){
            temp[i] = arr[i];
        }
        for(int i = low, j = mid+1, k = low; k <= high; k ++){
            if(i == mid+1){
                arr[k] = temp[j++];
            }else if(j == high+1){
                count[temp[i].id] += j-mid-1;
                arr[k] = temp[i++];
            }else if(temp[i].val > temp[j].val){
                arr[k] = temp[j++];
            }else{
                count[temp[i].id] += j-mid-1;
                arr[k] = temp[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
50
51
52
53
54

三、力扣493. 翻转对

class Solution {
    int[] temp;
    int count = 0;
    public int reversePairs(int[] nums) {
        temp = new int[nums.length];
        sort(nums,0, nums.length-1);
        return count;
    }
    public void sort(int[] nums, int low, int high){
        if(low == high){
            return;
        }
        int mid = low + (high-low)/2;
        sort(nums,low,mid);
        sort(nums,mid+1,high);
        merge(nums,low,high,mid);
    }
    public void merge(int[] nums, int low, int high, int mid){
        for(int i = low; i <= high; i ++){
            temp[i] = nums[i];
        }
        int end = mid+1;
        for(int i = low; i <= mid; i ++){
            while(end <= high && (long)nums[i] > (long)2*nums[end]){
                end ++;
            }
            count += end - mid -1;
        }
        for(int i = low, j = mid+1, k = low; k <= high; k ++){
            if(i == mid+1){
                nums[k] = temp[j++];
            }else if(j == high+1){
                nums[k] = temp[i++];
            }else if(temp[i] > temp[j]){   
                nums[k] = temp[j++];
            }else{
                nums[k] = temp[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

四、力扣327. 区间和的个数

class Solution {
    int lower,upper,count=0;
    long[] temp;
    public int countRangeSum(int[] nums, int lower, int upper) {
        this.lower= lower;
        this.upper = upper;
        long[] preSum = new long[nums.length+1];
        for (int i = 0; i < nums.length; i++) {
            preSum[i + 1] = (long)nums[i] + preSum[i];
        }
        temp = new long[preSum.length];
        sort(preSum, 0, preSum.length-1);
        return count;
    }
    public void sort(long[] nums, int low, int high){
        if(low == high){
            return;
        }
        int mid = low + (high-low)/2;
        sort(nums,low,mid);
        sort(nums,mid+1,high);
        merge(nums,low,high,mid);
    }
    public void merge(long[] nums,int low, int high, int mid){
        for(int i = low; i <= high; i ++){
            temp[i] = nums[i];
        }
        int start = mid+1, end = mid+1;
        for(int i = low; i <= mid; i ++){
            while(start <= high && nums[start]-nums[i] < lower){
                start ++;
            }
            while(end <= high && nums[end] - nums[i] <= upper){
                end ++;
            }
            count += end-start;
        }
        for(int i = low, j = mid+1, k = low; k <= high; k ++){
            if(i == mid+1){
                nums[k] = temp[j++];
            }else if(j == high+1){
                nums[k] = temp[i++];
            }else if(temp[i] > temp[j]){
                nums[k] = temp[j++];
            }else{
                nums[k] = temp[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
50