目录
柯里化
实现柯里化函数
var currying = function(fn) {
// fn 指官员消化老婆的手段
var args = [].slice.call(arguments, 1);
// args 指的是那个合法老婆
return function() {
// 已经有的老婆和新搞定的老婆们合成一体，方便控制
var newArgs = args.concat([].slice.call(arguments));
// 这些老婆们用 fn 这个手段消化利用，完成韦小宝前辈的壮举并返回
return fn.apply(null, newArgs);
};
};
// 下为官员如何搞定7个老婆的测试
// 获得合法老婆
var getWife = currying(function() {
var allWife = [].slice.call(arguments);
// allwife 就是所有的老婆的，包括暗渡陈仓进来的老婆
console.log(allWife.join(";"));
}, "合法老婆");
// 获得其他6个老婆
getWife("大老婆","小老婆","俏老婆","***蛮老婆","乖老婆","送上门老婆");
// 换一批老婆
getWife("超越韦小宝的老婆");
柯里化函数作用
- 参数复用；2. 提前返回；3. 延迟计算/运行
扁平化
请你编写一个函数，它接收一个 多维数组 arr 和它的深度 n ，并返回该数组的 扁平化 后的结果
// 输入
arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]
// 输出
[1, 2, 3, 4, 5, 6, 7, 8, [9, 10, 11], 12, 13, 14, 15]
n = 1
方法一: Array.flat
方法二: 递归
/*
1. 创建一个递归函数 flattening，该函数接受数组 nums 和层级 l 作为参数
2. 在 flattening 中，我们使用 for...of 循环来迭代 nums 数组的元素
3. 对于每个元素，我们检查它是否是数组以及层级 l 是否在指定范围内（l > 0 且 l <= n）。
如果元素是数组且满足层级条件，我们会递归调用 flattening，并将嵌套数组和层级减小 1（即 l - 1）传递给它。
如果元素不是数组或层级条件不满足，我们将元素推送到结果数组 res 中
*/
// 递归
var flat = function (arr, n) {
const res = [];
const flatting = (nums, l) => {
for(const num of nums) {
if(Array.isArray(num) && l > 0) {
flatting(num, l-1);
} else {
res.push(num)
}
}
}
flatting(arr, n);
return res;
};
// 队列
var flat = function (arr, n) {
let nestedArrayElement = true; // 仍然有嵌套数组需要扁平化
let queue; // 扁平化过程中存储元素
let depth = 0; // 当前深度级别
// 只要还有单个数组元素需要处理（nestedArrayElement 为 true），且深度小于 n
while(nestedArrayElement && depth < n) {
nestedArrayElement = false;
queue = [];
// for 循环遍历数组 arr 中的每个元素
for(let i = 0; i < arr.length; i++) {
// 如果元素是数组，将其元素展开到队列 queue 中
// 并将 nestedArrayElement 设置为 true，表示遇到嵌套数组
if(Array.isArray(arr[i])) {
queue.push(...arr[i]);
nestedArrayElement = true; // 只要还有单个数组元素需要处理
} else {
queue.push(arr[i]);
}
}
// 处理完数组 arr 的所有元素后，将数组 arr 更新为队列中的元素
arr = [...queue];
depth++; // 增加深度 depth
}
return arr;
};
[双指针]有序数组合并
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素
// var merge = function(nums1, m, nums2, n) {
// let i = m - 1; // nums1 行尾
// let j = n -1; // nums2 行尾
// let len = m + n - 1; // 记录被赋值的位置
// while (i >= 0 && j >=0) {
// if (nums1[i] > nums2[j]) {
// nums1[len] = nums1[i];
// i--;
// } else {
// nums1[len] = nums2[j];
// j--;
// }
// len--;
// }
// if (j + 1 !== 0) {
// let restNum2 = nums2.slice(0, j + 1);
// nums1.splice(0, j + 1, ...restNum2);
// }
// return nums1;
// };
/**
解法二
*/
// 从后往前确定两组中该用哪个数字
var merge = function(nums1, m, nums2, n) {
let len = nums1.length - 1;
let i = m - 1;
let j = n - 1;
var update = function(i, j, vi, vj) {
nums1[i] = vi;
nums1[j] = vj;
}
// 第二个数组全都插入进去为止
while (j >= 0) {
while (i >= 0 && nums1[i] > nums2[j]) {
update(i, len, 0, nums1[i]);
i--;
len--;
}
nums1[len] = nums2[j]
j--;
len--;
}
return nums1;
}
判断一个字符串是否是回文字符串
// 双指针 字符串的开头和结尾开始，向中间移动，并比较对应位置的字符是否相同。在比较字符时，可以将字符转换为小写字母来忽略大小写。
var isPalindrome = function(s) {
s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
let left = 0;
let right = s.length - 1;
while(left < right) {
if (s[left] != s[right]) {
return false;
}
left++;
right--;
}
return true;
};
[字符串]两个版本号 version1 和 version2
示例 1：
输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"
示例 2：
输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 "0"
示例 3：
输入：version1 = "0.1", version2 = "1.1"
输出：-1
解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2
/**
* @param {string} version1
* @param {string} version2
* @return {number}
*/
const compareVersion = function (version1, version2) {
const versions1s = version1.split('.');
const versions2s = version2.split('.');
const v1Len = versions1s.length;
const v2Len = versions2s.length;
const len = Math.max(v1Len, v2Len);
let flag = 0;
for (let i = 0; i < len; i++) {
// let x = 0, y = 0;
// if (i < v1Len) {
// x = parseInt(versions1s[i])
// }
// if (i < v2Len) {
// y = parseInt(versions2s[i])
// }
// if (x > y) {
// flag = 1;
// }
// if (x < y) {
// flag = -1;
// }
if ((parseInt(versions1s[i]) || 0) > (parseInt(versions2s[i]) || 0)) {
flag = 1;
break;
}
if ((parseInt(versions1s[i]) || 0) < (parseInt(versions2s[i]) || 0)) {
flag = -1;
break;
}
}
return flag;
};
版本号大小比较排序 ['1.45.0','1.5','6','3.3.3.3.3.3.3'] => ['1.5','1.45.0','3.3.3.3.3.3','6']
function sortVersions(versions) {
return versions.sort(compareVersion);
}
const versions = ['1.45.0', '1.5', '6', '3.3.3.3.3.3.3'];
const sortedVersions = sortVersions(versions);
console.log(sortedVersions);
给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
示例 1:
输入: a = "11", b = "10"
输出: "101"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
// 逐位相加的方法，并考虑进位
var addBinary = function (a, b) {
let result = '';
let carry = 0;
let i = a.length - 1;
let j = b.length - 1;
while (i >= 0 || j >= 0 || carry > 0) {
const digitA = i >= 0 ? parseInt(a[i]) : 0;
const digitB = j >= 0 ? parseInt(b[j]) : 0;
const sum = digitA + digitB + carry;
result = (sum % 2) + result;
carry = Math.floor(sum / 2);
i--;
j--;
}
return result;
};
[双指针 哈希]无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子字符串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
var lengthOfLongestSubstring1 = function(s) {
if (s === '') {
return 0;
}
if (s.length === 1) {
return 1;
}
let i = 0; // 左指针
let j = i + 1; // 右指针
const results = []; // 记录长度 最终选择最长的输出
while(j < s.length) {
let temRes = s[i] + '';
while (!temRes.includes(s[j]) && j < s.length) {
temRes+= s[j];
j++;
}
let curLen = j - i;
results.push(curLen);
i = i + 1;
j = i + 1;
}
const max = results.reduce((pre, cur, initial) => {
return pre > cur ? pre : cur;
});
return max;
};
var lengthOfLongestSubstring = function(s) {
// hash集合
const hash = new Set();
let rp = -1; // 右指针
let temp = 0; // 比较的结果
const len = s.length;
for (i = 0; i < len; i++) {
if (i !== 0) {
hash.delete(s[i - 1]);
}
while (rp + 1 < len && !hash.has(s[rp + 1])) {
hash.add(s[rp + 1]);
rp++;
}
temp = Math.max(temp, rp - i + 1);
}
return temp;
};
[哈希]两数之和
给定一个整数数组 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]
var twoSum1 = function(nums, target) {
const len = nums.length;
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
};
var twoSum2 = function(nums, target) {
const len = nums.length;
let rp = 0;
for (let i = 0; i < len; i++) {
rp = i + 1;
while (rp < len) {
if (nums[i] + nums[rp] === target) {
return [i, rp];
}
rp++;
}
}
return [];
};
// hash
var twoSum = function(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
if (map.has(target - nums[i])) {
return [map.get(target - nums[i]), i];
}
map.set(nums[i], i);
}
return [];
};
[栈]有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
/**
判断字符串是否有效的问题可以使用栈来解决。我们可以遍历字符串，当遇到左括号时，将其压入栈中；当遇到右括号时，检查栈顶元素是否与当前右括号匹配。如果匹配，则将栈顶元素弹出，继续遍历；如果不匹配或者栈为空，则说明字符串无效。最后，如果栈为空，且字符串遍历完毕，则字符串有效。
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
const stack = [];
const pairs = {
'{': '}',
'[': ']',
'(': ')',
};
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (char === '(' || char === '[' || char === '{') {
stack.push(char);
} else {
const top = stack.pop();
if (pairs[top] !== char) {
return false;
}
}
}
return stack.length === 0;
};
[双指针]三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
解决这个问题的一种常见方法是使用双指针。首先，对数组进行排序，然后遍历排序后的数组。在遍历过程中，固定一个元素，然后使用双指针从当前元素的下一个位置和数组末尾开始向中间移动，寻找满足条件的三个元素
var threeSum = function (nums) {
const result = [];
let sortNums = nums.sort((a, b) => a - b);
const len = sortNums.length
for (let i = 0; i < len - 2; i++) {
let m = i + 1;
let n = len - 1;
let cur = nums[i];
while (m < n) {
const sum = cur + nums[m] + nums[n];
if (sum === 0) {
result.push([cur, nums[m], nums[n]]);
// 跳过重复的元素
while (m < n && nums[m] === nums[m+1]) {
m++;
}
while (m < n && nums[n] === nums[n-1]) {
n--;
}
m++;
n--;
} else if(sum < 0) {
m++;
} else {
n--;
}
}
}
return Array.from(new Set(result.map(JSON.stringify)), JSON.parse);
};
[回溯 递归] 全排列 (再A一遍)
给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
/**回溯算法来生成全排列。通过不断地选择一个数字，将其添加到当前排列中，并递归生成剩余数字的排列，然后撤销选择，继续尝试下一个数字，直到所有数字都被使用。最终，所有可能的排列都被生成并存储在 result 数组中，然后返回给调用者。
* @param {number[]} nums
* @return {number[][]}
*/
function permute(nums) {
const result = [];
function backtrack(current, remaining) {
if (remaining.length === 0) {
result.push(current.slice()); // 将当前排列添加到结果中
return;
}
for (let i = 0; i < remaining.length; i++) {
const num = remaining[i];
current.push(num); // 将当前数字添加到当前排列中
remaining.splice(i, 1); // 从剩余数字中移除当前数字
backtrack(current, remaining); // 递归生成排列
remaining.splice(i, 0, num); // 恢复剩余数字的原始顺序
current.pop(); // 移除当前数字
}
}
backtrack([], nums);
return result;
}
[排序 二分]手撕快速排序
/*快速排序*/
function quikSort(arr) {
if (arr.length <= 1) {
return arr;
}
//取中间数值
var standardNum = arr.splice(Math.floor(arr.length / 2), 1);
var leftArr = [];
var rightArr = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] <= standardNum[0]) {
leftArr.push(arr[i]);
} else {
rightArr.push(arr[i]);
}
}
return quikSort(leftArr).concat(standardNum, quikSort(rightArr));
}
quikSort([5, 100, 6, 3, -12]); //[-12, 3, 5, 6, 100]
//冒泡
function sort(arr) {
for(let i = 1; i < arr.length; i++) {
for(let j = 0; j < i; j++) {
if(arr[j] > arr[i]) {
let temp;
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
console.log(arr)
return arr;
}