高频算法面试题

合并两个有序数组

const merge = (nums1, nums2) => {let p1 = 0;let p2 = 0;const result = [];let cur;while (p1 < nums1.length || p2 < nums2.length) {if (p1 === nums1.length) {cur = nums2[p2++];} else if (p2 === nums2.length) {cur = nums1[p1++];} else if (nums1[p1] < nums2[p2]) {cur = nums1[p1++];} else {cur = nums2[p2++];}result[p1 + p2 - 1] = cur;}return result;
}console.log(merge([1, 3, 5], [2, 4, 6, 8]);
// Output: [1, 2, 3, 4, 5, 6, 8 ]

计算数组的所有子集

function subsets(nums) {let result = []result.push([])for (const num of nums) {let newSubsets = []for (const subset of result) {let newSubset = subset.slice()newSubset.push(num)newSubsets.push(newSubset)}result.push(...newSubsets)}return result
}console.log(subsets([1,2,3]))
// Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

实现数组全排列算法

function permute(nums) {let result = [];const backtrack = (arr, set) => {if (set.size === nums.length) {result.push([...set]);return;}for (let i = 0; i < arr.length; i++) {if (set.has(arr[i])) continue;set.add(arr[i]);backtrack(arr, set);set.delete(arr[i]);}}backtrack(nums, new Set());return result;
}// 示例：
console.log(permute([1, 2, 3]));
// Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

SKU 计算（类似于多个数组的排列组合）

function permuteArrays(arrays) {if (arrays.length === 0) return [[]];const currentArray = arrays[0];const remainingArrays = arrays.slice(1);const permutations = [];const permsWithoutCurrent = permuteArrays(remainingArrays);for (let i = 0; i < currentArray.length; i++) {for (let j = 0; j < permsWithoutCurrent.length; j++) {const permutation = [currentArray[i], ...permsWithoutCurrent[j]];permutations.push(permutation);}}return permutations;
}// example usage
const arr1 = [1, 2];
const arr2 = ['a', 'b'];
const arr3 = ['x', 'y'];const allPermutations = permuteArrays([arr1, arr2, arr3]);console.log(allPermutations); // prints [[1, "a", "x"], [1, "a", "y"], [1, "b", "x"], [1, "b", "y"], [2, "a", "x"], [2, "a", "y"], [2, "b", "x"], [2, "b", "y"]

阿拉伯数字转换为中文

function arabicToChinese(num) {var chnNumChar = ["零", "一", "二", "三", "四", "五", "六", "七", "八", "九"];var chnUnitChar = ["", "十", "百", "千", "万", "亿", "万亿", "亿亿"];var strIns = "",chnStr = "";var unitPos = 0;var zero = true;while (num > 0) {var v = num % 10;if (v === 0) {if (!zero) {zero = true;chnStr = chnNumChar[v] + chnStr;}} else {zero = false;strIns = chnNumChar[v];strIns += chnUnitChar[unitPos];chnStr = strIns + chnStr;}unitPos++;num = Math.floor(num / 10);}return chnStr;
}console.log(arabicToChinese(1001));
// Output: 一千零一

把属性名转换为驼峰

let obj = {a_b: {a_b: "a_b",}};function toCamelCase(obj) {if (Array.isArray(obj)) {return obj.map((v) => toCamelCase(v));} else if (obj !== null && typeof obj === "object") {return Object.keys(obj).reduce((result, key) => ({...result,[key.replace(/(_\w)/g, (matches) => matches[1].toUpperCase())]:toCamelCase(obj[key]),}),{});}return obj;
}console.log(toCamelCase(obj))
// Output: { aB: { aB: 'a_b' } }

千位分隔数

var thousandSeparator = function(n) {let count = 0;let ans = "";do {let cur = n % 10;n = Math.floor(n / 10);ans += cur.toString();++count;if (count % 3 == 0 && n) {ans += ',';}} while (n);return ans.split('').reverse().join('');
};console.log(thousandSeparator(1234))
// Output: 1,234

无重复字符的最长子串

var lengthOfLongestSubstring = function(s) {const set = new Set()let max = 0for (let i = 0; i < s.length; i++) {set.clear()for (let j = i; j < s.length; j++) {const item = s[j]if (set.has(item)) {break} else {set.add(item)}}max = Math.max(max, set.size)}return max
};

最长连续递增子序列

var findLengthOfLCIS = function (nums) {let ans = 0;const n = nums.length;let start = 0;for (let i = 0; i < n; i++) {if (i > 0 && nums[i] <= nums[i - 1]) {start = i;}ans = Math.max(ans, i - start + 1);}return ans;
};
console.log(findLengthOfLCIS([1,3,5,4,7]))
// Output: 3

并发数量控制

class Schedule {constructor(maxNum) {this.list = [];this.maxNum = maxNumthis.workingNum = 0}add(promiseCreator) {this.list.push(promiseCreator)}start() {for (let index = 0; index < this.maxNum; index++) {this.doNext()}}doNext() {if (this.list.length && this.workingNum < this.maxNum) {this.workingNum++;const promise = this.list.shift();promise().then(() => {this.workingNum--;this.doNext();})}}
}const timeout = time => new Promise((resolve) => {setTimeout(resolve, time)
})const schedule = new Schedule(2);const addTask = (time, order) => {schedule.add(() => timeout(time).then(() => {console.log(order);}))
}addTask(1000, 1)
addTask(500, 2)
addTask(300, 3)
addTask(400, 4)schedule.start()

字符串相加

function addStrings (num1, num2) {let i = num1.length - 1let j = num2.length - 1let add = 0const ans = []while (i >= 0 || j >= 0 || add !== 0) {const x = i >= 0 ? +num1[i] : 0const y = j >= 0 ? +num2[j] : 0const result = x + y + addans.push(result % 10)add = Math.floor(result / 10)i -= 1j -= 1}return ans.reverse().join('')
}
console.log(addStrings('11', '123'))
// Output: '134'

x 的平方根

var mySqrt = function (x) {let l = 0;let r = x;let ans = -1;while (l <= r) {let mid = (l + r) >> 1;if (mid * mid <= x) {ans = mid;l = mid + 1;} else {r = mid - 1;}}return ans;
};
console.log(mySqrt(4))
// Output: 2

二叉树翻转

function reverse(node) {if (node != null) {let temp = node.left;node.left = node.right;node.right = temp;reverse(node.left);reverse(node.right);}
}

合并二叉树

function mergeTrees(t1, t2) {if (t1 == null)return t2;if (t2 == null)return t1;t1.value += t2.value;let left = mergeTrees(t1.left, t2.left);if (left) {t1.left = left}let right = mergeTrees(t1.right, t2.right);if (right) {t1.right = right}return t1;
}
console.log(mergeTrees(rootA, rootB))

判断对称二叉树

function isSymmetric (root) {return isMirror(root, root)
}function isMirror (t1, t2) {if (t1 == null && t2 == null) return true;if (t1 == null || t2 == null) return false;return (t1.value === t2.value) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right)
}console.log(isSymmetric(node1))

随机打乱算法

function gen(w) {const arr = [];for (let i = 0; i < w * 10000; i++) {arr[i] = i + 1}shuffle(arr)return arr
}// O(n) 的打乱算法
function shuffle(arr) {for (let i = 0; i < arr.length - 1; i++) {// [i, arr.length-1] 取一个整数const j = i + Math.floor(Math.random() * (arr.length - i));[arr[i], arr[j]] = [arr[j], arr[i]]}return arr
}console.log(Math.floor(Math.random() * 5))// 错误写法
function shuffle(arr) {return arr.sort(() => Math.random() - 0.5)
}