Count sorting

  1. Count the number of occurrences of each item
  2. Output the corresponding value according to the number of counts
  3. It is used in sorting scenarios with limited range

Radix sort

  1. Count the number of occurrences of each lower 16 digit, find the prefix and sort it in temp
  2. Count the number of occurrences of each digit with the highest 16 digits, find the prefix and sort the number of temp in the original array
  3. Radix sort is to make use of the stability between the data sorted in the previous two steps to achieve the final sorting effect

A topological sort

  1. Count the input degree of all elements and their corresponding relations, and add the element with the input degree of 0 to the team
  2. For each element in the queue, the entry degree of the element is reduced by one. If the entry degree of the element is 0, the element is in the queue
  3. Queue eject elements are topology sequences

LeetCode liver problem

    1. Relative sorting of arrays
// Count the number of occurrences of all numbers in arR1, arrange them according to the order of arR2, and add the rest
var relativeSortArray = function(arr1, arr2) {
    let cut = new Array(1001).fill(0)
    for(let i of arr1) cut[i]++
    let k = 0
    for(let i = 0; i < arr2.length; i++) {
        for(let j = 0; j < cut[arr2[i]]; j++) {
            arr1[k++] = arr2[i]
        }
        cut[arr2[i]] = 0
    }
    for(let i in cut) {
        if (cut[i] == 0) continue
        for(let j = 0; j < cut[i]; j++) arr1[k++] = i
    }
    return arr1
};
Copy the code
    1. The largest spacing
Cut [I]-1 = nums I = temp; // Cut [I]-1 = nums I = temp
Cut [I]-1 is the nums sorted position of I in temp. Cut [I]-1 is the nums sorted position of I
// Calculate the maximum difference of each element after sorting
var maximumGap = function(nums) {
    if (nums.length < 2) return 0
    let cut = new Array(65536).fill(0), temp = new Array(nums.length).fill(0)
    for(let i of nums) cut[i % 65536] + =1
    for(let i = 1; i < cut.length; i++) cut[i] += cut[i - 1]
    for(let i = nums.length - 1; i >=0 ; --i) temp[--cut[nums[i] % 65536]] = nums[i]
    cut.fill(0)
    for(let i of temp) cut[parseInt(i / 65536+ =)]1
    for(let i = 1; i < 65536; i++) cut[i] += cut[i - 1]
    for(let i = temp.length - 1; i >= 0; --i) nums[--cut[parseInt(temp[i] / 65536)]] = temp[i]
    let ans = 0
    for(let i = 1; i < nums.length; i++) {
        ans = Math.max(ans, nums[i] - nums[i - 1])}return ans
};
Copy the code
    1. H index,
// Sort the array by iterating over the number of digits that are greater than or equal to the reciprocal of the element at the end of the array
var hIndex = function(citations) {
    citations = citations.sort((a,b) = > a - b)
    let h = 1, len = citations.length
    while(h <= len && citations[len - h] >= h) ++h
    return h-1
};
Copy the code
    1. The curriculum
// Compute the topology order
var canFinish = function(numCourses, prerequisites) {
    let indeg = Array(numCourses).fill(0), g = Array(numCourses), q = [], cut = 0
    for(let i = 0; i < g.length; i++) g[i] = []
    for(let item of prerequisites) {
        indeg[item[0]] + =1
        g[item[1]].push(item[0])}for(let i = 0; i < indeg.length; i++) {
        if (indeg[i] == 0) q.push(i)
    }
    while(q.length > 0) {
        let top = q.shift()
        cut++
        for(let i of g[top]) {
            indeg[i] -= 1
            if (indeg[i] == 0) q.push(i)
        }
    }
    return cut == numCourses
};
Copy the code
    1. Schedule II
// Standard topological sort
var findOrder = function(numCourses, prerequisites) {
    let indeg = Array(numCourses).fill(0), g = Array(numCourses), q = [], ans = []
    for(let i = 0; i < g.length; i++) g[i] = []
    for(let item of prerequisites) {
        indeg[item[0]] + =1
        g[item[1]].push(item[0])}for(let i = 0; i < indeg.length; i++) {
        if (indeg[i] == 0) q.push(i)
    }
    while(q.length > 0) {
        let top = q.shift()
        ans.push(top)
        for(let i of g[top]) {
            indeg[i] -= 1
            if (indeg[i] == 0) q.push(i)
        }
    }
    return ans.length == numCourses ? ans : []
};
Copy the code
    1. Merge range
// Sort by the first item, then iterate to determine whether the endpoints at both ends are inclusive
var merge = function(intervals) {
    intervals = intervals.sort((a, b) = > a[0] - b[0])
    let ans = [intervals[0]]
    for(let i = 1; i < intervals.length; i++) {
        let len = ans.length - 1
        if (intervals[i][0] <= ans[len][1] && intervals[i][1] > ans[len][1]) {
            ans[len][1] = intervals[i][1]}if (intervals[i][0] > ans[len][1]) {
            ans.push(intervals[i])
        }
    }
    return ans
};
Copy the code
    1. Delete an overwritten range
// The first item is sorted from the smallest to the largest, and the second item is sorted from the largest to the smallest
var removeCoveredIntervals = function(intervals) {
    intervals = intervals.sort((a, b) = > {
        if (a[0] == b[0]) return b[1] - a[1]
        return a[0] - b[0]})let ans = [intervals[0]]
    for(let i = 1; i < intervals.length; i++) {
        let len = ans.length - 1
        if(intervals[i][0] >= ans[len][0] && intervals[i][1] <= ans[len][1]) {
            continue
        }
        ans.push(intervals[i])
    }
    return ans.length
};
Copy the code
  1. 491. Increasing subsequence
// Give recursive functions an explicit meaning:
// Find the combination of the KTH bit from nums and the position after it into the buff and add it to the result array
var getResult = function(nums, k, buff, ans) {
    if (buff.length > 1) ans.push(JSON.parse(JSON.stringify(buff)))
    buff.push(0)
    let map = {}
    for(let i = k; i < nums.length; i++) {
        if (map[nums[i]]) continue
        if (buff.length == 1 || nums[i] >= buff[buff.length - 2]) {
            buff[buff.length - 1] = nums[i]
            map[nums[i]] = 1
            getResult(nums, i + 1, buff, ans)
            buff.pop()
        }
    }
}
var findSubsequences = function(nums) {
    let ans = []
    getResult(nums, 0, [], ans)
    return ans
};
Copy the code
  1. Interview question 04.12. Summing up paths
// Give recursive functions an explicit meaning:
// pathSum: the number of paths found and sum is equal to the number of paths found from the root node + the number of paths found in the left subtree + the number of paths found in the right subtree
// getPathSum: Finds the sum of the paths from the current node. If the current node is equal to sum, a path is found. Then returns the sum of the left subtree (sum-root.val) + the sum of the right subtree (sum-root.val) + the number of paths currently found (1 or 0)
var getPathSum = function(root, sum) {
    if(! root)return 0
    const val = sum - root.val, a = root.val == sum ? 1 : 0
    return a + getPathSum(root.left, val) + getPathSum(root.right, val)
}
var pathSum = function(root, sum) {
    if(! root)return 0
    return getPathSum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum)
};









Copy the code