Skip to main content

力扣 600 以后

617.合并二叉树​

const mergeTrees = (t1, t2) => {
  if (!t1) return t2;
  if (!t2) return t1;

  t1.val += t2.val;

  t1.left = mergeTrees(t1.left, t2.left);
  t1.right = mergeTrees(t1.right, t2.right);

  return t1;
};

643.子数组最大平均数 I（滑动窗口）​

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findMaxAverage = function (nums, k) {
  let sum = 0;
  let len = nums.length;
  for (let i = 0; i < k; i++) {
    sum += nums[i];
  }
  let maxSum = sum;
  for (let i = k; i < len; i++) {
    sum = sum - nums[i - k] + nums[i];
    maxSum = Math.max(maxSum, sum);
  }
  return maxSum / k;
};

662.二叉树最大宽度（bfs 每一层挑战）​

由于要考虑大数情况 左子*2n,右子*2n+1n

function widthOfBinaryTree(root) {
  const queue = [[root, 1n]];
  let max = -1;
  while (queue.length) {
    const size = queue.length;
    // 当前层最右边的编号减去最左边的编号，012,2-1+1n
    max = Math.max(max, Number(queue[queue.length - 1][1] - queue[0][1] + 1n));
    for (let i = 0; i < size; i++) {
      const [node, index] = queue.shift();
      node?.left && queue.push([node.left, index * 2n]);
      node?.right && queue.push([node.right, index * 2n + 1n]);
    }
  }
  return max;
}

670.最大交换（贪心）​

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

输入: 2736 输出: 7236 解释: 交换数字 2 和数字 7。 示例 2 :

输入: 9973 输出: 9973 解释: 不需要交换。 注意:

通过以上可以观察到右边越大的数字与左边较小的数字进行交换，这样产生的整数才能保证越大。因此我们可以利用贪心法则，尝试将数字中右边较大的数字与左边较小的数字进行交换，这样即可保证得到的整数值最大。具体做法如下

var maximumSwap = function (num) {
  const charArray = [...("" + num)];
  const n = charArray.length;
  let maxIdx = n - 1;
  let idx1 = -1,
    idx2 = -1;
  for (let i = n - 1; i >= 0; i--) {
    if (charArray[i] > charArray[maxIdx]) {
      maxIdx = i;
    } else if (charArray[i] < charArray[maxIdx]) {
      idx1 = i;
      idx2 = maxIdx;
    }
  }
  if (idx1 >= 0) {
    swap(charArray, idx1, idx2);
    return parseInt(charArray.join(""));
  } else {
    return num;
  }
};

const swap = (charArray, i, j) => {
  const temp = charArray[i];
  charArray[i] = charArray[j];
  charArray[j] = temp;
};

674.最长连续递增序列​

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function (nums) {
  let ans = 1;
  const n = nums.length;
  let start = 0;
  // 连续递增，不行就清掉，记得挑战最大值就行
  for (let i = 0; i < n; i++) {
    if (i > 0 && nums[i] <= nums[i - 1]) {
      start = i;
    }
    ans = Math.max(ans, i - start + 1);
  }
  return ans;
};

695.岛屿的最大面积​

/**
 * @param {number[][]} grid
 * @return {number}
 */

//  变0里面设let num=1,num+=(向左) num+=（向右）。。。。return num
// 双循环内部如果出现1要挑战最大值 count=Math.max(count,areaOfIsland(grid,i,j,y,x))
var maxAreaOfIsland = function (grid) {
  let count = 0,
    x = grid[0].length,
    y = grid.length;
  for (let i = 0; i < y; i++) {
    for (let j = 0; j < x; j++) {
      if (grid[i][j] === 1) count = Math.max(count, areaOfIsland(i, j));
    }
  }
  return count;

  function areaOfIsland(i, j) {
    if (i >= y || i < 0 || j >= x || j < 0 || grid[i][j] === 0) return 0;
    let num = 1;
    grid[i][j] = 0;
    num += areaOfIsland(i + 1, j);
    num += areaOfIsland(i - 1, j);
    num += areaOfIsland(i, j + 1);
    num += areaOfIsland(i, j - 1);
    return num;
  }
};

700.二叉搜索树查找​

var searchBST = function (root, val) {
  if (!root) {
    return null;
  }
  if (val === root.val) {
    return root;
  }
  return searchBST(val < root.val ? root.left : root.right, val);
};

