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

李恒道

https://leetcode.cn/problems/house-robber-iii/?envType=study-plan-v2&envId=dynamic-programming
缓存秒了，看了答案才理解题意就知道怎么写了...
这个题问写的太误导人了

var rob = function (root) {
  const fCache = new Map();
  const gCache = new Map();
  const f = (root) => {
    if (root == null) {
      return 0;
    }
    if(fCache.has(root)){
      return fCache.get(root)
    }
    const fResult = g(root.left) + g(root.right) + root.val;
    fCache.set(root, fResult);
    return fResult;
  };
  const g = (root) => {
    if (root == null) {
      return 0;
    }
    if(gCache.has(root)){
      return gCache.get(root)
    }
    const gResult = Math.max(
      g(root.left) + g(root.right),
      g(root.left) + f(root.right),
      f(root.left) + g(root.right),
      f(root.left) + f(root.right)
    );

    gCache.set(root, gResult);
    return gResult;
  };
  const dfs = (root) => {
    const r1 = f(root);
    const r2 = g(root);
    return Math.max(r1, r2);
  };
  return dfs(root);
};

李恒道

https://leetcode.cn/problems/coin-change-ii/submissions/568515820/?envType=study-plan-v2&envId=dynamic-programming
一开始过于在乎局部的递归，没扣好缓存

var change = function (amount, coins) {
    const cache = new Map()
    const dfs = (amount, pos) => {
        if (amount == 0) {
            return 1
        }
        if (amount < 0) {
            return 0
        }
        if (pos >= coins.length) {
            return 0
        }
        const flag = `${amount} ${pos}`
        if (cache.has(flag)) {
            return cache.get(flag)
        }
        let result = undefined
        if (amount < coins[pos]) {
            result = dfs(amount, pos + 1)
        } else {
            result = dfs(amount, pos + 1) + dfs(amount - coins[pos], pos)
        }
        cache.set(flag, result)
        return result
    }
    return dfs(amount, 0)
};

李恒道

https://leetcode.cn/problems/coin-change-ii/submissions/568522610/?envType=study-plan-v2&envId=dynamic-programming
转换成二维dp

var change = function (amount, coins) {
    const dp = new Array(coins.length + 1).fill(0).map(() => new Array(amount + 1).fill(0))
    for (let index = 0; index < dp.length; index++) {
        dp[index][0] = 1
    }
    for (let index = dp.length - 2; index >= 0; index--) {
        for (let mount = 1; mount <= amount; mount++) {
            if (mount < coins[index]) {
                dp[index][mount] = dp[index + 1][mount]
            } else {
                dp[index][mount]  = dp[index + 1][mount] + dp[index][mount - coins[index]]
            }
        }
    }
    return dp[0].pop()
};

李恒道

https://leetcode.cn/problems/combination-sum-iv/solutions/2706336/ben-zhi-shi-pa-lou-ti-cong-ji-yi-hua-sou-y52j/?envType=study-plan-v2&envId=dynamic-programming
这题是真没思路，但是看了一眼题解就懂了...

var combinationSum4 = function (nums, target) {
    const cache = new Map()
    const dfs = (target) => {
        if(target==0){
            return 1
        }
        if (cache.has(target)) {
            return cache.get(target)
        }
        let result = 0
        for (let index = 0; index < nums.length; index++) {
            const num = nums[index];
            if (num <= target) {
                result += dfs(target - num)
            }
        }
        cache.set(target, result)
        return result
    }
    return dfs(target)
};

李恒道

https://leetcode.cn/problems/xor-operation-in-an-array/submissions/568601454/?envType=study-plan-v2&envId=primers-list
简单题练练go

func xorOperation(n int, start int) int {
    var numArr []int = make([]int, n)
    for index, _ := range numArr {
        numArr[index] = start + index*2
    }
    var result int
    for _, val := range numArr {
        result = result ^ val
    }
    return result
}

李恒道

https://leetcode.cn/problems/number-of-good-pairs/submissions/568601995/?envType=study-plan-v2&envId=primers-list
秒了！

func numIdenticalPairs(nums []int) int {
    var result int;
    for ind, val := range nums {
        for i := ind + 1; i < len(nums); i++ {
            if nums[i] == val {
                result++
            }
        }
    }
    return result
}

李恒道

https://leetcode.cn/problems/ones-and-zeroes/submissions/568659554/?envType=study-plan-v2&envId=dynamic-programming
缓存dfs秒了！

var findMaxForm = function (strs, m, n) {
    strs = strs.map((str) => {
        let hasOne = 0;
        let hasZero = 0;
        for (let index = 0; index < str.length; index++) {
            const char = str[index];
            if (char == '1') {
                hasOne++;
            } else {
                hasZero++
            }
        }
        return {
            one: hasOne,
            zero: hasZero
        }
    })
    const cache=new Map()
    const dfs = (pos, m, n) => {
        const flag=`${pos} ${m} ${n}`
        if(cache.has(flag)){
           return cache.get(flag)
        }
        if (pos >= strs.length) {
            return 0
        }
        let maxLen = 0;
        const one = strs[pos].one
        const zero = strs[pos].zero
        if (m >= zero && n >= one) {
            maxLen = Math.max(dfs(pos + 1, m, n), dfs(pos + 1, m - zero, n - one)+1)
        } else {
            maxLen = dfs(pos + 1, m, n)
        }
        cache.set(flag,maxLen)

        return maxLen
    }
    return dfs(0, m, n)
};

李恒道

https://leetcode.cn/problems/solving-questions-with-brainpower/submissions/568668652/?envType=study-plan-v2&envId=dynamic-programming
基础dp，贴手秒！

var mostPoints = function (questions) {
  const dp = new Array(questions.length).fill(0);
  dp[dp.length - 1] = questions[questions.length - 1][0];
  for (let index = questions.length - 2; index >= 0; index--) {
    const question = questions[index];
    const price = question[0];
    const jump = question[1] + index + 1;
    const nextValue = jump >= dp.length ? 0 : dp[jump];
    dp[index] = Math.max(dp[index + 1], nextValue + price);
  }
  return dp[0];
};

李恒道

https://leetcode.cn/problems/count-ways-to-build-good-strings/?envType=study-plan-v2&envId=dynamic-programming
爬楼梯的题
一开始怎么都不对
然后发现自己没取余

var countGoodStrings = function (low, high, zero, one) {
    const cache = new Map()
    const dfs = (len) => {
        if (cache.has(len)) {
            return cache.get(len)
        }
        if (len == high) {
            return 1
        }
        let result = 0;
        if (len + zero <= high) {
            result += dfs(len + zero)
        }
        if (len + one <= high) {
            result += dfs(len + one)
        }
        if (len >= low) {
            result += 1
        }
        result = result % (1000000000 + 7)
        cache.set(len, result)
        return result
    }
    return dfs(0)
};

李恒道

https://leetcode.cn/problems/count-good-triplets/submissions/568756318/?envType=study-plan-v2&envId=primers-list
做两道简单题压压惊

func intABS(num int) int {
    if num < 0 {
        return num * -1
    }
    return num
}
func countGoodTriplets(arr []int, a int, b int, c int) int {
    var result int

    for index := 0; index < len(arr); index++ {
        for indey := index + 1; indey < len(arr); indey++ {
            for indez := indey + 1; indez < len(arr); indez++ {
                if intABS(arr[index]-arr[indey]) <= a && intABS(arr[indey]-arr[indez]) <= b && intABS(arr[index]-arr[indez]) <= c {
                    result++
                }
            }
        }
    }
    return result
}