Leetcode-21
封控于宿舍，就这样子吧。
427 建立四叉树
时间：2022-04-29
抄的，题目就看了大半天了，难以看懂。
var construct = function (grid) {
const n = grid.length;
function dfs(i0, i1, j0, j1) {
if (i0 === i1 && j0 === j1) return new Node(grid[i0][j0], true);
// 递归求出4个子节点
const mi = Math.floor(i1 / 2 + i0 / 2),
mj = Math.floor(j1 / 2 + j0 / 2);
const tl = dfs(i0, mi, j0, mj);
const tr = dfs(i0, mi, mj + 1, j1);
const bl = dfs(mi + 1, i1, j0, mj);
const br = dfs(mi + 1, i1, mj + 1, j1);
const children = [tl, tr, bl, br];
// 求出所有子节点的 val 之和
const val = children.reduce((a, c) => a + c.val, 0);
// isLeaf：所有子节点的 val 之和是 4 或 0，且所有子节点都是叶子节点
const isLeaf = val % 4 === 0 && children.every((n) => n.isLeaf);
// node.val：所有子节点的 val 之和除以 4 并向上取整
// node.isLeaf：所有子节点的 val 之和是 4 或 0，且所有子节点都是叶子节点
// 4个子节点：当前节点是否有子节点由 isLeaf 决定
return new Node(Math.ceil(val / 4), isLeaf, ...(isLeaf ? [] : children));
}
return dfs(0, n - 1, 0, n - 1);
};
offer II 099 最小路径之和
时间：2022-04-29
简单的动态规划，一次过。
var minPathSum = function (grid) {
const m = grid.length,
n = grid[0].length;
const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
let tmp = 0;
for (let i = 0; i < m; i++) {
tmp += grid[i][0];
dp[i][0] = tmp;
}
tmp = 0;
for (let i = 0; i < n; i++) {
tmp += grid[0][i];
dp[0][i] = tmp;
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
};
908 最小差值 I
时间：2022-05-02
简单题，简单写
var smallestRangeI = function (nums, k) {
const min = Math.min(...nums);
const max = Math.max(...nums);
if (max - min > 2 * k) return max - min - 2 * k;
else return 0;
};
173 二叉搜索树迭代器
时间：2022-05-02
为下面1305做铺垫。就是转换成数组然后迭代，朴素的想法，但是非常拉胯
var BSTIterator = function (root) {
this.idx = 0;
this.arr = [];
inorderTraversal(root, this.arr);
};
BSTIterator.prototype.next = function () {
return this.arr[this.idx++];
};
BSTIterator.prototype.hasNext = function () {
return this.idx < this.arr.length;
};
const inorderTraversal = (root, arr) => {
if (!root) {
return;
}
inorderTraversal(root.left, arr);
arr.push(root.val);
inorderTraversal(root.right, arr);
};
正常的迭代法，用栈来保存。
var BSTIterator = function (root) {
this.cur = root;
this.stack = [];
};
BSTIterator.prototype.next = function () {
while (this.cur) {
this.stack.push(this.cur);
this.cur = this.cur.left;
}
this.cur = this.stack.pop();
const res = this.cur.val;
this.cur = this.cur.right;
return res;
};
BSTIterator.prototype.hasNext = function () {
return this.cur != null || this.stack.length;
};
1305 两棵二叉搜索树中的所有元素
时间：2022-05-02
朴素想法，两个数组，然后归并，方法拉了点
var getAllElements = function (root1, root2) {
const arr1 = [];
const arr2 = [];
const makeArr = (root, arr) => {
if (!root) return;
if (root.left) makeArr(root.left, arr);
arr.push(root.val);
if (root.right) makeArr(root.right, arr);
};
makeArr(root1, arr1);
makeArr(root2, arr2);
let i = 0,
j = 0;
const res = [];
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
res.push(arr1[i]);
i++;
} else {
res.push(arr2[j]);
j++;
}
}
if (i == arr1.length) return res.concat(arr2.slice(j));
else return res.concat(arr1.slice(i));
};
模仿173写个迭代器，精髓就是将之前的next给拆分成两份，变成next和peek两个不一样的，这样子就能变成迭代器了。
var getAllElements = function (root1, root2) {
const bst1 = new BSTIterator(root1);
const bst2 = new BSTIterator(root2);
const res = [];
while (bst1.hasNext() && bst2.hasNext()) {
if (bst1.peek() < bst2.peek()) res.push(bst1.next());
else res.push(bst2.next());
}
while (bst1.hasNext()) {
bst1.peek()
res.push(bst1.next());
}
while (bst2.hasNext()) {
bst2.peek()
res.push(bst2.next());
}
return res;
};
var BSTIterator = function (root) {
this.cur = root;
this.stack = [];
};
BSTIterator.prototype.next = function () {
this.cur = this.stack.pop();
const res = this.cur.val;
this.cur = this.cur.right;
return res;
};
BSTIterator.prototype.peek = function () {
while (this.cur) {
this.stack.push(this.cur);
this.cur = this.cur.left;
}
return this.stack[this.stack.length - 1].val;
};
BSTIterator.prototype.hasNext = function () {
return this.cur != null || this.stack.length !== 0;
};
1823 找出游戏的获胜者
时间：2022-05-04
剑指offer62道题目，还是不会，
var findTheWinner = function (n, k) {
if (n == 1) return 1;
return (findTheWinner(n - 1, k) + k - 1) % n + 1;
};
785 判断二分图
时间：2022-05-04
bfs比较好想，给当前节点上色，判断相邻的节点颜色是不是相同的，相同的就继续，否则就返回false。当然还有并查集，看不懂。
var isBipartite = function (graph) {
const n = graph.length;
const visited = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
if (visited[i] != 0) continue;
const que = [i];
visited[i] = 1;
while (que.length) {
const index = que.shift()
const arr = graph[index];
const cur = visited[index]
for (let j of arr) {
if (visited[j] == -cur) continue;
else if (visited[j] == cur) return false;
visited[j] = -cur;
que.push(j);
}
}
}
return true;
};
127 单词接龙
时间：2022-05-04
朴素单源BFS，没想到这么简单暴力，就硬拼凑单词，然后字典序里面查找，如果找到，那么就删除这个单词，然后push到队列里面，把层序也加一。只要找到endWord就是最短的，因为这个是队列，里面的层序是单调递增的，不会有小的。
var ladderLength = function (beginWord, endWord, wordList) {
const wordSet = new Set(wordList);
const queue = [];
queue.push([beginWord, 1]);
while (queue.length) {
const [word, level] = queue.shift(); // 当前出列的单词
if (word == endWord) {
return level;
}
for (let i = 0; i < word.length; i++) {
// 遍历当前单词的所有字符
for (let c = 97; c <= 122; c++) {
// 对应26个字母
const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1); // 形成新词
if (wordSet.has(newWord)) {
// 单词表里有这个新词
queue.push([newWord, level + 1]); // 作为下一层的词入列
wordSet.delete(newWord); // 避免该词重复入列
}
}
}
}
return 0; // bfs结束，始终没有遇到终点
};
双向BFS，目的就是为了减少空间，加快速度，两个依次交替执行，原理还是上面那样的。
var ladderLength = function (beginWord, endWord, wordList) {
const wordSet = new Set(wordList);
if (!wordSet.has(endWord)) return 0;
let begSet = [beginWord],
endSet = [endWord],
n = 1;
while (begSet.length > 0) {
const nextBegins = [];
if (begSet.length > endSet.length) [begSet, endSet] = [endSet, begSet];
for (let k = 0; k < begSet.length; k++) {
let m = begSet[k];
for (let i = 0; i < m.length; i++) {
for (let c = 97; c <= 122; c++) {
let newm = m.slice(0, i) + String.fromCharCode(c) + m.slice(i + 1);
if (endSet.includes(newm)) {
return n + 1;
}
if (wordSet.has(newm)) {
nextBegins.push(newm);
wordSet.delete(newm);
}
}
}
}
begSet = nextBegins;
n++;
}
return 0;
};
offer II 109 开密码锁
时间：2022-05-05
抄的，虽然和上述的差不多，但这个是不在字典序里面的，反正差点意思还是，而且写不出来我。还有一种A*算法，不看了，这种哪里是人能想出来的。
var openLock = function (deadends, target) {
if (target === '0000') return 0;
const dead = new Set(deadends);
if (dead.has('0000')) return -1;
let step = 0;
const queue = ['0000'],
visited = new Set();
visited.add('0000');
while (queue.length) {
++step;
const size = queue.length;
for (let i = 0; i < size; ++i) {
const status = queue.shift();
for (const nextStatus of get(status)) {
if (!visited.has(nextStatus) && !dead.has(nextStatus)) {
if (nextStatus === target) return step;
queue.push(nextStatus);
visited.add(nextStatus);
}
}
}
}
return -1;
};
// 枚举 status 通过一次旋转得到的数字
const get = (status) => {
const numPrev = (x) => (x === '0' ? '9' : parseInt(x) - 1 + '');
const numSucc = (x) => (x === '9' ? '0' : parseInt(x) + 1 + '');
const ret = [];
const array = Array.from(status);
for (let i = 0; i < 4; ++i) {
const num = array[i];
array[i] = numPrev(num);
ret.push(array.join(''));
array[i] = numSucc(num);
ret.push(array.join(''));
array[i] = num;
}
return ret;
};
111 计算除法
时间：2022-05-05
这道题极品难，应该有困难的难度，但是力扣标的还是中等。这道题我看题解都费劲，有好几种写法，我直接抄的bfs，这里面用了邻接表，就是把它们抽象成图，然后再从图的源头开始找，一路找下来，写起来还是相当的复杂。
var calcEquation = function (equations, values, queries) {
let nvars = 0;
const variables = new Map();
const n = equations.length;
for (let i = 0; i < n; i++) {
if (!variables.has(equations[i][0])) variables.set(equations[i][0], nvars++);
if (!variables.has(equations[i][1])) variables.set(equations[i][1], nvars++);
}
// edges就是邻接表
const edges = new Array(nvars).fill(0).map(() => []);
for (let i = 0; i < n; i++) {
const va = variables.get(equations[i][0]),
vb = variables.get(equations[i][1]);
edges[va].push([vb, values[i]]);
edges[vb].push([va, 1.0 / values[i]]);
}
const queriesCount = queries.length;
const ret = [];
for (let i = 0; i < queriesCount; i++) {
const query = queries[i];
let result = -1.0;
if (variables.has(query[0]) && variables.has(query[1])) {
const ia = variables.get(query[0]),
ib = variables.get(query[1]);
if (ia === ib) {
// 存在并且相同就返回1
result = 1.0;
} else {
// 从源头开始查找
const points = [ia];
const ratios = new Array(nvars).fill(-1.0);
ratios[ia] = 1.0;
while (points.length && ratios[ib] < 0) {
const x = points.pop();
for (const [y, val] of edges[x]) {
if (ratios[y] < 0) {
ratios[y] = ratios[x] * val;
points.push(y);
}
}
}
result = ratios[ib];
}
}
ret[i] = result;
}
return ret;
};
这里用邻接矩阵的，用的floyd，看起来比上述的简单多了，这种是我比较推荐的，也是我有可能自己有能力写出来的，当然这个速度慢了很多，适合比较稠密的图。
var calcEquation = function (equations, values, queries) {
let nvars = 0;
const variables = new Map(),
n = equations.length;
for (let i = 0; i < n; i++) {
if (!variables.has(equations[i][0])) variables.set(equations[i][0], nvars++);
if (!variables.has(equations[i][1])) variables.set(equations[i][1], nvars++);
}
// 邻接矩阵
const graph = new Array(nvars).fill(0).map(() => new Array(nvars).fill(-1.0));
for (let i = 0; i < n; i++) {
const va = variables.get(equations[i][0]),
vb = variables.get(equations[i][1]);
graph[va][vb] = values[i];
graph[vb][va] = 1.0 / values[i];
}
// Floyd算法，O(n^3)的时间复杂度，O(n^2)的空间复杂度
// 1、遍历所有的点
for (let k = 0; k < nvars; k++) {
// 2、遍历开始的点
for (let i = 0; i < nvars; i++) {
// 3、遍历结束的点
for (let j = 0; j < nvars; j++) {
// 4、如果有开始的点到中间的点 和 中间的点到结束的点，那么就更新开始到结束的点的权重
if (graph[i][k] > 0 && graph[k][j] > 0) {
graph[i][j] = graph[i][k] * graph[k][j];
}
}
}
}
const queriesCount = queries.length;
const res = new Array(queriesCount).fill(0);
for (let i = 0; i < queriesCount; i++) {
const query = queries[i];
let result = -1.0;
// 先判断分母和分子有没有这两个数
if (variables.has(query[0]) && variables.has(query[1])) {
const ia = variables.get(query[0]),
ib = variables.get(query[1]);
if (graph[ia][ib] > 0) {
result = graph[ia][ib];
}
}
res[i] = result;
}
return res;
};
933 最近的请求次数
时间：2022-05-06
用的shift，时间非常拉胯。
var RecentCounter = function () {
this.que = [];
};
/**
* @param {number} t
* @return {number}
*/
RecentCounter.prototype.ping = function (t) {
this.que.push(t);
while (this.que[0] < t - 3000) {
this.que.shift();
}
return this.que.length;
};
记住下标，还是一直推进去，可是更慢了。
var RecentCounter = function () {
this.que = [];
this.start = 0;
};
/**
* @param {number} t
* @return {number}
*/
RecentCounter.prototype.ping = function (t) {
while (this.start < this.que.length && this.que[this.start] < t - 3000) {
this.start++;
}
this.que.push(t);
return this.que.length - this.start;
};
offer II 112 最长递增路径
时间：2022-05-06
用的是什么记忆化搜索，需要用一个数组来保存，用普通的深度优先是过不去的，用这个比较合适。
var longestIncreasingPath = function (matrix) {
const dirs = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1]
];
const m = matrix.length;
const n = matrix[0].length;
let res = 0;
const maxArr = new Array(m).fill(0).map(() => new Array(n).fill(0));
const dfs = (i, j) => {
if (maxArr[i][j] != 0) return maxArr[i][j];
++maxArr[i][j];
for (let dir of dirs) {
const x = dir[0] + i;
const y = dir[1] + j;
if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
maxArr[i][j] = Math.max(dfs(x, y) + 1, maxArr[i][j]);
}
}
return maxArr[i][j];
};
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
res = Math.max(res, dfs(i, j));
}
}
return res;
};
offer II 113 课程顺序
时间：2022-05-06
用的bfs搜索，首先先用edges保存A->B这种关系，然后再用indeg保存入度，比如A的入度为0，B的入度为1，然后用队列保存入度为0的，然后除去这些入度为0的，同时把有联系的节点入度减一，再去找下一个入度为0的。
var findOrder = function (numCourses, prerequisites) {
const edges = new Array(numCourses).fill(0).map(() => []),
indeg = new Array(numCourses).fill(0);
for (let [aft, pre] of prerequisites) {
edges[pre].push(aft);
indeg[aft]++;
}
const queue = [],
res = [];
for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) queue.push(i);
while (queue.length) {
const node = queue.shift();
res.push(node);
for (let out of edges[node]) {
--indeg[out];
if (indeg[out] == 0) queue.push(out);
}
}
if (res.length != numCourses) return [];
return res;
};
433 最小基因变化
时间：2022-05-07
这题和前几天做的127差不多一模一样，思路都一样的，直接copy过来改一下参数就行了。
var minMutation = function (start, end, bank) {
const arr = ['A', 'C', 'G', 'T'];
const wordSet = new Set(bank);
if (!wordSet.has(end)) return -1;
const queue = [];
queue.push([start, 0]);
while (queue.length) {
const [word, level] = queue.shift(); // 当前出列的单词
if (word == end) {
return level;
}
for (let i = 0; i < word.length; i++) {
// 遍历当前单词的所有字符
for (let c of arr) {
// 对应26个字母
const newWord = word.slice(0, i) + c + word.slice(i + 1); // 形成新词
if (wordSet.has(newWord)) {
// 单词表里有这个新词
queue.push([newWord, level + 1]); // 作为下一层的词入列
wordSet.delete(newWord); // 避免该词重复入列
}
}
}
}
return -1; // bfs结束，始终没有遇到终点
};
434 字符串中的单词数
时间：2022-05-07
简单题我都又错了好几次，这个用split分词，为什么老是会有空格加进来，实在是想不通。
var countSegments = function (s) {
return s.split(' ').filter(c => c).length
};
offer II 114 外星文字典
时间：2022-05-07
经典拓扑排序，和之前做的题目差不多。没去搜定义，估计这个拓扑排序就是先给出点与点之间的图关系，然后还有一个入度，然后处理一番，再根据入度为0的开始入队列处理，处理完这个节点，相应的与之关联的节点入度-1，再次压入入度为0的。这道题难点在于构建图那部分，需要将两个字符串进行对比才行。
- 难点一：前面的字符串包含后面的字符串，并且长度不相同，那么不管什么排序都是不可能的
- 难点二：处理完两个字符串不相同的部分就应该直接break，后面的不是按照顺序了。
- 难点三：最后处理完的结果如果不等于所有出现的字符的数量，那么就返回空串
var alienOrder = function (words) {
const graph = {},
inDegrees = {};
for (let word of words) {
for (let ch of word) {
graph[ch] = {}; // 键保存起始节点 值里保存结束节点
inDegrees[ch] = 0; // 入度都初始化 0
}
}
for (let i = 1; i < words.length; i++) {
// 构造图和入度 难点
let w1 = words[i - 1];
let w2 = words[i];
if (w1.startsWith(w2) && w1.length !== w2.length) return ''; // 无论什么样的排序都是不可能的
for (let j = 0; j < w1.length && j < w2.length; j++) {
let ch1 = w1[j]; // 前面
let ch2 = w2[j]; // 后面
if (ch1 !== ch2) {
if (!graph[ch1][ch2]) {
graph[ch1][ch2] = true; // 图中较小的字母指向较大的字母
++inDegrees[ch2];
}
break; //终止 for 循环 因为顺序是按照前面的字母优先
}
}
}
const queue = []; // 找出图的拓扑排序即可
for (let ch in inDegrees) if (inDegrees[ch] == 0) queue.push(ch);
let res = '';
while (queue.length) {
let ch = queue.shift();
res += ch;
for (let next in graph[ch]) {
--inDegrees[next];
if (inDegrees[next] == 0) queue.push(next);
}
}
return res.length === Object.keys(graph).length ? res : ''
};
offer II 115 重建序列
时间：2022-05-07
很合理，中等题，30%的通过率，我一共错了五次，还是在偷看别人的答案基础上，这个案例真的恶心，给的都太奇葩了，非得要多判断判断。
var sequenceReconstruction = function (org, seqs) {
if (seqs.length == 0) return false;
const graph = {},
inDegrees = {},
len = org.length;
for (let seq of seqs) {
for (let s of seq) {
if (s > len || s < 1) return false;
if (!graph[s]) {
graph[s] = {}; // 键保存起始节点 值里保存结束节点
inDegrees[s] = 0; // 入度都初始化 0
}
}
}
// 构建拓扑图
for (let seq of seqs) {
const n = seq.length;
for (let i = 0; i < n - 1; i++) {
const cur = seq[i],
next = seq[i + 1];
if (!graph[cur][next]) {
graph[cur][next] = true;
++inDegrees[next];
}
}
}
const queue = [],
res = [];
for (let num in inDegrees) if (inDegrees[num] == 0) queue.push(num);
while (queue.length === 1) {
const num = queue.shift();
res.push(num);
for (let next in graph[num]) {
--inDegrees[next];
if (inDegrees[next] == 0) queue.push(next);
}
}
return res.toString() === org.toString();
};
442 数组中重复的数据
时间：2022-05-08
抄的，这种技巧性的题目完全搞不来，想法很简单，就是找到数字相对应的下标，然后不相同的话就挪过去，相当于排序了？
var findDuplicates = function (nums) {
const swap = (nums, index1, index2) => {
const temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
};
const n = nums.length;
for (let i = 0; i < n; ++i) {
while (nums[i] != nums[nums[i] - 1]) {
swap(nums, i, nums[i] - 1);
}
}
const ans = [];
for (let i = 0; i < n; ++i) {
if (nums[i] - 1 !== i) {
ans.push(nums[i]);
}
}
return ans;
};
这里还有一个按照正负号来分的，就是判断对应的下标处是正的还是负的，负的说明已经出现过一次了，正的说明还没出现过，那么转换成负数的。
var findDuplicates = function(nums) {
const n = nums.length;
const ans = [];
for (let i = 0; i < n; ++i) {
const x = Math.abs(nums[i]);
if (nums[x - 1] > 0) {
nums[x - 1] = -nums[x - 1];
} else {
ans.push(x);
}
}
return ans;
}
839 相似字符串组
坚决不学并查集，麻烦死了，还要背模板，背的到吗？有这个能力吗？面试会考吗？而且并查集的东西都可以转换成bfs或者dfs，根本不需要并查集。下面这种接法就是抄的dfs，就是嗯找，就是需要用一个visited来标记找过了没，速度很快，真的巨快，比起并查集不知道高到哪里去了。
const numSimilarGroups = (strs) => {
const n = strs.length,
len = strs[0].length,
visited = new Array(n).fill(false);
let res = 0;
const checkStrIsSimilar = (str1, str2) => {
let number = 0;
for (let i = 0; i < len; i++) {
if (str1[i] !== str2[i]) {
number++;
if (number > 2) return false;
}
}
return number === 2 || number === 0;
};
const dfs = (index) => {
for (let i = 0; i < n; i++) {
if (!visited[i] && checkStrIsSimilar(strs[index], strs[i])) {
visited[i] = true;
dfs(i);
}
}
};
for (let i = 0; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
dfs(i);
res++;
}
}
return res;
};
offer II 118 多余的边
时间：2022-05-08
焯！还是用上了并查集，最简单的并查集，就是用合并和查找两个操作，我这里写的都非常简单了。就是如果两个节点不是一个帮派的，就合并，如果是一个帮派的，那么说明这条边是重复多余的，那么就返回这条边，这算最简单的一道并查集了。
var findRedundantConnection = function (edges) {
const n = edges.length,
parent = new Array(n + 1).fill(0).map((_, index) => index);
const find = (index) => (parent[index] === index ? index : find(parent[index]));
const union = (index1, index2) => (parent[find(index1)] = find(index2));
for (let i = 0; i < n; i++) {
const edge = edges[i],
node1 = edge[0],
node2 = edge[1];
if (find(node1) != find(node2)) union(node1, node2);
else return edge;
}
return [0];
};
942 增减字符串匹配
时间：2022-05-09
挺难的，还是看的解析，贪心算法，I就是贪左边，D就是贪右边
var diStringMatch = function (s) {
const res = [];
let i = 0,
j = s.length;
for (let ch of s) res.push(ch === 'I' ? i++ : j--);
res.push(i)
return res;
};
面试 0101 判定字符是否唯一
时间：2022-05-10
第一道简单题就这么难，要求不用其他的数据结构来存储，盲猜需要位运算
var isUnique = function (astr) {
const arr = new Array(26).fill(0);
for (let i of astr) {
if (arr[i.charCodeAt() - 97] == 0) {
arr[i.charCodeAt() - 97]++;
} else return false;
}
return true;
};
位运算，如果与的时候不等于0，那么就是重复了，返回false，否则就用或
var isUnique = function (astr) {
let mark = 0;
for (let i of astr) {
if ((mark & (1 << (i.charCodeAt() - 97))) !== 0) return false;
else mark |= 1 << (i.charCodeAt() - 97);
}
return true;
};
面试 0102 判定是否互为字符重排
时间：2022-05-10
和242相同，但是面试题没有给出相似题，还得自己去找，所以还是再给一次题解吧。
var CheckPermutation = function(s, t) {
const n = s.length;
if (n != t.length) return false;
const arr = new Array(26).fill(0);
for (let i = 0; i < n; i++) {
arr[s[i].charCodeAt() - 97]++;
arr[t[i].charCodeAt() - 97]--;
}
for (let i of arr) {
if (i != 0) return false;
}
return true;
};
面试 0103 URL化
时间：2022-05-10
别说，还挺难的，但是用js的api就是快啊
var replaceSpaces = function (s, length) {
if (s.length != length) s = s.substring(0, length);
return s.replace(/ /g, '%20');
};
面试 0104 回文排列
时间：2022-05-10
确实难啊，这还没有规定字符串的范围，确实比leetcode简单题难一点。
var canPermutePalindrome = function (s) {
const set = {};
for (let i of s) {
if (!set[i]) set[i] = 1;
else set[i]--;
}
let flag = false;
for (let a in set) {
if (set[a] & 1) {
if (!flag) flag = true;
else return false;
}
}
return true;
};
944 删列造序
时间：2022-05-12
看错题目了，是删列，不是删行
var minDeletionSize = function (strs) {
const n = strs.length,
m = strs[0].length;
let res = 0;
for (let i = 0; i < m; i++) {
for (let j = 1; j < n; j++) {
if (strs[j][i].charCodeAt() < strs[j - 1][i].charCodeAt()) {
res++;
break;
}
}
}
return res;
};
面试 0105 一次编辑
时间：2022-05-12
一次过，速度一般，空间不错
var oneEditAway = function (first, second) {
const n = first.length,
m = second.length;
if (first === second) return true;
if (Math.abs(n - m) > 1) return false;
if (n > m) {
return deleteOneWord(first, second);
} else if (m > n) {
return deleteOneWord(second, first);
} else {
let flag = false;
for (let i = 0; i < n; i++) {
if (first[i] != second[i]) {
if (!flag) flag = true;
else return false;
}
}
return true;
}
};
const deleteOneWord = (chang, duan) => {
if (chang.substring(duan.length) === duan) return true;
let j = 0;
for (let i = 0; i < chang.length; i++) {
if (chang[i] != duan[j]) {
if (i != j) return false;
continue;
}
j++;
}
return true;
};
面试 0106 字符串压缩
时间：2022-05-12
错了好几次。没看完整题目，如果压缩后还变大了， 那就不值得压缩了。
var compressString = function (s) {
let res = '',
cnt = 0,
tmp = s[0];
for (let i of s) {
if (i != tmp) {
res += tmp + cnt;
cnt = 0;
tmp = i;
}
cnt++;
}
res += tmp + cnt;
return res.length >= s.length ? s : res;
};
面试 0108 零矩阵
时间：2022-05-12
之前写过的，就是拿两个数组记录一下，当然力扣应该有原题，但是我找不到了，还有两行变量标记的水平
var setZeroes = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const row = new Array(m).fill(false);
const col = new Array(n).fill(false);
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
row[i] = col[j] = true;
}
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
};
面试 0109 字符串轮转
时间：2022-05-12
原题是796，摘抄过来了，一模一样。
var isFlipedString = function(s1, s2) {
return s1.length === s2.length && (s1 + s1).indexOf(s2) !== -1;
};
面试 0201 移除重复节点
时间：2022-05-13
这道题简单倒是简单，但是我怎么错了好几次。
var removeDuplicateNodes = function (head) {
if (!head || !head.next) return head;
const set = new Set();
let cur = head,
next = head,
prev = head;
while (next) {
if (!set.has(next.val)) {
set.add(next.val);
prev = cur;
cur.val = next.val;
cur = cur.next;
}
next = next.next;
}
prev.next = null;
return head;
};
面试 0202 返回倒数第 k 个节点
时间：2022-05-13
问题不大，这题简单
var kthToLast = function (head, k) {
let next = head;
while (k-- > 0) next = next.next;
let res = head;
while (next) {
res = res.next;
next = next.next;
}
return res.val;
};
面试 0203 删除中间节点
时间：2022-05-13
题目看错了，好几次，难顶、
var deleteNode = function (node) {
let prev = node;
while (node.next) {
prev = node;
node.val = node.next.val
node = node.next
}
prev.next = null
};
这个妙，相当于脑筋急转弯了，把下一个节点的值先复制过来，然后下一个节点就是正常的删除，相当于转换为了删除下一个节点了，而不是当前节点。
var deleteNode = function (node) {
node.val = node.next.val
// 当前节点的 next，指向当前节点的下一个节点的 next
node.next = node.next.next
};
面试 0204 分割链表
时间：2022-05-13
妈的，和预期结果不一样，迟迟没有提交，才发现符合预期的不止一个结果
var partition = function (head, x) {
let cur = head,
next = head;
while (next) {
if (next.val < x) {
[cur.val, next.val] = [next.val, cur.val]
cur = cur.next;
}
next = next.next;
}
return head;
};
面试 0205 链表求和
时间：2022-05-14
以为做过，结果不一样，这个反而简单一点，因为链表是反向存储数字的，不用翻转
var addTwoNumbers = function (l1, l2) {
let add = 0;
let prev = new ListNode(-1);
const head = prev;
while (l1 || l2) {
const x = l1 ? l1.val : 0;
const y = l2 ? l2.val : 0;
const res = x + y + add;
prev.next = new ListNode(res % 10);
add = Math.floor(res / 10);
l1 = l1 ? l1.next : l1;
l2 = l2 ? l2.next : l2;
prev = prev.next;
}
if (add == 1) prev.next = new ListNode(add);
return head.next;
};
812 最大三角形面积
时间：2022-05-15
复制粘贴，甚至都不想看
var largestTriangleArea = function (points) {
const n = points.length;
let ret = 0.0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
ret = Math.max(ret, triangleArea(points[i][0], points[i][1], points[j][0], points[j][1], points[k][0], points[k][1]));
}
}
}
return ret;
};
const triangleArea = (x1, y1, x2, y2, x3, y3) => {
return 0.5 * Math.abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2);
};
面试 0301 三合一
时间：2022-05-15
倒也简单，就是二维数组管理嘛，也不是很难
var TripleInOne = function (stackSize) {
this.stack = [];
this.size = stackSize;
};
/**
* @param {number} stackNum
* @param {number} value
* @return {void}
*/
TripleInOne.prototype.push = function (stackNum, value) {
if (!this.stack[stackNum]) {
this.stack[stackNum] = [];
}
if (this.stack[stackNum].length < this.size) {
this.stack[stackNum].push(value);
}
};
/**
* @param {number} stackNum
* @return {number}
*/
TripleInOne.prototype.pop = function (stackNum) {
if (!this.stack[stackNum]) return -1;
if (!this.stack[stackNum].length) return -1;
return this.stack[stackNum].pop();
};
/**
* @param {number} stackNum
* @return {number}
*/
TripleInOne.prototype.peek = function (stackNum) {
if (!this.stack[stackNum]) return -1;
if (!this.stack[stackNum].length) return -1;
return this.stack[stackNum][this.stack[stackNum].length - 1];
};
/**
* @param {number} stackNum
* @return {boolean}
*/
TripleInOne.prototype.isEmpty = function (stackNum) {
if (!this.stack[stackNum]) return true;
if (!this.stack[stackNum].length) return true;
return false;
};
面试 0302 栈的最小值
时间：2022-05-15
这题做过一模一样的，还行
*/
var MinStack = function () {
this.stack = [];
this.minStack = [];
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function (x) {
this.stack.push(x);
const len = this.minStack.length;
if (len == 0 || x <= this.minStack[len - 1]) this.minStack.push(x);
};
/**
* @return {void}
*/
MinStack.prototype.pop = function () {
const tmp = this.stack.pop();
if (tmp === this.getMin()) {
this.minStack.pop();
}
};
/**
* @return {number}
*/
MinStack.prototype.top = function () {
return this.stack[this.stack.length - 1];
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
return this.minStack[this.minStack.length - 1];
};
面试 0303 堆盘子
时间：2022-05-15
真是龙鸣的题目，也不知道想这种题目干嘛。
var StackOfPlates = function (cap) {
this.stack = [[]];
this.cur = 0;
this.size = cap;
};
/**
* @param {number} val
* @return {void}
*/
StackOfPlates.prototype.push = function (val) {
if (!this.size) return null;
if (this.stack[this.cur].length == this.size) {
this.stack[++this.cur] = [];
}
this.stack[this.cur].push(val);
};
/**
* @return {number}
*/
StackOfPlates.prototype.pop = function () {
const res = this.stack[this.cur].pop();
if (this.cur > 0 && this.stack[this.cur].length == 0) {
this.stack.pop();
--this.cur;
}
return res ?? -1;
};
/**
* @param {number} index
* @return {number}
*/
StackOfPlates.prototype.popAt = function (index) {
if (index > this.cur) return -1;
const res = this.stack[index].pop();
if (this.cur > 0 && this.stack[index].length == 0) {
this.stack.splice(index, 1);
--this.cur;
}
return res ?? -1;
};
