//得到支点下标
function partition(arr, low, high) {
const tmp = arr[low];
while (low < high) {
//high位置值大于tmp，high自减
while (low < high && arr[high] >= tmp) {
high--;
}
arr[low] = arr[high];
//位置值小于tmp，low自增
while (low < high && arr[low] < tmp) {
low++;
}
arr[high] = arr[low];
}
//将支点值赋给high位置
arr[high] = tmp;
//返回支点下标
return high;
}
//非递归快速排序
export function quickSort(arr, start = 0, end = arr.length - 1) {
const stack = [];
stack.push(start);
stack.push(end);
let low = 0,
high = 0;
//栈不为空，继续操作
while (stack.length) {
//获取栈中区间下标
high = stack.pop();
low = stack.pop();
//获取支点下标
const par = partition(arr, low, high);
//如果区间长度大于1，则区间两端下标入栈
if (par > low + 1) {
stack.push(low);
stack.push(par - 1);
}
if (par + 1 < high) {
stack.push(par + 1);
stack.push(high);
}
}
}
//冒泡插入归并是稳定排序
//冒泡排序 升序
export function bubbleSort(arr) {
for(let i = 0; i < arr.length; i++) {
for(let j = i; j < arr.length; j++) {
if(arr[i] > arr[j]) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
}
}
//插入排序，将当前值与前面已排列好的数组中对应位置交换
export function insertSort(arr) {
for(let i = 0; i < arr.length; i++) {
for(let j = i; j > 0; j--) {
if(arr[j] < arr[j - 1]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
} else {
break;
}
}
}
}
//选择排序, 选取剩余序列中最小的值与对应位置交换
export function selectSort(arr) {
for(let i = 0; i < arr.length; i++) {
let minIndex = i;
for(let j = i; j < arr.length; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
//交换最小的与最前面的值
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
//大数相加
export function bigDataAdd(s, t) {
const maxLength = Math.max(s.length, t.length);
const sArr = s.padStart(maxLength, '0').split('');
const tArr = t.padStart(maxLength, '0').split('');
let carry = 0;
const result = [];
for(let i = maxLength - 1; i > 0; i--) {
const sum = parseInt(sArr[i]) + parseInt(tArr[i]) + carry;
carry = sum > 10 ? 1 : 0;
result.push(sum % 10);
}
if(carry != 0) {
result.push(carry);
}
return result.reverse().join('');
}
//找到数组里只出现一次的数, 相同的数异或自己是0，0异或一个数是那个数
export function getOnceNum(arr) {
if(arr.length == 1) {
return arr[0];
}
let resultNum = 0;
for(let i =0; i < arr.length; i++) {
resultNum ^= arr[i];
}
return resultNum;
}
//找到数组里出现最多的类型, 返回类型数组和数量
export function getMostType(arr) {
const typeMap = {};
let num = 0;
for(let i = 0; i < arr.length; i++) {
const type = typeof arr[i];
if(typeMap[type]) {
typeMap[type] ++;
} else {
typeMap[type] = 1;
}
num = typeMap[type] > num ? typeMap[type]: num;
}
const result = [];
for(const key in typeMap) {
if(typeMap[key] == num) {
result.push(key);
}
}
result.push(num);
}
//手写new函数
export function myNew() {
const obj = new Object();
const context = [].shift.call(arguments);
obj.__proto__ = context.protoType;
const result = context.apply(obj, arguments);
return typeof result === 'object' ? result : obj;
}
//手写call函数
export function newCall() {
const [context, ...args] = [...arguments];
context.fn = this;
const res = context.fn(args);
delete context.fn;
return res;
}
//手写apply函数, apply函数有两个参数，可以不用解析
export function newApply(context, args) {
context.fn = this;
const res = args ? context.fn(args) : context.fn();
delete context.fn;
return res;
}
//手写bind函数
export function newBind(context) {
const _self = this;
const args = Array.prototype.slice(arguments, 1);
return function() {
const bindArgs = Array.prototype.slice.apply(arguments);
return _self.apply(context, [...args, ...bindArgs]);
}
}
//反转字符串
export function reverseStr(str) {
if(str.length == 1) {
return str;
}
const stack = [];
for(let i = str.length - 1; i >= 0; i--) {
stack.push(str[i]);
}
let result = '';
while(stack.length) {
result += stack.shift(stack[0]);
}
return result;
}
//最长不重复子串
export function maxUniqueSubStr(str) {
if(!str) {
return 0;
}
const stack = [];
let left = 0;
let result = 0;
let currentLength = 0;
while(left < str.length) {
currentLength ++;
while(stack.includes(str[left])) { //出现重复字符了，左侧出栈，直到无重复字符
stack.shift();
currentLength --;
}
if(currentLength > result) {
result = currentLength;
}
stack.push(str[left]);
left ++;
}
return result;
}
//输出倒计时, 可能会有误差delay
export function logCountDown(endDateStr) {
const endDate = new Date(endDateStr).getTime();
const nowDate = new Date().getTime();
const second = Math.floor((endDate - nowDate) / 1000 % 60);
const minute = Math.floor((endDate - nowDate) / 1000 / 60 % 60);
const hour = Math.floor((endDate - nowDate) / 1000 / 60 / 60 % 24);
console.log(`${ hour }-${ minute }-${ second }`);
}
setInterval(() => {
logCountDown('2023-03-23 12:00:00');
}, 1000);
//KMP算法看不懂我要死了啊啊啊啊啊啊啊啊啊
//二分法找元素下标
export function binarySearch(arr, key, left, right) {
left = left ? left : 0;
right = right ? right : arr.length - 1;
while(left <= right) {
const mid = Math.floor((left + right) / 2);
if(arr[mid] < key) {
left = mid + 1;
} else if(arr[mid] > key) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
//最长回文子串
export function longestPalindrome(s) {
let start = 0, end = 0;
const n = s.length;
let i = 0;
while (i < n) {
let left = i, right = i;
//如果后面有连续相同字符，把right向右扩展到最后一个相同字符的位置，
//并把i设置到该位置的下一个位置。
//因为每次循环i左边的字符一定和i不相同，所以不需要将left向左扩展
while (right < n - 1 && s.charAt(right + 1) == s.charAt(left)) {
right++;
}
i = right + 1;
while (left > -1 && right < n && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if (right - left - 1> end - start) {
end = right;
start = left + 1;
}
}
return s.substring(start, end);
}
//二叉树搜素
export function searchNode(root, value) {
let node = root;
while(node && node.val != value) {
node = node.val > value ? node.left : node.right;
}
return node;
}
//给定一个字符串，输出全排列 abc 输出 [abc,acb,bac,bca,cab,cba]
//回溯法
export function perMutation(str) {
const res = new Set();
const myPor = (old, str) => {
if(str.length == 0) {
res.add(old);
}
for(let i = 0; i < str.length; i++) {
const copy = [...str];
copy.splice(i, 1);
myPor(old + str[i], copy);
}
}
myPor('', str.split(''));
return res;
}
//手撕节流
export function throttle(fn, wait) {
let last = null;
return function() {
const now = new Date().getTime();
//初次执行
if(!last) {
fn.apply(this, arguments);
last = now;
return;
}
//后续触发
if(now - last >= wait) {
fn.apply(this, arguments);
last = now;
}
}
}
//手撕防抖
export function debounce(fn, delay) {
let timer = null;
return function () {
const args = arguments;
if(timer) {
clearTimeout(timer);
timer = null;
}
timer = setTimeout(() => {
fn.apply(this, args);
timer = null;
}, delay)
}
}
//手撕instanceof
export function myInstanceOf(leftObj, rightObj) {
let leftProtoType = Object.getPrototypeOf(leftObj);
const rightProtoType = rightObj.prototyppe;
while(leftProtoType) {
if(leftProtoType === rightProtoType) {
return true;
}
leftProtoType = Object.getPrototypeOf(leftProtoType);
}
return false;
}
//模拟promise.all
// const p1 = function() {
// return new Promise((resolve) => {
// setTimeout(() => {
// resolve(100);
// },100);
// })
// }
// const p2 = function() {
// return new Promise((resolve) => {
// setTimeout(() => {
// resolve(200);
// },100);
// })
// }
export function promiseAll(tasks) {
const arr = new Array(tasks.length).fill(0).map(() => {
return { val: undefined, success: false };
});
return new Promise((resolve, reject) => {
for(let i = 0; i < tasks.length; i++) {
tasks[i]().then(res => {
arr[i].val = res.value;
arr[i].success = true;
if(arr.every(item => {
item.success == true;
})) {
resolve(arr.map(item => item.val));
}
}).catch(err => {
reject(err);
})
}
})
}
//接雨水 leetcode 42
export function waterHeight(arr) {
let count = 0;
let leftMax = 0, rightMax = 0;
let left = 0, right = arr.length -1;
while(left < right) {
if(arr[left] > leftMax) {
leftMax = arr[left];
}
if(arr[right] > rightMax) {
rightMax = arr[right];
}
if(leftMax < rightMax) {
count += leftMax - arr[left];
left ++;
} else {
count += rightMax - arr[right];
right--
}
}
return count;
}
//最少硬币个数
export function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(null);
for(let i = 0; i < coins.length; i++) {
for(let j = 0; j <= amount; j++) {
if(j >= coins[i]) {
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
}
return dp[amount];
}
//硬币最多组合数
export function maxCoins(coins, amount) {
const dp = new Array(amount + 1).fill(null);
dp[0] = 1;
for(let i = 0; i < coins.length; i++) {
for(let j = 0; j <= amount; j++) {
if(j >= coins[i]) {
dp[j] = dp[j] + dp[j - coins[i]];
}
}
}
return dp[amount];
}
//层次遍历二叉树
export function levelOrder(root) {
if(!root) {
return [];
}
const result = [];
BFSTree(result, root, 0);
return result;
}
function BFSTree(result, root, level) {
if(result.length == level) {
result.push([]);
}
result[level].push(root.val);
if(root.left) {
BFSTree(result, root.left, level + 1);
}
if(root.right) {
BFSTree(result, root.right, level + 1);
}
}
//螺旋矩阵,入参为二维数组
export function SpiralOrder(arr) {
if(!arr.length || !arr[0].length) {
return [];
}
const result = [];
let top = 0, bottom = arr.length - 1, left = 0, right = arr[0].length - 1;
// eslint-disable-next-line no-constant-condition
while(true) {
for(let i = left; i <= right; i++){
result.push(arr[top][i]);
}
if(++top > bottom) {
break;
}
for(let i = top; i <= bottom; i++) {
result.push(arr[i][right]);
}
if(--right < left) {
break;
}
for(let i = right; i >= left; i--) {
result.push(arr[bottom][i]);
}
if(--bottom < top) {
break;
}
for(let i = bottom; i >= top; i--) {
result.push(arr[i][left]);
}
if(++left > right) {
break;
}
}
return result;
}
//盛最多水的容器leetcode hot100
export function moreWater(height) {
let res = 0;
let left = 0, right = height.length - 1;
while(left < right) {
const area = (right - left) * Math.min(height[left], height[right]); //高度较低的乘以距离就是可以盛的水
res = Math.max(res, area);
if(height[left] < height[right]) {
left++;
} else {
right--;
}
}
return res;
}
//生成括号
export function generateParenthesis(n) {
const result = [];
DFSGP('', n, n, result);
return result;
}
function DFSGP(str, left, right, result) { //左右括号的数量
if(left > right || left < 0) {
return;
}
if(left == 0 && right == 0) {
result.push(str);
}
// eslint-disable-next-line prefer-template
DFSGP(str + '(', left - 1, right, result);
// eslint-disable-next-line prefer-template
DFSGP(str + ')', left, right - 1, result);
}
//环形链表
export function circleLinkList(arr) {
const result = new Set();
for(let i = 0; i < arr.length; i++) {
if(result.has(arr[i])) {
return true;
}
result.add(arr[i]);
}
return false;
}