Merge sort

  1. Process the left to get the information on the left
  2. Process the right to get the information on the right
  3. Complete the merge process to get information across both sides

Hand rip merge sort

// Divide the array into left and right sides until the number of elements is 1
// Define a storage space temp to store sorted target arrays with Pointers P1 and p2 to the left and right arrays respectively
// Place the smaller values pointed to by P1 and p2 into the temp array and move the pointer backwards
// Finally, put the temp values into arR in order to complete the sorting
function merge_sort(arr, l, r) {
    if (l >= r) return
    let mid = (l + r) >> 1
    merge_sort(arr, l, mid)
    merge_sort(arr, mid + 1, r)
    let temp = Array(r - l + 1), k = 0, p1 = l, p2 = mid + 1
    while (p1 <= mid || p2 <= r) {
        if (p2 > r || (p1 <= mid && arr[p1] <= arr[p2])) {
            temp[k++] = arr[p1++]
        } else {
            temp[k++] = arr[p2++]
        }
    }
    for(let i = l; i <= r; i++) arr[i] = temp[i - l]
}
Copy the code

LeetCode liver problem

  1. Sword refers to Offer 51. Reverse pair in array
// In merge sort, the inversions in the array are equal to the inversions on the left + the inversions on the right + the inversions across the left and right
// Inversions across the left and right ranges are the remaining values of the left ranges when the right ranges enter temp during the merge (mid-p1+1)
var temp = []
var countReversePairs = function(nums, l, r) {
    if (l >= r) return 0;
    let mid = (l + r) >> 1, ans = 0;
    ans += countReversePairs(nums, l, mid);
    ans += countReversePairs(nums, mid + 1, r);
    let k = l, p1 = l, p2 = mid + 1;
    while((p1 <= mid) || (p2 <= r)) {
        if ((p2 > r) || (p1 <= mid && nums[p1] <= nums[p2])) {
            temp[k++] = nums[p1++]
        } else {
            temp[k++] = nums[p2++]
            ans += (mid - p1 + 1)}}for(let i = l; i <= r; i++) nums[i] = temp[i]
    return ans
}
var reversePairs = function(nums) {
    while (temp.length < nums.size) temp.push(0);
    return countReversePairs(nums, 0, nums.length - 1)};Copy the code
    1. Merge K ascending linked lists
// Iterate through lists to put each list into priority queue, pop the smallest node after virtual node RET each time, finally return ret.next
var mergeKLists = function(lists) {
    let q = new MinPriorityQueue({priority: p= > p.val}), ret = new ListNode()
    for (let i = 0; i < lists.length; i++) {
        if(! lists[i])continue
        q.enqueue(lists[i])
    }
    let p = ret
    while(! q.isEmpty()) {let top = q.dequeue()
        if (top.element.next) q.enqueue(top.element.next)
        p.next = top.element
        p = p.next
    }
    return ret.next
};
Copy the code
    1. Sorting list
var mergeSort = function(head, n) {
    if(! head || ! head.next)return head;
    let l = n >> 1, r = n - l;
    let lp = head, rp = lp, p
    for (let i = 1; i < l; i ++) rp = rp.next
    p = rp
    rp = rp.next
    p.next = null
    lp = mergeSort(lp, l)
    rp = mergeSort(rp, r)
    let ret = new ListNode()
    p = ret
    while(lp || rp) {
        if (rp == null || (lp && lp.val <= rp.val)) {
            p.next = lp
            lp = lp.next
            p = p.next
        } else {
            p.next = rp
            rp = rp.next
            p = p.next
        }
    }
    return ret.next;

}
var sortList = function(head) {
    let n = 0, p = head;
    while (p) {
        n += 1
        p = p.next;
    } 
    return mergeSort(head, n);
};
Copy the code
    1. Two binary search trees for all elements
var sortTree = function(root, arr) {
    if(! root)return []
    root.left && sortTree(root.left, arr)
    arr.push(root.val)
    root.right && sortTree(root.right, arr)
    return arr
}
var getAllElements = function(root1, root2) {
    let arr_left = sortTree(root1, []), arr_right = sortTree(root2, [])
    let i = 0, j = 0, ans = []
    while(i < arr_left.length || j < arr_right.length) {
        if (j >= arr_right.length || (i < arr_left.length && arr_left[i] <= arr_right[j])) {
            ans.push(arr_left[i])
            i++
        } else {
            ans.push(arr_right[j])
            j++
        }
    }
    return ans
};
Copy the code
    1. The number of intervals
