LeetCode Problems' Solutions
A Frontend Development Engineer Live in China.
You can find me in my Website and Email.
TypeScript 67 hrs 45 mins 🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟨⬜⬜⬜⬜⬜ 78.73 %
JSON 7 hrs 11 mins 🟩🟩⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜ 08.35 %
JavaScript 6 hrs 1 min 🟩🟩⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜ 07.00 %
Other 1 hr 5 mins 🟨⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜ 01.27 %
Bash 43 mins ⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜ 00.84 %
解题**：
从数组的中间元素开始，如果中间元素就是目标值直接返回。
如果目标值大于或者小于中间元素，则在数组大于或小于中间元素的那一半里寻找。
代码：
var guessNumber = function(n) {
let low = 1, high = n;
while (low <= high) {
const mid = Math.floor((high + low) / 2);
const res = guess(mid);
if (res === -1) {
high = mid - 1;
} else if (res === 1) {
low = mid + 1;
} else {
return mid;
}
}
};复杂度分析：
解题**：
利用分而治之的**：分、解、合
代码：
var guessNumber = function (n) {
const rec = (low, high) => {
const mid = Math.floor((low + high) / 2);
const res = guess(mid);
if (res === 0) {
return mid;
} else if (res === -1) {
return rec(low, mid - 1);
} else {
return rec(mid + 1, high);
}
};
return rec(1, n);
};复杂度分析：
解题**：
代码：
最小堆的类：
class MinHeap {
constructor() {
this.heap = [];
}
getParentIndex(i) {
return (i - 1) >> 1;
}
getLeftIndex(i) {
return 2 * i + 1;
}
getRightIndex(i) {
return 2 * i + 2;
}
swap(i1, i2) {
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
shiftUp(index) {
if ( index === 0) return;
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value) {
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
}
shiftDown(index) {
if (index > this.heap.length - 1) return;
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
if (this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value) {
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}
if (this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value) {
this.swap(rightIndex, index);
this.shiftDown(rightIndex);
}
}
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
pop() {
this.heap[0] = this.heap.pop();
this.shiftDown(0)
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}var topKFrequent = function(nums, k) {
const map = new Map();
const h = new MinHeap();
nums.forEach(num => {
map.set(num, map.has(num) ? map.get(num) + 1 : 1)
});
map.forEach((value, key) => {
h.insert({value, key});
if (h.size() > k) {
h.pop();
}
});
return h.heap.map(a => a.key);
};复杂度分析：
解题**：
新链表的下一个节点一定是K个链表头中的最小节点，所以考虑选择使用最小堆
步骤：
代码：
最小堆的类：
class MinHeap {
constructor() {
this.heap = [];
}
getParentIndex(i) {
return (i - 1) >> 1;
}
getLeftIndex(i) {
return 2 * i + 1;
}
getRightIndex(i) {
return 2 * i + 2;
}
swap(i1, i2) {
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
shiftUp(index) {
if ( index === 0) return;
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val) {
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
}
shiftDown(index) {
if (index > this.heap.length - 1) return;
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
if (this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val) {
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}
if (this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val) {
this.swap(rightIndex, index);
this.shiftDown(rightIndex);
}
}
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
pop() {
if (this.size() === 1) return this.heap.shift();
const top = this.heap[0];
this.heap[0] = this.heap.pop();
this.shiftDown(0);
return top;
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}var mergeKLists = function(lists) {
const h = new MinHeap();
const res = new ListNode(null);
let p = res;
lists.forEach(l => {
!!l && h.insert(l);
})
while (h.size()) {
const node = h.pop();
p.next = node;
p = p.next;
if (node.next) {
h.insert(node.next)
}
}
return res.next;
};复杂度分析：
解题**：
如果是左括号就入栈，如果是右括号就看看栈顶元素是否与当前的匹配，匹配就出桟，不匹配的话直接返回。
全部遍历完，如果栈空了，就代表都匹配成功了。
代码：
var isValid = function(s) {
const stack = [], map = {
")": "(",
"]": "[",
"}": "{",
};
for (str of s) {
if (str => ["(", "[", "{"].includes(str)) {
stack.push(str)
} else {
if (stack[stack.length - 1] === map[str]) {
stack.pop();
} else {
return false;
}
}
}
return stack.length === 0;
};复杂度分析：
解题**：
代码：
复杂度分析：
解题**：
代码：
var letterCombinations = function (digits) {
if (digits.length == 0) return [];
const map = new Map(),
res = [];
// 初始化字典映射
map.set("2", "abc");
map.set("3", "def");
map.set("4", "ghi");
map.set("5", "jkl");
map.set("6", "mno");
map.set("7", "pqrs");
map.set("8", "tuv");
map.set("9", "wxyz");
const dfs = (curStr, i) => {
// 指针越界，递归的出口
if (i > digits.length - 1) {
// 将解推入res
res.push(curStr);
// 结束当前递归分支，进入另一个递归分支
return;
}
const letters = map.get(digits[i]);
// 不同的字母选择代表不同的递归分支
for (const l of letters) {
dfs(curStr + l, i + 1);
}
};
dfs("", 0);
return res;
};复杂度分析：
解题**：
维护一个队列。
起初让空字符串入列，让当前层的字符串逐个出列，出列的字符串，会构建它下一层的新字母串，并入列。
一层层地，考察到数字串的最末位，就到了最底一层，此时队列中存的是所有构建完毕的字母串，返回 queue 即可。
和传统的BFS不同，这里控制了层序遍历的深度，等于 digits 的长度，而不是 while(queue.length){.. 那样让所有的节点入列出列，最后还会剩下最后一层节点，留在 queue 中返回。
代码：
const letterCombinations = (digits) => {
if (digits.length == 0) return [];
const map = {
2: "abc",
3: "def",
4: "ghi",
5: "jkl",
6: "mno",
7: "pqrs",
8: "tuv",
9: "wxyz",
};
const queue = [];
queue.push("");
for (let i = 0; i < digits.length; i++) {
// bfs的层数，即digits的长度
const levelSize = queue.length; // 当前层的节点个数
for (let j = 0; j < levelSize; j++) {
// 逐个让当前层的节点出列
const curStr = queue.shift(); // 出列
const letters = map[digits[i]];
for (const l of letters) {
queue.push(curStr + l); // 生成新的字母串入列
}
}
}
return queue; // 队列中全是最后一层生成的字母串
};复杂度分析：
解题**：
这题主要就是理解问题，理解了问题的话就不难了：就是一个队列的题。超过3000ms的队列前面的元素给出桟，最后返回队列的数量即为当前的请求数。
代码：
var RecentCounter = function() {
this.q = [];
};
/**
* @param {number} t
* @return {number}
*/
RecentCounter.prototype.ping = function(t) {
this.q.push(t);
while (this.q[0] < t - 3000) {
this.q.shift();
}
return this.q.length;
};
/**
* Your RecentCounter object will be instantiated and called as such:
* var obj = new RecentCounter()
* var param_1 = obj.ping(t)
*/复杂度分析：
解题**：
用两个指针，一个上一个节点，一个当前节点。
遍历列表，断开当前节点的next指向，并用一个临时变量储存起来。
当前节点的next指向改为指向上一个节点。
继续往下移，直到当前节点不存在，返回上一个节点则为结果。
代码：
var reverseList = function(head) {
let prev = null;
let curr = head;
while(curr) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
};复杂度分析：
解题**：
递归的两个条件：
head.next.next = head具体过程可参看动画演示+多种解法 206. 反转链表 - 反转链表 - 力扣（LeetCode），里面关于递归的图解幻灯片，记录了函数的整个递归过程，更容易理解。
代码：
var reverseList = function(head) {
if(!head || !head.next) return head;
const reverseNode = reverseList(head.next);
// 改变当前节点的指向
head.next.next = head;
// 防止链表循环，需要将head.next设置为空
head.next = null;
return reverseNode;
};复杂度分析：
解题**：
把题目的规则转换为状态，形成这样一张图：
所有的字符串刚进来都是状态 0 的位置，接下来的字符串逐个拼接会走到不同的状态，最终走到红色位置即为true，否则为false。
代码：
var isNumber = function (s) {
/**
* blank 空格
* sign + -
* digit 0-9
* e e
* . .
*/
const graph = {
0: { blank: 0, sign: 1, ".": 2, digit: 6 },
1: { digit: 6, ".": 2 },
2: { digit: 3 },
3: { digit: 3, e: 4 },
4: { digit: 5, sign: 7 },
5: { digit: 5 },
6: { digit: 6, ".": 3, e: 4 },
7: { digit: 5 },
};
let state = 0;
for (let c of s.trim()) {
if (c >= '0' && c <= '9') {
c = 'digit';
} else if (c === ' ') {
c = 'blank';
} else if (c === '+' || c === '-') {
c = 'sign';
}
// 如果得到的当前节点为 undefined 说明不在可用字符范围，直接返回false
if (graph[state] === undefined) return false;
state = graph[state][c];
// 如果得到的状态为 undefined 说明不在可用字符范围，也直接返回false
if (state === undefined) return false;
}
// 走到红色节点就为true
if ([3, 5, 6].includes(state)) {
return true;
}
return false;
};复杂度分析：
此题与94. 二叉树的中序遍历和145. 二叉树的后序遍历类似，解题思路基本一致，只是访问节点的先后顺序不同，因此放一起说明。
解题**：
前序遍历指的是依次访问根节点、左节点、右节点。因此按照顺序访问，并在左右节点递归调用就可以了。
递归终止的条件为碰到空节点。
代码：
前序遍历
var preorderTraversal = function(root) {
// 递归终止条件
if (root === null) {
return [];
}
const res = [];
// 先访问根节点
res.push(root.val);
// 再访问左节点
if (root.left) {
const leftRes = preorderTraversal(root.left);
leftRes.forEach(val => res.push(val));
}
// 最后访问右节点
if (root.right) {
const rightRes = preorderTraversal(root.right);
rightRes.forEach(val => res.push(val));
}
return res;
};中序遍历
var inorderTraversal = function(root) {
// 递归终止条件
if (root === null) {
return [];
}
const res = [];
// 先访问左节点
if (root.left) {
const leftRes = inorderTraversal(root.left);
leftRes.forEach(val => res.push(val));
}
// 再访问根节点
res.push(root.val);
// 最后访问右节点
if (root.right) {
const rightRes = inorderTraversal(root.right);
rightRes.forEach(val => res.push(val));
}
return res;
};后序遍历
var postorderTraversal = function(root) {
// 递归终止条件
if (root === null) {
return [];
}
const res = [];
// 先访问左节点
if (root.left) {
const leftRes = postorderTraversal(root.left);
leftRes.forEach(val => res.push(val));
}
// 再访问右节点
if (root.right) {
const rightRes = postorderTraversal(root.right);
rightRes.forEach(val => res.push(val));
}
// 最后访问根节点
res.push(root.val);
return res;
};复杂度分析：
解题**：
完全可以利用栈的特性来模拟访问，先入栈根节点，出栈访问，再入栈右节点与左节点，按照顺序，出栈左节点和右节点即可。
代码：
前序遍历
var preorderTraversal = function (root) {
const res = [];
const stack = [];
if (root) stack.push(root);
while (stack.length > 0) {
const node = stack.pop();
res.push(node.val);
if (node.right) {
stack.push(node.right);
}
if (node.left) {
stack.push(node.left);
}
}
return res;
};中序遍历
借助一个指针来指向当前节点，先一直遍历到左子节点，进行入栈
var inorderTraversal = function(root) {
if (!root) return [];
const res = [];
const stack = [];
let curr = root;
while (stack.length || curr) {
while (curr) {
stack.push(curr);
curr = curr.left;
}
const node = stack.pop();
res.push(node.val)
if (node.right) {
curr = node.right
}
}
return res;
};后序遍历
后序遍历我们通过前序遍历来转换一下：前序遍历是根左右，把它变成根右左，然后反过来就是左右根，也就是后序遍历的遍历顺序。
var postorderTraversal = function(root) {
if (!root) return [];
const res = [];
const stack = [root];
while (stack.length) {
const node = stack.pop();
// 虽然我们要先遍历的是右子节点，但是因为栈的特性，所以要先入栈左子节点
if (node.left) {
stack.push(node.left);
}
res.push(node.val);
if (node.right) {
stack.push(node.right);
}
}
// 把结果反过来就是后序遍历的输出了
return res.reverse();
};复杂度分析：
其实和递归都是一样的。两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同。
解题**：
Morris的通用解法过程：
Morris 的整体思路就是将 以某个根结点开始，找到它左子树的最右侧节点之后与这个根结点进行连接
我们可以从 图2 看到，如果这么连接之后，cur 这个指针是可以完整的从一个节点顺着下一个节点遍历，将整棵树遍历完毕，直到 7 这个节点右侧没有指向。
var preorderTraversal = function(root) {
if (root == null) {
return;
}
let cur1 = root;//当前开始遍历的节点
let cur2 = null;//记录当前结点的左子树
while (cur1 != null) {
cur2 = cur1.left;
if (cur2 != null) {
while (cur2.right != null && cur2.right != cur1) {//找到当前左子树的最右侧节点，且这个节点应该在指向根结点之前，否则整个节点又回到了根结点。
cur2 = cur2.right;
}
if (cur2.right == null) {//这个时候如果最右侧这个节点的右指针没有指向根结点，创建连接然后往下一个左子树的根结点进行连接操作。
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {//当左子树的最右侧节点有指向根结点，此时说明我们已经回到了根结点并重复了之前的操作，同时在回到根结点的时候我们应该已经处理完 左子树的最右侧节点 了，把路断开。
cur2.right = null;
}
}
cur1 = cur1.right;//一直往右边走，参考图
}
}代码：
前序遍历
var preorderTraversal = function(root) {
if (!root) return;
const res = [];
let cur1 = root; // 当前开始遍历的节点
let cur2; // 记录当前结点的左子树
while(cur1) {
cur2 = cur1.left;
if(cur2) {
// 找到当前左子树的最右侧节点，
// 且这个节点应该在指向根结点之前，否则整个节点又回到了根结点。
while (cur2.right && cur2.right !== cur1) {
cur2 = cur2.right;
}
// 这个时候如果最右侧这个节点的右指针没有指向根结点，
// 创建连接然后往下一个左子树的根结点进行连接操作。
if (!cur2.right) {
cur2.right = cur1;
res.push(cur1.val);
cur1 = cur1.left;
continue;
} else { // 当左子树的最右侧节点有指向根结点，
// 此时说明我们已经回到了根结点并重复了之前的操作，
// 同时在回到根结点的时候我们应该已经处理完 左子树的最右侧节点了，把路断开。
cur2.right = null;
}
} else {
res.push(cur1.val);
}
// 一直往右边走
cur1 = cur1.right;
}
};中序遍历
从最左侧开始顺着右节点打印。也就是在将cu1切换到上层节点的时候。
var inorderTraversal = function(root) {
if (!root) return [];
const res = [];
let cur1 = root;
let cur2;
while(cur1) {
cur2 = cur1.left;
//构建连接线
if(cur2) {
while (cur2.right && cur2.right !== cur1) {
cur2 = cur2.right;
}
if (!cur2.right) {
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
}
}
res.push(cur1.val);
cur1 = cur1.right;
}
return res;
};后序遍历
当我们到达最左侧，也就是左边连线已经创建完毕了。
打印 4
打印 5 2
打印 6
打印 7 3 1
我们将一个节点的连续右节点当成一个单链表来看待。
当我们返回上层之后，也就是将连线断开的时候，打印下层的单链表。
比如返回到 ２，此时打印 ４
比如返回到 １，此时打印 ５ ２
比如返回到 ３，此时打印 ６
那么我们只需要将这个单链表逆序打印就行了
这里不应该打印当前层，而是下一层，否则根结点会先与右边打印。
var postorderTraversal = function(root) {
if (!root) return [];
const res = [];
// 翻转单链表
const postMorrisReverseList = (root) => {
let cur = root;
let pre;
while (cur) {
let next = cur.right;
cur.right = pre;
pre = cur;
cur = next;
}
return pre;
};
// 打印函数
const postMorrisPrint = (root) => {
const reverseList = postMorrisReverseList(root);
let cur = reverseList;
while (cur) {
res.push(cur.val);
cur = cur.right;
}
postMorrisReverseList(reverseList);
};
let cur1 = root; // 遍历树的指针变量
let cur2; // 当前子树的最右节点
while(cur1) {
cur2 = cur1.left;
if(cur2) {
while (cur2.right && cur2.right !== cur1) {
cur2 = cur2.right;
}
if (!cur2.right) {
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
postMorrisPrint(cur1.left);
}
}
cur1 = cur1.right;
}
postMorrisPrint(root);
return res;
};复杂度分析：
解题**：
遍历整个链表，将当前节点保存在哈希表中。
如果哈希表中已存在，则代表回到了之前已经遍历过的节点，也就是有环；反之保存在哈希表中，继续遍历下去。
代码：
var detectCycle = function(head) {
const visited = new Set();
while (head) {
if (visited.has(head)) {
return head;
}
visited.add(head);
head = head.next;
}
return null;
};复杂度分析：
解题**：
建议看这个：环形链表 II（双指针法，清晰图解） - 环形链表 II - 力扣（LeetCode）
关键点就是：
代码：
var detectCycle = function(head) {
if (head === null) return null;
let slow = head, fast = head;
while (fast !== null) {
// 慢指针每次走 1步
slow = slow.next;
if (fast.next === null) return null;
// 快指针每次走2步
fast = fast.next.next;
// 快慢指针相遇
if (fast === slow) {
// 这时把快指针重新指向头部节点
let ptr = head;
// 当快慢指针相遇的时候，就是入环节点的位置
while (ptr !== slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
};复杂度分析：
解题**：
在广度优先遍历过程中，如果遇到叶子节点，停止遍历，返回节点层级。
var minDepth = function(root) {
if (!root) return 0;
// 广度优先需要使用一个队列，同时额外再维护一个深度
const q = [[root, 1]];
while (q.length) {
const [n, deepth] = q.shift();
if (!n.left && !n.right) return deepth;
// console.log(n.val, deepth);
if (n.left) q.push([n.left, deepth + 1]);
if (n.right) q.push([n.right, deepth + 1]);
}
};复杂度分析：
26_删除排序数组中的重复项
42_接雨水
121_买卖股票的最佳时机
209_长度最小的子数组
141_环形链表
202_快乐数
876_链表的中间结点
##字符串操作
6_Z字形变换
14_最长公共前缀
736_划分字母区间
7_整数反转
8_字符串转换整数
9_回文数
43_字符串相乘
172_阶乘后的零
258_各位相加
54_螺旋矩阵
73_矩阵置零
945_使数组唯一的最小增量
32_最长有效括号
155_最小栈
224_基本计算器
316_去除重复字母
215_数组中的第K个最大元素
347_前K个高频元素
101_对称二叉树
104_二叉树的最大深度
226_翻转二叉树
236_二叉树的最近公共祖先
23_合并K个排序链表
33_搜索旋转排序数组
34_在排序数组中查找元素的第一个和最后一个位置
5_最长回文子串
53_最大子序和
62_不同路径
64_最小路径和
70_爬楼梯
118_杨辉三角
300_最长上升子序列
746_使用最小花费爬楼梯
1277_统计全为1的正方形子矩阵
94_二叉树的中序遍历
102_二叉树的层次遍历
110_平衡二叉树
144_二叉树的前序遍历
145_二叉树的后序遍历
98_验证二叉搜索树
450_删除二叉搜索树中的节点
701_二叉搜索树中的插入操作
解题**：
代码：
复杂度分析：
解题思路：
代码：
var addTwoNumbers = function (l1, l2) {
if (!l1 || !l2) {
return l1 ? l1 : l2;
}
let x = (y = carry = sum = 0);
// res 是一个哨兵节点，用来返回一个新链表
let res = (tmp = new ListNode());
// 遍历列表 l1 和 l2 直至到达它们的尾端。
// 还必须检查 carry = 1carry=1 是否成立，
// 如果成立，则向返回列表追加一个含有数字 11 的新结点。
while (l1 || l2 || carry) {
tmp.next = new ListNode();
x = l1 ? l1.val : 0;
y = l2 ? l2.val : 0;
sum = x + y + carry;
// 更新进位的值
carry = Math.floor(sum / 10);
// 创建一个数值为 (sum mod 10) 的新结点，并将其设置为当前结点的下一个结点
tmp.next.val = sum % 10;
// 然后将当前结点前进到下一个结点。
tmp = tmp.next;
// 将节点继续前进到下一个结点。
l1 = l1 ? l1.next : l1;
l2 = l2 ? l2.next : l2;
}
return res.next;
};复杂度分析：
解题**：
因为集合天然的去重复性，所以把数组1中的元素全部放在集合中。
遍历数组2，看看集合中是否存在相应元素，存在的话就保存起来，并从集合中移除，这样下次再遍历到相同元素的话就不会再次添加。
代码：
var intersection = function(nums1, nums2) {
const set = new Set();
nums1.forEach(x => set.add(x));
const res = [];
nums2.forEach(y => {
if (set.has(y)) {
res.push(y);
set.delete(y);
}
})
return res;
};复杂度分析：
代码：
var intersection = function(nums1, nums2) {
let tmp = {};
return nums1.filter((item) => {
if(!tmp[item] && nums2.includes(item)){
tmp[item] = true;
return nums2.includes(item)
}
})
};代码：
var intersection = function(nums1, nums2) {
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
let i = 0, j = 0;
const res = new Set();
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
res.add(nums1[i]);
i++;
j++;
}
}
return [...res];
};复杂度分析：
两层循环，遍历每个元素，查找是否存在一个值与之相加为 target 的目标元素
var twoSum = function(nums, target) {
const len = nums.length;
for(let i = 0; i < len - 1; i++) {
for(let j = i + 1; j < len; j++) {
if (nums[i] + nums[j] === target) {
return [i, j]
}
}
}
};复杂度分析：
每次循环都要遍历剩下的数组元素
没有占用额外的空间
优化方案：
已经遍历过的元素，可以不用再遍历，利用哈希表缓存起来，空间换时间。
第一次循环把所有值和相应的index存到哈希表中，然后第二循环的时候，找到之前缓存的哈希表中对应的值。
var twoSum = function(nums, target) {
const len = nums.length, map = {};
for(let i = 0; i < len; i++) {
map[nums[i]] = i;
}
for(let i = 0; i < len; i++) {
const complement = target - nums[i];
if (map[complement] && map[complement] !== i) {
return [i, map[complement]];
}
}
};复杂度分析：
在进行哈希表缓存的时候，直接就检查现有哈希表中有没有目标值。
var twoSum = function(nums, target) {
const len = nums.length, map = {};
for(let i = 0; i < len; i++) {
const result = map[nums[i]];
// 第一个数字的index为0时，其实是一个假值，需要额外处理下
if (result === 0 || result) {
return [result, i];
}
map[target - nums[i]] = i;
}
};复杂度分析：
只遍历了一次 O(n)，后面都是查找之前遍历过的元素 O(1)。
所需的额外空间取决于哈希表中存储的元素数量，最多需要存储 n 个元素。
解题**：
遍历整个链表，将当前节点保存在哈希表中。
如果哈希表中已存在，则代表回到了之前已经遍历过的节点，也就是有环；反之保存在哈希表中，继续遍历下去。
代码：
var hasCycle = function(head) {
if (!head) return false;
let curr = head.next;
const map = new Map();
while(curr) {
if (map.has(curr)) {
return true;
}
map.set(curr, true);
curr = curr.next;
}
return false;
};复杂度分析：
解题**：
快指针每次走两步，慢指针每次走一步。
代码：
var hasCycle = function(head) {
if (!head || !head.next) return false;
let slow = head, fast = head.next;
while (fast) {
if (slow.val === fast.val) return true;
if (!fast.next || !fast.next.next) return false;
fast = fast.next.next;
slow = slow.next;
}
return false;
};复杂度分析：
解题**：
先循环判断头节点，然后再循环判断后面的节点。
头节点遍历完后，记得看下链表是否为空，空就直接返回。
代码：
var removeElements = function(head, val) {
// 把所有符合条件的head全部删除
while (head && head.val !== null && head.val === val) {
let delNode = head;
head = head.next;
delNode.next = null;
}
// 如果此时链表已经为空，直接返回
if (head === null) {
return null
}
// 处理中间部分
let prev = head;
while (prev.next !== null) {
if (prev.next.val === val) {
const delNode = prev.next;
prev.next = prev.next.next;
delNode.next = null;
} else {
prev = prev.next
}
}
return head;
};解题**：
优化上面的一种解法，添加一个虚拟头节点，这样后面的链表就可以用统一的逻辑来处理了。
代码：
var removeElements = function(head, val) {
// 头部增加一个虚拟头节点，也叫哨兵节点
let dummyHead = new ListNode(-1)
dummyHead.next = head;
let prev = dummyHead;
while (prev.next !== null) {
if (prev.next.val === val) {
prev.next = prev.next.next;
} else {
prev = prev.next
}
}
return dummyHead.next;
};解题**：
链表是一种天然可递归的数据结构，用递归也就更简洁的可以解决这个方法。
代码：
var removeElements = function(head, val) {
if (head === null) {
return null;
}
head.next = removeElements(head.next, val);
return head.val === val ? head.next : head;
};复杂度分析：
解题**：
最简单就是以下这种递归解法了，但是会爆栈的可能，以及leetcode也提示超时了：
var tribonacci = function(n) {
if (n === 0) return 0;
if (n === 1 || n === 2) return 1;
return tribonacci(n - 3) + tribonacci(n - 2) + tribonacci(n - 1)
};优化的方案还是拿空间换时间，把每次计算的斐波那契数给缓存起来。
var tribonacci = function(n) {
const map = [0, 1, 1];
const recursion = (n) => {
if (map[n] !== undefined) {
return map[n];
}
map[n] = recursion(n - 1) + recursion(n - 2) + recursion(n - 3);
return map[n];
};
return recursion(n);
};复杂度分析：
解题**：
上面的方法性能是最优的，但是空间比较浪费，利用动态规划来只存储最后计算的三个斐波那契数。
代码：
var tribonacci = function(n) {
const ans = [0, 1, 1];
for (let i = 3; i <= n; i++) {
ans[i] = ans[i - 3] + ans[i - 2] + ans[i - 1];
}
return ans[n];
};复杂度分析：
解题**：
深度优先遍历图（这边用广度优先遍历也可以）。
构造一个 Map， key为当前遍历的节点，value则为克隆的节点。
遍历节点的neighbors时，添加进克隆节点里即可。
代码：
var cloneGraph = function(node) {
if (!node) return;
const visited = new Map();
const dfs = (n) => {
const nCopy = new Node(n.val);
visited.set(n, nCopy);
(n.neighbors || []).forEach(ne => {
if(!visited.has(ne)) {
dfs(ne);
}
nCopy.neighbors.push(visited.get(ne));
})
};
dfs(node);
return visited.get(node);
};复杂度分析：
解题**：
代码：
复杂度分析：
var isAnagram = function(s, t) {
const map1 = new Map();
const map2 = new Map();
function countNum(str, map) {
for (let i = 0; i < str.length; i++) {
const current = str[i]
const value = map.get(current);
if (value) {
map.set(current, value + 1)
} else {
map.set(current, 1)
}
}
}
countNum(s, map1);
countNum(t, map2);
if (map1.size !== map2.size || (
[...map1.keys()].sort().join("") !== [...map2.keys()].sort().join("")
)) {
return false;
}
for(let [key, value] of map1) {
if (value !== map2.get(key)) {
return false;
}
}
return true;
};解题**：
主要是得出这个公式：f(x)=f(x−1)+f(x−2)，因为每次只可能跨1级或2级。
边界条件是0级的时候，步数为0；1级的时候，步数为1。以这两个边界条件向后推导，比如知道f(0)和f(1)，就能得出f(2)，而知道了f(1)和f(2)就能得到f(3)。
这里可以用「滚动数组**」，用一个数组进行不断滚动来得出最后的结果。
代码：
var climbStairs = function(n) {
let p = 0, q = 0, r = 1;
for (let i = 1; i <= n; i++) {
p = q;
q = r;
r = p + q;
}
return r;
};复杂度分析：
解题**：
看知乎的这个帖子：如何理解汉诺塔的递归？。
主要是总结出递归的这个函数，其实自己一步步走一遍的话，还是能明白的。
重点**是理解开始柱，中转柱，目标柱这三个概念，具体还是看上面的帖子吧，不再赘述。
代码：
var hanota = function(A, B, C) {
const move = (n, from, buffer, to) => {
if (n === 1) {
console.log(A, '--->', C);
to.push(from.pop());
} else {
move(n - 1, from, to, buffer);
console.log(A, '--->', C);
move(1, from, buffer, to);
move(n - 1, buffer, from, to);
}
}
move(A.length, A, B, C);
};复杂度分析：
解题**：
代码：
var reverse = function(x) {
let result = 0;
while(x !== 0) {
result = result * 10 + x % 10;
x = (x / 10) | 0;
}
return (result | 0) === result ? result : 0;
};复杂度分析：
解题**：
代码：
var isSymmetric = function(root) {
if (!root) return true;
const isMirror = (l, r) => {
if (!l && !r) return true;
if (l && r && (l.val === r.val) &&
isMirror(l.left, r.right) &&
isMirror(l.right, r.left)
) {
return true;
}
return false;
}
return isMirror(root.left, root.right);
};复杂度分析：
解题**：
代码：
var invertTree = function(root) {
if (!root) return null;
return {
val: root.val,
left: invertTree(root.right),
right: invertTree(root.left)
};
};复杂度分析：
解题**：
利用回溯法，不断地往前一个结果的尾部追加左括号或者右括号。
代码：
var generateParenthesis = function(n) {
const arr = [];
function generate(left, right, str) {
// 递归终结条件：n 都用完了
if (left === n && right ===n) {
arr.push(str);
return;
}
// 如果左括号没用完（第一肯定先使用左括号），就继续递归
if(left < n) {
generate(left + 1, right, str + '(');
}
// 如果右括号没用完（右括号肯定比左括号少，且有括号没用完），就继续递归
if(right < left) {
generate(left, right + 1, str + ')')
}
}
generate(0, 0, '');
return arr;
};复杂度分析：
自己还没实现，后面补
参考sl1673495/leetcode-javascript#31
解题**：
利用广度优先遍历节点，同时记录当前的层数。
利用一个数组，保存层数索引相对的节点值。
代码：
var levelOrder = function(root) {
if (!root) return [];
const res = [];
const q = [[root, 0]];
while (q.length) {
const [n, level] = q.shift();
if (res[level]) {
res[level].push(n.val)
} else {
res[level] = [n.val];
}
if (n.left) q.push([n.left, level + 1]);
if (n.right) q.push([n.right, level + 1]);
}
return res;
};复杂度分析：
解题**：
遍历一遍，得出相应字母的出现频率，再遍历一遍，如果频率为1，则返回当前位置。
代码：
var firstUniqChar = function(s) {
const startIndex = 'a'.charCodeAt();
// 创建一个长度为26的字母表，初始频率都为0
const freq = Array.from({length: 26}, x => 0);
// 与a做比较得到索引位置，如果重复则频率+1
for (let i = 0; i < s.length; i++) {
freq[s.charCodeAt(i) - startIndex] ++;
}
// 最后再扫一遍s，如果在频率表中的频率为1，则代表只出现过一次
for (let i = 0; i < s.length; i++) {
if (freq[s.charCodeAt(i) - startIndex] === 1) {
return i;
}
}
return -1;
};复杂度分析：
解题**：
代码：
最小堆的类：
class MinHeap {
constructor() {
this.heap = [];
}
getParentIndex(i) {
return (i - 1) >> 1;
}
getLeftIndex(i) {
return 2 * i + 1;
}
getRightIndex(i) {
return 2 * i + 2;
}
swap(i1, i2) {
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
shiftUp(index) {
if ( index === 0) return;
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex] > this.heap[index]) {
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
}
shiftDown(index) {
if (index > this.heap.length - 1) return;
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
if (this.heap[leftIndex] < this.heap[index]) {
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}
if (this.heap[rightIndex] < this.heap[index]) {
this.swap(rightIndex, index);
this.shiftDown(rightIndex);
}
}
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
pop() {
this.heap[0] = this.heap.pop();
this.shiftDown(0)
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}var findKthLargest = function(nums, k) {
const h = new MinHeap();
nums.forEach(num => {
h.insert(num);
if (h.size() > k) {
h.pop();
}
});
return h.peek();
};复杂度分析：
解题思路：
建立一个对应的数组，来记录节点对应的下标信息。倒数第N个节点，也就是 正数的数组长度 - n。将这个节点的前一个节点的next指向下一个节点即可。
代码：
let removeNthFromEnd = function (head, n) {
let node = head;
let nodes = [];
do {
nodes.push(node);
node = node.next;
} while (node)
const len = nodes.length;
const index = len - n;
const targetNode = nodes[index];
const prevNode = nodes[index - 1];
if (prevNode) {
prevNode.next = targetNode.next;
}
const tempNext = targetNode.next;
targetNode.next = null;
if (targetNode === head) {
return tempNext;
}
return head;
}复杂度分析：
解题思路：
使用 2 个指针：fast 快指针提前走 n+1 步；slow 指针指向当前距离 fast 倒数第 n 个节点， 初始为 head。然后， fast 、 slow 同步向前走，直到 fast.next 为 null。
此时，fast 为最后一个节点，slow 就是倒数第 n+1 个节点，此时问题就变更为删除链表中的 slow 的后继节点。
还需要利用哨兵节点来解决当链表的长度就为 n 的时候无法前进到第 n+1 个节点的边界情况。
代码：
let removeNthFromEnd = function (head, n) {
// 添加哨兵节点
let dummy = new ListNode(0);
dummy.next = head;
let fast = dummy, slow = dummy;
// 快指针先走 n+1 步
while(n--) {
fast = fast.next;
}
// 快慢指针同时走
// 快指针走到最后的时候，慢指针的位置就是第N个节点的前一个节点的位置
while(fast && fast.next) {
fast = fast.next;
slow = slow.next;
}
// 删除这个节点
slow.next = slow.next.next;
return dummy.next;
}复杂度分析：
解题**：
代码：
复杂度分析：
由于数组不可变的，用线段树其实相对更复杂，可以有更简单的解法。
解题**：
初始时，左右指针分别指向数组的左右两端。
容纳的水量是由（两个指针指向的数字中较小值 * 指针之间）的距离决定的。因此，我们移动数字较小的那个指针，一直到2个指针重合。
代码：
var maxArea = function(height) {
let ans = 0, L = 0, R = height.length - 1;
while(L <= R) {
const now = Math.min(height[L], height[R]) * (R - L);
ans = Math.max(ans, now);
height[L] > height[R] ? R-- : L++ ;
}
return ans
};复杂度分析：
解题**：
遇到不同于val的项，就将其直接覆盖到nums数组中，并记一次累加值，当遍历完之后，所有不同于val的项就都放到nums数组的前面了，而这个累加值就是这个前面数组的长度。
代码：
var removeElement = (nums, val) => {
let count= 0
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== val) {
nums[count] = nums[i];
count++;
}
}
return count;
}复杂度分析：
解题**：
左指针在数组开始的位置，右指针在数组结尾的位置。当左指针的项等于val的时候，把右指针的项给拿过来，同时右指针往左移一位；而当等于的时候，左指针往右移一位。当两个指针相遇的时候，左指针的位置就是所有不等于val项的数组的长度。
代码：
var removeElement = function(nums, val) {
let L = 0, R = nums.length - 1;
while (L <= R) {
if (nums[L] === val) {
nums[L] = nums[R];
R--;
} else {
L++;
}
}
return L;
};遇到和val相同的项就直接用splice删除，后面的项就都会往前移一位。
代码：
var removeElement = function(nums, val) {
for (let i = 0; i < nums.length ; i++) {
if (nums[i] === val) {
nums.splice(i, 1);
// 指针 i 要 -1，新项需重新判定，不然会漏掉
i--;
}
}
return nums.length;
};为了避免遍历时执行多遍计算数组长度的操作，影响效率,，建议在循环开始以变量的形式缓存下数组长度，若在循环内部有可能改变数组长度，请务必慎重处理，避免数组越界。因此这里会改变数组长度的做法，是有危险的，不推荐。
另一种写法：
只要数组中还存在和val相同的项，就删除。
var removeElement = (nums, val) => {
while (nums.indexOf(val) !== -1) {
nums.splice(nums.indexOf(val),1)
}
return nums.length
}复杂度分析：
时间复杂度：O(n)
这几种方法都需要遍历一次数组，因此时间复杂度都是O(n)
空间复杂度：O(1)
没有占用额外的空间
解题**：
利用一个哈希函数，将对应位置的树两两交换，这里的哈希函数其实就是当前长度-1再减去当前的索引，就是相应反转后的位置。
代码：
var reverseString = function(s) {
const len = s.length;
const halfLen = Math.round(len/2);
// 只用遍历前一半数组
for (let i = 0; i < halfLen; i++) {
// 两两交换
[s[i], s[len - 1 -i]] = [s[len - 1 -i], s[i]];
}
return s;
};复杂度分析：
解题**：
遍历nums1，存到哈希表中，value为出现的次数。
遍历nums2，如果哈希表中存在，就把结果存起来，同时哈希表中出现次数需要减1，如果此时次数为0了，就移除这个key。
代码：
var intersect = function(nums1, nums2) {
const map = new Map();
nums1.forEach(x => {
if (map.has(x)) {
map.set(x, map.get(x) + 1);
} else {
map.set(x, 1);
}
});
const res = [];
nums2.forEach(y => {
if (map.has(y)) {
res.push(y);
map.set(y, map.get(y) - 1);
if(map.get(y) === 0) {
map.delete(y);
}
}
});
return res;
};复杂度分析：
代码：
const intersect = (nums1, nums2) => {
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b); // 先排序，使得重复的元素相邻出现
const res = [];
let p1 = 0; // 两个指针
let p2 = 0;
while (p1 < nums1.length && p2 < nums2.length) { // 用&& 因为有一个越界了就不能找交集
if (nums1[p1] > nums2[p2]) { // p1指向的数大，移动p2，期待遇到一样大的
p2++;
} else if (nums1[p1] < nums2[p2]) { // 类似
p1++;
} else { // 遇到相同的，推入res数组，两个指针同时移动考察下一个
res.push(nums1[p1]);
p1++;
p2++;
}
}
return res;
};如果给定的数组已经排好序呢？你将如何优化你的算法？
使用两个指针遍历两个数组，也就是方法二
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
使用方法一的哈希表解法更优
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
因为内存有限，所以无法存在哈希表中，所以使用双指针遍历。
但是方法二中需要改造，一般说排序算法都是针对于内部排序，一旦涉及到跟磁盘打交道（外部排序），则需要特殊的考虑。归并排序是天然适合外部排序的算法，可以将分割后的子数组写到单个文件中，归并时将小文件合并为更大的文件。当两个数组均排序完成生成两个大文件后，即可使用双指针遍历两个文件，如此可以使空间复杂度最低。
解题**：
这道题如果使用暴力求解法，也就是三重循环来枚举，首先时间复杂度是O(N^3)，还得使用哈希表来进行去重，得到最终的一个不重复的三元数组，时间复杂度与空间复杂度都非常高。
可以通过先排序，再用三重循环，来保证循环的元素不重复。
同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。举个例子，如果排完序的数组为
代码：
[0, 1, 2, 2, 2, 3]
^ ^ ^当枚举的第一个三元数组是 (0, 1, 2)，后面一次枚举依旧是 (0, 1, 2)，因此要将第三重循环跳到一个完全不同的元素，即跳过2也就是最后一个元素3。
用暴力法试一下：
var threeSum = function (nums) {
nums = nums.sort((a, b) => a - b);
const len = nums.length,
result = [];
const check = (i, j, k) => nums[i] + nums[j] + nums[k] === 0;
for (let i = 0; i < len - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
if (nums[i] === 0 && nums[i + 1] === 0 && nums[i + 2] === 0) {
result.push([0, 0, 0]);
break;
}
for (let j = i + 1; j < len - 1; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) {
continue;
}
for (let k = j + 1; k < len; k++) {
if (k > j + 1 && nums[k] === nums[k - 1]) {
continue;
}
check(i, j, k) && result.push([nums[i], nums[j], nums[k]]);
}
}
}
return result;
};时间复杂度仍然为 O(N^3)，这是无法接受的，因此需要进行优化。
因为 a + b + c = 0，在保持 a 不变的前提下，随着 b 的增大，c 就会逐渐变小，因此我们让第三重循环的指针从最右边开始往右遍历。这样的话，将枚举的时间复杂度从 O(N^2)减少至 O(N)。这就是双指针的方法。
这道题的难点在于重复项的判断。
var threeSum = function(nums) {
const result = [];
const len = nums.length;
if (len < 3) {
return result;
}
nums = nums.sort((a, b) => a - b);
for (let i = 0; i < len; i++) {
// 如果当前数组大于0，则三数之和一定大于0，所以结束循环
if (nums[i] > 0) break;
// 重复项跳过循环
if (i > 0 && nums[i] === nums[i-1]) continue;
let L = i + 1;
let R = len - 1;
while (L < R) {
const sum = nums[i] + nums[L] + nums[R];
if (sum === 0) {
// 跳过重复项
result.push([nums[i], nums[L], nums[R]])
while (L < R && nums[L] === nums[L + 1]) L++;
while (L < R && nums[R] === nums[R - 1]) R--;
L++;
R--;
}
else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return result;
};复杂度分析：
时间复杂度：O(N^2)。
空间复杂度：O(logN)。额外排序的空间复杂度为 O(logN)。使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为 O(N)。
写法一：
代码：
var longestCommonPrefix = function(strs) {
if (strs.length == 0) return "";
let ans = strs[0];
for (let i = 1; i < strs.length; i++) {
let j = 0;
for (; j < ans.length && j < strs[i].length; j++) {
if (ans[j] != strs[i][j]) break;
}
ans = ans.substr(0, j);
if (ans === "") return ans;
}
return ans;
};写法二：
代码：
var longestCommonPrefix = function(strs) {
// 当字符串数组长度为 0 时则公共前缀为空，直接返回
if (strs.length === 0) return '';
// 令最长公共前缀 ans 的值为第一个字符串，进行初始化
const ans = strs[0];
const len = ans.length;
// ans 是空字符串的特殊情况
if (len === 0) return '';
for (let i = 0; i < len; i++) {
if (!strs.every(str => str[i] === ans[i])) {
// 首次判定的时候就有不满足的项，直接抛空出去
if (i === 0) return '';
// 当有不满足项出现的时候，把之前满足的字符串抛出去
return ans.slice(0, i);
}
}
// 循环跑完也没有return出去，说明全部满足，把判断的这个字符return出去
return ans;
};复杂度分析：
解题思路：
找出最大字符串与最小字符串，然后比较出来的公共前缀也为其它字符串的公共前缀。
这里需要注意的是，比较大小是按照字符的大小，比如abac是小于abc的。
代码：
var longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) return "";
if(strs.length === 1) return strs[0]
let min = 0, max = 0
for(let i = 1; i < strs.length; i++) {
if(strs[min] > strs[i]) min = i
if(strs[max] < strs[i]) max = i
}
for(let j = 0; j < strs[min].length; j++) {
if(strs[min].charAt(j) !== strs[max].charAt(j)) {
return strs[min].substring(0, j)
}
}
return strs[min];
};复杂度分析：
解题思路：
把问题分解为子问题：找2个字符串的最长公共前缀
代码：
var longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) return "";
return lCPrefixRec(strs)
};
// 若分裂后的两个数组长度不为 1，则继续分裂
// 直到分裂后的数组长度都为 1，
// 然后比较获取最长公共前缀
function lCPrefixRec(arr) {
let length = arr.length
if(length === 1) {
return arr[0]
}
let mid = Math.floor(length / 2),
left = arr.slice(0, mid),
right = arr.slice(mid, length)
return lCPrefixTwo(lCPrefixRec(left), lCPrefixRec(right))
}
// 求 str1 与 str2 的最长公共前缀
function lCPrefixTwo(str1, str2) {
let j = 0
for(; j < str1.length && j < str2.length; j++) {
if(str1.charAt(j) !== str2.charAt(j)) {
break
}
}
return str1.substring(0, j)
}复杂度分析：
解题**：
代码：
var deleteDuplicates = function (head) {
let p = head;
while (p && p.next) {
if (p.val === p.next.val) {
p.next = p.next.next;
} else {
p = p.next;
}
}
return head;
};复杂度分析：
解题**：
暴力解法时间复杂度较高，会达到 O(n^2)，故而采取滑动窗口的方法降低时间复杂度。
用滑动窗口来解决，滑动窗口其实就是一个队列。当右指针查找到不重复的项时，当前左右指针之间的队列就是当前的无重复字符。再不断移动这个队列，就能查找出最长的符合要求的队列。
代码：
var lengthOfLongestSubstring = function(s) {
let ans = 0;
for (let L = 0; L < s.length; L++) {
let R = L + 1;
// 只要R所在位置的元素出现过，L就往后继续走
while (!s.slice(L, R).includes(s[R]) && R < s.length) {
R++;
}
ans = Math.max(ans, R - L);
}
return ans;
};更有效率的代码：
var lengthOfLongestSubstring = function(s) {
const set = new Set();
let R = -1, ans = 0;
const len = s.length;
for (let L = 0; L < len; L++) {
if (L !== 0) {
// 左指针向右移动一格，移除一个字符
set.delete(s.charAt(L - 1))
}
while ( R + 1 < len && !set.has(s.charAt(R + 1))) {
// 不断地移动右指针
set.add(s.charAt(R + 1));
++R;
}
ans = Math.max(ans, R - L + 1)
}
return ans;
};复杂度分析：
解题思路：
可以定义一个递归的辅助函数 helper，这个辅助函数对于节点和它的下一个节点进行交换，比如 helper(1) 处理 1 -> 2，并且把交换变成 2 -> 1 的尾节点 1 的 next 继续指向 helper(3) 也就是交换后的 4 -> 3。
边界情况在于，如果顺利的作了两两交换，那么交换后我们的函数返回出去的是 交换后的头部节点，但是如果是奇数剩余项的情况下，没办法做交换，那就需要直接返回 原本的头部节点。
代码：
var swapPairs = function(head) {
if (!head) return null;
function helper(node) {
let tempNext = node.next;
if (tempNext) {
let tempNextNext = node.next.next;
node.next.next = node;
node.next = tempNextNext ? helper(tempNextNext) : null;
}
return tempNext || node
}
return helper(head) || head;
};用自身进行递归的代码：
var swapPairs = function(head) {
// 1. 终止条件：当前没有节点或者只有一个节点，肯定就不需要交换了
if (head == null || head.next == null) return head;
// 2. 调用单元
// 需要交换的两个节点是 head 和 head.next
let firstNode = head;
let secondNode = head.next;
// firstNode 连接后面交换完成的子链表
firstNode.next = swapPairs(secondNode.next);
// secondNode 连接 firstNode
secondNode.next = firstNode;
// 3. 返回值：返回交换完成的子链表
// secondNode 变成了头结点
return secondNode;
};复杂度分析：
加哨兵节点
代码：
var swapPairs = function(head) {
let shaob = new ListNode(0); // 添加哨兵 加0
shaob.next = head;
let shao = shaob; //shao 是为了一直往下指, 而 shaob 其实是为了返回第二个节点
while(shao.next != null && shao.next.next != null) {
let start = shao.next; // 代表第一次的1
let end = shao.next.next; // 代表第一次的2
shao.next = end; // 0 指向 2
start.next = end.next; // 1 指向 3
end.next = start; // 2 指向 1
shao = start; // 将此时的1 也就是交换后的1当哨兵 继续循环
}
return shaob.next // 返回的是最初哨兵的前一个 就是链表头
};复杂度分析：
解题**：
判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）
递归的终止条件是当两个链表都为空的时候。
代码：
var mergeTwoLists = function(l1, l2) {
if (l1 === null || l2 === null) {
return l1 || l2;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};复杂度分析：
解题**：
设定一个哨兵节点，再维护一个 prev 指针，一开始的时候 prev 就指向哨兵节点。
迭代判断l1和l2当前节点的大小，如果小就接在哨兵节点后面，同时把当前链表后移。不管是哪个链表接在了后面，当前的 prev 指针都要后移一位。
当循环终止的时候，肯定是l1和l2至少一个已经空了，直接把另外一个接在后面就可以了。
代码：
var mergeTwoLists = function(l1, l2) {
const prehead = new ListNode(-1);
let prev = prehead;
while (l1 !== null && l2 !== null) {
// l1和l2谁小就接在后面，同时当前指针后移一位
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
// 不管将哪一个元素接在了后面，我都需要把 prev 向后移一位。
prev = prev.next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，直接将链表末尾指向未合并完的链表即可
prev.next = l1 === null ? l2 : l1;
return prehead.next;
};复杂度分析：
解题**：
代码：
复杂度分析：
解题**：
在深度优先遍历的过程中，记录当前路径的节点值的和。
在叶子节点处，判断当前路径的节点值的和是否等于目标值。
代码：
var hasPathSum = function(root, sum) {
if(!root) return false;
let res = false;
const dfs = (node, s) => {
// console.log(node.val, s);
// 如果是叶子节点，且当前路径的和为sum，就证明找到一个符合要求的路径
if (!node.left && !node.right && s === sum) {
res = true;
}
if(node.left) dfs(node.left, s + node.left.val);
if(node.right) dfs(node.right, s + node.right.val);
};
dfs(root, root.val);
return res;
};复杂度分析：
解题**：
代码：
var isSameTree = function(p, q) {
if (!p && !q) return true
if (p && q && p.val === q.val &&
isSameTree(p.left, q.left) &&
isSameTree(p.right, q.right)
) {
return true;
}
return false;
};复杂度分析：
解题**：
二叉树的最大深度即为左子树的深度与右子树深度的较大值 + 1，而求子树的深度一样可以用这个方法计算。
一直递归到空节点结束。
代码：
var maxDepth = function(root) {
if (!root) return 0;
if (root.left === null && root.right === null) {
return 1;
}
const leftDepth = maxDepth(root.left) + 1;
const rightDepth = maxDepth(root.right) + 1;
return Math.max(leftDepth, rightDepth);
};复杂度分析：
TODO
解题**：
若前一个元素大于0，则将其加入到当前元素上。
最后结果既是这个加上的值的最大值。
为什么前面的小于0就丢了，因为如果这个数组都是正数，一直加下去就可以了。没有什么最大子序和，最大就是他自己。
贪心，前面的小于0，就丢了。动态规划，前面的元素大于0，就和当前元素相加。
那贪心和动态规划的区别是什么呢？？
动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
代码：
var maxSubArray = function(nums) {
// 初始值为0,最大值为第一个无素。
let pre = 0, maxAns = nums[0];
nums.forEach((x) => {
// 前一个元素加到当前元素上，取较大值
pre = Math.max(pre + x, x);
// 取结果的最大值
maxAns = Math.max(maxAns, pre);
console.log(pre, maxAns)
});
return maxAns;
};复杂度分析：
TODO
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.