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

李恒道

https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/submissions/566841289/?envType=study-plan-v2&envId=dynamic-programming
没逼出来转移
缓存给掏了

var longestSubsequence = function (arr, difference) {
    const dp = new Array(arr.length).fill(1)
    let max = 0
    const cache = new Map()
    for (let index = 0; index < arr.length; index++) {
        const num = arr[index];
        if(cache.has(num-difference)){
            dp[index] =dp[cache.get(num-difference)] +1
        }
        cache.set(num, index)
        max = Math.max(max, dp[index])
    }
    return max
};

李恒道

https://leetcode.cn/problems/uncrossed-lines/submissions/566871965/?envType=study-plan-v2&envId=dynamic-programming
一开始没灵感
看下评论是最长子序列
秒了！

var maxUncrossedLines = function (nums1, nums2) {
    const dp = new Array(nums1.length + 1).fill(0).map(() => new Array(nums2.length + 1).fill(0));
    for (let index = 1; index < dp.length; index++) {
        for (let indey = 1; indey < dp[0].length; indey++) {
            if (nums1[index - 1] == nums2[indey - 1]) {
                dp[index][indey] = dp[index - 1][indey - 1] + 1
            } else {
                dp[index][indey] = Math.max(dp[index - 1][indey], dp[index][indey - 1])
            }
        }
    }
    return dp[nums1.length][nums2.length]
};

李恒道

https://leetcode.cn/problems/longest-arithmetic-subsequence/submissions/567002873/?envType=study-plan-v2&envId=dynamic-programming
这题理清也花了挺久的
主要能感觉到是多维
但是搞了半天等差也没解决
最后发现原来根据数据范围定义
精妙

var longestArithSeqLength = function (nums) {
    const minv = _.min(nums);
    const maxv = _.max(nums);
    const sep = maxv - minv;
    let ans = 0
    for (let index = -sep; index <= sep; index++) {
        if(index==-5){
            debugger
        }
        const cache = new Map()
        for (const num of nums) {
            if (num >= 0 && num - index <= maxv) {
                if (cache.has(num - index)) {
                    cache.set(num, cache.get(num - index) + 1)
                } else {
                    cache.set(num, 1)
                }
                ans=Math.max(ans,cache.get(num))
            }else{
                cache.set(num, 1)
            }

        }

    }
    return ans;
};

李恒道

https://leetcode.cn/problems/russian-doll-envelopes/submissions/567169728/?envType=study-plan-v2&envId=dynamic-programming
抬手打上了一波dp，dp超时了
以为是贪心，贪心g了
又试二分，边界没扣明白也g了...

var maxEnvelopes = function (envelopes) {
    envelopes = envelopes.sort((a, b) => {
        if (a[0] == b[0]) {
            return b[1] - a[1]
        }
        return a[0] - b[0]
    })
    const arr = []
    const findIndex = (num) => {
        let left = 0, right = arr.length - 1;
        while (left < right) {
            const center = left + Math.floor((right-left) / 2)
            if (arr[center] < num) {
                left = center + 1
            } else {
                right = center
            }
        }
        return left
    }
    for (let index = 0; index < envelopes.length; index++) {
        const envelop = envelopes[index][1];
        if (arr[arr.length - 1] < envelop) {
            arr.push(envelop)
        } else {
           const index= findIndex(envelop)
           arr[index]=envelop
        }
    }
    return arr.length

};

李恒道

https://leetcode.cn/problems/find-the-longest-valid-obstacle-course-at-each-position/submissions/567246405/?envType=study-plan-v2&envId=dynamic-programming
本来理清了，感觉是二分
还是不熟练
二分被我写错了好多边界炸了

