Skip to main content

力扣剩

剑指​

100 ～ 199​

120.寻找文件副本（数组重复元素）​

0 ≤ documents[i] ≤ n-1 要求原地 [3,2,3,1]

相当于把 3 交换到对应 index 位

[1,2,3,3] 这样到第二个 3 时，先去查对应 index 位

注意 while nums[i]不等于 i 尽量一次把所有数排到对应 index 上

实在排不了的，靠遍历去看 一旦nums[i] == nums[cur]就说明以前遇到过一次并排好

[2,1,3,3]

[3,1,2,3]

var findRepeatDocument = function (nums) {
  let cur;
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] != i) {
      cur = nums[i];
      if (nums[i] == nums[cur]) {
        return nums[i];
      } else {
        nums[i] = nums[cur];
        nums[cur] = cur;
      }
    }
  }
};

136.只出现一次的数字​

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

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

// yihuo运算
var singleNumber = function (nums) {
  let ans = 0;
  for (const num of nums) {
    ans ^= num;
  }
  return ans;
};

162.寻找峰值（二分，往峰找）​

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

var findPeakElement = function (nums) {
  let l = 0,
    r = nums.length - 1;
  while (l < r) {
    let mid = Math.floor((l + r) >> 1);
    //因为题目中明确过没有相等的值，所以直接大于即可
    if (nums[mid] > nums[mid + 1]) r = mid;
    else l = mid + 1;
  }
  return l;
};

168.Excel 表列名称​

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

例如：

A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ...

/**
 * @param {number} columnNumber
 * @return {string}
 */
var convertToTitle = function (columnNumber) {
  const sb = [];
  while (columnNumber !== 0) {
    columnNumber--;
    // 用String上的fromCharCode从数字转为string,记得加上A
    sb.unshift(String.fromCharCode((columnNumber % 26) + "A".charCodeAt()));
    columnNumber = Math.floor(columnNumber / 26);
  }
  // push进的是低位
  return sb.join("");
};

172.阶乘后的零​

https://leetcode.cn/problems/factorial-trailing-zeroes/description/

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n (n - 1) (n - 2) ... 3 2 1

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

// 可以观察到只有5*4产生一个0，10*5*4=2*5*5*4产生两个0
// 能分解多少个5就能产生多少0
var trailingZeroes = function (n) {
  let ans = 0;
  while (n !== 0) {
    n = Math.floor(n / 5);
    ans += n;
  }
  return ans;
};

187.破冰游戏（约瑟夫环/圆圈中最后剩下的数字）​

/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var lastRemaining = function (n, m) {
  // 最后一个人,则在2人中向右移动m位,是幸存位,每m位都是幸存位
  // x
  // x0
  let res = 0;
  for (let i = 2; i <= n; i++) {
    res = (res + m) % i;
  }
  return res;
};

模拟 会超时

/**
 * 频繁数组操作
 * Time Limit Exceeded 6/36 cases passed (N/A)
 * console.log(lastRemaining(70866,116922));
 */
var lastRemaining_bak = function (n, m) {
  let dp = new Array(n).fill(0).map((_, index) => index);
  while (dp.length > 1) {
    let index = m % dp.length === 0 ? dp.length - 1 : (m % dp.length) - 1;
    dp = [...dp.slice(index + 1), ...dp.slice(0, index)];
  }
  return dp[0];
};

200 ～ 299​

231.2 的幂​

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function (n) {
  return n > 0 && (n & (n - 1)) === 0;
};
//一个数 n 是 2 的幂，当且仅当 n 是正整数，并且 n 的二进制表示中仅包含 1 个 1
// -1后最后一位1后的0还是0，1变成0（就是最后一位1）.用&位运算，
// 高位没有1，最后一位1也变成0了，说明一共就一个1

232.用栈实现队列​

void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false

var MyQueue = function () {
  this.inStack = [];
  this.outStack = [];
};

MyQueue.prototype.push = function (x) {
  this.inStack.push(x);
};

MyQueue.prototype.pop = function () {
  // 该if为此题重点，inStack继续push，只有等到outStack为空时，才会把in倒进out里
  // 因为outstack才是被用到的队列前端
  if (!this.outStack.length) {
    this.in2out();
  }
  return this.outStack.pop();
};

MyQueue.prototype.peek = function () {
  if (!this.outStack.length) {
    this.in2out();
  }
  return this.outStack[this.outStack.length - 1];
};

MyQueue.prototype.empty = function () {
  return this.outStack.length === 0 && this.inStack.length === 0;
};

MyQueue.prototype.in2out = function () {
  while (this.inStack.length) {
    this.outStack.push(this.inStack.pop());
  }
};

300 ～ 399​

342.4 的幂​

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfFour = function (n) {
  // 如果 n 是 4 的幂，那么 n 一定也是 2 的幂。因此我们可以首先判断 n 是否是 2 的幂
  return n > 0 && (n & (n - 1)) === 0 && n % 3 === 1;
};

