leetcode

我的 leetcode 题解(JavaScript)


单从提交记录看, 似乎是第四次不需要看题解能自己做完 leetcode 周赛了, 不过独立做完的次数应该比四次多了吧, 速度还是太慢

第三题是之前自己一直比较烦的那种题, 不过这些写出来了

/**
 * @param {number[]} chips
 * @return {number}
 */
var minCostToMoveChips = function (chips) {
  const m = {};
  let min = Number.MAX_SAFE_INTEGER;
  for (const c of chips) {
    if (m[c])++m[c];
    else m[c] = 1;
  }
  for (const i in m) {
    let sum = 0;
    for (const j in m) if (i !== j) sum += m[j] * (Math.abs(i - j) % 2);
    if (sum < min) min = sum;
  }
  return min;
};



/**
 * @param {number[]} arr
 * @param {number} difference
 * @return {number}
 */
var longestSubsequence = function (arr, difference) {
  const m = {};
  let max = 1;
  for (let i = 0; i < arr.length; i++) {
    if (m[arr[i]]) continue;
    let b = i + 1, bb = arr[i], sum = 1;
    const mi = [];
    while (b < arr.length) {
      if (arr[b] === bb + difference) {
        mi.push(arr[b]);
        bb += difference;
        ++sum;
      }
      ++b;
    }
    for (const mii of mi) m[mii] = sum;
    if (sum > max) max = sum;
  }
  return max;
};



/**
 * @param {number[][]} grid
 * @return {number}
 */
var getMaximumGold = function (grid) {
  let max = Number.MIN_SAFE_INTEGER;
  const m = grid.length;
  if (m <= 0) return 0;
  const n = grid[0].length;
  let sum = 0;
  const dfs = (x, y, visited) => {
    const t = visited[x][y];
    sum += t;
    if (x - 1 >= 0 && visited[x - 1][y]) { visited[x][y] = 0; dfs(x - 1, y, visited) }
    if (y + 1 < n && visited[x][y + 1]) { visited[x][y] = 0; dfs(x, y + 1, visited) }
    if (x + 1 < m && visited[x + 1][y]) { visited[x][y] = 0; dfs(x + 1, y, visited) }
    if (y - 1 >= 0 && visited[x][y - 1]) { visited[x][y] = 0; dfs(x, y - 1, visited) }
    if ((!visited[x - 1] || !visited[x - 1][y])
      && (!visited[x + 1] || !visited[x + 1][y])
      && (!visited[y + 1] || !visited[x][y + 1])
      && (!visited[y - 1] || !visited[x][y - 1])) {
      if (sum > max) max = sum;
    }
    visited[x][y] = t;
    sum -= t;
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j]) dfs(i, j, grid);
    }
  }
  return max;
};




/**
 * @param {number} n
 * @return {number}
 */
var countVowelPermutation = function (n) {
  const dpa = [1, 3], dpe = [1, 2], dpi = [1, 2], dpo = [1, 1], dpu = [1, 2];
  if (n === 1) return 5;
  if (n === 2) return 10;
  for (let i = 2; i < n; i++) {
    dpa[i] = (dpe[i - 1] + dpi[i - 1] + dpu[i - 1]) % 1000000007;
    dpe[i] = (dpa[i - 1] + dpi[i - 1]) % 1000000007;
    dpi[i] = (dpe[i - 1] + dpo[i - 1]) % 1000000007;
    dpo[i] = dpi[i - 1];
    dpu[i] = (dpi[i - 1] + dpo[i - 1]) % 1000000007;
  }
  return (dpa[n - 1] + dpe[n - 1] + dpi[n - 1] + dpo[n - 1] + dpu[n - 1]) % 1000000007;
};