Leetcode_题解
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
// 滑动窗口（也是双指针的原理）
var minSubArrayLen = function(target, nums) {
// 双指针都从左边开始
let left = 0, right = 0, sum = 0, length = Infinity;
while(right < nums.length){
// 当 sum < target 时，右指针向右移一个
sum += nums[right];
// 如果满足 sum >= target，就逐步让左指针向右移一个
while(sum >= target){
length = Math.min(length, right - left + 1);
sum -= nums[left];
left++;
};
right++;
}
return length === Infinity ? 0 : length;
};给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
/**
* @param {number[]} nums
* @return {number[]}
*/
// 平方之后改变顺序是因为负数
// 新数组的最大值只有可能从左右两边开始，越靠近中间的值越不可能是新数组的最大值。
// 降序填充新数组。
// 双指针，left， right
var sortedSquares = function(nums) {
const newNums = new Array(nums.length - 1);
let newIndex = nums.length - 1, left = 0, right = nums.length - 1;
while(left <= right){
let numsLeft = nums[left] ** 2, numsRight = nums[right] ** 2;
if(numsLeft > numsRight){
newNums[newIndex] = numsLeft;
left++;
}else{
newNums[newIndex] = numsRight;
right--;
}
newIndex--;
}
return newNums;
};给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
/**
* @param {number} n
* @return {number[][]}
*/
var generateMatrix = function(n) {
// 构建矩阵
const res = new Array(n).fill(0).map(() => new Array(n).fill(0));
let fillNum = 1; // 填充数
// 转一次，行数要 -2，列数要 - 2，一共要转几个完整圈？
// 向下取整。因为如果是奇数，还会留一个正中间的值，这不算一个完整圈
let turns = Math.floor(n);
// 标记上、右、下、左 开始的位置
let top = 0, right = n - 1, bottom = n - 1, left = 0;
for(let t = 0; t < turns; t++){
// 上面的行，从左到右。区间：左闭右开
for(let i = left; i < right; i++){
res[top][i] = fillNum;
fillNum++;
}
// 右边的列，从上到下。区间：上闭下开
for(let i = top; i < bottom; i++){
res[i][right] = fillNum;
fillNum++;
}
// 下面的行，从右到左。区间：右闭左开
for(let i = right; i > left; i--){
res[bottom][i] = fillNum;
fillNum++;
}
// 左边的列，从下到上。区间：下闭上开
for(let i = bottom; i > top; i--){
res[i][left] = fillNum;
fillNum++;
}
// 一圈执行完毕，每个标记进行修改
top += 1;
right -= 1;
bottom -= 1;
left += 1;
}
// 处理 n 为奇数
if(n % 2 === 1){
let centerRow = Math.floor(n / 2), centerCol = Math.floor(n / 2);
res[centerRow][centerCol] = n ** 2;
}
return res
};给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
暴力解法可以使用嵌套循环实现，其时间复杂度为 O(n^2)，空间复杂度为 O(1) ，这里不详细赘述。
我们可以使用 Map 数据结构来记录先前遍历过的数据，时间复杂度为 O(n)，但也带来了 O(n) 的空间复杂度。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = new Map();
for(let i = 0; i < nums.length; i++) {
x = target - nums[i];
if(map.has(x)) {
return [map.get(x),i]
}
map.set(nums[i],i);
}
}设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
恕我直言，直接看示例，完全不知道输出是什么样的，无从下手...只能按照题目的逻辑慢慢啃...
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3
// 节点对象
var LinkNode = function(val, next){
this.val = val;
this.next = next;
}
var MyLinkedList = function() {
this.length = 0;
this.head = null;
this.tail = null;
};
// 根据 index 返回链表节点，便于后续方法
MyLinkedList.prototype.getNode = function(index) {
if(index > this.length || index < 0) return null;
let dummyHead = new LinkNode(0, this.head); // 采用虚拟头节点
let cur = dummyHead;
while(index > -1){
cur = cur.next;
index--;
}
return cur;
};
/**
* @param {number} index
* @return {number}
*/
MyLinkedList.prototype.get = function(index) {
if(index >= this.length || index < 0) return -1;
return this.getNode(index).val;
};
/**
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtHead = function(val) {
let newHead = new LinkNode(val, this.head);
this.head = newHead;
this.length++;
if(!this.tail){ // 如果在这之前没有节点，也需要把 tail 设置为新节点
this.tail = newHead;
}
};
/**
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtTail = function(val) {
let newTail = new LinkNode(val, null);
if(!this.head){
this.head = newTail;
}else{
this.tail.next = newTail;
}
this.tail = newTail;
this.length++;
};
/**
* @param {number} index
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtIndex = function(index, val) {
if(index === this.length){ // 等于 length, 尾部插入
this.addAtTail(val);
}else if(index > this.length){
return;
}else if(index <= 0){ // 小于等于0，头部插入
this.addAtHead(val);
}else{
// 获取 index 前一个位置的节点
let indexNode = this.getNode(index - 1);
let newNode = new LinkNode(val, indexNode.next);
indexNode.next = newNode;
this.length++;
}
};
/**
* @param {number} index
* @return {void}
*/
MyLinkedList.prototype.deleteAtIndex = function(index) {
if(index < 0 || index >= this.length) return;
if(index === 0){ // 如果删除的是第一个节点
this.head = this.head.next;
if(this.length === 1){ // 如果这个节点也同时是尾节点
this.tail = this.head
}
this.length--;
}else{
let node = this.getNode(index - 1);
node.next = node.next.next;
if(index === this.length - 1){ // 如果删除的是最后一个节点
this.tail = node;
}
this.length--
}
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* var obj = new MyLinkedList()
* var param_1 = obj.get(index)
* obj.addAtHead(val)
* obj.addAtTail(val)
* obj.addAtIndex(index,val)
* obj.deleteAtIndex(index)
*/给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
// “队列” 求解： 滑动窗口，每次滑动需要从队首移除元素，从队尾加入新的元素。
var maxSlidingWindow = function(nums, k) {
const n = nums.length;
const q = []; // 队列
// 初始化，把值放入队列中
for (let i = 0; i < k; i++) {
// 如果队尾的index对应的值比当前index对应的值小，则弹出队尾的index，以确保把最大值的index放在队首（队列内存的是 index，而不是具体的值）
while (q.length && nums[i] >= nums[q[q.length - 1]]) {
q.pop();
}
q.push(i);
}
const ans = [nums[q[0]]];
for (let i = k; i < n; i++) {
while (q.length && nums[i] >= nums[q[q.length - 1]]) {
q.pop();
}
q.push(i);
// 如果队首（最大值）的index不在窗口范围内了，则从队首弹出
while (q[0] <= i - k) {
q.shift();
}
ans.push(nums[q[0]]);
}
return ans;
};时间复杂度为：O(n^2)，不占用额外内存。
// 选择排序：从小到大
const selectionSort = (arr) => {
let minIndex = 0, len = arr.length;
for(let i = 0; i < len - 1; i++){
// 初始化当前最小数的 index
minIndex = i;
// 从当前位置后一个开始查找剩余数里的最小数
for(let j = i + 1; j < len; j++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
// 将最小数和本次循环开始位置的数交换位置
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
return arr;
}
const arr = [1, 2, 5, 3, 9, 7, 4, 6, 10, 8];
console.log(selectionSort(arr));给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
/**
* @param {string} s
* @return {boolean}
*/
// 括号匹配 是经典考察 “栈” 的题目
var isValid = function(s) {
const stack = []; // 栈
for(const a of s){
switch(a){
case '(':
stack.push(')');
break;
case '[':
stack.push(']');
break;
case '{':
stack.push('}');
break;
default:
// 如果不是上面几种，那就说明是右括号，于是取出 stack 中的第一个元素进行配对
const top = stack.pop();
if(top !== a){
return false;
}
}
}
return stack.length === 0;
};编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
/**
* @param {number} n
* @return {boolean}
*/
// 计算一个数字的每个位平方和
var getSquareSum = function(n){
let sum = 0;
while(n){
sum += (n % 10) ** 2;
n = Math.floor(n / 10); // 向下取整
}
return sum;
}
var isHappy = function(n) {
const result = new Set();
let num = n;
while(true){
let sum = getSquareSum(num);
if(sum === 1){ // 满足要求，返回 true
return true;
}
if(result.has(sum)){ // 如果集合里有这个数，意味着会出现循环（即链表成环），那么这个数不可能是快乐数，只会将无尽循环下去
return false;
}
result.add(sum);
num = sum;
}
};将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I
示例 3：
输入：s = "A", numRows = 1
输出："A"
行索引先增后减，因此，使用一个数组存储每行的内容，并设定标记
flag来改变判断行索引增加还是减少。
时间复杂度：O(n)
空间复杂度：O(n)
/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function(s, numRows) {
// 判断行数长度，小于2直接返回原字符串
if(numRows < 2){
return s
}
// 记录每行的结果
const result = Array(numRows).fill('')
let rowIndex = 0;
let flag = -1; // 记录是否要转向
for(element of s){
// 在第一行和最后一行，要转向
if(rowIndex === 0 || rowIndex === numRows - 1){
flag = -flag;
}
result[rowIndex] += element;
rowIndex += flag;
}
return result.join('')
};给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
递归求解：类似于求解二叉树的最大深度，但是值得注意的是二叉树最小深度的定义，容易理解错误。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
// 结束条件
if(!root) return 0;
let leftDepth = minDepth(root.left);
let rightDepth = minDepth(root.right);
// 注意最小深度的概念，叶子结点是没有任何子树的节点。
if(root.left === null && root.right !== null){
return 1 + rightDepth;
}
if(root.left !== null && root.right === null){
return 1 + leftDepth;
}
return 1 + Math.min(leftDepth, rightDepth);
};给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
递归求解：分别对左右子树进行深度递归，需最大值。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
const getNode = (child, level) => {
if(!child) return level;
// 对左子树进行递归遍历
let deepLeft = getNode(child.left, level + 1);
// 对右子树进行递归遍历
let deepRight = getNode(child.right, level + 1);
// 取最大的值
return Math.max(deepLeft, deepRight);
}
return getNode(root, 0);
};归并排序就是将一个数组当成一棵二叉树。首先，自上而下不断二分成两个数组，直到最低层，只剩叶子节点（即每个数组只剩一个元素）。
接着，自下而上合并。把属于同一个父节点的两个叶子节点进行合并，即把里面的元素比较大小并合并成一个新的数组，作为它们父节点的值。
重复这个步骤，直到最后得到根节点。其值就是排列有序的数组。
时间复杂度为：O(nlogn)。
// 归并排序：从小到大
const mergeSort = (arr) => {
let len = arr.length;
// 如果数组就一个元素，不用排序
if(len < 2) return arr;
// 将数组对半分
const middle = Math.floor(len / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
// 递归：不断地将数组对半分，分到left 和 right都只有一个元素了开始排序合并。
return merge(mergeSort(left), mergeSort(right));
}
const merge = (left, right) => {
// 合并后的结果数组
const result = [];
//
while(left.length && right.length){
// 遍历 left 和 right 中的元素并比较，小的加入 result
if(left[0] < right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}
// 判断哪个数组里还有数，说明大，都应该插入在 result 现有元素的后面
while(left.length){
result.push(left.shift());
}
while(right.length){
result.push(right.shift());
}
return result;
}
const arr = [1, 2, 5, 3, 9, 7, 4, 6, 10, 8];
console.log(mergeSort(arr));给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
回溯。遵守回溯三部曲：确定递归参数、终止条件、单层逻辑。在单层逻辑中要记得回溯。
/**
* @param {string} s
* @return {string[][]}
*/
const isPalindrome = (s, l, r) => {
for (let i = l, j = r; i < j; i++, j--) {
if(s[i] !== s[j]) return false;
}
// 如果是单个字符，则不进入 for 循环判断，单个字符自身就是一个回文串
return true;
}
var partition = function(s) {
const res = [], path = [], len = s.length;
function backtracking(startIndex) {
// 终止条件
if(startIndex >= len) {
res.push([...path]);
return;
}
// 单层逻辑
for(let i = startIndex; i < len; i++) {
// 如果不是回文子串，就跳过 push 和递归的环节，让 i 继续向右移动。
if(!isPalindrome(s, startIndex, i)) continue;
// 是回文子串，就 push，并让 startIndex 向右移一个，开始继续分割后面的内容
path.push(s.slice(startIndex, i + 1));
backtracking(i + 1);
// 回溯
path.pop();
}
}
backtracking(0);
return res;
};给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
// 方法一：先用 Map 统计，再利用优先队列（小顶堆）进行排序
// 时间复杂度：O（n)
// js 没有堆 需要自己构造
class Heap {
constructor(compareFn) {
this.compareFn = compareFn;
this.queue = [];
}
// 添加
push(item) {
// 推入元素
this.queue.push(item);
// 上浮
let index = this.size() - 1; // 记录推入元素下标
let parent = Math.floor((index - 1) / 2); // 记录父节点下标
while (parent >= 0 && this.compare(parent, index) > 0) { // 注意compare参数顺序
[this.queue[index], this.queue[parent]] = [this.queue[parent], this.queue[index]];
// 更新下标
index = parent;
parent = Math.floor((index - 1) / 2);
}
}
// 获取堆顶元素并移除
pop() {
// 堆顶元素
const out = this.queue[0];
// 移除堆顶元素 填入最后一个元素
this.queue[0] = this.queue.pop();
// 下沉
let index = 0; // 记录下沉元素下标
let left = 1; // left 是左子节点下标 left + 1 则是右子节点下标
let searchChild = this.compare(left, left + 1) > 0 ? left + 1 : left;
while (searchChild !== undefined && this.compare(index, searchChild) > 0) { // 注意compare参数顺序
[this.queue[index], this.queue[searchChild]] = [this.queue[searchChild], this.queue[index]];
// 更新下标
index = searchChild;
left = 2 * index + 1;
searchChild = this.compare(left, left + 1) > 0 ? left + 1 : left;
}
return out;
}
size() {
return this.queue.length;
}
// 使用传入的 compareFn 比较两个位置的元素
compare(index1, index2) {
// 处理下标越界问题
if (this.queue[index1] === undefined) return 1;
if (this.queue[index2] === undefined) return -1;
return this.compareFn(this.queue[index1], this.queue[index2]);
}
}
const topKFrequent = function (nums, k) {
const map = new Map();
for (const num of nums) {
map.set(num, (map.get(num) || 0) + 1);
}
// 创建小顶堆
const heap= new Heap((a, b) => a[1] - b[1]);
// entry 是一个长度为2的数组，0位置存储key，1位置存储value
for (const entry of map.entries()) {
heap.push(entry);
if (heap.size() > k) {
heap.pop();
}
}
// return heap.queue.map(e => e[0]);
const res = [];
for (let i = heap.size() - 1; i >= 0; i--) {
res[i] = heap.pop()[0];
}
return res;
};
// 方法二：直接用Map统计，再进行排序
// 时间复杂度：O（nlongn) 快速排序
var topKFrequent = function(nums, k) {
const countMap = new Map();
for(const el of nums){
countMap.set(el, (countMap.get(el) || 0) + 1);
}
return [...countMap.entries()].sort((a, b) => b[1] - a[1]).slice(0, k).map(el => el[0]);
};给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab"
输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab"
输出：true
/**
* @param {string} ransomNote
* @param {string} magazine
* @return {boolean}
*/
// 经典哈希表解法，需要记录数据。但这里由于数据量较小，可以用数组代替
var canConstruct = function(ransomNote, magazine) {
const arr = new Array(26).fill(0);
const zero = 'a'.charCodeAt();
// 记录 magazine 里面的字母及其出现次数
for(const m of magazine){
arr[m.charCodeAt() - zero]++;
}
// 如果 ransomNote 里面的字母对应的 arr 中的值为0，不够减了，返回 false，反之减一
for(const r of ransomNote){
if(!arr[r.charCodeAt() - zero]){
return false;
}
arr[r.charCodeAt() - zero]--;
}
return true;
};给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
// 返回链表，考虑虚拟头节点，便于操作头部和返回链表
var swapPairs = function(head) {
let dummyHead = new ListNode(0, head);
let cur = dummyHead; // 从虚拟节点开始
while(cur.next && cur.next.next){
let temp1 = cur.next; // 当前节点的下一个
let temp2 = cur.next.next; // 当前节点的下下个
// 倒叙操作
temp1.next = temp2.next;
temp2.next = temp1;
cur.next = temp2;
// 每次循环结束，右移2个
cur = cur.next.next;
}
return dummyHead.next
};/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
/*
* 双指针法：快慢指针，快指针以慢指针两倍的速度向前走。
* 如果有环，则追及问题一定是有解的。
* 当快慢指针相遇时，让另一个慢指针从头出发，两个慢指针继续走，最后会在环口相遇。
*/
var detectCycle = function(head) {
if (head === null) {
return null;
}
let slow = head, fast = head;
while (fast !== null) {
// 慢指针每次走 1 步
slow = slow.next;
// 快指针每次走 2 步
if (fast.next !== null) {
fast = fast.next.next;
} else {
return null;
}
// 相遇的时候，快指针停，慢指针继续走，另一个慢指针从头走
if (fast === slow) {
let ptr = head;
while (ptr !== slow) { // 相遇的点就是环口。
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
};
/*
* 集合法：把一个链表的节点加入到集合中，
*/
var detectCycle = function(head) {
const nodes = new Set();
let temp = head;
while(temp){
// 判断集合里有没有某个节点，有则说明是环口
if(nodes.has(temp)){
return temp;
}
nodes.add(temp);
temp = temp.next;
}
return null
}时间复杂度为：O(n^2)。
// 插入排序：从小到大
const insertionSort = (arr) => {
// 定义 current 为当前待插入元素；prevIndex 用于标记当前和待插入元素比较的元素。
let len = arr.length, current, prevIndex;
// 因为要和前面的值相比，找到自己该插入的位置，因此要从数组第二个数开始（从第一个开始也没问题，但是无效对比，浪费时间）。
for(let i = 1; i < len; i++){
// prevIndex 每次从待插入元素的前一个位置开始
prevIndex = i - 1;
current = arr[i];
// 如果当前比较的元素比待插入元素大，该元素后移一个
while(prevIndex >= 0 && arr[prevIndex] > current){
arr[prevIndex + 1] = arr[prevIndex];
prevIndex--;
}
// 找到了待插入元素的位置
arr[prevIndex + 1] = current;
}
return arr;
}
const arr = [1, 2, 5, 3, 9, 7, 4, 6, 10, 8];
console.log(insertionSort(arr));按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
解题过程：
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
// 验证能不能落子，因为我们在递归中是从上往下放，只需要考虑列、左上斜线、右上斜线有没有皇后
function isValid(row, col, chessBoard, n) {
// 检查列
for(let i = 0; i < row; i++) {
if(chessBoard[i][col] === 'Q') {
return false;
}
}
// 检查左上角斜线
for(let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if(chessBoard[i][j] === 'Q') {
return false;
}
}
// 检查右上斜线
for(let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if(chessBoard[i][j] === 'Q') {
return false;
}
}
return true;
}
// 棋盘数据返回成一维数组
function transformChessBoard(chessBoard) {
let chessBoardBack = []
chessBoard.forEach(row => {
let rowStr = ''
row.forEach(value => {
rowStr += value
})
chessBoardBack.push(rowStr);
})
return chessBoardBack
};
const result = [];
// 回溯法
function backtracing(row,chessBoard) {
// 结束条件：如果能找到最后一行，说明找到了正确结果
if(row === n) {
result.push(transformChessBoard(chessBoard))
return
}
// 单层逻辑
for(let col = 0; col < n; col++) {
if(isValid(row, col, chessBoard, n)) {
chessBoard[row][col] = 'Q';
// 进入下一行
backtracing(row + 1, chessBoard);
// 回溯
chessBoard[row][col] = '.';
}
}
}
// 构建二维数组
let chessBoard = new Array(n).fill([]).map(() => new Array(n).fill('.'))
backtracing(0, chessBoard);
return result;
};给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
return Array.from(new Set(nums1.filter(el => nums2.includes(el))))
};备注：如果是多个数组的交集，可以把这些数组都放进一个数组中，然后使用 reduce 即可。
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
// 双指针，i 和 newIndex，一个用于遍历，一个用于记录新的位置。时间复杂度 O(n),空间复杂度 O(1)
var removeElement = function(nums, val) {
let newIndex = 0;
for(let i = 0; i < nums.length; i++){
if(nums[i] !== val){
nums[newIndex] = nums[i];
newIndex++;
}
}
return newIndex;
};给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
三数之和的进阶版，依旧采用求解三数之和的思路：双指针法。区别在于：四数之和在外面又多加一层 for 循环。
对于五数、六数...，就是在外面继续增加 for 循环。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
// 三数之和的进阶版，依旧采用求解三数之和的思路：双指针法
// 区别在于：四数之和在外面又多加一层 for 循环
var fourSum = function(nums, target) {
const len = nums.length;
if(len < 4) return [];
// 排序
nums.sort((a, b) => a - b);
const res = [];
for(let i = 0; i < len - 3; i++) {
// 剪枝：最小的四个数之和都大于 target
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
// 剪枝：当前数 + 三个最大的数都小于 target，直接移动 i 到下一个，增大
if (nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) {
continue;
}
// 去重i
if(i > 0 && nums[i] === nums[i - 1]) continue;
for(let j = i + 1; j < len - 2; j++) {
// 去重j
if(j > i + 1 && nums[j] === nums[j - 1]) continue;
// 剪枝
if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
if (nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) continue;
let l = j + 1, r = len - 1;
while(l < r) {
const sum = nums[i] + nums[j] + nums[l] + nums[r];
if(sum < target) { l++; continue}
if(sum > target) { r--; continue}
res.push([nums[i], nums[j], nums[l], nums[r]]);
// 对nums[left]和nums[right]去重
while(l < r && nums[l] === nums[l + 1]); l++
while(l < r && nums[r] === nums[r - 1]); r--
// l 和 r 指针都要动，否则一定会重复，浪费计算时间
l++;
r--
}
}
}
return res;
};实现二叉树的前、中、后序遍历。
// 前序遍历: 中 -> 左 ->右
const preorderTraversal = (root) => {
let res=[];
// 使用递归遍历
const dfs=function(root){
if(root===null)return ;
//先序遍历所以从父节点开始
res.push(root.val);
//递归左子树
dfs(root.left);
//递归右子树
dfs(root.right);
}
dfs(root);
return res;
};
// 中序遍历: 左 -> 中 -> 右
const inorderTraversal = (root) => {
let res=[];
const dfs=function(root){
if(root===null){
return ;
}
// 先左，再中，最后右
dfs(root.left);
res.push(root.val);
dfs(root.right);
}
dfs(root);
return res;
};
// 后序遍历: 左 -> 右 -> 中
const postorderTraversal = function(root) {
let res=[];
const dfs=function(root){
if(root===null){
return ;
}
// 先左，再右，最后中
dfs(root.left);
dfs(root.right);
res.push(root.val);
}
dfs(root);
return res;
};任何能够用递归解决的问题，也都可以用迭代法解决。在迭代法中，我们需要使用栈数据结构。
// 前序遍历:
// 入栈 右 -> 左
// 出栈 中 -> 左 -> 右
const preorderTraversal = (root, res = []) => {
if(!root) return res;
const stack = [root];
let cur = null;
while(stack.length) {
// 取一个，插入其右、左子树
cur = stack.pop();
res.push(cur.val);
cur.right && stack.push(cur.right);
cur.left && stack.push(cur.left);
}
return res;
};
//中序遍历:
// 入栈 左 -> 右
// 出栈 左 -> 中 -> 右
const inorderTraversal = (root, res = []) => {
const stack = [];
let cur = root;
while(stack.length || cur) {
if(cur) {
stack.push(cur);
// 左子树
cur = cur.left;
} else {
// 弹出父亲节点
cur = stack.pop();
res.push(cur.val);
// 右子树
cur = cur.right;
}
};
return res;
};
// 后序遍历:
// 入栈 左 -> 右
// 出栈 中 -> 右 -> 左 结果翻转
const postorderTraversal = (root, res = []) => {
if (!root) return res;
const stack = [root];
let cur = null;
do {
cur = stack.pop();
res.push(cur.val);
cur.left && stack.push(cur.left);
cur.right && stack.push(cur.right);
} while(stack.length);
return res.reverse();
};给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
使用队列的先进先出特性。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
const res = [];
const queue = [];
if(root === null) return res;
queue.push(root);
while(queue.length){
let len = queue.length; // 记录当前层级的节点
const curlevel = [];
while(len--){
// 取得队列头部第一个数
const cur = queue.shift();
curlevel.push(cur.val);
// 插入左右子树
cur.left && queue.push(cur.left);
cur.right && queue.push(cur.right)
}
res.push(curlevel);
}
return res;
};给你一个二叉树的根节点 root ， 检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3]
输出：true
递归求解。先比较左右树，再分别让左树的左子树与右树的右子树比较，左树的右子树和右树的左子树比较。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if(!root) return true; // 判断根节点为空
// 递归比较
const compare = (left, right) => {
// 如果一个空一个不空，返回 false
if(left === null && right !== null || left !== null && right === null){
return false;
// 如果两个都为空，返回 true
}else if(left === null && right === null){
return true;
// 如果都不为空，但是值不一样，返回 false
}else if(left.val !== right.val){
return false;
}
// 如果上面没有 return，则继续递归
let outside = compare(left.left, right.right);
let inside = compare(left.right, right.left);
return outside && inside;
}
return compare(root.left, root.right);
};给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
/**
* @param {string} s
* @return {string}
*/
// 匹配成对问题，考虑使用 “栈”
var removeDuplicates = function(s) {
const stack = [];
for(const el of s){
// 如果和栈顶元素相同，则直接让栈顶元素出栈，并进入下一轮循环
if(el === stack[stack.length - 1]){
stack.pop();
continue;
}else{ // 反之，把当前元素压入栈中
stack.push(el);
}
}
// 如果严格按照栈来操作，还需要一个一个从栈顶取出，并进行字符串反转
return stack.join('');
};给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
// 记录左、右、中
let left = 0, mid = 0, right = nums.length - 1;
while(left <= right){
mid = left + parseInt((right - left) / 2);
if(nums[mid] > target){
right = mid - 1;
}else if(nums[mid] < target){
left = mid + 1;
}else{
return mid;
}
}
return -1;
};给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
求高度，应该采用后序遍历；求深度，应该采用前序遍历。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
// 求高度，一定是后序遍历
const getHeight = (root) => {
// 结束条件
if(!root) return 0;
let leftHeight = getHeight(root.left);
if(leftHeight === -1) return -1;
let rightHeight = getHeight(root.right);
if(rightHeight === -1) return -1;
// 如果平衡，则加上当前节点的高度；反之返回 -1，表示不平衡
return Math.abs(leftHeight - rightHeight) > 1 ? -1 : 1 + Math.max(leftHeight, rightHeight);
}
return getHeight(root) === -1 ? false : true
};给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
思路：链表的基础应用。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
// 初始空节点，const不可改变，用于记录结果链表的初始位置。next指向我们计算的结果链表的第一位。
const myNode = new ListNode();
// 临时节点，记录结果链表的每一位，后续会移动。
let moveNode = myNode;
// 是否进位
let addOne = 0;
// 循环计算
while(l1 || l2 || addOne){
const value1 = l1 ? l1.val : 0;
const value2 = l2 ? l2.val : 0;
const sum = value1 + value2 + addOne;
addOne = (sum < 10) ? 0 : 1;
const result = sum % 10;
if(l1){
l1 = l1.next;
}
if(l2){
l2 = l2.next;
}
// 创建新的节点，并指向
moveNode.next = new ListNode(result)
moveNode = moveNode.next;
}
// 返回的结果应该是 myNode.next，指向我们的结果链表。而不是moveNode，moveNode只是中间量
return myNode.next
};编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
// 双指针法
var reverseString = function(s) {
let left = 0;
let right = s.length - 1;
while(left < right){
[s[left], s[right]] = [s[right], s[left]];
left++
right--;
}
};给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
两种解法：中心扩展和动态规划。
中心扩展：
枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。
即：遍历每一个字符，并向左和右分别逐个扩展，进行判断。
时间复杂度： O(n^2)
空间复杂度： O(1)动态规划：
思路：只有 S [i+1:j-1] 是回文串，并且 S 的第 i 和 j 个字母相同时，S [i: j]才会是回文串。
动态规划的状态转移方程：P(i, j) = P(i+1, j−1) ∧( Si == Sj)
因此，需要构建矩阵进行记录并判断。
时间复杂度： O(n^2)
空间复杂度： O(n^2)
很显然，中心扩展法比动态规划更优。这里我为了熟悉一下动态规划，就采用了动态规划解法。
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
const stringLen = s.length;
if(stringLen < 2){
return s
}
// 动态规划数组，stringLen x stringLen，myArray[l][r]表示，s中从l到r这一段是不是回文
let myArray = Array(stringLen).fill().map(() => Array(stringLen).fill(false));
let maxLength = 1;
let left = 0;
let right = 0;
// 动规求解
for(let r = 1; r < stringLen; r++){
for(let l = 0; l < r; l++){
// s[l] == s[r] 并且 l+1 到 r-1 这部分是回文，或者子串长度只有2或者3
if((s[l] == s[r]) && ((r - l <= 2) || (myArray[l + 1][r - 1] == true))){
myArray[l][r] = true;
if(r - l + 1 > maxLength){
maxLength = r - l + 1;
left = l;
right = r;
}
}
}
}
return s.slice(left, right + 1)
};给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
解题思路：
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
// 合并数组
const concatArr = nums1.concat(nums2);
// 排序
concatArr.sort((a, b) => a < b ? -1: a > b ? 1 : 0);
const arrLength = concatArr.length;
// 奇偶判断
if(arrLength % 2 !== 0){
return concatArr[(arrLength - 1) / 2];
}else{
const middle = concatArr.slice(arrLength / 2 - 1, arrLength / 2 + 1)
return (middle[0] + middle[1]) / 2
}
};给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
/**
* @param {string[]} tokens
* @return {number}
*/
// 匹配成对问题：使用 “栈”
var evalRPN = function(tokens) {
const stack = [];
for(const t of tokens){
if(isNaN(Number(t))){ // 判断是不是运算符
let b = stack.pop(); // 第二个运算数
let a = stack.pop(); // 第一个运算数
switch(t){
case '+':
stack.push(a + b);
break;
case '-':
stack.push(a - b);
break;
case '*':
stack.push(a * b);
break;
case '/':
let res = a / b;
if(res < 0){
res = Math.ceil(res);
}else{
res = Math.floor(res);
}
stack.push(res)
break;
}
}else{ // 如果是数字，就压入栈中
stack.push(Number(t))
}
}
// 最后的结果就是栈内最后一个元素
return stack.pop();
};整体思路：确定一个基准值，让它左边的元素们都比它小，右边的元素们都比它大，这个位置就是该基准值在顺序序列中的位置。
排序流程：
i 和 j ，前者从左向右移动，后者从右向左移动。base ，那么应该 j 指针先动，i 指针后动。j 指针移动到比 base 值小的位置，就停止，否则一直向左；当 j 指针停止时，说明对应位置的值小于 base。i 指针移动，每当 i 指针移动到比 base 值大的位置，则停止，否则一直向右。Step3 - Step5。base 在顺序序列中的正确位置，它也把序列分为了两部分。然后分别对这两部分执行上面的流程（递归）。时间复杂度为：O(nlogn)。
O(nlogn)，且常数项系数较小。O(n^2)。// 交换位置
const swap = (arr, left, right) => {
[arr[left], arr[right]] = [arr[right], arr[left]];
}
// 快速排序：从小到大
const quickSort = (arr, left, right) => {
if(left >= right) return;
let i = left, j = right, base = arr[left]; // 初始化双指针和基准值
while(i < j){
while(i < j && arr[j] >= base) j--;
while(i < j && arr[i] <= base) i++;
if(i < j){
swap(arr, i, j);
}
}
swap(arr, left, j); // 交换base值和i与j相遇停止所在位置的值，因为j先动，i后动，所以停止位置的值一定是小于 base 的
// 至此已经确定了 base 值在顺序序列中的位置，后续就是对它左右两边的两个序列，继续确定各自第一个值（base）的排序位置。
quickSort(arr, left, j - 1);
quickSort(arr, j + 1, right);
}
const arr = [1, 2, 5, 3, 9, 7, 4, 6, 10, 8];
quickSort(arr, 0, arr.length - 1);
console.log(arr);时间复杂度为：O(n^2)。
// 冒泡排序：从小到大
const bubbleSort = function(arr){
const len = arr.length;
// 只需要遍历 len - 1 次即可，最后一次只剩一个值不用动
for(let i = 0; i < len - 1; i++){
// 每一次 i 的循环结束，index 为 len - 1 - i 的数都是这一次循环里最大的值，之后不用再操作
for(let j = 0; j < len - 1 - i; j++){
if(arr[j] > arr[j+1]){ // 如果前者比后者大，则交换位置
[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
}
}
}
return arr;
}
const arr = [1, 2, 5, 3, 9, 7, 4, 6, 10, 8];
console.log(bubbleSort(arr));给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
解：
不需要额外的创建新的树，可以直接在 root1 或 root2 上进行操作，前中后序深度遍历都可以。严格遵守 “递归三部曲”。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root1
* @param {TreeNode} root2
* @return {TreeNode}
*/
var mergeTrees = function(root1, root2) {
// 自上而下：前序遍历
// 递归终止条件：
if(root1 === null) return root2;
if(root2 === null) return root1;
// 单层逻辑：直接操作 root1 即可
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
};给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
使用 “滑动窗口” 求解。
右侧标记逐个向右边滑动，如果出现重复的字符，左侧标记直接跳转到重复字符的下一位置。
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
const strLength = s.length;
if(strLength == 0){ // 判断长度，如果为0，直接返回0
return 0;
}
// 记录值和对应的索引
const myMap = new Map();
// 初始化
let left = 0;
let right = 0;
let maxLength = 1;
// 存放第一个值
myMap.set(s[0], 0);
// 滑动窗口
while(right < strLength - 1){
right++;
// 如果窗口内包含了重复的，直接left跳到重复值的后面以为
if(myMap.has(s[right])){
let newLeft = myMap.get(s[right]);
// 法1: 选择性删除 “旧数据”。先判断，如果是则不变，不是则改变left
// 这种方法 效率更高
if(newLeft < left){
myMap.delete(s[newLeft])
}else{
left = newLeft + 1
}
// 法2: 时刻删除“旧数据”。每次都删除不在新left和right之间的元素，保证map中都是有效数据
// 这种方法 稍微耗时+占内存
// for(let [key, value] of myMap.entries()){
// if(value < left){
// myMap.delete(key)
// }
// }
};
// 添加right位置的值
myMap.set(s[right], right);
maxLength = Math.max(maxLength, right - left + 1)
}
return maxLength
};给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
探究的内容和深度相关，采用前序遍历。
root.left && getPath(root.left, curPath + '->', res); 和 root.right && getPath(root.right, curPath + '->', res); 中了，因为是**在函数的参数中添加了 ->，实际上并不会影响到当前的 curPath。/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {string[]}
*/
var binaryTreePaths = function(root) {
// 和深度有关，前序遍历
const getPath = (root, curPath, res) => {
// 确定结束条件
if(root.left === null && root.right === null){
curPath += root.val;
res.push(curPath);
return;
}
// 当前逻辑，如果子树不空，就继续往下找
curPath += root.val;
root.left && getPath(root.left, curPath + '->', res);
root.right && getPath(root.right, curPath + '->', res);
}
const res = [], curPath ='';
getPath(root, curPath, res);
return res;
};给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
示例 4：
输入：x = 0
输出：0
思路：
- 将整数转为
string并按位转为数组形式。- 接着，对数组进行倒序排列。
- 最后，根据正负分情况重组为数组。
/**
* @param {number} x
* @return {number}
*/
var reverse = function(x) {
// number 转 string
const str = x.toString();
// string 转 array
const arr = Array.from(str);
// 倒序排列
arr.reverse();
const strLength = str.length;
let result;
// 判断正负
if(x < 0){
result = 0 - Number(arr.slice(0, strLength - 1).join(''))
}else{
result = Number(arr.join(''))
}
// 判断是否超过范围
return (result < Math.pow(-2, 31) || result > Math.pow(2, 31) - 1) ? 0 : result
};找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
回溯法，回溯法的递归一般不需要 return 某个值。遵守回溯三部曲：
回溯三部曲和递归三部曲一样，哪里有回溯哪里就有递归，但是一定要记得操作后进行回溯。
/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function(k, n) {
const res = [];
const path = [];
const backTracking = (sum, path, startIndex) => {
// 剪枝
if(sum > n) return;
// 终止条件
if(path.length === k){
if(sum === n){
// res.push(path);
// 向上面一样写会出错
res.push([...path]);
}
return;
}
for(let i = startIndex; i <= 9 - (k - path.length) + 1; i++){
sum += i;
path.push(i);
backTracking(sum, path, i + 1);
// 回溯
path.pop();
sum -= i;
}
}
backTracking(0, path, 1);
return res;
};给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
// 直接对原始链表操作：会出现头节点和其他节点的处理方式不一样的问题，需要单独处理头节点。
// 虚拟头节点：让真实的头节点变为第二个节点，因此所有节点的处理方式都相同。
var removeElements = function(head, val) {
const dummyHead = new ListNode(0, head);
// tempNode 记录当前遍历位置的节点
let tempNode = dummyHead;
while(tempNode.next !== null){
if(tempNode.next.val === val){
tempNode.next = tempNode.next.next;
continue; // 已经修改过 next 了，不用后移，直接跳出循环，下一次循环开始判断新的next节点的值
}
// 如果没进入 if 判断，则后移一个节点
tempNode = tempNode.next;
}
// 返回的应该是虚拟头的 next
return dummyHead.next;
};给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
通过递归即可实现。使用递归三大准则：
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
// 终止条件
if(!root) return null;
// 交换左右子树
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
// 返回节点，递归的顶部就是 root 节点
return root;
};给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
哈希表-Map 经典题目：需要记录值及其对应的参数
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number[]} nums3
* @param {number[]} nums4
* @return {number}
*/
var fourSumCount = function(nums1, nums2, nums3, nums4) {
const twoSumMap = new Map(); // 记录前两个数组的任意两数之和，及其出现的次数
let count = 0; // 记录元组数量
for(const n1 of nums1){
for(const n2 of nums2){
const twoSum = n1 + n2;
twoSumMap.set(twoSum, (twoSumMap.get(twoSum) || 0) + 1);
}
}
for(const n3 of nums3){
for(const n4 of nums4){
const twoSum = n3 + n4;
count += (twoSumMap.get(0 - twoSum) || 0); // 找出能和这两个数之和加起来为0的数对应的出现次数并加在count上。如果找不到，count加0
}
}
return count;
};请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
注意：
本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
示例 1：
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："42"（读入 "42"）
^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
示例 2：
输入：s = " -42"
输出：-42
解释：
第 1 步：" -42"（读入前导空格，但忽视掉）
^
第 2 步：" -42"（读入 '-' 字符，所以结果应该是负数）
^
第 3 步：" -42"（读入 "42"）
^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
示例 3：
输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。
思路：
正则表达式（如果对正则表达式不清楚的，点击这里查看）
/**
* @param {string} s
* @return {number}
*/
var myAtoi = function(s) {
const Max = Math.pow(2, 31) - 1;
const Min = Math.pow(-2, 31);
// 正则表达式 / 匹配字符串开头^ 匹配0个或者1个+或-号[\+\-]? 判断存在至少一个数组 \d+ /
let reg = new RegExp(/^[\+\-]?\d+/);
const result = Number(s.trim().match(reg))
return result < Min ? Min : result > Max ? Max : result
};/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
/* 方法一：双指针
* 首先弄清楚什么是链表相交：都交汇于某个节点，后续连接的节点都一样
* 如果有一长一短，那么必然是以短的为主，长链表也只可能在后面与短链表相交，然后到尾
* 因此，先让长链表移动到剩余部分和短链表一样长，再开始比较。
*/
// 返回链表长度
var getListLen = function(head) {
let len = 0, cur = head;
while(cur) {
len++;
cur = cur.next;
}
return len;
}
var getIntersectionNode = function(headA, headB) {
let curA = headA,curB = headB,
lenA = getListLen(headA),
lenB = getListLen(headB);
if(lenA < lenB) {
// 让curA为最长链表的头，lenA为其长度
// 交换变量注意加 “分号” ，两个数组交换变量在同一个作用域下时
// 如果不加分号，下面两条代码等同于一条代码: [curA, curB] = [lenB, lenA]
[curA, curB] = [curB, curA];
[lenA, lenB] = [lenB, lenA];
}
let i = lenA - lenB; // 求长度差
while(i-- > 0) { // 让curA和curB在同一起点上（末尾位置对齐）
curA = curA.next;
}
while(curA && curA !== curB) { // 遍历curA 和 curB，遇到相同则直接返回
curA = curA.next;
curB = curB.next;
}
return curA;
};
/*
* 方法二：集合查找
* 先遍历 A，把每一个节点都存入集合中
* 再遍历 B，在集合中找相同的节点
*/
var getIntersectionNode = function(headA, headB) {
const nodes = new Set();
let temp = headA;
while (temp) {
nodes.add(temp);
temp = temp.next;
}
temp = headB;
while (temp) {
if (nodes.has(temp)) {
return temp;
}
temp = temp.next;
}
return null;
};给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
// 双指针的经典应用:slow 和 fast
var removeNthFromEnd = function(head, n) {
let dummyHead = new ListNode(0, head);
let slow = dummyHead;
let fast = dummyHead;
// 先让 fast 比 slow 快 n+1 步。这样当 fast 到 null 的时候，slow 的下一个节点就是要删掉的节点
for(let i = 0; i < n + 1; i++){
fast = fast.next;
}
while(fast){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummyHead.next;
};给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
可以像两数求和一样使用哈希表，但是因为去重问题，哈希表-Map 方法容易出错。这里采用 双指针 法。
/**
* @param {number[]} nums
* @return {number[][]}
*/
// 双指针法
var threeSum = function(nums) {
const res = [], len = nums.length;
// 将数组排序，从小到大
nums.sort((a, b) => a - b);
for (let i = 0; i < len - 2; i++) {
let l = i + 1, r = len - 1;
// 数组排过序，如果第一个数大于0直接返回res
if (nums[i] > 0) return res
// 去重
if (i > 0 && nums[i] === nums[i - 1]) continue
while(l < r) {
let threeSum = nums[i] + nums[l] + nums[r]
// 三数之和小于0，要让值增大，则左指针向右移动
if (threeSum < 0) l++
// 三数之和大于0，要让值减小，则右指针向左移动，
else if (threeSum > 0) r--
else {
res.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 指针都要动，否则一定会重复，浪费计算时间
l++;
r--;
}
}
}
return res
};给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例2:
输入：head = []
输出：[]
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
// 迭代法：双指针**
var reverseList = function(head) {
let prev = null; // 记录前一个节点
let cur = head; // 当前节点
let next = null; // 记录后一个节点
while(cur){
next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
};
/*
* 个人认为：反转操作也可以使用 “栈” 来实现，即先进后出的**。
*/给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []
右视图就是输出每一层的最后一个值，使用层序遍历即可。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
const res = [], queue = [];
if(root === null) return res;
queue.push(root);
while(queue.length){
let len = queue.length;
while(len--){
const cur = queue.shift();
// 右视图就是输出每一层的最后一个值
if(len === 0) res.push(cur.val);
cur.left && queue.push(cur.left);
cur.right && queue.push(cur.right);
}
}
return res;
};
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.