Sum [j] -sum [I] is between lower and upper and j> I
// The sum on the left + the sum on the right + the number of intervals across the sum on the left
var countTwoPart = function(sum, l1, r1, l2, r2, lower, upper) {
    let ans = 0, k1 = l1, k2 = l1
    for(let j = l2; j <= r2; j++) {
        let a = sum[j] - upper
        let b = sum[j] - lower
        while(k1 <= r1 && sum[k1] < a) k1 += 1
        while(k2 <= r1 && sum[k2] <= b) k2 += 1
        ans += k2 - k1
    }
    return ans
}
var margeSort = function(sum, l, r, lower, upper) {
    if (l >= r) return 0
    let mid = (l + r) >> 1, ans = 0
    ans += margeSort(sum, l, mid, lower, upper)
    ans += margeSort(sum, mid + 1, r, lower, upper)
    ans += countTwoPart(sum, l, mid, mid + 1, r, lower, upper)
    let k = l, p1 = l, p2 = mid + 1
    while(p1 <= mid || p2 <= r) {
        if (p2 > r || (p1 <= mid && sum[p1] <= sum[p2])) {
            temp[k++] = sum[p1++]
        } else {
            temp[k++] = sum[p2++]
        }
    }
    for(let i = l; i <= r; i++) sum[i] = temp[i]
    return ans
}
let temp
var countRangeSum = function(nums, lower, upper) {
    let sum = Array(nums.length + 1)
    temp = Array(nums.length + 1).fill(0)
    sum[0] = 0
    for (let i = 0; i < nums.length; i++) sum[i + 1] = nums[i] + sum[i]
    return margeSort(sum, 0, sum.length - 1, lower, upper)
};
Copy the code
    1. Maximum suborder sum
// Find the prefix and array, iterate over the prefix and array and subtract the smaller value from the larger value
var maxSubArray = function(nums) {
    let sum = [0], pre = 0
    for (let i = 0; i < nums.length; i++) sum.push(nums[i] + sum[i])
    let ans = sum[1]
    for (let i = 1; i < sum.length; i++) {
        ans = Math.max(sum[i] - pre, ans)
        pre = Math.min(sum[i], pre)
    }
    return ans
};
Copy the code
    1. Subarray and sorted interval sum
// 0,0,1, 0,2... 0,n-1, and 1,1,1,2,1,3... One,n minus one and so on must be ordered,
// The idea of mimicking merging is to put each sequence pair into a priority queue, popup the minimum each time and add the sum
var rangeSum = function(nums, n, left, right) {
    let q = new MinPriorityQueue({priority: p= > p.sum})
    for (let i = 0; i < n; i++) {
        q.enqueue({i: i, j: i, sum: nums[i]})
    }
    let ans = 0, mod = 1000000000+7
    for (let i = 0; i < right; i++) {
        let top = q.dequeue().element
        if (top.j < n - 1) q.enqueue({i: top.i, j: top.j + 1.sum: top.sum + nums[top.j + 1]})
        if (i >= left - 1) ans += top.sum
    }
    return ans % mod
};
Copy the code
  1. 04.08. First common ancestor
// Give recursive functions an explicit meaning: find nodes whose values are equal to p or q
// If the current node is p or q, it is the first common ancestor
// If p or Q is found in both subtrees, the ancestor is the first common ancestor
// If only one can be found, that means the first common ancestor is found
var lowestCommonAncestor = function(root, p, q) {
    if(! root)return root
    if (root == p || root == q) return root
    let l = lowestCommonAncestor(root.left, p, q), r = lowestCommonAncestor(root.right, p, q)
    if (l && r) return root
    if (l) return l
    return r
};
Copy the code
    1. The sum of the deepest leaf nodes
// For each subtree recursion, the ans is reset at deeper levels, equal to the accumulation at deeper levels
function getResult(root, k, result) {
    if(! root)return
    if (k == result.max_k) result.ans += root.val
    if (k > result.max_k) {
        result.max_k = k
        result.ans = root.val
    }
    getResult(root.left, k + 1, result)
    getResult(root.right, k + 1, result)
    return
}
var deepestLeavesSum = function(root) {
    let result = {
        max_k: 0.ans: 0
    }
    getResult(root, 1, result)
    return result.ans
};
Copy the code