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

李恒道

https://leetcode.cn/problems/maximum-number-of-coins-you-can-get/submissions/594669717/
贪心秒了

var maxCoins = function (piles) {
  piles = piles.sort((a, b) => b - a);
  const times = piles.length / 3;
  let ans=0
  for (let index = 0; index < times; index++) {
    ans+=piles[2*index+1]
  }
  return ans
};

李恒道

https://leetcode.cn/problems/maximum-points-after-collecting-coins-from-all-nodes/description/
打卡题

var maximumPoints = function (edges, coins, k) {
  const edgeMap = new Map();
  for (const [a, b] of edges) {
    if (!edgeMap.has(a)) {
      edgeMap.set(a, []);
    }
    edgeMap.get(a).push(b);
    if (!edgeMap.has(b)) {
      edgeMap.set(b, []);
    }
    edgeMap.get(b).push(a);
  }
  const cache = new Array(coins.length)
    .fill(0)
    .map(() => new Array(14).fill(-1));
  const dfs = (index, divide, father) => {
    const tag = `${index} ${divide} ${father}`;
    if (cache[index][divide]!==-1) {
      return cache[index][divide]
    }
    let noDiv = (coins[index] >> divide) - k;
    let runDiv = coins[index] >> (divide + 1);

    for (const nextIndex of edgeMap.get(index)) {
      if (father == nextIndex) {
        continue;
      }
      noDiv += dfs(nextIndex, divide, index);
      if (divide < 13) {
        runDiv += dfs(nextIndex, divide + 1, index);
      }
    }
    cache[index][divide]=Math.max(noDiv, runDiv)
    return Math.max(noDiv, runDiv);
  };
  return dfs(0, 0, -1);
};

李恒道

https://leetcode.cn/submissions/detail/594876022/
这个题真的啃了好久才拿下
爽！

function calcZ(S) {
  let s = S.split("");
  let n = s.length;
  let z = new Array(n).fill(0);
  let boxL = 0;
  let boxR = 0;
  for (let i = 1; i < n; i++) {
    if (i <= boxR) {
      z[i] = Math.min(z[i - boxL], boxR - i + 1);
    }
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) {
      boxL = i;
      boxR = i + z[i];
      z[i]++;
    }
  }
  return z;
}

function jump(arr) {
  let rightBorder = arr[0];
  let nextBorder = arr[0];
  let time = 1;
  for (let index = 0; index < arr.length; index++) {
    const len = arr[index];
    nextBorder = Math.max(nextBorder, index + len);
    if (index == rightBorder) {
      if (index == nextBorder) {
        return -1;
      }
      rightBorder = nextBorder;
      time++;
    }
  }
  //   while (curIndex < rightBorder&&curIndex<arr.length) {
  //     nextBorder = Math.max(nextBorder, curIndex + arr[curIndex]);
  //     if (curIndex == rightBorder ) {
  //       //最后一个，更新成新边界
  //       rightBorder = nextBorder;
  //       time++;
  //     }
  //     curIndex++;
  //   }
  //   if(curIndex==arr.length){
  //     return time
  //   }
  return time;
}

/**
 * @param {string[]} words
 * @param {string} target
 * @Return {number}
 */
var minValidStrings = function (words, target) {
  let maxJump = new Array(target.length).fill(0);
  for (const word of words) {
    const zArr = calcZ(word + "#" + target);
    for (let index = 0; index < maxJump.length; index++) {
      maxJump[index] = Math.max(maxJump[index], zArr[word.length + 1 + index]);
    }
  }
  return jump(maxJump);
};

李恒道

https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/submissions/594877334/
a了

const jump = (arr) => {
    let rightBorder = arr[0];
    let nextBorder = arr[0];
    let times=1
    for (let index = 0; index < arr.length; index++) {
      if(index==rightBorder+1){
          if(nextBorder==rightBorder){
              return -1
          }
          rightBorder=nextBorder;
          times++
      }
      const len = arr[index];
      nextBorder = Math.max(nextBorder,  len);
    }
    return times
  };
  var minTaps = function (n, ranges) {
    const arr = new Array(n + 1).fill(0);
    for (let index = 0; index < ranges.length; index++) {
      const range = ranges[index];
      const start = Math.max(index - range,0)
      arr[start] = Math.max(arr[start], index+range);
    }
    return jump(arr)
  };

李恒道

https://leetcode.cn/problems/video-stitching/submissions/594877672/
A过，边界问题

