Merge sort
- Process the left to get the information on the left
- Process the right to get the information on the right
- 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
- 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
-
- 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
-
- 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
-
- 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
-
- 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
-
- 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
-
- 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
- 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
-
- 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