// n & (n-1)

//一个数 n 是 2 的幂，当且仅当 n 是正整数，并且 n 的二进制表示中仅包含 1 个 1
// -1后最后一位1后的0还是0，1变成0（就是最后一位1）.用&位运算，
// 高位没有1，最后一位1也变成0了，说明一共就一个1

400 ～ 499​

415.字符串相加（双指针）​

const addStrings = function (num1, num2) {
  let l1 = num1.length - 1;
  let l2 = num2.length - 1;
  let place = 0;
  let res = [];
  while (l1 >= 0 || l2 >= 0) {
    let x = l1 >= 0 ? +num1.charAt(l1--) : 0;
    let y = l2 >= 0 ? +num2.charAt(l2--) : 0;
    let sum = x + y + place;
    place = Math.floor(sum / 10);
    res.push(sum % 10);
  }
  if (place > 0) {
    res.push(place);
  }
  return res.reverse().join("");
};

416.分割等和数组*​

[1,2,3]->[1,2] [3]

https://leetcode.cn/problems/partition-equal-subset-sum/solutions/553978/bang-ni-ba-0-1bei-bao-xue-ge-tong-tou-by-px33/?envType=study-plan-v2&envId=top-100-liked

动规五部曲分析如下：

确定 dp 数组以及下标的含义 01 背包中，dp[j] 表示： 容量为 j 的背包，所背的物品价值最大可以为 dp[j]。

本题中每一个元素的数值既是重量，也是价值。

套到本题，dp[j]表示 背包总容量（所能装的总重量）是 j，放进物品后，背的最大重量为 dp[j]。

那么如果背包容量为 target， dp[target]就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了。

有录友可能想，那还有装不满的时候？

拿输入数组 [1, 5, 11, 5]，距离， dp[7] 只能等于 6，因为 只能放进 1 和 5。

而 dp[6] 就可以等于 6 了，放进 1 和 5，那么 dp[6] == 6，说明背包装满了。

2.确定递推公式 01 背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题，相当于背包里放入数值，那么物品 i 的重量是 nums[i]，其价值也是 nums[i]。

所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

dp 数组如何初始化 在 01 背包，一维 dp 如何初始化，已经讲过，

从 dp[j]的定义来看，首先 dp[0]一定是 0。

如果题目给的价值都是正整数那么非 0 下标都初始化为 0 就可以了，如果题目给的价值有负数，那么非 0 下标就要初始化为负无穷。

这样才能让 dp 数组在递推的过程中取得最大的价值，而不是被初始值覆盖了

// 画图找规律吧，记得dp数组为一半长度，最终取最后一个
function canPartition(nums: number[]): boolean {
  /**
        weightArr = nums;
        valueArr = nums;
        bagSize = sum / 2; (sum为nums各元素总和);
        按照0-1背包处理
     */
  const sum: number = nums.reduce((pre, cur) => pre + cur);
  if (sum % 2 === 1) return false;

  // 因为只算到每个背包装sum/2个，所以最后结果满足题目二分数组的要求
  const bagSize: number = sum / 2;
  const weightArr: number[] = nums;
  const valueArr: number[] = nums;
  const goodsNum: number = weightArr.length;
  // 每个背包装0个，一直到装goodsNum个
  const dp: number[][] = new Array(goodsNum)
    .fill(0)
    // 在装x个情况下的我每一位最多可以装多重的（多有价值的）
    .map((_) => new Array(bagSize + 1).fill(0));
  // 初始化，如果每个背包装1个，（dp0),那么每个背包的
  for (let i = weightArr[0]; i <= bagSize; i++) {
    dp[0][i] = valueArr[0];
  }
  for (let i = 1; i < goodsNum; i++) {
    for (let j = 0; j <= bagSize; j++) {
      // 放不下，价值不变，保持每个背包少装这一个的价值
      if (j < weightArr[i]) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = Math.max(
          dp[i - 1][j],
          dp[i - 1][j - weightArr[i]] + valueArr[i]
        );
      }
    }
  }
  return dp[goodsNum - 1][bagSize] === bagSize;
}

LCR174.二叉搜索树的第 K 大​

某公司组织架构以二叉搜索树形式记录，节点值为处于该职位的员工编号。请返回第 cnt 大的员工编号。

var kthLargest = function (root, k) {
  let res = null;
  // 中序遍历
  let inOrderTraverseNode = function (node) {
    if (node !== null && k > 0) {
      // 先遍历右⼦树，到最大值
      // 往右搜是找最大，往左搜是找最小
      inOrderTraverseNode(node.right);
      k--;
      // 然后根节点
      if (k === 0) {
        res = node.val;
        return;
      }
      // 再遍历左⼦树
      inOrderTraverseNode(node.left);
    }
  };
  inOrderTraverseNode(root);
  return res;
};

将由 0，1，2 组成的数组排序为 1 在前，0 在中间，2 在后面的数组​

三指针原地排序