704.二分查找​

如果目标值存在返回下标，否则返回 -1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let left = 0,
    right = nums.length - 1;
  while (left <= right) {
    mid = Math.floor((right - left) / 2) + left;
    if (nums[mid] === target) return mid;
    if (nums[mid] > target) {
      right = mid - 1;
    }
    if (nums[mid] < target) {
      left = mid + 1;
    }
  }
  return -1;
};

718.最长重复子数组(dp 对角线)​

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */

//  初始化m+1*n+1的二维数组
// 因为已经省去了左边和顶边的初始化
// 所以从 1,1开始遍历,如果nums[i-1]===nums[j-1]
// dp[i][j]=dp[i-1][j-1]+1
// 每次循环用dp[i][j]挑战最大值

// 为了省去初始化第一行和第一列为0
var findLength = function (nums1, nums2) {
  const m = nums1.length,
    n = nums2.length;
  let ans = 0;
  // 直接像下面这样初始化 二维数组中的数组都是同一个引用，所以是不行的！
  // let dp = Array(m + 1).fill(Array(n + 1).fill(0));
  const dp = new Array(m + 1).fill().map(() => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (nums1[i - 1] === nums2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      }
      ans = Math.max(ans, dp[i][j]);
    }
  }
  return ans;
};

739.每日温度 （栈，从后往前遍历）​

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。 输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]

时间复杂度 ON

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
const dailyTemperatures = (T) => {
  const res = new Array(T.length).fill(0);
  const stack = [];
  //   从后往前遍历
  // 73
  // 76
  // 76 72
  // 76 72 69
  // 76 72 71
  //76 75
  for (let i = T.length - 1; i >= 0; i--) {
    //每一次入栈，都把栈顶还原到下一个高于当前的温度
    while (stack.length && T[i] >= T[stack[stack.length - 1]]) {
      stack.pop();
    }
    // 栈内存有index
    if (stack.length) {
      //
      res[i] = stack[stack.length - 1] - i;
    }
    stack.push(i);
  }
  return res;
};

887.鸡蛋掉落​

function EggDrop(K, N) {
  // K剩余鸡蛋数，N剩余要测层数
  // 记忆map
  const map = {};

  this.dp = function (K, N) {
    //楼层数为0
    if (N === 0) {
      return 0;
    }
    //鸡蛋数为1, 最坏要试N次
    if (K === 1) {
      return N;
    }
    //以 N_K 记忆map，属于减少计算次数
    const key = `${N}_${K}`;
    if (map[key] !== undefined) {
      return map[key];
    }

    let result = Number_MAX_SAFE_INTEGER;
    let low = 1;
    let high = N;
    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      let broken = dp(K - 1, mid - 1);
      let unBroken = dp(K, N - mid);
      // broken：鸡蛋从 mid 楼层掉下后破裂，因此需要用一个更少的鸡蛋（K - 1）检查 mid - 1 楼层以下
      // unBroken：鸡蛋没有破裂，因此需要用相同数量的鸡蛋（K）检查 N - mid 楼层以上。

      // 为什么用N-mid？因为mid没摔碎，怎么找mid以上呢，
      // 即mid~N，即N-mid

      // 如果这次摔碎了后所花的次数比这次没摔碎下一步所花次数多，
      // 说明应该选择往下试，同时挑战最小值
      if (broken > unBroken) {
        high = mid - 1;
        result = Math.min(result, broken + 1);
      } else {
        low = mid + 1;
        result = Math.min(result, unBroken + 1);
      }
    }
    map[key] = result;
    return result;
  };
  return this.dp(K, N);
}

958.二叉树的完整性校验(bfs 加一个判断)​

如果当前节点为 null，且栈内还有其它节点（而且不是 null），直接返回 false

var isCompleteTree = function (root) {
  if (!root) return true;
  const queue = [root];

  while (queue.length) {
    let node = queue.shift();

    // 如果当前节点为null，且栈内还有其它节点（而且不是null)，直接返回 false
    if (!node && queue[0]) {
      return false;
    }

    if (node) {
      queue.push(node.left);
      queue.push(node.right);
    }
  }

  return true;
};

1047.删除字符串中所有相邻重复项​

输入："abbaca" 输出："ca"

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function (s) {
  let stack = [];
  for (c of s) {
    if (stack.length && c === stack[stack.length - 1]) {
      stack.pop();
    } else {
      stack.push(c);
    }
  }
  return stack.join("");
};

