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

李恒道

https://leetcode.cn/problems/to-lower-case/submissions/568756876/?envType=study-plan-v2&envId=primers-list
这个更6

func toLowerCase(s string) string {
    return strings.ToLower(s)
}

李恒道

https://leetcode.cn/problems/decode-ways/submissions/568871759/?envType=study-plan-v2&envId=dynamic-programming
爬楼梯的魔改题，dp边界一开始抠蒙了

var numDecodings = function (s) {
    const dp = new Array(s.length).fill(0);
    if (s[dp.length - 1] !== '0') {
        dp[dp.length - 1] = 1;
    }
    const isValid = (str) => {
        if (str[0] == '0') {
            return false
        }
        if (str[0] == '1') {
            return true
        }
        if (str[0] == '2') {
            if (parseInt(str[1]) <= 6) {
                return true
            } else {
                return false
            }
        }
    }
    for (let index = s.length - 2; index >= 0; index--) {
        const char = s[index];
        if (char == '0') {
            continue;
        }
        if (isValid(char + s[index + 1])) {
            dp[index] = dp[index + 1] + (index + 2>=s.length?1:dp[index + 2])
        } else {
            dp[index] = dp[index + 1]
        }
    }
    return dp[0]
};

李恒道

https://leetcode.cn/problems/minimum-cost-for-tickets/submissions/568892337/?envType=study-plan-v2&envId=dynamic-programming
缓存秒了！
但是感觉转dp自己维度太多了...

var mincostTickets = function (days, costs) {
  days.unshift(days[0]);
  const cache = new Map();
  const dfs = (pos, day) => {
    const flag = `${pos} ${day}`;
    if (cache.has(flag)) {
      return cache.get(flag);
    }
    if (pos >= days.length) {
      return 0;
    }
    const lastDay = days[pos] - days[pos - 1];
    let result = 0;
    if (day <= lastDay) {
      result = Math.min(
        dfs(pos + 1, 1) + costs[0],
        dfs(pos + 1, 7) + costs[1],
        dfs(pos + 1, 30) + costs[2]
      );
    } else {
      result = dfs(pos + 1, day - lastDay);
    }
    cache.set(flag, result);
    return result;
  };
  return dfs(1, 0);
};

李恒道

https://leetcode.cn/problems/domino-and-tromino-tiling/submissions/569120236/?envType=study-plan-v2&envId=dynamic-programming
这题没凹出来
状态被我设计的太复杂了

var numTilings = function (n) {
    const dp = new Array(n).fill(0).map(() => new Array(4).fill(0))
    // 0不填充
    // 1填充满
    // 2上界
    // 3下界
    dp[0][0] = 1;
    dp[0][1] = 1;
    for (let index = 1; index < dp.length; index++) {
        dp[index][0] = dp[index - 1][1]
        dp[index][1] = dp[index - 1][0] + dp[index - 1][1] + dp[index - 1][2] + dp[index - 1][3]
        dp[index][2] = dp[index - 1][0] + dp[index - 1][3]
        dp[index][3] = dp[index - 1][0] + dp[index - 1][2]
        dp[index][0]= dp[index][0]%(1000000000 + 7)
        dp[index][1]= dp[index][1]%(1000000000 + 7)
        dp[index][2]= dp[index][2]%(1000000000 + 7)
        dp[index][3]= dp[index][3]%(1000000000 + 7)
    }
    return dp[n - 1][1]
};

李恒道

https://leetcode.cn/problems/add-digits/submissions/569132366/?envType=study-plan-v2&envId=primers-list
简单题压压惊

func addDigits(num int) int {
    var calc = func(num int) int {
        var newNum int
        for {
            if num == 0 {
                break
            }
            newNum += num % 10
            num = num / 10
        }
        return newNum
    }
    for {
        if num < 10 {
            return num
        }
        num = calc(num)
    }
}

李恒道

https://leetcode.cn/problems/subtract-the-product-and-sum-of-digits-of-an-integer/submissions/569134967/?envType=study-plan-v2&envId=primers-list
再练一题go

func subtractProductAndSum(n int) int {
    var calc1 = func(num int) int {
        var newNum int
        for {
            if num == 0 {
                break
            }
            newNum += (num % 10)
            num = num / 10
        }
        return newNum
    }
    var calc2 = func(num int) int {
        var newNum int = 1
        for {
            if num == 0 {
                break
            }
            newNum *= (num % 10)
            num = num / 10
        }
        return newNum
    }
    return calc2(n) - calc1(n)
}

李恒道

https://leetcode.cn/problems/same-tree/submissions/569139967/?envType=study-plan-v2&envId=top-interview-150
dfs简单题
秒了！

var isSameTree = function (p, q) {
    const dfs = (a, b) => {
        if (a == null || b == null) {
            return a == b
        }
        if (a.val == b.val) {
            const left = dfs(a.left, b.left)
            const right = dfs(a.right, b.right)
            return left == true && left == right
        }
        return false
    }
    return dfs(p, q)
};

李恒道

https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/submissions/569146960/
双指针，但是条件判断写的有点脏了

var maxVowels = function (s, k) {
    let left = 0;
    let right = 0;
    let maxNum = "aeiou".indexOf(s[0]) !== -1 ? 1 : 0;
    let result = 0
    for (let index = 1; index < s.length; index++) {
        const char = s[index];

        if ("aeiou".indexOf(char) !== -1) {
            //是
            if ((right - left + 1) !== k) {
                right++;
                maxNum++;
            } else {
                if ("aeiou".indexOf(s[left]) !== -1) {
                    right++;
                    left++;
                } else {
                    right++;
                    left++;
                    maxNum++;
                }
            }
        } else {
            //不是
            if ((right - left + 1) !== k) {
                right++;
            } else {
                if ("aeiou".indexOf(s[left]) !== -1) {
                    result = Math.max(result, maxNum)
                    right++;
                    left++;
                    maxNum--;
                } else {
                    right++;
                    left++;
                }
            }
        }

    }
    return  Math.max(result, maxNum)
};

李恒道

https://leetcode.cn/problems/maximum-average-subarray-i/submissions/569147459/
定长顺了，秒！

var findMaxAverage = function (nums, k) {
    let pos = 0;
    let result = Number.MIN_SAFE_INTEGER;
    let avergeNum = 0
    for (let index = 0; index < nums.length; index++) {
        const num = nums[index];
        avergeNum += num;
        pos++;
        if (pos <= k-1) {
            continue;
        }
        result = Math.max(result, avergeNum / k)
        avergeNum -= nums[index - k + 1]
    }
    return result
};

李恒道

https://leetcode.cn/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/submissions/569147579/
过

var numOfSubarrays = function (arr, k, threshold) {
    let pos = 0;
    let result = 0;
    let avergeNum = 0;
    for (let index = 0; index < arr.length; index++) {
        const num = arr[index];
        avergeNum += num;
        pos++;
        if (pos <= k - 1) {
            continue;
        }
        if((avergeNum / k)>=threshold){
            result++
        }
        avergeNum -= arr[index - k + 1]
    }
    return result
};