const jump = (arr,time) => {
  let rightBorder = arr[0];
  let nextBorder = arr[0];
  let times = 1;
  for (let index = 0; index < arr.length - 1&&index<time; index++) {
    const len = arr[index];
    nextBorder = Math.max(nextBorder, len);
    if (index == rightBorder) {
      if (nextBorder == rightBorder) {
        return -1;
      }
      rightBorder = nextBorder;
      times++;
    }
  }
  return times;
};

/**
 * @param {number[][]} clips
 * @param {number} time
 * @Return {number}
 */
var videoStitching = function (clips, time) {
  const arr = new Array(time + 1).fill(0);
  for (let index = 0; index < clips.length; index++) {
    const clip = clips[index];
    arr[clip[0]] = Math.max(arr[clip[0]], clip[1]);
  }
  return jump(arr,time);
};

李恒道

https://leetcode.cn/problems/repeated-substring-pattern/submissions/594877849/?envType=study-plan-v2&envId=programming-skills
超级耗时的飘过...
幸亏是简单题

func repeatedSubstringPattern(s string) bool {
    var sep string
    for i := 0; i < len(s)-1; i++ {
        sep += string(s[i])
        if len(s)%(i+1) != 0 {
            continue
        }
        time := len(s) / (i + 1)
        repeatedString := ""
        for i := 0; i < time; i++ {
            repeatedString += sep
        }
        if repeatedString == s {
            return true
        }
    }
    return false
}

李恒道

https://leetcode.cn/problems/can-make-arithmetic-progression-from-sequence/submissions/594877887/?envType=study-plan-v2&envId=programming-skills
排序，过了

func canMakeArithmeticProgression(arr []int) bool {
    sort.Ints(arr)
    sep := arr[1] - arr[0]
    for i := 2; i < len(arr); i++ {
        if arr[i]-arr[i-1] !=sep {
            return false
        }
    }
    return true
}

李恒道

https://leetcode.cn/problems/monotonic-array/submissions/594877916/?envType=study-plan-v2&envId=programming-skills
简单题，练练手感

func isMonotonic(nums []int) bool {
    isAdd := nums[len(nums)-1] > nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] != isAdd && (nums[i] != nums[i-1]) {
            return false
        }
    }
    return true
}

李恒道

https://leetcode.cn/problems/basic-calculator/submissions/595063421/?envType=study-plan-v2&envId=top-interview-150
我操
一次过

var calculate = function (s) {
  s = s.replaceAll(" ", "");
  const dfs = (pos) => {
    const numStack = [];
    const opStack = [];
    while (pos < s.length) {
      const char = s[pos];
      if (char == "(") {
        const result = dfs(pos + 1);
        pos = result.end + 1;
        numStack.push(result.val);
      } else if (char == ")") {
        //遇到自身括号，应该跳出
        break;
      } else if (char == "+" || char == "-") {
        opStack.push(char);
        if (
          pos == 0 ||
          s[pos - 1] == "(" ||
          s[pos - 1] == "+" ||
          s[pos - 1] == "-"
        ) {
          numStack.push(0);
        }
        pos++;
      } else {
        let pushNum = 0;
        while (
          pos < s.length &&
          s[pos].charCodeAt() >= 48 &&
          s[pos].charCodeAt() <= 57
        ) {
          const num = s[pos].charCodeAt() - 48;
          pos++;
          pushNum = pushNum * 10 + num;
        }
        numStack.push(pushNum);
      }
    }
    //计算Stack
    while (numStack.length > 1) {
      const num1 = numStack.shift();
      const num2 = numStack.shift();
      const op = opStack.shift();
      numStack.unshift(op == "+" ? num1 + num2 : num1 - num2);
    }
    return {
      val: numStack[0],
      end: pos,
    };
  };
  return dfs(0).val;
};

李恒道

https://leetcode.cn/problems/minimum-number-of-coins-for-fruits/description/
打卡题

var minimumCoins = function (prices) {
  const cache = new Array(prices.length + 1).fill(-1);
  const dfs = (index) => {
    if(cache[index]!=-1){
      return cache[index]
    }
    let i = index + 1;
    if (2 * i >= prices.length) {
      return prices[index];
    }
    let ans = Number.MAX_SAFE_INTEGER;
    for (let pos = i + 1; pos <= 2 * i + 1; pos++) {
      ans = Math.min(ans, dfs(pos - 1));
    }
    ans += prices[index];
    cache[index]=ans
    return ans;
  };
  return dfs(0);
};