1143.最长公共子序列​

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */

//  建立m+1*n+1的矩阵，双重循环遍历
// 第一重记下text1当前位，第二重记下text2当前位，如果两位相同，dp[i][j]=左上位
// 否则dp[i][j] = 左侧和上侧的最大
// 返回dp[m][n]
var longestCommonSubsequence = function (text1, text2) {
  const m = text1.length,
    n = text2.length;
  const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    const c1 = text1[i - 1];
    for (let j = 1; j <= n; j++) {
      const c2 = text2[j - 1];
      if (c1 === c2) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        // 已经是最长的方式以后一定是最长
        // 因为后面公共的一定是往前面的上面加，互相不影响
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
};

1291.顺次数​

输出：low = 1000, high = 13000 输出：[1234,2345,3456,4567,5678,6789,12345]

滑动窗口

/**
 * @param {number} low
 * @param {number} high
 * @return {number[]}
 */
var sequentialDigits = function (low, high) {
  //计算low high 位数
  var l1 = low.toString().length;
  var l2 = high.toString().length;
  var str = "123456789";
  var result = [];
  //滑动取值
  while (l1 <= l2) {
    let idx = 0;
    while (idx + l1 <= str.length) {
      let num = parseInt(str.substring(idx, idx + l1));
      if (num >= low && num <= high) {
        result.push(num);
      }
      idx++;
    }
    l1++;
  }
  return result;
};

1444.切披萨的方案数​

https://leetcode.cn/problems/number-of-ways-of-cutting-a-pizza/description/

var ways = function (pizza, k) {
  let row = pizza.length;
  let column = pizza[0].length;
  let remains = new Array(row).fill(null).map((each) => []);
  let mod = 1e9 + 7;

  // 从右下角开始搜起，remains数组每一个位置表示从该格到右下角区域的苹果数
  for (let i = row - 1; i >= 0; i--) {
    for (let j = column - 1; j >= 0; j--) {
      let current = pizza[i][j] === "A" ? 1 : 0;
      //初始化行
      if (i === row - 1) {
        remains[i][j] = (remains[i][j + 1] || 0) + current;
        continue;
      }
      // 初始化列
      if (j === column - 1) {
        remains[i][j] = (remains[i + 1][j] || 0) + current;
        continue;
      }

      remains[i][j] =
        // 记得减去重叠的
        remains[i][j + 1] + remains[i + 1][j] + current - remains[i + 1][j + 1];
    }
  }

  let dp = [];
  // dp数组为切法
  for (let i = 0; i < row; i++) {
    dp[i] = new Array();
    for (let j = 0; j < column; j++) {
      dp[i][j] = new Array(k).fill(0);
    }
  }

  for (let i = row - 1; i >= 0; i--) {
    for (let j = column - 1; j >= 0; j--) {
      // 在这里切0刀，只有一种方法
      if (remains[i][j] > 0) dp[i][j][0] = 1;

      // 切k刀
      for (let cut = 1; cut < k; cut++) {
        // 横着切
        for (let r = i + 1; r < row; r++) {
          // 如果剩余部分有苹果，则在这里横着切k刀为在这里切k-1刀的所有方法
          // 加上目前切k刀已知的的方法
          if (remains[i][j] - remains[r][j] > 0) {
            dp[i][j][cut] = (dp[r][j][cut - 1] + dp[i][j][cut]) % mod;
          }
        }
        // 竖着切
        for (let r = j + 1; r < column; r++) {
          if (remains[i][j] - remains[i][r] > 0) {
            dp[i][j][cut] = (dp[i][r][cut - 1] + dp[i][j][cut]) % mod;
          }
        }
      }
    }
  }
  return dp[0][0][k - 1];
};

1556.千位分隔数​

/**
 * @param {number} n
 * @return {string}
 */

//  var thousandSeparator = function(n) {
//     return (n).toLocaleString().replace(/\,/g, '.')
// };

var thousandSeparator = function (n) {
  if (n === 0) return "0";
  let count = 0;
  let ans = "";
  while (n) {
    let cur = n % 10;
    n = Math.floor(n / 10);
    ans += cur.toString();
    ++count;
    if (count % 3 == 0 && n) {
      ans += ".";
    }
  }
  return ans.split("").reverse().join("");
};