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

李恒道

https://leetcode.cn/problems/zigzag-conversion/submissions/563823224/
这题过的也一般

var convert = function (s, numRows) {
    if(numRows===1){
        return s
    }
    const arr = new Array(numRows).fill(0).map(() => {
        return []
    })
    s = s.split("")
    let index = 0;
    let cycle = numRows * 2 - 2
    while (index < s.length) {
        const cycleIndex = index % cycle
        if (cycleIndex < numRows) {
            arr[cycleIndex].push(s[index])
        } else {
            arr[cycle-cycleIndex].push(s[index])
        }
        index++
    }
    let result=""
    for (let index = 0; index < arr.length; index++) {
        const charArr = arr[index];
        result+=charArr.join("")
    }
    return result
};

李恒道

https://leetcode.cn/problems/partition-labels/submissions/564073897/?envType=study-plan-v2&envId=top-100-liked
没读懂题...理解了直接一波秒了QAQ

var partitionLabels = function (s) {
    s = s.split("")
    const map = new Map()
    for (let index = 0; index < s.length; index++) {
        const char = s[index];
        map.set(char, index)
    }
    let end = map.get(s[0])
    let start = 0;
    const result = []
    for (let index = 0; index < s.length; index++) {
        const char = s[index];
        end = Math.max(map.get(char), end)
        if (end === index) {
            result.push(end - start + 1)
            start = end + 1;
            end = map.get(s[start])
        }
    }
    return result
};

李恒道

https://leetcode.cn/problems/pascals-triangle/submissions/564078200/?envType=study-plan-v2&envId=top-100-liked
基础dp，秒了！

var generate = function (numRows) {
    const arr = [1]
    const result = [[...arr]]
    for (let index = 1; index < numRows; index++) {
        arr.push(1)
        for (let pos = arr.length - 2; pos > 0; pos--) {
            arr[pos]=arr[pos]+arr[pos-1]
        }
        result.push([...arr])
    }
    return result
};

李恒道

https://leetcode.cn/problems/house-robber/submissions/564114516/?envType=study-plan-v2&envId=top-100-liked
缓存dp，秒

var rob = function (nums) {
    const map = new Map()
    const robHouse = (l) => {
        if (l >= nums.length) {
            return 0
        }
        if (map.has(l)) {
            return map.get(l)
        }
        const result1 = nums[l] + robHouse(l + 2);
        const result2 = robHouse(l + 1);
        const result = Math.max(result1, result2);
        map.set(l, result)
        return result
    }
    return robHouse(0)
};

李恒道

https://leetcode.cn/problems/perfect-squares/?envType=study-plan-v2&envId=top-100-liked
抄答案了，这题边界扣反了
我以为需要1一路加上去...
思路反了明明都差不多，结果完全不同
呜呜呜

var numSquares = function (n) {
    const cacheArr = new Array(n + 1).fill(0)
    cacheArr[1] = 1
    for (let index = 2; index <= n; index++) {
        let nums = Number.MAX_SAFE_INTEGER
        for (let indey = 1; indey * indey <= index; indey++) {
            nums = Math.min(nums, cacheArr[index - indey*indey])
        }
        cacheArr[index] = nums + 1
    }
    return cacheArr.pop()
};

李恒道

https://leetcode.cn/problems/coin-change/submissions/564195866/?envType=study-plan-v2&envId=top-100-liked
背包问题
秒！

var coinChange = function (coins, amount) {
    coins.sort((a,b)=>a-b)
    const cacheArr = new Array(amount + 1).fill(0)
    for (let index = 1; index < cacheArr.length; index++) {
        let nums = Number.MAX_SAFE_INTEGER-1
        for (let indey = 0; coins[indey] <= index; indey++) {
            nums = Math.min(nums, cacheArr[index-coins[indey]])
        }
        cacheArr[index] = nums + 1
    }
    const result=cacheArr.pop()
    return result===Number.MAX_SAFE_INTEGER?-1:result
};

李恒道

https://leetcode.cn/problems/word-break/submissions/564204978/?envType=study-plan-v2&envId=top-100-liked
缓存秒的
但是明显dfs的边界没扣好
懒得细化了

var wordBreak = function (s, wordDict) {
    s = s.split("")
    const map = new Map()
    let maxWordLength = 0
    for (const word of wordDict) {
        map.set(word, true)
        maxWordLength = Math.max(maxWordLength, word.length)
    }
    let result = false
    const cache = new Map()
    const dfs = (pos) => {
        if (result) {
            return;
        }
        if (pos >= s.length) {
            result = true;
            return;
        }
        let char = ""
        for (let index = 0; (index < maxWordLength && (pos+index) < s.length)&&(!result); index++) {
            char += s[pos + index]
            if (map.has(char)&&(!cache.has(pos+ char.length))) {
                dfs(pos + char.length)
            }
        }
        cache.set(pos, false)
    }
    dfs(0)
    return result

};

李恒道

https://leetcode.cn/problems/longest-increasing-subsequence/submissions/564210484/?envType=study-plan-v2&envId=top-100-liked
标准dp
秒

var lengthOfLIS = function (nums) {
    const dp = new Array(nums.length).fill(0)
    let result=Number.MIN_SAFE_INTEGER
    for (let index = 0; index < dp.length; index++) {
        let num = 0;
        for (let indey = 0; indey < index; indey++) {
            if(nums[index]>nums[indey]){
                num=Math.max(num,dp[indey])
            }

        }
        dp[index] = num + 1;
        result=Math.max(result, dp[index])
    }
    return result
};

wuxin0011

道长基础很好啊，都知道fib的快速幂解法 有这些基础早就进入1w了

李恒道

wuxin0011 发表于 2024-9-13 09:34
道长基础很好啊，都知道fib的快速幂解法 有这些基础早就进入1w了

以前做前端喜欢看别人的一些框架设计和算法
所以之前就会一些了
就是没系统刷过算法
leetcode还算偏古典的总体上不是特别难
就是想打出来排名太难了...
我一开始心思不嗖嗖嗖窜上去
结果到现在打了100多题连10w都还没进去呢
估计要小半年QAQ