function quickSort(arr, left, right) {if (left >= right) return
const base = arr[left]
let p = left, q = right
while (p < q) {while (arr[q] > base && q >= p) {q--}
while (arr[p] < base && p <= q) {p++}
const temp = arr[q]
arr[q] = arr[p]
arr[p] = temp
}
arr[p] = base
quickSort(arr, left, p)
quickSort(arr, p + 1, right)
}
function mergeSort(arr) {if (arr.length <= 1) return arr
const mid = Math.floor(arr.length / 2)
const left = arr.slice(0, mid)
const right = arr.slice(mid)
const leftArr = mergeSort(left)
const rightArr = mergeSort(right)
const result = []
while (leftArr.length > 0 && rightArr.length > 0) {if (leftArr[0] < rightArr[0]) {result.push(leftArr.shift())
} else {result.push(rightArr.shift())
}
}
return result.concat(leftArr).concat(rightArr)
}
var twoSum = function (nums, target) {let hash = {};
for (let i = 0; i < nums.length; i++) {if (hash[target - nums[i]] !== undefined) {return [i, hash[target - nums[i]]];
}
hash[nums[i]] = i;
}
return [];};
var threeSum = function(nums) {
const len = nums.length;
if(len < 3) return [];
nums.sort((a, b) => a - b);
const resSet = new Set();
for(let i = 0; i < len - 2; i++) {if(nums[i] > 0) break;
let l = i + 1, r = len - 1;
while(l < r) {const sum = nums[i] + nums[l] + nums[r];
if(sum < 0) {l++; continue};
if(sum > 0) {r--; continue};
resSet.add(`${nums[i]},${nums[l]},${nums[r]}`);
l++;
r--;
}
}
return Array.from(resSet).map(i => i.split(","));
};
var search = function(nums, target) {
let left = 0, right = nums.length - 1;
// 应用左闭右闭区间
while (left <= right) {let mid = left + Math.floor((right - left)/2);
if (nums[mid] > target) {right = mid - 1; // 去右面闭区间寻找} else if (nums[mid] < target) {left = mid + 1; // 去右面闭区间寻找} else {return mid;}
}
return -1;
};
var generateMatrix = function(n) {
let startX = startY = 0; // 起始地位
let loop = Math.floor(n/2); // 旋转圈数
let mid = Math.floor(n/2); // 两头地位
let offset = 1; // 管制每一层填充元素个数
let count = 1; // 更新填充数字
let res = new Array(n).fill(0).map(() => new Array(n).fill(0));
while (loop--) {
let row = startX, col = startY;
// 上行从左到右（左闭右开）for (; col < startY + n - offset; col++) {res[row][col] = count++;
}
// 右列从上到下（左闭右开）for (; row < startX + n - offset; row++) {res[row][col] = count++;
}
// 上行从右到左（左闭右开）for (; col > startX; col--) {res[row][col] = count++;
}
// 左列做下到上（左闭右开）for (; row > startY; row--) {res[row][col] = count++;
}
// 更新起始地位
startX++;
startY++;
// 更新 offset
offset += 2;
}
// 如果 n 为奇数的话，须要独自给矩阵最两头的地位赋值
if (n % 2 === 1) {res[mid][mid] = count;
}
return res;
};
var merge = function(nums1, m, nums2, n) {
let p1 = m - 1, p2 = n - 1;
let tail = m + n - 1;
var cur;
while (p1 >= 0 || p2 >= 0) {if (p1 === -1) {cur = nums2[p2--];
} else if (p2 === -1) {cur = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {cur = nums1[p1--];
} else {cur = nums2[p2--];
}
nums1[tail--] = cur;
}
};
function shuffle(arr) {
var i, j, temp;
for (i = arr.length - 1; i > 0; i--) {j = Math.floor(Math.random() * (i + 1));
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return arr;
}
// 这个实现有问题
function shuffle(arr){return arr.sort(function(){return Math.random() - 0.5;
});
}
var addStrings = function (num1, num2) {const result = []
let p = num1.length - 1
let q = num2.length - 1
let add = 0
while (p >= 0 || q >= 0 || add) {const x = p >= 0 ? Number(num1[p]) : 0
const y = q >= 0 ? Number(num2[q]) : 0
const sum = x + y + add
result.unshift(sum % 10)
add = Math.floor(sum / 10)
p--
q--
}
return result.join('')
};
var thousandSeparator = function(n) {
let res = ''
let count = 0
const str = n.toString()
const len = str.length
for(let i = len - 1; i >= 0; i--) {
count++
if (count % 3 === 0 && i !== 0) {res = '.' + str[i] + res
} else {res = str[i] + res
}
}
return res
};
var isValid = function(s) {
const n = s.length;
if (n % 2 === 1) {return false;}
const pairs = new Map([[')', '('],
[']', '['],
['}', '{']
]);
const stk = [];
for (let ch of s){if (pairs.has(ch)) {if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {return false;}
stk.pop();}
else {stk.push(ch);
}
};
return !stk.length;
};
var reverseList = function(head) {
let pre = null
let cur = head
while(cur !== null) {
const temp = cur.next
cur.next = pre
pre = cur
cur = temp
}
return pre
};
var removeNthFromEnd = function(head, n) {let ret = new ListNode()
ret.next = head
let p = ret, q = ret
// p 先后退 N
while(n--) {p = p.next}
// p 遍历到尾结点
while(p.next !== null) {
p = p.next
q = q.next
}
q.next = q.next.next
return ret.next
};
var mergeTwoLists = function(l1, l2) {const prehead = new ListNode(-1);
let prev = prehead;
while (l1 != null && l2 != null) {if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，咱们间接将链表开端指向未合并完的链表即可
prev.next = l1 === null ? l2 : l1;
return prehead.next;
};
// 递归
var preorderTraversal = function(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;
};
// 迭代
var preorderTraversal = function(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;
};
var levelOrder = function(root) {
// 二叉树的层序遍历
let res=[],queue=[];
queue.push(root);
if(root===null){return res;}
while(queue.length!==0){
// 记录以后层级节点数
let length=queue.length;
// 寄存每一层的节点
let curLevel=[];
for(let i=0;i<length;i++){let node=queue.shift();
curLevel.push(node.val);
// 寄存以后层下一层的节点
node.left&&queue.push(node.left);
node.right&&queue.push(node.right);
}
// 把每一层的后果放到后果数组
res.push(curLevel);
}
return res;
};
var maxdepth = function(root) {if (!root) return root
return 1 + math.max(maxdepth(root.left), maxdepth(root.right))
};
var lowestCommonAncestor = function(root, p, q) {
// 应用递归的办法
// 须要从下到上，所以应用后序遍历
// 1. 确定递归的函数
const travelTree = function(root,p,q) {
// 2. 确定递归终止条件
if(root === null || root === p||root === q) {return root;}
// 3. 确定递归单层逻辑
let left = travelTree(root.left,p,q);
let right = travelTree(root.right,p,q);
if(left !== null&&right !== null) {return root;}
if(left ===null) {return right;}
return left;
}
return travelTree(root,p,q);
};
var isSymmetric = function(root) {
// 应用递归遍历左右子树 递归三部曲
// 1. 确定递归的参数 root.left root.right 和返回值 true false
const compareNode=function(left,right){
//2. 确定终止条件 空的状况
if(left===null&&right!==null||left!==null&&right===null){return false;}else if(left===null&&right===null){return true;}else if(left.val!==right.val){return false;}
//3. 确定单层递归逻辑
let outSide=compareNode(left.left,right.right);
let inSide=compareNode(left.right,right.left);
return outSide&&inSide;
}
if(root===null){return true;}
return compareNode(root.left,root.right);
};
// 输出：A: [1,2,3,2,1] B: [3,2,1,4,7] 输入：3 解释：长度最长的公共子数组是 [3, 2, 1]。const findLength = (A, B) => {
// A、B 数组的长度
const [m, n] = [A.length, B.length];
// dp 数组初始化，都初始化为 0
const dp = new Array(m + 1).fill(0).map(x => new Array(n + 1).fill(0));
// 初始化最大长度为 0
let res = 0;
for (let i = 1; i <= m; i++) {for (let j = 1; j <= n; j++) {// 遇到 A[i - 1] === B[j - 1]，则更新 dp 数组
if (A[i - 1] === B[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;
}
// 更新 res
res = dp[i][j] > res ? dp[i][j] : res;
}
}
// 遍历实现，返回 res
return res;
};
// 输出：text1 = "abcde", text2 = "ace" 输入：3 解释：最长公共子序列是 "ace"，它的长度为 3。const longestCommonSubsequence = (text1, text2) => {let dp = Array.from(Array(text1.length+1), () => Array(text2.length+1).fill(0));
for(let i = 1; i <= text1.length; i++) {for(let j = 1; j <= text2.length; j++) {if(text1[i-1] === text2[j-1]) {dp[i][j] = dp[i-1][j-1] +1;;
} else {dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
}
}
}
return dp[text1.length][text2.length];
};
const findLengthOfLCIS = (nums) => {let dp = Array(nums.length).fill(1);
for(let i = 0; i < nums.length - 1; i++) {if(nums[i+1] > nums[i]) {dp[i+1] = dp[i]+ 1;
}
}
return Math.max(...dp);
};
var longestPalindrome = function (s) {
const len = s.length
if (len < 2) return s
let max = 0
let str = s[0]
const dp = Array.from(new Array(len), () => new Array(len))
for(let j=0; j< len; j++) {for(let i=0; i<j; i++) {dp[i][j] = s[i] === s[j] && (j - i < 3 || dp[i+1][j-1])
if(dp[i][j] && j -i + 1 > max) {
max = j - i + 1
str = s.substring(i, j+1)
}
}
}
return str
}
const longestPalindromeSubseq = (s) => {
const strLen = s.length;
let dp = Array.from(Array(strLen), () => Array(strLen).fill(0));
for(let i = 0; i < strLen; i++) {dp[i][i] = 1;
}
for(let i = strLen - 1; i >= 0; i--) {for(let j = i + 1; j < strLen; j++) {if(s[i] === s[j]) {dp[i][j] = dp[i+1][j-1] + 2;
} else {dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][strLen - 1];
};
function sub(arr) {
let max = 0
let base = 0
const has = new Map()
for(let i = 0; i < arr.length; i++) {const cur = arr[i]
if (hash.hash(cur)) {base = Math.max(base, has.get(cur) + 1)
}
hast.set(cur, i)
max = Math.max(max, i - base + 1)
}
return max
}
function largestSum(arr) {let max = Number.MIN_SAFE_INTEGER, fmin = arr[0], fmax= arr[0]
for(let num of arr) {if (num < 0) {
const temp = fmax
fmax = fmin
fmin = temp
}
fmin = Math.min(fmin*num, num)
fmax = Math.max(fmax*num, num)
max = Math.max(max, fmax)
}
return max
}
function minCount(days, cost) {
const len = days.length
let maxDay = days[len - 1], minDay = days[0]
let dp = new Array(maxDay + 31).fill(0)
for(let d = maxDay, i = len -1; d >= minDay; d--) {if (days[i] === d) {dp[d] = Math.min(dp[d + 1] + cost[0], dp[d+7] + cost[1], dp[d+30]+cost[2])
i--
} else {dp[d] = dp[d+1]
}
}
return dp[minDay]
}