var longestObstacleCourseAtEachPosition = function (obstacles) {
    const arr = []
    const findIndex = (num) => {
        let left = 0, right = arr.length - 1;
        while (left < right) {
            const center = left + Math.floor((right - left) / 2)
            if (arr[center] < num) {
                left = center + 1
            } else if (arr[center] == num) {
                left = center + 1
            } else{
                right = center
            }
        }
        return left
    }
    const result = []
    for (let index = 0; index < obstacles.length; index++) {
        const num = obstacles[index];
        if (index == 8) {
            debugger
        }
        if (arr.length == 0 || arr[arr.length - 1] <= num) {
            arr.push(num)
            result.push(arr.length)
        } else {
            const index = findIndex(num);
            result.push(arr[index] == num ? index + 2 : index + 1);
            arr[index] = num;
        }

    }
    return result
};

李恒道

https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/submissions/567248011/?envType=study-plan-v2&envId=dynamic-programming
困难题一波缓存秒了！

var minInsertions = function (s) {
    const cache=new Map()
    const dfs = (l, r) => {
        if(cache.has(`${l} ${r}`)){
            return cache.get(`${l} ${r}`)
        }
        if (l == r || l > r) {
            return 0
        }
        let result=0
        if (s[l] === s[r]) {
            result= dfs(l + 1, r - 1)
        } else {
            result= Math.min(dfs(l + 1, r), dfs(l, r - 1)) + 1
        }

        cache.set(`${l} ${r}`,result)
        return result
    }
    return dfs(0, s.length - 1)
};

李恒道

https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/submissions/567260989/?envType=study-plan-v2&envId=dynamic-programming
动态规划版本

var minInsertions = function (s) {
    const dp = new Array(s.length).fill(0).map(() => {
        return new Array(s.length).fill(0)
    })
    for (let index = s.length - 2; index >= 0; index--) {
        for (let indey = index + 1; indey < s.length; indey++) {
            if (s[index] == s[indey]) {
                dp[index][indey] = dp[index + 1][indey - 1]
            } else {
                dp[index][indey] = Math.min(dp[index][indey - 1], dp[index + 1][indey]) + 1
            }

        }
    }

    return dp[0][s.length - 1]
};

李恒道

https://leetcode.cn/problems/isomorphic-strings/submissions/567292154/?envType=study-plan-v2&envId=top-interview-150
简单题平复一下心情，今天收工

var isIsomorphic = function (s, t) {
    const cache1 = {

    }
    const cache2 = {

    }
    for (let index = 0; index < s.length; index++) {
        const char1 = s[index];
        const char2 = t[index];
        if ((cache1[char1] !== undefined && cache1[char1] !== char2) || (cache2[char2] !== undefined && cache2[char2] !== char1)) {
            return false
        } else {
            cache1[char1] = char2
            cache2[char2]=char1
        }
    }
    return true
};

李恒道

https://leetcode.cn/problems/word-pattern/submissions/567303904/?envType=study-plan-v2&envId=top-interview-150
过了！

var wordPattern = function (pattern, s) {
    s = s.split(" ");
    const cache = new Map();
    const reverseCache = new Map();
    for (let index = 0; index < s.length; index++) {
        const word = s[index];
        const pChar = pattern[index];
        if (cache.get(pChar) == undefined &&  reverseCache.get(word) == undefined) {
            cache.set(pChar, word)
            reverseCache.set(word, pChar)
        } else {
            if (cache.get(pChar) != word) {
                return false
            }
            if (reverseCache.get(word) != pChar) {
                return false
            }
        }

    }
    for (let index = 0; index < pattern.length; index++) {
        const char = pattern[index];
        if (cache.get(char)== undefined) {
            return false
        }
    }
    for (let index = 0; index < s.length; index++) {
        const word = s[index];
        if (reverseCache.get(word)== undefined) {
            return false
        }
    }
    return true
};

李恒道

https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/submissions/567381052/?envType=study-plan-v2&envId=top-interview-150
贪心秒了！

var findMinArrowShots = function (points) {
    points = points.sort((a, b) => a[0] - b[0])
    let result = [points[0]]
    for (let index = 1; index < points.length; index++) {
        const point = points[index]
        const lastPoint = result[result.length - 1]
        if (point[0]<=lastPoint[1] ) {
            result.pop();
            result.push([Math.max(point[0], lastPoint[0]), Math.min(point[1], lastPoint[1])])
        }else{
            result.push(point)
        }
    }
    return result.length
};