Leetcode-22
刷程序员面试金典题目了，这个难度比较难，而且没有给原题提示，所以还得自己去找，有些题目还稍微改了一下题目，所以还得稍微修改一下。
面试 0406 后继者
时间：2022-05-16
用的递归，用上迭代应该会快一点。
var inorderSuccessor = function (root, p) {
let res = null, prev;
const dfs = (root) => {
if (!root) return;
dfs(root.left);
if (prev) {
prev = null;
res = root;
return;
}
if (p.val == root.val) prev = p;
dfs(root.right);
};
dfs(root)
return res;
};
中序遍历的迭代法，居然没有写出来，有点尬。
var inorderSuccessor = function (root, p) {
const st = [];
let prev = false;
while (st.length || root) {
while (root) {
st.push(root);
root = root.left;
}
const node = st.pop();
if (prev) return node;
if (node.val === p.val) prev = true;
root = node.right;
}
return null;
};
没看到二叉树，当然这个算法也非常的牛逼，我应该写不出来，说是二叉搜索树的二分法，相当于找右边的边界节点，理解起来还是非常的困难，四行代码，真的神仙代码。
var inorderSuccessor = function (root, p) {
const target = p.val;
let cur = root,
res = null;
while (cur) {
if (cur.val > target) {
res = cur;
cur = cur.left;
} else cur = cur.right;
}
return res;
};
面试 0304 化栈为队
时间：2022-05-16
两个栈来作为一个队列
var MyQueue = function () {
this.in = [];
this.out = [];
};
/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function (x) {
this.in.push(x);
};
/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function () {
if (this.out.length) return this.out.pop();
while (this.in.length) {
this.out.push(this.in.pop());
}
return this.out.pop();
};
/**
* Get the front element.
* @return {number}
*/
MyQueue.prototype.peek = function () {
if (this.out.length) return this.out[this.out.length - 1];
while (this.in.length) {
this.out.push(this.in.pop());
}
return this.out[this.out.length - 1];
};
/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
return !this.out.length && !this.in.length;
};
面试 0305 栈排序
时间：2022-05-16
这题说实话有点龙鸣的，我以为对栈进行排序呢，结果就是添加的时候，把最小的放在上面就行了，就这？这题真不行。
var SortedStack = function () {
this.stack = [];
};
/**
* @param {number} val
* @return {void}
*/
SortedStack.prototype.push = function (val) {
if (this.isEmpty() || val < this.peek()) {
this.stack.push(val);
} else {
const min = this.stack.pop();
this.push(val);
this.stack.push(min);
}
};
/**
* @return {void}
*/
SortedStack.prototype.pop = function () {
return this.stack.pop();
};
/**
* @return {number}
*/
SortedStack.prototype.peek = function () {
return this.stack[this.stack.length - 1] ?? -1; //使用空值合并运算符，如果前者为空则取后者值
};
/**
* @return {boolean}
*/
SortedStack.prototype.isEmpty = function () {
return !this.stack.length;
};
面试 0306 动物收容所
时间：2022-05-16
var AnimalShelf = function () {
this.cat = [];
this.dog = [];
// this.any = [];
};
/**
* @param {number[]} animal
* @return {void}
*/
AnimalShelf.prototype.enqueue = function (animal) {
if (animal[1] == 0) this.cat.push(animal[0]);
else this.dog.push(animal[0]);
// this.any.push(animal[0]);
};
/**
* @return {number[]}
*/
AnimalShelf.prototype.dequeueAny = function () {
if (!this.cat.length && !this.dog.length) return [-1, -1];
if (!this.cat.length && this.dog.length) return [this.dog.shift(), 1];
if (this.cat.length && !this.dog.length) return [this.cat.shift(), 0];
if (this.cat[0] < this.dog[0]) return [this.cat.shift(), 0];
else return [this.dog.shift(), 1];
};
/**
* @return {number[]}
*/
AnimalShelf.prototype.dequeueDog = function () {
if (this.dog.length) return [this.dog.shift(), 1];
else return [-1, -1];
};
/**
* @return {number[]}
*/
AnimalShelf.prototype.dequeueCat = function () {
if (this.cat.length) return [this.cat.shift(), 0];
else return [-1, -1];
};
面试 0401 节点间通路
时间：2022-05-17
用的邻接表，方法是深度优先的方法。
var findWhetherExistsPath = function (n, graph, start, target) {
if (target >= n) return false;
// 构建映射关系表
const map = {};
for (const g of graph) {
const x = g[0],
y = g[1];
if (map[x] === undefined) map[x] = [];
if (!map[x].includes(y)) map[x].push(y);
}
const vis = new Array(n).fill(false);
const dfs = (index) => {
if (index == target) return true;
if (vis[index]) return false;
vis[index] = true;
const to = map[index];
if (to == undefined) return false; // 没有可去的点了，无法到达，返回false
for (let i = 0; i < to.length; i++) {
if (dfs(to[i])) return true; // 递归进入下一层
}
return false;
};
return dfs(start);
};
改成bfs了，比dfs慢一点
var findWhetherExistsPath = function (n, graph, start, target) {
if (target >= n) return false;
// 构建映射关系表
const map = {};
for (const g of graph) {
const x = g[0],
y = g[1];
if (map[x] === undefined) map[x] = [];
if (!map[x].includes(y)) map[x].push(y);
}
const vis = new Array(n).fill(false);
const que = [start];
while (que.length) {
const index = que.pop();
if (index == target) return true;
if (vis[index]) continue;
vis[index] = true;
const to = map[index];
if (to == undefined) continue;
for (let i = 0; i < to.length; i++) {
if(!vis[to[i]]) que.push(to[i]);
}
}
return false;
};
面试 0402 最小高度树
时间：2022-05-17
确实简单，简单递归一下
var sortedArrayToBST = function (nums) {
const dfs = (start, end) => {
if(start>end) return null;
if (start == end) return new TreeNode(nums[start]);
const mid = (start + end) >> 1;
const root = new TreeNode(nums[mid]);
root.left = dfs(start, mid - 1);
root.right = dfs(mid + 1, end);
return root;
};
return dfs(0, nums.length - 1);
};
面试 0403 特定深度节点链表
时间：2022-05-17
有点拉写的，
var listOfDepth = function (tree) {
if (!tree) return [];
let que = [tree],
res = [];
while (que.length) {
const length = que.length;
const arr = [];
const node = new ListNode(que[0].val);
que[0].left && arr.push(que[0].left);
que[0].right && arr.push(que[0].right);
let next = node;
for (let i = 1; i < length; i++) {
const tmp = new ListNode(que[i].val);
next.next = tmp;
next = next.next;
que[i].left && arr.push(que[i].left);
que[i].right && arr.push(que[i].right);
}
que = arr;
res.push(node);
}
return res;
};
看了一下，别人的，用头结点比较合适，速度也能上去，代码量也少一点。
var listOfDepth = function (tree) {
let res = [];
let list = [tree];
let nums = 1; // 保存下一轮循环需要遍历的节点个数
while (list.length) {
// 定义头节点
let head = new ListNode(0);
let temp = head;
for (let i = 0; i < nums; i++) {
// 先进先出
let indexTree = list.shift();
temp.next = new ListNode(indexTree.val);
temp = temp.next;
if (indexTree.left) list.push(indexTree.left);
if (indexTree.right) list.push(indexTree.right);
}
nums = list.length;
res.push(head.next);
}
return res;
};
668 乘法表中第k小的数
时间：2022-05-18
很难，没想明白，就是反向问题，找到第x个数字，然后去寻找他是第k小的数字，然后二分搜索
var findKthNumber = function (m, n, k) {
let left = 1,
right = m * n;
while (left < right) {
const x = left + ((right - left) >> 1);
let count = Math.floor(x / n) * n;
for (let i = Math.floor(x / n) + 1; i <= m; ++i) {
count += Math.floor(x / i);
}
if (count >= k) {
right = x;
} else {
left = x + 1;
}
}
return left;
};
面试 0404 检查平衡性
时间：2022-05-18
抄的，主要是我没想好返回值是啥，返回值直接是当前节点的高度就行了，如果是-1，则直接返回-1，干。
var isBalanced = function (root) {
const dfs = (root) => {
if (!root) return 0;
const left = dfs(root.left);
const right = dfs(root.right);
if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1;
return Math.max(left, right) + 1;
};
return dfs(root) >= 0;
};
面试 0405 合法二叉搜索树
时间：2022-05-18
确实还是喜欢这个中序遍历的递归，但有点拉
var isValidBST = function (root) {
let prev = null;
let res = true;
const dfs = (root) => {
if (!root) return;
dfs(root.left);
if (!prev) prev = root;
else {
if (prev.val >= root.val) {
res = false;
return;
}
prev = root;
}
dfs(root.right);
};
dfs(root);
return res;
};
还有一种这种写法，搞不来，当然我之前也都写过了。还是中序遍历香啊
var isValidBST = function (root) {
const dfs = (root, lower, upper) => {
if (root === null) {
return true;
}
if (root.val <= lower || root.val >= upper) {
return false;
}
return dfs(root.left, lower, root.val) && dfs(root.right, root.val, upper);
}
return dfs(root, -Infinity, Infinity);
};
面试 0408 首个共同祖先
时间：2022-05-18
抄的236，没想到还是做不出来，尿了。这里再讲解一遍。从底向上查找，所以回溯，用的后序遍历，先处理根节点，如果根节点是其中寻找的一个节点，那么就直接返回结果。然后后序遍历左右节点，如果左右子树都有值，相当于左右子树找到了p和q，那么就返回当前节点。
var lowestCommonAncestor = function(root, p, q) {
if (root == p || root == q || root == null) return root;
const resLeft = lowestCommonAncestor(root.left,p,q);
const resRight = lowestCommonAncestor(root.right,p,q);
if (resLeft && resRight) return root;
if (resLeft) return resLeft;
if (resRight) return resRight;
return null;
};
462 最少移动次数使数组元素相等 II
时间：2022-05-19
找到数组的中位数，然后再找每个数字与中位数的差值。朴素想法
var minMoves2 = function (nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
let res = 0,
x = nums[Math.floor(n / 2)];
for (let i = 0; i < n; i++) {
res += Math.abs(nums[i] - x);
}
return res;
};
用上快速排序的想法，找到中位数，其实这个想法就是找到数组中第K个最小的数字。
var minMoves2 = function (nums) {
let n = nums.length,
// x就是中位数
x = quickSelect(nums, 0, n - 1, Math.floor(n / 2)),
ret = 0;
for (let i = 0; i < n; ++i) {
ret += Math.abs(nums[i] - x);
}
return ret;
};
const quickSelect = (nums, left, right, index) => {
const rp = Math.floor(Math.random() * (right - left + 1)) + left;
swap(nums, rp, right);
let x = nums[right],
i = left;
for (let j = left; j < right; ++j) {
if (nums[j] <= x) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, right);
if (i === index) {
return nums[i];
} else {
return i < index ? quickSelect(nums, i + 1, right, index) : quickSelect(nums, left, i - 1, index);
}
};
const swap = (nums, index1, index2) => {
const temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
};
215 数组中的第K个最大元素
时间：2022-05-19
挪用上面的东西，差不多稍微改一下就行了，从大到小排序（不是）
var findKthLargest = function (nums, k) {
return quickSelect(nums, 0, nums.length - 1, k - 1);
};
const quickSelect = (nums, left, right, index) => {
const rp = Math.floor(Math.random() * (right - left + 1)) + left;
swap(nums, rp, right);
let x = nums[right],
i = left;
for (let j = left; j < right; ++j) {
if (nums[j] >= x) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, right);
if (i === index) {
return nums[i];
} else {
return i < index ? quickSelect(nums, i + 1, right, index) : quickSelect(nums, left, i - 1, index);
}
};
const swap = (nums, index1, index2) => {
const temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
};
面试 0409 二叉搜索树序列
时间：2022-05-19
这道题难啊，反正我做不出来，抄也不懂
var BSTSequences = function (root) {
if (root === null) return [[]];
const res = [];
var findPath = function (cur, queue, path) {
// 传入 cur 形参
if (cur.left) queue.push(cur.left);
if (cur.right) queue.push(cur.right);
if (queue.length === 0) {
// 终止条件
res.push(path); // 存放结果
return;
}
for (let i = 0; i < queue.length; i++) {
let newQueue = queue.slice(0, i).concat(queue.slice(i + 1, queue.length));
// 构造新数组，newQueue 其实是将 queue[i] 删除后的数组
findPath(queue[i], newQueue, [...path,queue[i].val]);
}
};
findPath(root, [], [root.val]);
return res;
};
面试 0410 检查子树
时间：2022-05-19
判断t2是不是t1的子树，注意的就是两者都有值不相同的时候，应该去找到t1的子节点和t2去比较
var checkSubTree = function (t1, t2) {
if (!t1 && !t2) return true;
if (!t1 || !t2) return false;
if (t1.val == t2.val) {
return checkSubTree(t1.left, t2.left) && checkSubTree(t1.right, t2.right);
} else {
return checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
}
};
面试 0412 求和路径
时间：2022-05-19
好像做过，但是没有做过，做过113，还以为这题和那题一样，但是不一样，那题是从根节点到子节点的数量，限定了必须要从根节点开始，但是这道题不是，没有限定从什么节点开始，也没有限定从什么节点结束，只要是其中一段路径就行了。所以rootSum就是113的做法，但是因为没有限定开始节点，所以还得继续递归遍历左右节点。
var pathSum = function (root, sum) {
if (root == null) {
return 0;
}
let ret = rootSum(root, sum);
ret += pathSum(root.left, sum);
ret += pathSum(root.right, sum);
return ret;
};
const rootSum = (root, sum) => {
if (root == null) return 0;
let ret = 0;
const val = root.val;
if (val === sum) ret++;
ret += rootSum(root.left, sum - val);
ret += rootSum(root.right, sum - val);
return ret;
};
或者用上前缀和+哈希表
前缀和是当前节点到根节点的和，哈希表key存的是前缀和，value存的是前缀和出现的次数。这里的关键是还需要回溯撤销map的个数。
var pathSum = function (root, sum) {
const map = new Map();
let res = 0;
const dfs = (root, presum) => {
if (!root) return 0;
map.set(presum, (map.get(presum) || 0) + 1);
let target = presum + root.val;
res += map.get(target - sum) || 0;
dfs(root.left, target);
dfs(root.right, target);
// 回溯 撤销
map.set(presum, map.get(presum) - 1);
};
dfs(root, 0);
return res
};
436 寻找右区间
时间：2022-05-20
和我想的差不多，但是我想错了，就是原数组不应该动，我把原数组给动了，所以用起来有点问题。最后还是用的官解来弄的。
var findRightInterval = function (intervals) {
const n = intervals.length;
const startIntervals = new Array(n).fill(0).map(() => new Array(2).fill(0));
for (let i = 0; i < n; i++) {
startIntervals[i][0] = intervals[i][0];
startIntervals[i][1] = i;
}
startIntervals.sort((o1, o2) => o1[0] - o2[0]);
const ans = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
let left = 0;
let right = n - 1;
let target = -1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (startIntervals[mid][0] >= intervals[i][1]) {
target = startIntervals[mid][1];
right = mid - 1;
} else {
left = mid + 1;
}
}
ans[i] = target;
}
return ans;
};
面试 0501 插入
时间：2022-05-20
算是简单题吧，也不是很难
var insertBits = function (N, M, i, j) {
for (let m = i; m <= j; m++) {
N &= ~(1 << m);
}
return N + (M << i);
};
面试 0502 二进制数转字符串
时间：2022-05-20
var printBin = function (num) {
const res = num.toString(2);
if (res.length >= 32) return 'ERROR';
else return res;
};
正常求解小数的二进制我也不会，不过看了一眼，发现还挺简单的
var printBin = function (num) {
let res = '0.';
while (num != 0) {
num *= 2;
if (num >= 1) {
//乘2后num>=1,说明此时整数部分为1，取完该整数部分1后，num接着利用的还是其小数部分，所以要减掉整数部分（即1）
res += '1';
num -= 1;
} else {
//小于1说明整数部分为0，取该整数部分0
res += '0';
}
if (res.length > 32) return 'ERROR';
}
return res;
};
面试 0503 翻转数位
时间：2022-05-20
这题目居然做不出来，虽然标榜简单题，但是还是挺难的，这个insert有点骚的，相当于延迟了一步，这样子就把0转变1的一次机会给包括进去了，佷骚。
var reverseBits = function (num) {
let cur = 0;
let insert = 0;
let res = 0;
for (let i = 0; i < 32; i++) {
if (num & (1 << i)) {
// 1 逻辑与 判断是1
cur++;
insert++;
} else {
insert = cur + 1;
cur = 0;
}
res = Math.max(res, insert);
}
return res;
};
961 在长度2N的数组中找出重复N次的元素
时间：2022-05-21
哈希表
var repeatedNTimes = function (nums) {
const found = new Set();
for (const num of nums) {
if (found.has(num)) {
return num;
}
found.add(num);
}
// 不可能的情况
return -1;
};
还有一个是胡乱法则，有一个期望值
var repeatedNTimes = function(nums) {
const n = nums.length;
while (true) {
const x = Math.floor(Math.random() * n), y = Math.floor(Math.random() * n);
if (x !== y && nums[x] === nums[y]) {
return nums[x];
}
}
};
面试 0504 下一个数
时间：2022-05-21
妈的，都看不懂，只能抄一个最暴力的解法了，就无脑++和无脑–，然后判断1的长度是不是相同就行了。尿了，真的难
var findClosedNumbers = function (num) {
// 这个测试用例超时哈哈
if (num == 2147483647) return [-1, -1];
function cntOne(num) {
let cnt = 0;
while (num != 0) {
num &= num - 1;
cnt++;
}
return cnt;
}
let cnt1 = cntOne(num);
const res = [-1, -1];
for (let i = num + 1; i < 2147483647; i++) {
if (cntOne(i) == cnt1) {
res[0] = i;
break;
}
}
for (let i = num - 1; i >= 0; i--) {
if (cntOne(i) == cnt1) {
res[1] = i;
break;
}
}
return res;
};
面试 0506 整数转换
时间：2022-05-21
var convertInteger = function (A, B) {
let res = 0;
for (let i = 0; i < 32; i++) {
const a = (A >> i) & 1,
b = (B >> i) & 1;
if (a != b) res++;
}
return res;
};
面试 0507 配对交换
时间：2022-05-21
简单方法
var exchangeBits = function (num) {
for (let i = 0; i < 31; i += 2) {
const a = (num >> i) & 1;
const b = (num >> (i + 1)) & 1;
if (a != b) {
num ^= 1 << (i + 1);
num ^= 1 << i;
}
}
return num;
};
这个好像更简单，但是不推荐嗷，因为写不出来
0x55555555 = 0b0101_0101_0101_0101_0101_0101_0101_0101
0xaaaaaaaa = 0b1010_1010_1010_1010_1010_1010_1010_1010
var exchangeBits = function (num) {
let odd = num & 0x55555555;
//偶数
let even = num & 0xaaaaaaaa;
odd = odd << 1;
even = even >>> 1;
return odd | even;
};
面试 0508 绘制直线
时间：2022-05-21
没看懂题目，直接抄的
var drawLine = function (length, w, x1, x2, y) {
const res = [];
const width = length * 32;
let sum = 0;
const left = y * w + x1;
const right = y * w + x2;
for (let i = 0; i < width; ++i) {
sum <<= 1;
if (left <= i && i <= right) {
sum++;
}
if ((i + 1) % 32 === 0) {
res.push(sum);
sum = 0;
}
}
return res;
};
面试 0801 三步问题
时间：2022-05-22
还行，就是取余的时候别忘了
var waysToStep = function (n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 4;
let dp1 = 1,
dp2 = 2,
dp3 = 4;
tmp = 0;
const MOD = 1000000007;
for (let i = 4; i <= n; i++) {
tmp = (dp3 + dp2 + dp1) % MOD;
dp1 = dp2;
dp2 = dp3;
dp3 = tmp;
}
return dp3;
};
面试 0802 迷路的机器人
时间：2022-05-22
这个回溯最重要的一个点，是将obstacleGrid[i][j] = 1;标红，这样子下次就不用去回溯了，否则还要去回溯，直接终止。
var pathWithObstacles = function (obstacleGrid) {
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
if (obstacleGrid[0][0] == 1) return [];
let res;
const dfs = (i, j, path) => {
if (res) return;
if (obstacleGrid[i][j] == 1) return;
path.push([i, j]);
if (i == m - 1 && j == n - 1) {
res = Array.from(path);
return;
}
if (i + 1 < m) {
dfs(i + 1, j, path);
}
if (j + 1 < n) {
dfs(i, j + 1, path);
}
obstacleGrid[i][j] = 1;
path.pop();
};
dfs(0, 0, []);
return res ? res : [];
};
面试 0803 魔术索引
时间：2022-05-22
啊，这，还有更简单的吗？二分搜索？
var findMagicIndex = function (nums) {
for (let i = 0; i < nums.length; i++) if (nums[i] === i) return i;
return -1;
};
面试 0804 幂集
时间：2022-05-22
子集，078相同的题目。
var subsets = function (nums) {
const res = [];
const n = nums.length;
const dfs = (path, index) => {
res.push(Array.from(path));
for (let i = index; i < n; i++) {
path.push(nums[i]);
dfs(path, i + 1);
path.pop();
}
};
dfs([], 0);
return res;
};
面试 0805 递归乘法
时间：2022-05-22
朴素想法
var multiply = function (A, B) {
if (A == 0 || B == 0) return 0;
if (B == 1) return A;
if (A == 1) return B;
return multiply(A, B - 1) + A;
};
这个方法就很巧妙，用位运算可以加快运算的效率，如果B的最低位是1，那么就乘以2再加上A，否则就是直接乘以2；
var multiply = function (A, B) {
if (B) {
if (B & 1) return multiply(A << 1, B >> 1) + A;
else return multiply(A << 1, B >> 1);
}
return 0;
};
或者精简成下面这一行，但是速度好慢啊，这样子真的会快吗？
var multiply = function (A, B) {
return B ? multiply(A << 1, B >> 1) + (B & 1 ? A : 0) : 0;
};
面试 0806 汉诺塔问题
时间：2022-05-23
这不可能会的呀，怎么可能能够成功呢。
把 n-1 号盘子移动到缓冲区
把1号从起点移到终点
然后把缓冲区的n-1号盘子也移到终点
var hanota = function (A, B, C) {
const move = (n, from, buffer, to) => {
// 移动n层汉诺塔
if (n === 1) {
to.push(from.pop());
} else {
move(n - 1, from, to, buffer);
move(1, from, buffer, to);
move(n - 1, buffer, from, to);
}
};
move(A.length, A, B, C);
};
面试 0807 无重复字符串的排列组合
时间：2022-05-23
全排列，为什么我还是做错了！！！！！！！！！！！！！全排列的索引是从0开始的！！！！！！
var permutation = function (S) {
const n = S.length;
const used = new Array(n).fill(false);
const res = [];
const backtrace = (path) => {
if (path.length==n) {
res.push(path.join(''));
return;
}
for (let i = 0; i < n; i++) {
if (used[i]) continue;
used[i] = true;
path.push(S[i]);
backtrace(path);
path.pop();
used[i] = false;
}
};
backtrace([], 0);
return res;
};
面试 0808 有重复字符串的排列组合
时间：2022-05-23
通过了，就是忘了一次排序了，拉了。
var permutation = function (S) {
S = Array.from(S).sort();
const n = S.length;
const used = new Array(n).fill(false);
const res = [];
const backtrace = (path) => {
if (path.length == n) {
res.push(path.join(''));
return;
}
for (let i = 0; i < n; i++) {
if (used[i] || (i > 0 && S[i - 1] === S[i] && !used[i - 1])) continue;
used[i] = true;
path.push(S[i]);
backtrace(path);
path.pop();
used[i] = false;
}
};
backtrace([], 0);
return res;
};
965 单值二叉树
时间：2022-05-24
简简单单。
var isUnivalTree = function (root) {
const val = root.val;
const dfs = (root) => {
if (!root) return true;
if (root.val !== val) return false;
return dfs(root.left) && dfs(root.right);
};
return dfs(root);
};
面试 0810 颜色填充
时间：2022-05-24
也算简单题吧，就是繁琐了一点
var floodFill = function (image, sr, sc, newColor) {
const dirs = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1]
];
const m = image.length,
n = image[0].length;
const target = image[sr][sc];
const used = new Array(m).fill(0).map(() => new Array(n).fill(false));
const dfs = (row, col) => {
used[row][col] = true;
image[row][col] = newColor;
for (let dir of dirs) {
const x = dir[0] + row,
y = dir[1] + col;
if (x >= 0 && x < m && y >= 0 && y < n && target == image[x][y] && !used[x][y]) {
dfs(x, y);
}
}
};
dfs(sr, sc);
return image;
};
面试 0811 硬币
时间：2022-05-24
没做出来，是多重背包问题，外循环是物品数量，内循环是背包的容量。
var waysToChange = function (n) {
const dp = new Array(n + 1).fill(0),
MOD = 1000000007;
dp[0] = 1;
const coins = [25, 10, 5, 1]
for (let coin of coins) {
for (let i = coin; i <= n; i++) {
dp[i] = (dp[i] + dp[i - coin]) % MOD;
}
}
return dp[n];
};
面试 0813 堆箱子
时间：2022-05-24
说是这道题就是上升子序列的变种题目，其实差不多，就是我想不明白为什么一定要按照某一个维度进行排序先，搞不明白实属是。我的理解就是dp中，是查找dp[i]和dp[j]的关系，按照排序后，dp[j]铁定小于dp[i]，这样子才能使得动态规划正确，如果不排序，那么比dp[i]小的箱子可能跑到dp[i]后面了，dp[j]就不完整了。
dp[i] 表示以第 i 个箱子为最底端箱子时，箱堆的最大高度。
var pileBox = function (box) {
const n = box.length,
dp = new Array(n).fill(0);
box.sort((a, b) => a[0] - b[0]);
let res = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (box[i][0] > box[j][0] && box[i][1] > box[j][1] && box[i][2] > box[j][2]) {
dp[i] = Math.max(dp[j], dp[i]);
}
}
dp[i] += box[i][2];
res = Math.max(dp[i], res);
}
return res;
};
面试 0814 布尔运算
时间：2022-05-24
原作者思路：区间DP/分治算法 – 布尔运算，真的变态，我直接跳了，这道题应该是困难的水平，而不是中等的水平，真的难。
var countEval = function (s, result) {
let n = s.length;
// 创建三维数组
let dp = new Array(n).fill(0).map(() => new Array(n).fill(0).map(() => new Array(2).fill(0)));
// 初始化basecase s[i] 为 1,则 dp[i][i][1] = 1, dp[i][i][0] = 0
for (let i = 0; i < n; i += 2) {
let tmp = 0;
if (s[i] == '1') tmp = 1;
dp[i][i][0] = 1 - tmp;
dp[i][i][1] = tmp;
}
// 从0开始，每次+2
for (let step = 0; step < n; step += 2) {
// 计算 i - （i+step） 的情况， j 为中间间隔点 s[j] 为符号
for (let i = 0; i + step < n; i += 2) {
for (let j = i + 1; j < i + step; j += 2) {
let left0 = dp[i][j - 1][0],
left1 = dp[i][j - 1][1];
let right0 = dp[j + 1][i + step][0],
right1 = dp[j + 1][i + step][1];
if (s[j] == '&') {
dp[i][i + step][0] += left0 * (right0 + right1) + left1 * right0;
dp[i][i + step][1] += left1 * right1;
} else if (s[j] == '|') {
dp[i][i + step][0] += left0 * right0;
dp[i][i + step][1] += left0 * right1 + left1 * (right0 + right1);
} else {
//s[j]=='^'
dp[i][i + step][0] += left0 * right0 + left1 * right1;
dp[i][i + step][1] += left0 * right1 + left1 * right0;
}
}
}
}
return dp[0][n - 1][result];
};
467 环绕字符串中唯一的子字符串
时间：2022-05-25
抄的官解，和我想象中的不一样呢。
自己秒想的是依次找到连续子串，然后直接数学算出这个数量，但是不行，因为有些子串是重复出现的，所以计算会多算了，只能用官解这种方法。
dp[i] 表示以 i 结尾且在 s 中的子串的最长长度。
var findSubstringInWraproundString = function (p) {
const dp = new Array(26).fill(0);
let k = 0;
for (let i = 0; i < p.length; ++i) {
if (i > 0 && (p[i].charCodeAt() - p.charCodeAt(i - 1) + 26) % 26 === 1) {
// 字符之差为 1 或 -25
++k;
} else {
k = 1;
}
dp[p.charCodeAt(i) - 97] = Math.max(dp[p[i].charCodeAt() - 97], k);
}
return dp.reduce((a, b) => a + b);
};
面试 1001 合并排序的数组
时间：2022-05-25
就这？或者把while里面的c>=0改成n>=0，从理论上来讲，这个速度会更快，但是实测没有，但是有误差，这种绝对能快一点，理论上。
var merge = function (A, m, B, n) {
let a,
b,
c = m + n - 1;
m--;
n--;
while (c >= 0) {
a = m < 0 ? -Infinity : A[m];
b = n < 0 ? -Infinity : B[n];
if (a < b) {
A[c] = b;
n--;
} else {
A[c] = a;
m--;
}
c--;
}
return A;
};
面试 1002 变位词组
时间：2022-05-25
用计数的方法，这里有一个点就是count虽然是数组，但是在作为对象的属性名时，会自动转换成字符串，就很绝，所以才能够通过。
var groupAnagrams = function (strs) {
const map = new Object();
for (let s of strs) {
const count = new Array(26).fill(0);
for (let c of s) {
count[c.charCodeAt() - 'a'.charCodeAt()]++;
}
map[count] ? map[count].push(s) : (map[count] = [s]);
}
return Object.values(map);
};
面试 1003 搜索旋转数组
时间：2022-05-25
var search = function (arr, target) {
return arr.findIndex((v) =>v == target);
};
//或者一句话
const search = (arr, target) => arr.findIndex((v) => v === target);
// 或者下面这句话，但是这个时间变长了许多
const search = (arr, target) => arr.indexOf(target);
这个真的太难了，有一些特例，比如第一句这种。然后蜂聚arr[mid]与arr[j]的关系，以及target是否在这之间来判断。难。
var search = function (arr, target) {
if (arr[0] == target) return 0;
let i = 0,
j = arr.length - 1;
while (i <= j) {
let mid = (i + j) >> 1;
if (arr[mid] == target) {
while (mid > 0 && arr[mid - 1] == arr[mid]) mid--;
return mid;
}
if (arr[mid] < arr[j]) {
if (arr[mid] < target && target <= arr[j]) i = mid + 1;
else j = mid - 1;
} else if (arr[mid] > arr[j]) {
if (arr[i] <= target && target < arr[mid]) j = mid - 1;
else i = mid + 1;
} else {
j--;
}
}
return -1;
};
相比上面这种，下面这种更好理解和更好写，相当于拆分了两次，用两次二分搜索，先找到一次突变点，再正常的二分搜索。
var search = function (arr, target) {
let i = 0,
j = arr.length - 1;
while (j > 0 && arr[i] == arr[j]) j--;
// 然后找到那个跳变的左边界
while (i <= j) {
const mid = (i + j) >> 1;
if (arr[mid] >= arr[0]) i = mid + 1;
else j = mid - 1;
}
// 判断目标是在左线段还是右线段
if (target >= arr[0]) i = 0;
else j = arr.length - 1;
// 常规二分查找，找到左边界
while (i <= j) {
const mid = (i + j) >> 1;
if (arr[mid] < target) i = mid + 1;
else j = mid - 1;
}
return arr[i] == target ? i : -1;
};
面试 1005 稀疏数组搜索
时间：2022-05-26
var findString = function (words, s) {
return words.indexOf(s);
};
二分法，就是需要空格的时候需要往左找到非空格的字符。
var findString = function (words, s) {
let l = 0,
r = words.length - 1;
while (l <= r) {
let mid = (l + r) >> 1;
while (l < mid && words[mid] == '') mid--
if (s === words[mid]) return mid;
else if (s < words[mid]) r = mid - 1;
else l = mid + 1;
}
return -1;
};
面试 1009 排序矩阵查找
时间：2022-05-26
以前写过，从右上角开始查询，思路很正确。
var searchMatrix = function (matrix, target) {
const m = matrix.length;
if (m == 0) return false;
const n = matrix[0].length;
let i = 0,
j = n - 1;
while (i < m && j >= 0) {
if (target > matrix[i][j]) i++;
else if (target < matrix[i][j]) j--;
else return true;
}
return false;
};
面试 1010 数字流的秩
时间：2022-05-26
纯用这个api的方法。
var StreamRank = function () {
this.stack = [];
};
/**
* @param {number} x
* @return {void}
*/
StreamRank.prototype.track = function (x) {
this.stack.push(x);
};
/**
* @param {number} x
* @return {number}
*/
StreamRank.prototype.getRankOfNumber = function (x) {
return this.stack.filter((v) => v <= x).length;
};
用的数组后挪+二分搜索的方法。
var StreamRank = function () {
this.stack = [];
};
/**
* @param {number} x
* @return {void}
*/
StreamRank.prototype.track = function (x) {
let index = this.getRankOfNumber(x) ;
let i = this.stack.length;
while (index < i) {
this.stack[i] = this.stack[i - 1];
i--;
}
this.stack[index] = x;
};
/**
* @param {number} x
* @return {number}
*/
StreamRank.prototype.getRankOfNumber = function (x) {
const stack = this.stack;
let i = 0,
j = stack.length - 1;
while (i <= j) {
const m = (i + j) >> 1;
if (stack[m] <= x) i = m + 1;
else j = m - 1;
}
return i;
};
面试 1011 峰与谷
时间：2022-05-26
这题太龙鸣了，没说要求修改原数组，结果是要修改原数组
var wiggleSort = function (nums) {
nums.sort((a, b) => b - a);
let i = 0,
j = nums.length - 1;
const res = [];
while (i < j) {
res.push(nums[i++]);
res.push(nums[j--])
}
if (i == j) res.push(nums[i]);
const len = res.length;
for (let i = 0; i < len; i++) {
nums[i] = res[i];
}
};
这里有一个直接修改原数组的方法，根据奇偶性进行修改。偶数是峰，奇数是谷，然后分别判断是不是这样子的，不是的话就交换。
var wiggleSort = function (nums) {
// 偶数是峰，奇数是谷
for (let i = 1; i < nums.length; i++) {
if (i & 1) {
if (nums[i] > nums[i - 1]) [nums[i], nums[i - 1]] = [nums[i - 1], nums[i]];
} else {
if (nums[i] < nums[i - 1]) [nums[i], nums[i - 1]] = [nums[i - 1], nums[i]];
}
}
};
