【当前无排名】挑战leetcode进入前1w名

李恒道

https://leetcode.cn/problems/summary-ranges/submissions/573763991/?envType=study-plan-v2&envId=top-interview-150
简单题，收工

var summaryRanges = function (nums) {
    if (nums.length == 1) {
        return ["" + nums[0]]
    }
    const result = []
    nums.push("")
    let startNum = nums[0];
    let endNum = nums[0]
    for (let index = 1; index < nums.length; index++) {
        const num = nums[index];
        if (num == endNum + 1) {
            endNum = endNum + 1
        } else {
            result.push(startNum == endNum ? "" + endNum : startNum + "->" + endNum)
            startNum = nums[index]
            endNum = nums[index]
        }
    }
    return result
};

李恒道

https://leetcode.cn/problems/permutation-in-string/submissions/573963026/
复杂hash表问题
主要就是考coding能力...

var checkInclusion = function (s1, s2) {
    const hash = new Map();
    for (let index = 0; index < s1.length; index++) {
        const char = s1[index];
        hash.set(char, (hash.get(char) ?? 0) + 1)
    }
    let max = hash.size;
    for (let index = 0; index < s1.length; index++) {
        const char = s2[index];
        if (hash.has(char)) {
            const nums = hash.get(char)
            if (nums == 1) {
                max--;
            }
            hash.set(char, nums - 1)
        }
    }

    if (max == 0) {
        return true;
    }
    for (let index = s1.length; index < s2.length; index++) {
        if (index == 8) {
            debugger
        }
        const char = s2[index];
        if (hash.has(char)) {
            const nums = hash.get(char)
            if (nums == 1) {
                max--;
            }
            hash.set(char, nums - 1)
        }
        const popNum = hash.get(s2[index - s1.length])
        if (popNum !== undefined) {
            if (popNum == 0) {
                max++;
            }
            hash.set(s2[index - s1.length], popNum + 1)
        }
        if (max == 0) {
            return true;
        }
    }
    return false

};

李恒道

https://leetcode.cn/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-ii/submissions/573963836/
一次过，露头就秒！

var minOperations = function (nums) {
    let times = 0;
    let isReserver = false
    for (let index = 0; index < nums.length; index++) {
        let num = nums[index]
        if (isReserver) {
            num = num == 1 ? 0 : 1
        }
        if (num == 0) {
            times++;
            isReserver = !isReserver
        }
    }
    return times
};

李恒道

https://leetcode.cn/problems/count-the-number-of-inversions/submissions/573976840/?envType=daily-question&envId=2024-10-17
这题前几天没做出来
终于搞懂了
太复杂了...

var numberOfPermutations = function (n, requirements) {
    const req = new Map()
    for (const item of requirements) {
        req.set(item[0], item[1])
    }
    if (req[0] !== 0 && req[0] !== undefined) {
        return 0
    }
    const cache = new Array(n).fill(0).map(() => new Array(req.get(n - 1)+1).fill(-1))
    const dfs = (pos, needNums) => {
        if (pos == 0) {
            return needNums == 0 ? 1 : 0
        }
        if (cache[pos][needNums] !== -1) {
            return cache[pos][needNums]
        }
        const nextNeed = req.get(pos - 1)
        if (nextNeed == undefined) {
            const minIndex = Math.min(pos, needNums);
            let num = 0;
            for (let index = 0; index <= minIndex; index++) {
                num += dfs(pos - 1, needNums - index)
                num = num % 1000000007
            }
            cache[pos][needNums] = num
            return num
            //不存在
        } else {
            if (needNums < nextNeed) {
                cache[pos][needNums] = 0
                return 0
            }
            if (needNums - pos > nextNeed) {
                cache[pos][needNums] = 0
                return 0
            }
            const result = dfs(pos - 1, nextNeed) % 1000000007
            cache[pos][needNums] = result
            return result
        }
    }
    return dfs(n - 1, req.get(n - 1))
};

李恒道

https://leetcode.cn/problems/average-of-levels-in-binary-tree/submissions/573981968/?envType=study-plan-v2&envId=top-interview-150
二叉树遍历
秒了

var averageOfLevels = function (root) {
    const stack = []
    const result = []
    stack.push(root)
    while (stack.length !== 0) {
        let val = 0;
        let len = stack.length;
        for (let index = 0; index < len; index++) {
            const item = stack.shift()
            val += item.val;
            if (item.left != null) {
                stack.push(item.left)
            }
            if (item.right != null) {
                stack.push(item.right)
            }
        }
        result.push(val / len)
    }
    return result

};

李恒道

https://leetcode.cn/problems/smallest-range-i/submissions/574158049/
一开始以为贼复杂...
直到下决心试试先干一下看看...
发现一次过

var smallestRangeI = function (nums, k) {
    const min = Math.min(...nums);
    const max = Math.max(...nums);
    return (max - min - (2 * k)) < 0 ? 0 : (max - min - (2 * k))
};

李恒道

https://leetcode.cn/problems/reverse-integer/submissions/574321327/
简单题，今天累了水一下

var reverse = function (x) {
    let result = 0;
    const isNeg = x < 0 ? -1 : 1;
    x=Math.abs(x)
    while (x !== 0) {
        result = result * 10
        result += x % 10;
        x = Math.floor(x / 10)
    }
    if (result<-2147483648||result>2147483647){
        return 0
    }
    return result * isNeg
};

李恒道

https://leetcode.cn/problems/rotate-list/submissions/574326188/
链表题
凑个数睡觉

var rotateRight = function (head, k) {
    if(head==null){
        return head
    }
    let len = 1;
    let originHead = head
    while (head.next != null) {
        head = head.next;
        len++;
    }
    k = k % len
    if (k == 0) {
        return originHead
    }
    len = len - k ;
    head.next = originHead;
    for (let index = 0; index < len; index++) {
        head = head.next;
    }
    let ret = head.next;
    head.next = null;
    return ret
};

李恒道

https://leetcode.cn/problems/recover-binary-search-tree/submissions/574555795/
基础题，直接秒了

var recoverTree = function (root) {
    let firstNode = null;
    let secondNode = null;
    let lastNode = null;
    const dfs = (node) => {
        if (node == null) {
            return;
        }
        dfs(node.left)
        if (lastNode !== null) {
            if (lastNode.val > node.val) {
                firstNode = firstNode ?? lastNode
                secondNode = node
            }
        }
        lastNode = node;
        dfs(node.right)
    }
    dfs(root)
    const firstVal = firstNode.val;
    firstNode.val = secondNode.val;
    secondNode.val = firstVal
};

李恒道

https://leetcode.cn/problems/first-missing-positive/submissions/574564523/
秒了

var firstMissingPositive = function (nums) {
    let l = 0;
    let r = nums.length;
    const swap = (a, b) => {
        const temp = nums[a];
        nums[a] = nums[b]
        nums[b] = temp
    }
    for (let index = 0; index < nums.length; index++) {
        while (nums[index] > 0 && nums[index] <= nums.length && nums[nums[index] - 1] !== nums[index]) {
            swap(index, nums[index] - 1)
        }
    }
    for (let index = 0; index < nums.length; index++) {
        const num = nums[index];
        if (num !== index + 1) {
            return index + 1
        }
    }
    return nums.length + 1
};