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

李恒道

https://leetcode.cn/problems/sum-root-to-leaf-numbers/submissions/574873979/?envType=study-plan-v2&envId=top-interview-150
dfs秒了

var sumNumbers = function (root) {
    let str = [];
    let total = 0;

    const dfs = (head) => {
        if(head==null){
            return
        }
        str.push(head.val);
        if (head.left == null && head.right == null) {
            total+=parseInt(str.join(""))
        } else {
            dfs(head.left);
            dfs(head.right);
        }
        str.pop()
    }
    dfs(root)
    return total

};

李恒道

https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/submissions/575398891/
约瑟夫问题

var iceBreakingGame = function (num, target) {
    const dfs = (n, len) => {
        if (n == 1) {
            return 0
        }
        return (dfs(n - 1, len - 1) + target) % len
    }
    return dfs(num, num)
};

李恒道

https://leetcode.cn/problems/patching-array/submissions/575406181/
边界题

var minPatches = function (nums, n) {
    let border = 0;
    let addNum = 0;
    for (let index = 0; index < nums.length; index++) {
        const num = nums[index]
        while (border < num - 1) {
            border += (border + 1)
            addNum++;
            if (border >= n) {
                return addNum
            }
        }
        border += num
        if (border >= n) {
            return addNum
        }
    }
    while (border < n) {
        border += (border + 1)
        addNum++;
        if (border >= n) {
            return addNum
        }
    }
};

李恒道

https://leetcode.cn/problems/design-add-and-search-words-data-structure/submissions/575498971/?envType=study-plan-v2&envId=top-interview-150
基础题

var WordDictionary = function () {
    this.tree = {}
};

/** 
 * @param {string} word
 * @Return {void}
 */
WordDictionary.prototype.addWord = function (word) {
    word = word.split("");
    let head = this.tree
    for (let index = 0; index < word.length; index++) {
        const char = word[index];
        head = head[char] ?? (head[char] = {})
    }
    head.end = true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function (word) {
    word = word.split("")
    const dfs = (node, pos) => {
        if (pos >= word.length) {
            return node.end!==undefined? true:false
        }
        if (word[pos] !== '.') {
            if (node[word[pos]] !== undefined) {
                return dfs(node[word[pos]], pos + 1)
            } else {
                return false
            }
        } else {
            const arr = Object.keys(node)
            for (let index = 0; index < arr.length; index++) {
                const char = arr[index];
                if(char=='end'){
                    continue;
                }
                if (dfs(node[char], pos + 1)) {
                    return true
                }
            }
            return false
        }
    }
    return dfs(this.tree, 0)
};

李恒道

https://leetcode.cn/problems/distinct-subsequences-ii/

卡我边界我靠

var distinctSubseqII = function (s) {
    const cache = new Map()
    let all = 1;
    const mod = 1e9 + 7
    for (let index = 0; index < s.length; index++) {
        const char = s[index];
        const lastAll = all
        all = (all + all)
        all = all % mod
        all = (all - (cache.get(char) ?? 0) + mod) % mod;
        cache.set(char, lastAll)
    }
    return (all - 1 + mod) % mod
};

李恒道

扣边界版本

var distinctSubseqII1 = function (s) {
    const cache = new Map()
    let all = 0;
    const mod = 1e9 + 7
    for (let index = 0; index < s.length; index++) {
        const char = s[index];
        const lastAll = all
        all = (all + all + 1)% mod
        all = (all - (cache.get(char) ?? 0) + mod) % mod;
        cache.set(char, lastAll + 1)
    }
    return all
};

李恒道

https://leetcode.cn/problems/maximum-total-reward-using-operations-i/submissions/
这题卡的要死

var maxTotalReward = function (rewardValues) {
    rewardValues = rewardValues.sort((a, b) => a - b)
    const dp = new Array(rewardValues.length).fill(0)
        .map(() => new Array(rewardValues[rewardValues.length - 1] * 2).fill(0))
    for (let index = 0; index < dp.length; index++) {
        dp[index][0] = true
    }
    dp[0][rewardValues[0]] = true
    let maxValue = rewardValues[0]
    for (let index = 1; index < dp.length; index++) {
        for (let indey = 1; indey < dp[0].length; indey++) {
            dp[index][indey] = dp[index - 1][indey]
            if ((indey - rewardValues[index]) < rewardValues[index]) {
                dp[index][indey] = dp[index][indey] || dp[index - 1][indey - rewardValues[index]]
            }
            if (dp[index][indey]) {
                maxValue = Math.max(maxValue, indey)
            }
        }
    }
    return maxValue
};

李恒道

https://leetcode.cn/problems/palindrome-pairs/submissions/575765214/
搞了半天回文对比偷懒导致的过不去...

var palindromePairs = function (words) {
    const cache = new Map()
    for (let index = 0; index < words.length; index++) {
        const word = words[index].split("").reverse().join("");
        cache.set(word, index)
    }
    let result = [];

    const isPalindrome = (str) => {
        let l = 0, r = str.length - 1;
        while (l < r) {
            if (str[l] == str[r]) {
                l++;
                r--
            } else {
                return false
            }
        }
        return true;
    }
    for (let index = 0; index < words.length; index++) {
        const word = words[index];
        if (isPalindrome(word) && cache.has("") && word !== "") {
            result.push([index, cache.get("")])
        }
        for (let len = 1; len <= word.length; len++) {
            const left = word.slice(0, len);
            const right = word.slice(len, word.length);

            if (isPalindrome(left) && cache.has(right)) {
                result.push([cache.get(right), index])
            }
            if (isPalindrome(right) && cache.has(left) && cache.get(left) !== index) {
                result.push([index, cache.get(left)])
            }
        }

    }
    return result

};