前端基础，深入以及算法数据结构
字节跳动长期招聘各个岗位的员工，扫下面二维码直接进入内推渠道，反馈快哦~~
不清楚投哪个岗位，也可以发简历到我邮箱 [email protected] ，由我来帮你选择合适的岗位~~~
[16、JS执行上下文] (待完成)
[17、JavaScript异步编程]（待完成）
[2、实现一个模板引擎] (待完成)
[3、webpack原理] (待完成)
[6、灰度发布] (待完成)
[7、Vuex原理] (待完成)
[8、VueRouter原理] (待完成)
[2、React diff算法] (待完成)
[4、ReactRouter原理] (待完成)
出处：LeetCode 算法第30题
给定一个字符串 s 和一些长度相同的单词 **words。**在 s 中找出可以恰好串联 words 中所有单词的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1:
输入: s = "barfoothefoobarman", words = ["foo","bar"] 输出: [0,9] 解释: 从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。 输出的顺序不重要, [9,0] 也是有效答案。示例 2:
输入: s = "wordgoodstudentgoodword", words = ["word","student"] 输出: []
方法一，将words拼成字符串，去s里面寻找是否匹配，但是时间复杂度太高，数据多的时候会超时
方法二，由于单词的长度是固定的，所以可以在s中截取单词长度的字符串，去匹配words中的单词
方法一
/**
* @param {string} s
* @param {string[]} words
* @return {number[]}
*/
function copy(array) {
var result = [];
for (var i = 0, len = array.length; i < len; i++) {
result.push(array[i]);
}
return result;
}
var findSubstring = function (s, words) {
var result = [];
if (s.length == 0 || words.length == 0) {
return result;
}
var length = words.length;
var wordString = words.join('');
var wordLength = wordString.length;
if (s.length === wordLength && (s.indexOf(wordString) >= 0)) {
result.push(s.indexOf(wordString));
} else {
var oneWordLength = words[0].length;
var temp = [];
for (var i = 0; i < length; i++) {
temp.push(words[i]);
var copyWords = copy(words);
copyWords[i] = '';
DFS(s, length, temp, result, copyWords, oneWordLength);
temp.pop();
}
}
return Array.from(new Set(result));
};
function DFS(s, length, temp, result, copyWords, oneWordLength) {
if (temp.length == length) {
var tempValue = temp.join('');
for (var i = 0; i <= s.length - oneWordLength; i += oneWordLength) {
var index = s.indexOf(tempValue, i);
if (index >= 0) {
result.push(index);
}
}
}
var empty = true;
for (var j = 0; j < copyWords.length; j++) {
if (copyWords[j] != '') {
empty = false;
}
}
while (!empty) {
for (var i = 0; i < copyWords.length; i++) {
if (copyWords[i] != '') {
var tempValue = copyWords[i];
temp.push(copyWords[i]);
copyWords[i] = '';
DFS(s, length, temp, result, copyWords, oneWordLength);
for (var j = 0; j < copyWords.length; j++) {
if (copyWords[j] != '') {
empty = false;
} else {
empty = true;
}
}
temp.pop();
copyWords[i] = tempValue;
}
}
}
}方法二
var findSubstring2 = function(s, words) {
var result = [];
if(words.length===0)return result;
let len = words[0].length;
function find(str){
let s,begin = 0;
while(str.length >= len){
s = str.substr(0,len);
let index = words.indexOf(s,begin);
if(index >= 0){
let tmp = words[begin];
words[begin] = words[index];
words[index] = tmp;
begin++;
str=str.substr(len);
if(begin==words.length) return true;
}else{
return false;
}
}
}
for (let i=0;i<=s.length-len;i++){
if(find(s.substr(i))) result.push(i);
}
return result;
};出处：LeetCode 算法第11题
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。画 n 条垂直线，使得垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
**注意：**你不能倾斜容器，n 至少是2。
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
经典的木桶问题，能盛水的多少取决于短边的高度。
暴力破解，使用时间复杂度为O(n^2)的算法
var maxArea = function (height) {
var maxArea = 0;
var low = 0, high = height.length;
for (var i = low; i < high - 1; i++) {
for (var j = i + 1; j < high; j++) {
var result = 0;
if (height[i] < height[j]) {
result = (j - i) * height[i];
} else {
result = (j - i) * height[j]
}
if (result > maxArea) {
maxArea = result
}
}
}
return maxArea;
};从数组两边向中间靠拢，记录每一次计算的面积，当左边小于右边时，使左边向右移动，因为此时右边不管怎么动，左边已经决定了面积的大小，除非右边移动后比左边还要小，但这是获取的面积只会更小。反之亦然。只需一遍遍历即可，时间复杂度为O(n)
var maxArea2 = function (height) {
var maxArea = 0;
var low = 0, high = height.length - 1;
while (low < high) {
maxArea = Math.max(maxArea, Math.min(height[low], height[high]) * (high - low));
if (height[low] < height[high]) {
low++;
} else {
high--;
}
}
return maxArea;
}出处：LeetCode 算法第56题
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2:
输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
对所有项按start大小进行排序，遍历所有的项。
/**
* Definition for an interval.
* function Interval(start, end) {
* this.start = start;
* this.end = end;
* }
*/
/**
* @param {Interval[]} intervals
* @return {Interval[]}
*/
var merge = function (intervals) {
if (intervals.length <= 1) {
return intervals;
}
var result = [];
intervals.sort(function (a, b) {
return a.start - b.start;
});
var start = intervals[0].start;
var end = intervals[0].end;
for (var i = 0; i < intervals.length; i++) {
if (intervals[i].start <= end) {
end = Math.max(end, intervals[i].end);
} else {
result.push(new Interval(start, end));
start = intervals[i].start;
end = intervals[i].end;
}
}
result.push(new Interval(start, end));
return result;
};出处：LeetCode 算法第93题
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]
典型的深度遍历，遍历所有的可能
/**
* @param {string} s
* @return {string[]}
*/
function restoreIpAddresses(s) {
const res = [];
dfs([], 0);
return res;
function dfs(prefix, idx) {
if (prefix.length === 4 && idx === s.length) {
res.push(prefix.join('.'));
return;
}
if (prefix.length === 4 || idx === s.length) {
return;
}
for (let r = idx; r < s.length; r++) {
if (r !== idx && s[idx] === '0') return;
const num = parseInt(s.slice(idx, r + 1));
if (num > 255) {
return;
}
prefix.push(num);
dfs(prefix, r + 1);
prefix.pop();
}
}
}出处：LeetCode 算法第29题
给定两个整数，被除数
dividend和除数divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数
dividend除以除数divisor得到的商。示例 1:
输入: dividend = 10, divisor = 3 输出: 3示例 2:
输入: dividend = 7, divisor = -3 输出: -2说明:
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
由于不能使用乘法除法，我们可以使用减法来计算被除数包含几个除数，但当数值很大的时候直接循环做减法会花费很长的时间，所以可以使用位移运算符每次使除数加倍，让被除数减去位移后不超过被除数的最大除数，记录位移的次数。但即使这样使用JS也无法AC，寻求更好的解法。
var divide = function (dividend, divisor) {
var sign = ((dividend < 0) ^ (divisor < 0)) ? true : false;
var divid = Math.abs(dividend);
var divis = Math.abs(divisor);
var result = 0;
if (divid < divis) {
return result;
}
while (divid >= divis) {
var temp = divis, p = 1;
while (divid >= (temp << 1)) {
temp = temp << 1;
p = p << 1;
}
divid -= temp;
result += p;
}
return sign ? -result : result;
};出处：LeetCode 算法第8题
实现
atoi，将字符串转为整数。在找到第一个非空字符之前，需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号，选取该符号，并将其与后面尽可能多的连续的数字组合起来，这部分字符即为整数的值。如果第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
字符串可以在形成整数的字符后面包括多余的字符，这些字符可以被忽略，它们对于函数没有影响。
当字符串中的第一个非空字符序列不是个有效的整数；或字符串为空；或字符串仅包含空白字符时，则不进行转换。
若函数不能执行有效的转换，返回 0。
说明：
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。如果数值超过可表示的范围，则返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42" 输出: 42示例 2:
输入: " -42" 输出: -42 解释: 第一个非空白字符为 '-', 它是一个负号。 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。示例 3:
输入: "4193 with words" 输出: 4193 解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。示例 4:
输入: "words and 987" 输出: 0 解释: 第一个非空字符是 'w', 但它不是数字或正、负号。 因此无法执行有效的转换。示例 5:
输入: "-91283472332" 输出: -2147483648 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。
首先通过正则去除收尾部的空白字符，并提取从头开始的数字。判断数字正负以及长度，考虑所有情况
/**
* @param {string} str
* @return {number}
*/
var myAtoi = function (str) {
var INT_MAX = Math.pow(2, 31) - 1;
var INT_MIN = Math.pow(-2, 31);
var string = str.replace(/^(\s+)|(\s+)$/g, '');
var match = /^(?:\-|\+)?(\d+)/.exec(string);
if (match) {
var sign = (string.charAt(0) == '-') ? -1 : 1;
var digits = match[1];
var carry = Math.floor(INT_MAX / 10);
var remainder = INT_MAX - carry * 10 - (sign == 1 ? 1 : 0);
var result = 0;
for (var i = 0; i < digits.length; ++i) {
var currentNum = parseInt(digits.charAt(i));
if ((result == carry && currentNum > remainder) || result > carry) {
return sign == 1 ? INT_MAX : INT_MIN;
} else {
result = (result * 10) + currentNum;
}
}
return sign * result;
} else {
return 0;
}
};正则表达式，有木有人像我一样，学了不知道多少遍，学的时候看起来都懂了，过一段时间就又忘的差不多了，等真正要用到的时候，还是一脸懵逼。说到底还是练习的不够多，一直处于只看不做的程度上。所以搜集了这些正则习题，来保证温故而知新。建议读者看完题目后可以自己先做一做，然后再看实现方法。本文不讲基础，只记录习题，如果后续有新的题目，也会保持更新。
1、var s1 = "get-element-by-id"; 给定这样一个连字符串，写一个function转换为驼峰命名法形式的字符串 getElementById
var f = function(s) {
return s.replace(/-\w/g, function(x) {
return x.slice(1).toUpperCase();
})
}
2、判断字符串是否包含数字
function containsNumber(str) {
var regx = /\d/;
return regx.test(str);
}
3、判断电话号码
function isPhone(tel) {
var regx = /^1[34578]\d{9}$/;
return regx.test(tel);
}
4、判断是否符合指定格式
给定字符串str，检查其是否符合如下格式
function matchesPattern(str) {
return /^(\d{3}-){2}\d{4}&/.test(str);
}
5、判断是否符合USD格式
给定字符串 str，检查其是否符合美元书写格式
function isUSD(str) {
var regx = /^\$\d{1,3}(,\d{3})*(\.\d{2})?$/;
return regx.test(str);
}
6、JS实现千位分隔符
function format(number) {
var regx = /\d{1,3}(?=(\d{3})+$)/g;
return (number + '').replace(regx, '$&,') // $&表示与regx相匹配的字符串
}
7、获取 url 参数
获取 url 中的参数
function getUrlParam(url, key) {
var arr = {};
url.replace(/\??(\w+)=(\w+)&?/g, function(match, matchKey, matchValue) {
if (!arr[matchKey]) {
arr[matchKey] = matchValue;
} else {
var temp = arr[matchKey];
arr[matchKey] = [].concat(temp, matchValue);
}
});
if (!key) {
return arr;
} else {
for (ele in arr) {
if (ele = key) {
return arr[ele];
}
}
return '';
}
}
8、验证邮箱
function isEmail(email) {
var regx = /^([a-zA-Z0-9_\-])+@([a-zA-Z0-9_\-])+(\.[a-zA-Z0-9_\-])+$/;
return regx.test(email);
}
9、验证身份证号码
身份证号码可能为15位或18位，15位为全数字，18位中前17位为数字，最后一位为数字或者X
function isCardNo(number) {
var regx = /(^\d{15}$)|(^\d{18}$)|(^\d{17}(\d|X|x)$)/;
return regx.test(number);
}
10、匹配汉字
var regx = /^[\u4e00-\u9fa5]{0,}$/;
11、去除首尾的'/'
var str = '/asdf//';
str = str.replace(/^\/*|\/*$/g, '');
12、判断日期格式是否符合 '2017-05-11'的形式，简单判断，只判断格式
var regx = /^\d{4}\-\d{1,2}\-\d{1,2}$/
13、判断日期格式是否符合 '2017-05-11'的形式，严格判断（比较复杂）
var regx = /^(?:(?!0000)[0-9]{4}-(?:(?:0[1-9]|1[0-2])-(?:0[1-9]|1[0-9]|2[0-8])|(?:0[13-9]|1[0-2])-(?:29|30)|(?:0[13578]|1[02])-31)|(?:[0-9]{2}(?:0[48]|[2468][048]|[13579][26])|(?:0[48]|[2468][048]|[13579][26])00)-02-29)$/;
14、IPv4地址正则
var regx = /^(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)$/;
15、十六进制颜色正则
var regx = /^#?([a-fA-F0-9]{6}|[a-fA-F0-9]{3})$/;
16、车牌号正则
var regx = /^[京津沪渝冀豫云辽黑湘皖鲁新苏浙赣鄂桂甘晋蒙陕吉闽贵粤青藏川宁琼使领A-Z]{1}[A-Z]{1}[A-Z0-9]{4}[A-Z0-9挂学警港澳]{1}$/;
17、过滤HTML标签
var str="<p>dasdsa</p>nice <br> test</br>"
var regx = /<[^<>]+>/g;
str = str.replace(regx, '');
18、密码强度正则，最少6位，包括至少1个大写字母，1个小写字母，1个数字，1个特殊字符
var regx = /^.*(?=.{6,})(?=.*\d)(?=.*[A-Z])(?=.*[a-z])(?=.*[!@#$%^&*? ]).*$/;
19、URL正则
var regx = /^((https?|ftp|file):\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/;
20、匹配浮点数
var regx = /^-?([1-9]\d*\.\d*|0\.\d*[1-9]\d*|0?\.0+|0)$/;
21、<OPTION value="待处理">待处理</OPTION>
写一个正则表达式,匹配 "<OPTION value="待处理">"
var str = '<OPTION value="待处理">待处理</OPTION>';
var regx = /^<.*?>/;
var resiult = regx.exec(str)[0];
最后推荐一个练习正则的网站 regulex，可以查看正则匹配的走向
出处：LeetCode 算法第36题
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字
1-9在每一行只能出现一次。- 数字
1-9在每一列只能出现一次。- 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用
'.'表示。示例 1:
输入: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: true示例 2:
输入: [ ["8","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: false 解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。说明:
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 给定数独序列只包含数字
1-9和字符'.'。- 给定数独永远是
9x9形式的。
本题是一个二维数组，如果用暴力破解会有很高的时间复杂度，所以我们可以定义几个map，通过空间换时间的方式来降低时间复杂度
var isValidSudoku = function (board) {
var flag = true;
for (var i = 0; i < 9; i++) {
var rowMap = {};
var colMap = {};
var cubeMap = {};
for (var j = 0; j < 9; j++) {
if (board[i][j] != '.') {
if (rowMap[board[i][j]] == true) {
flag = false;
} else {
rowMap[board[i][j]] = true;
}
}
if (board[j][i] != '.') {
if (colMap[board[j][i]] == true) {
flag = false;
} else {
colMap[board[j][i]] = true;
}
}
var RowIndex = 3 * Math.floor(i / 3) + Math.floor(j / 3);
// 列号+偏移量
var ColIndex = 3 * Math.floor(i % 3) + Math.floor(j % 3);
if (board[RowIndex][ColIndex] != '.') {
if (cubeMap[board[RowIndex][ColIndex]] == true) {
flag = false;
} else {
cubeMap[board[RowIndex][ColIndex]] = true;
}
}
}
}
return flag;
};出处：LeetCode 算法第746题
数组的每个索引做为一个阶梯，第
i个阶梯对应着一个非负数的体力花费值cost[i](索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
输入: cost = [10, 15, 20] 输出: 15 解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。示例 2:
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出: 6 解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。注意：
cost的长度将会在[2, 1000]。- 每一个
cost[i]将会是一个Integer类型，范围为[0, 999]。
同样是动态规划问题
var minCostClimbingStairs = function (cost) {
var length = cost.length;
var dp = [];
dp[0] = cost[0];
dp[1] = cost[1];
for (var i = 2; i < length; i++) {
dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i];
}
return Math.min(dp[i-1], dp[i-2])
};出处：LeetCode 算法第33题
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回
-1。你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1
忽略中间的拆分，还是按照二分法来进行查找
var search = function (nums, target) {
if (nums.length == 0) {
return -1;
}
var left = 0;
var right = nums.length - 1;
while (left <= right) {
var mid = Math.ceil((left + right) / 2);
if (nums[mid] == target) {
return mid;
}
if (nums[mid] >= nums[left]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
};出处：LeetCode 算法第78题
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
**说明：**解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
还是采用深度递归遍历的算法，枚举所有可能性
var subsets = function (nums) {
var result = [];
var temp = [];
DFS(result, temp, -1, nums);
return result;
};
function DFS(result, temp, index, nums) {
if (index <= nums.length) {
result.push(copy(temp));
for (var i = index + 1; i < nums.length; i++) {
temp.push(nums[i]);
DFS(result, temp, i, nums);
temp.pop();
}
}
}
function copy(array) {
var res = [];
for (var i = 0, len = array.length; i < len; i++) {
res.push(array[i]);
}
return res;
}出处：LeetCode 算法第75题
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]进阶：
- 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。- 你能想出一个仅使用常数空间的一趟扫描算法吗？
方法1
var sortColors = function (nums) {
var red = 0, white = 0, blue = 0;
for (var i = 0, len = nums.length; i < len; i++) {
if (nums[i] == 0) {
red++;
} else if (nums[i] == 1) {
white++;
} else {
blue++;
}
}
for (var i = 0; i < red; i++) {
nums[i] = 0;
}
for (var i = red; i < red + white; i++) {
nums[i] = 1;
}
for (var i = red + white; i < red + white + blue; i++) {
nums[i] = 2;
}
};方法2
var sortColors = function (nums) {
var length = nums.length;
if (length == 0) {
return nums;
}
var head = 0, cursor = 0, tail = length - 1;
while (cursor <= tail) {
if (nums[cursor] == 0) {
var temp = nums[head];
nums[head] = nums[cursor];
nums[cursor] = temp;
cursor++;
head++;
} else if (nums[cursor] == 2) {
var temp = nums[tail];
nums[tail] = nums[cursor];
nums[cursor] = temp;
tail--;
} else {
cursor++;
}
}
}出处：LeetCode 算法第80题
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定 nums = [1,1,1,2,2,3], 函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 你不需要考虑数组中超出新长度后面的元素。示例 2:
给定 nums = [0,0,1,1,1,1,2,3,3], 函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 你不需要考虑数组中超出新长度后面的元素。说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以**“引用”**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }
定义变量记录前一项的值以及出现的次数，判断下一个值是否与前一个值一样以及出现的次数，如果超出要求则删除当前项，否则查看下一项。
var removeDuplicates = function (nums) {
if (nums.length === 0) {
return 0;
}
var i = 0;
var flag = nums[0];
var count = 0;
while (nums[i] != undefined) {
if (nums[i] == flag) {
if (count <= 1) {
count = count + 1;
i = i + 1;
} else {
nums.splice(i, 1);
}
} else {
flag = nums[i];
count = 1;
i = i + 1;
}
}
return nums.length;
};博主，请问您的vue源码分析，git上，我没找到仓库也
出处：阿里笔试题
现在有数组A和数组B，数组A表示男生数组，每个男生元素都有姓名和工号，数组B表示女生数组，每个女生元素有姓名和工号，现在要求把两个数组合成一个按工号排序的升序数组，如果男生女生工号一样，则把女生工号加1，要求最后所得的数组不能有重复的工号
设置双指针，遍历两个数组，将每一个项加入到新的数组中。设置一个count来记录重复的次数，使得后面的工牌号都向后偏移count个位置，防止重复
/**
*
* @param {*} man {name: '', no: ''}
* @param {*} woman {name: '', no: ''}
* @return []
*/
function uniqueArray(man, woman) {
var man_length = man.length,
woman_length = woman.length;
if (man_length === 0) {
return woman;
}
if (woman_length === 0) {
return man;
}
var i = 0,
j = 0,
count = 0, // 记录新数组的工号相比于原数组增加的数量
result = [];
man.sort(function (prev, next) { // 将原数组按升序排序
return prev.no - next.no;
})
woman.sort(function (prev, next) { // 将原数组按升序排序
return prev.no - next.no;
})
while (i < man_length && j < woman_length) {
if (man[i].no === woman[j].no) {
man[i].no += count;
woman[j].no += (1 + count);
result.push(man[i]);
result.push(woman[j]);
count++;
i++;
j++;
} else if (man[i].no < woman[j].no) {
man[i].no += count;
result.push(man[i]);
i++;
} else {
woman[j].no += count;
result.push(woman[i]);
j++;
}
}
while (i < man_length) {
man[i].no += count;
result.push(man[i]);
i++;
}
while (j < woman_length) {
woman[j].no += count;
result.push(woman[j]);
j++;
}
return result;
}前段时间在工作中写Hybrid页面时遇到了这样的一个场景，公司需要一系列的活动组件，在每个组件注册的时候都需要调用App端提供的一个接口。一开始也考虑了几种方式，包括mixin、组件继承以及react高阶组件。但经过了种种衡量，最后选择使用了高阶组件的做法。
React官方已不推荐使用Mixins的技术来实现代码的重用，Mixins技术有一系列的缺点，首先Mixins会造成命名冲突，我们通过以下的方式来注入Mixins：
var myMixins = require('myMixins');
var Button = React.createClass({
mixins: [myMixins],
// ...
})
如果你需要注入多个mixins,其中一个是自己的，另外的可能是第三方的。那有可能在两个mixins里使用了相同名称的方法，这会使得其中的一个不起作用，而你能做的只有修改其中一个方法的名称。另一方面，一个mixins一开始可能是非常简单的，仅仅需要实现某一个功能，但当业务越加的复杂，需要往其中加入更多的方法的时候，就会变得非常复杂。要深入了解mixins的缺点，可以查看官方博客。
对于我自己来说这种方法以前使用的比较多，先创建一个BaseComponent，在其中实现一系列公共的方法，其后的每个组件都继承于这个组件，但缺点是不够灵活，在基础组件中只能实现一些比较固定的方法，而对于每个组件的定制化会有很大的限制。
由于mixins的一系列缺点，React官方也意识到使用mixins所带来的痛点远远高于技术本身产生的优点，而高阶组件便可以代替mixins，而且当深入之后它还有着更加丰富的用法。
高阶组件（HOC）是React中对组件逻辑进行重用的高级技术。但高阶组件本身并不是React API。它只是一种模式，这种模式是由React自身的组合性质必然产生的。
说到高阶组件，就先得说到高阶函数了，高阶函数是至少满足下列条件的函数：
1、接受一个或多个函数作为输入
2、输出一个函数
在javascript这门函数为一等公民的语言中，高阶函数的使用还是非常之多的，像我们平时的回调函数等等，都用到了高阶函数的知识。我们先来看一个简单的高阶函数
var fun = function(x, y) {
return x + y;
}
fun是一个函数，下面我们将整个函数作为参数传递给另一个函数
var comp = function(x, y, f) {
return f(x,y);
}
验证一下
comp(1,2,fun) // 3
类比高阶函数的定义，高阶组件就是接受一个组件作为参数，在函数中对组件做一系列的处理，随后返回一个新的组件作为返回值。
我们先定义一个高阶组件BaseActivity
const BaseActivity = (WrappedComponent) => {
return class extends Component {
render() {
return (
<section>
<div>我的包裹组件</div>
<WrappedComponent />
</section>
)
}
}
}
组件接受一个被包裹的组件作为参数，返回了一个经过处理的匿名组件。
在其他组件中使用这个高阶组件
class Example extends React.PureComponent {
constructor(props) {
super(props);
this.state = {
width: '100%',
height: '100%'
}
}
componentWillMount() {
if ((navigator.userAgent.match(/(phone|pad|pod|iPhone|iPod|ios|iPad|Android|Mobile|BlackBerry|IEMobile|MQQBrowser|JUC|Fennec|wOSBrowser|BrowserNG|WebOS|Symbian|Windows Phone)/i))) {
return;
} else {
this.setState({
width: '375px',
height: '640px'
})
}
}
render() {
let { width, height } = this.state;
return (
<div className="activity">
<div className="activity-content" style={{ width, height }}>
<button className="btn">参加活动</button>
</div>
</div>
)
}
}
export default BaseActivity(Example);
具体用法就是在export 组件的时候，使用BaseActivity函数来包裹这个组件，看下输出的react dom内容
在Example组件外面包裹了一个匿名组件。
既然高阶组件是一个函数，我们就可以向里面传递我们需要的参数
const BaseActivity = (WrappedComponent, title) => {
return class extends Component {
render() {
return (
<section>
<div>{title}</div>
<WrappedComponent />
</section>
)
}
}
}
在Example中这样export
export default BaseActivity(Example, '这是高阶组件的参数');
我们看下输出的react dom
可以看到参数已经传递进去了。
当然还可以这样用(柯里化)
const BaseActivity (title) => (WrappedComponent) => {
return class extends Component {
render() {
return (
<section>
<div>{title}</div>
<WrappedComponent />
</section>
)
}
}
}
在Example中这样export
export default BaseActivity('这是高阶组件的参数')(Example);
这种用法在ant-design的表单以及redux的connect中我们都可以看到
// ant
const WrappedDemo = Form.create()(Demo)
// redux
export default connect(mapStateToProps, mapDispatchToProps)(Counter)
高阶组件还可以扩展原组件的props属性，如下所示：
const BaseActivity (title) => (WrappedComponent) => {
return class extends Component {
render() {
const newProps = {
id: Math.random().toString(8)
}
return (
<section>
<div>{title}</div>
<WrappedComponent {...this.props} {...newProps}/>
</section>
)
}
}
}
看下输出的react dom
高阶组件也有一系列的缺点，首先是被包裹组件的静态方法会消失，这其实也是很好理解的，我们将组件当做参数传入函数中，返回的已经不是原来的组件，而是一个新的组件，原来的静态方法自然就不存在了。如果需要保留，我们可以手动将原组件的方法拷贝给新的组件，或者使用hoist-non-react-statics之类的库来进行拷贝。
高阶函数对于初学者来说可能不太好理解，但当你深入其中，了解其中的原理之后，我们可以使用高阶函数来完成很多的工作。
出处：LeetCode 算法第16题
给定一个包括 n 个整数的数组
nums和 一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如，给定数组 nums = [-1，2，1，-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
还是采用双指针的方式，先将一个数固定，用双指针来遍历剩下的数。
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function (nums, target) {
nums.sort(function (a, b) {
return a - b;
});
var result = nums[0] + nums[1] + nums[2];
var sum = Math.abs(result - target);
var length = nums.length;
for (var i = 0; i < length - 2; i++) {
var leftPtr = i + 1;
var rightPtr = length - 1;
while (leftPtr < rightPtr) {
var current = nums[i] + nums[leftPtr] + nums[rightPtr];
if (Math.abs(current - target) < sum) {
sum = Math.abs(current - target);
result = current;
} else {
if (current > target) {
rightPtr--;
} else {
leftPtr++;
}
}
}
}
return result;
};出处：LeetCode 算法第48题
给定一个 *n *× n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ], 原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ]示例 2:
给定 matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], 原地旋转输入矩阵，使其变为: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ]
矩阵共有四个面，旋转后某个点在四个面上的相应位置会进行相应的交换
var rotate = function (matrix) {
var length = matrix.length - 1;
for (var i = 0; i <= length / 2; i++) {
for (var j = 0; j < length / 2; j++) {
var temp = matrix[i][j];
matrix[i][j] = matrix[length - j][i];
matrix[length - j][i] = matrix[length - i][length - j];
matrix[length - i][length - j] = matrix[j][length - i];
matrix[j][length - i] = temp;
}
}
};出处：LeetCode 算法第77题
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
还是采取深度优先遍历，当组合的个数达到要求时存入结果中
var combine = function (n, k) {
var result = [];
var temp = [];
DFS(result, temp, 1, n + 1, k);
return result;
};
function copy(array) {
var result = [];
for (var i = 0, len = array.length; i < len; i++) {
result.push(array[i]);
}
return result;
}
function DFS(result, temp, index, n, k) {
if (temp.length == k) {
result.push(copy(temp));
return;
}
if (index < n) {
for (var p = index; p < n; p++) {
temp.push(p);
DFS(result, temp, p + 1, n, k);
temp.pop();
}
}
}出处：LeetCode 算法第24题
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.说明:
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
创建临时的节点，使其next为head，顺序判断链表中相邻的两个元素，并将他们进行交换。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function (head) {
if (head == null || head.next == null) {
return head;
}
var first = new ListNode(0);
first.next = head;
var res = first;
while (first.next != null && first.next.next != null) {
var one = first.next;
var two = first.next.next;
one.next = two.next;
two.next = one;
first.next = two;
first = first.next.next;
}
return res.next;
};出处：LeetCode 算法第2题
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
简单的链表，每相加两个链表的值，将进位放存放在carry里，余数存放在remainder里。进行下一次计算时，需要加上carry的值。另一个易错点就是当其中一个链表已经到尾部，而carry的值为1时的情况。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function (l1, l2) {
var result = new ListNode(0);
var head = result;
var carry = 0;
var remainder = 0;
while (l1 != null && l2 != null) {
var temp = l1.val + l2.val + (carry ? 1 : 0);
if (temp >= 10) {
carry = 1;
remainder = temp % 10;
} else {
carry = 0;
remainder = temp;
}
var add = new ListNode(remainder);
result.next = add;
result = result.next;
l1 = l1.next;
l2 = l2.next;
}
if (l1 == null && l2 == null) {
}
if (l1 == null) {
while (l2 != null) {
if (carry) {
var temp = l2.val + (carry ? 1 : 0);
if (temp >= 10) {
carry = 1;
remainder = temp % 10;
} else {
carry = 0;
remainder = temp;
}
var add = new ListNode(remainder);
result.next = add;
result = result.next;
l2 = l2.next;
} else {
var add = new ListNode(l2.val);
result.next = add;
result = result.next;
l2 = l2.next;
}
}
} else {
while (l1 != null) {
if (carry) {
var temp = l1.val + (carry ? 1 : 0);
if (temp >= 10) {
carry = 1;
remainder = temp % 10;
} else {
carry = 0;
remainder = temp;
}
var add = new ListNode(remainder);
result.next = add;
result = result.next;
l1 = l1.next;
} else {
var add = new ListNode(l1.val);
result.next = add;
result = result.next;
l1 = l1.next;
}
}
}
if (carry) {
var add = new ListNode(1);
result.next = add;
result = result.next;
carry = 0;
}
return head.next;
};出处 LeetCode 算法第94题
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2]
简单，递归即可
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
var result = [];
if (root == null) {
return result;
}
return result.concat(inorderTraversal(root.left), root.val, inorderTraversal(root.right));
};出处：LeetCode 算法第18题
给定一个包含 n 个整数的数组
nums和一个目标值target，判断nums中是否存在四个元素 *a，*b，c 和 d ，使得 a + b + c + d 的值与target相等？找出所有满足条件且不重复的四元组。注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
先对数组进行排序，随机取两个数，对于剩下的数，使用两个指针分别从头部以及尾部进行扫描，计算符合要求的答案。改算法可以将时间复杂度保证在O(n^2)
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
var tempresult = [];
var exist = [];
var sortNums = nums.sort(function (a, b) { return a - b });
var length = nums.length;
for (var i = 0; i < length - 1 - 2; i++) {
for (var j = i + 1; j < length - 1 - 1; j++) {
var number1 = sortNums[i];
var number2 = sortNums[j];
var low = j + 1;
var high = length - 1;
while (low < high) {
if ((number1 + number2 + sortNums[low] + sortNums[high]) === target) {
if (exist.indexOf([number1, number2, sortNums[low], sortNums[high]].join(',')) < 0) {
tempresult.push([number1, number2, sortNums[low], sortNums[high]]);
exist.push([number1, number2, sortNums[low], sortNums[high]].join(','));
}
}
if ((number1 + number2 + sortNums[low] + sortNums[high]) < target) {
low++;
} else {
high--;
}
}
}
}
return tempresult;
};出处：LeetCode 算法第81题
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,0,1,2,2,5,6]可能变为[2,5,6,0,0,1,2])。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回
true，否则返回false。示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false进阶:
- 这是 搜索旋转排序数组 的延伸题目，本题中的
nums可能包含重复元素。- 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
var search = function (nums, target) {
if (nums.length == 0) {
return false;
}
var left = 0;
var right = nums.length - 1;
while (left <= right) {
var mid = Math.ceil((left + right) / 2);
if (nums[mid] == target) {
return true
}
if (nums[mid] > nums[left]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else if (nums[mid] < nums[left]) {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
left = left + 1;
}
}
return false;
};出处：LeetCode 算法第43题
给定两个以字符串形式表示的非负整数
num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"说明：
num1和num2的长度小于110。num1和num2只包含数字0-9。num1和num2均不以零开头，除非是数字 0 本身。- 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
在JS中可以使用+号使字符串变成数字，但当两个很大的数字相乘时，得到的答案会丢失精度，所以不能直接采用乘法的方式。可以通过一个字符串来存储每一位相乘得到的结果，最后再拼成最后的答案。
var multiply = function (num1, num2) {
var resultArray = [];
for (var i = num1.length - 1; i >= 0; i--) {
for (var j = num2.length - 1; j >= 0; j--) {
var temp = +num1[i] * +num2[j];
if (resultArray[i + j + 1]) {
resultArray[i + j + 1] += temp;
} else {
resultArray[i + j + 1] = temp;
}
}
}
var resultLength = resultArray.length - 1;
var carry = 0;
for (var i = resultLength; i >= 0; i--) {
if (!resultArray[i]) {
resultArray[i] = 0;
}
resultArray[i] += carry;
carry = Math.floor(resultArray[i] / 10);
resultArray[i] = Number(resultArray[i] % 10);
}
var result = "";
var firstZero = false;
for (var i = 0; i <= resultLength; i++) {
if (!firstZero && resultArray[i] == 0) {
continue;
} else {
result += resultArray[i];
firstZero = true;
}
}
if (result == "") {
return "0";
}
return result;
};出处 LeetCode 算法第105题
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：
3 / \ 9 20 / \ 15 7
按照思路递归遍历数组，前序遍历的第一个值为树的根，其在中序遍历中对应的值的前面的数都在其左子树上
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
function helper(preorder, inorder) {
if (preorder.length == 0 || inorder.length == 0) {
return null;
}
var rootVal = preorder[0];
var index = inorder.indexOf(rootVal);
var perorderLeft = preorder.slice(1, index + 1);
var perorderRight = preorder.slice(index + 1);
var InorderLeft = inorder.slice(0, index);
var InorderRight = inorder.slice(index + 1);
var root = new TreeNode(rootVal);
if (perorderLeft.length > 0) {
root.left = buildTree(perorderLeft, InorderLeft);
}
if (perorderRight.length > 0) {
root.right = buildTree(perorderRight, InorderRight);
}
return root;
}
var buildTree = function (preorder, inorder) {
if (preorder.length == 0 || inorder.length == 0) {
return [];
}
return helper(preorder, inorder);
};出处：LeetCode 算法第32题
给定一个只包含
'('和')'的字符串，找出最长的包含有效括号的子串的长度。示例 1:
输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"
使用一个栈来保存最长匹配的字符串，每次遇到匹配的对，如果是和前面连续的，则使最大值加2。并使堆栈弹出两个值。
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function (s) {
var result = 0;
var arrayStack = [0];
s.split('').forEach(item => {
if (item == '(') {
arrayStack.push(0);
} else {
var length = arrayStack.length;
if (length >= 2) {
arrayStack[length - 2] += arrayStack.pop() + 2;
result = Math.max(result, arrayStack[length - 2]);
} else {
arrayStack = [0];
}
}
});
return result;
};
console.log(longestValidParentheses(')(()())'));出处：LeetCode 算法第47题
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
相比于上一题，本题的元素是可以重复的，所以我们需要一个数组来保存当前的项是否已经添加了
var permuteUnique = function (nums) {
if (nums.length === 0) {
return [];
}
var result = [];
var resultStr = [];
var used = [];
var temp = [];
DFS(nums, result, temp, used, resultStr);
return result;
};
function copy(array) {
var result = [];
for (var i = 0, len = array.length; i < len; i++) {
result.push(array[i]);
}
return result;
}
function DFS(nums, result, temp, used, resultStr) {
if (temp.length === nums.length) {
if (resultStr.indexOf(temp.join(',')) < 0) {
result.push(copy(temp));
resultStr.push(temp.join(','));
}
};
for (var i = 0; i < nums.length; i++) {
if (used[i]) {
continue
}
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue
}
used[i] = true;
temp.push(nums[i]);
DFS(nums, result, temp, used, resultStr);
used[i] = false;
temp.pop();
}
}出处：LeetCode 算法第40题
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0] 输出: 3示例 2:
输入: [3,4,-1,1] 输出: 2示例 3:
输入: [7,8,9,11,12] 输出: 1说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
本题的难点在于时间复杂度为O(n)，而空间复杂度为常数，这就限制了我们只能使用原数组进行操作。所以我们可以使用下标为i的项保存i+1来解决，如果其中第i项的值不等于i+1，则说明数组中没有i+1这个正数。
var firstMissingPositive = function (nums) {
var len = nums.length;
if (len <= 0) {
return 1;
}
for (var i = 0; i < len; i++) {
if (nums[i] > 0) {
while(nums[i] < i + 1 && nums[i] != nums[nums[i] -1]) {
var tempIndex = nums[i] - 1;
var temp = nums[i];
nums[i] = nums[tempIndex];
nums[tempIndex] = temp;
}
}
}
for (var i = 0; i < len; i++) {
if (nums[i] !== i + 1) {
return i + 1;
}
}
return nums.length + 1;
};出处：LeetCode 算法第79题
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false.
采用深度遍历搜索的方式，遍历所有可能性，得到结果
var exist = function (board, word) {
var row = board.length;
var col = board[0].length;
var visit = [];
for (var x = 0; x < row; x++) {
visit[x] = [];
}
for (var i = 0; i < row; i++) {
for (var j = 0; j < col; j++) {
if (dfs(board, visit, i, j, 0, word)) {
return true;
}
}
}
return false;
};
function dfs(board, visit, row, col, index, word) {
if (index == word.length) {
return true;
}
if (row < 0 || col < 0 || row >= board.length || col >= board[0].length) {
return false;
}
var ch = word[index];
if (!visit[row][col] && ch == board[row][col]) {
visit[row][col] = true;
var res = dfs(board, visit, row - 1, col, index + 1, word) || dfs(board, visit, row + 1, col, index + 1, word) || dfs(board, visit, row, col - 1, index + 1, word) || dfs(board, visit, row, col + 1, index + 1, word);
visit[row][col] = false;
return res;
}
return false;
}出处：LeetCode 算法第90题
给定一个可能包含重复元素的整数数组 *nums*，返回该数组所有可能的子集（幂集）。
**说明：**解集不能包含重复的子集。
示例:
输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
采用深度递归遍历遍历所有可能性，并与已经存在的组合进行过滤
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function (nums) {
var result = [];
var temp = [];
var exist = [];
nums.sort();
DFS(result, temp, exist, -1, nums);
return result;
};
function DFS(result, temp, exist, index, nums) {
if (index <= nums.length) {
if (exist.indexOf(temp.join('')) < 0) {
result.push(copy(temp));
exist.push(temp.join(''));
}
for (var i = index + 1, len = nums.length; i < len; i++) {
temp.push(nums[i]);
DFS(result, temp, exist, i, nums);
temp.pop();
}
}
}
function copy(array) {
var res = [];
for (var i = 0, len = array.length; i < len; i++) {
res.push(array[i]);
}
return res;
}在目前的前端面试中，vue的双向数据绑定已经成为了一个非常容易考到的点，即使不能当场写出来，至少也要能说出原理。本篇文章中我将会仿照vue写一个双向数据绑定的实例，名字就叫myVue吧。结合注释，希望能让大家有所收获。
Vue的双向数据绑定的原理相信大家也都十分了解了，主要是通过 Object对象的defineProperty属性，重写data的set和get函数来实现的,这里对原理不做过多描述，主要还是来实现一个实例。为了使代码更加的清晰，这里只会实现最基本的内容，主要实现v-model，v-bind 和v-click三个命令，其他命令也可以自行补充。
添加网上的一张图
页面结构很简单，如下
<div id="app">
<form>
<input type="text" v-model="number">
<button type="button" v-click="increment">增加</button>
</form>
<h3 v-bind="number"></h3>
</div>包含：
1. 一个input，使用v-model指令
2. 一个button，使用v-click指令
3. 一个h3，使用v-bind指令。
我们最后会通过类似于vue的方式来使用我们的双向数据绑定，结合我们的数据结构添加注释
var app = new myVue({
el:'#app',
data: {
number: 0
},
methods: {
increment: function() {
this.number ++;
},
}
})首先我们需要定义一个myVue构造函数：
function myVue(options) {
}为了初始化这个构造函数，给它添加一 个_init属性
function myVue(options) {
this._init(options);
}
myVue.prototype._init = function (options) {
this.$options = options; // options 为上面使用时传入的结构体，包括el,data,methods
this.$el = document.querySelector(options.el); // el是 #app, this.$el是id为app的Element元素
this.$data = options.data; // this.$data = {number: 0}
this.$methods = options.methods; // this.$methods = {increment: function(){}}
}接下来实现_obverse函数，对data进行处理，重写data的set和get函数
并改造_init函数
myVue.prototype._obverse = function (obj) { // obj = {number: 0}
var value;
for (key in obj) { //遍历obj对象
if (obj.hasOwnProperty(key)) {
value = obj[key];
if (typeof value === 'object') { //如果值还是对象，则遍历处理
this._obverse(value);
}
Object.defineProperty(this.$data, key, { //关键
enumerable: true,
configurable: true,
get: function () {
console.log(`获取${value}`);
return value;
},
set: function (newVal) {
console.log(`更新${newVal}`);
if (value !== newVal) {
value = newVal;
}
}
})
}
}
}
myVue.prototype._init = function (options) {
this.$options = options;
this.$el = document.querySelector(options.el);
this.$data = options.data;
this.$methods = options.methods;
this._obverse(this.$data);
}接下来我们写一个指令类Watcher，用来绑定更新函数，实现对DOM元素的更新
function Watcher(name, el, vm, exp, attr) {
this.name = name; //指令名称，例如文本节点，该值设为"text"
this.el = el; //指令对应的DOM元素
this.vm = vm; //指令所属myVue实例
this.exp = exp; //指令对应的值，本例如"number"
this.attr = attr; //绑定的属性值，本例为"innerHTML"
this.update();
}
Watcher.prototype.update = function () {
this.el[this.attr] = this.vm.$data[this.exp]; //比如 H3.innerHTML = this.data.number; 当number改变时，会触发这个update函数，保证对应的DOM内容进行了更新。
}更新_init函数以及_obverse函数
myVue.prototype._init = function (options) {
//...
this._binding = {}; //_binding保存着model与view的映射关系，也就是我们前面定义的Watcher的实例。当model改变时，我们会触发其中的指令类更新，保证view也能实时更新
//...
}
myVue.prototype._obverse = function (obj) {
//...
if (obj.hasOwnProperty(key)) {
this._binding[key] = { // 按照前面的数据，_binding = {number: _directives: []}
_directives: []
};
//...
var binding = this._binding[key];
Object.defineProperty(this.$data, key, {
//...
set: function (newVal) {
console.log(`更新${newVal}`);
if (value !== newVal) {
value = newVal;
binding._directives.forEach(function (item) { // 当number改变时，触发_binding[number]._directives 中的绑定的Watcher类的更新
item.update();
})
}
}
})
}
}
}那么如何将view与model进行绑定呢？接下来我们定义一个_compile函数，用来解析我们的指令（v-bind,v-model,v-clickde）等，并在这个过程中对view与model进行绑定。
myVue.prototype._init = function (options) {
//...
this._complie(this.$el);
}
myVue.prototype._complie = function (root) { root 为 id为app的Element元素，也就是我们的根元素
var _this = this;
var nodes = root.children;
for (var i = 0; i < nodes.length; i++) {
var node = nodes[i];
if (node.children.length) { // 对所有元素进行遍历，并进行处理
this._complie(node);
}
if (node.hasAttribute('v-click')) { // 如果有v-click属性，我们监听它的onclick事件，触发increment事件，即number++
node.onclick = (function () {
var attrVal = nodes[i].getAttribute('v-click');
return _this.$methods[attrVal].bind(_this.$data); //bind是使data的作用域与method函数的作用域保持一致
})();
}
if (node.hasAttribute('v-model') && (node.tagName == 'INPUT' || node.tagName == 'TEXTAREA')) { // 如果有v-model属性，并且元素是INPUT或者TEXTAREA，我们监听它的input事件
node.addEventListener('input', (function(key) {
var attrVal = node.getAttribute('v-model');
//_this._binding['number']._directives = [一个Watcher实例]
// 其中Watcher.prototype.update = function () {
// node['vaule'] = _this.$data['number']; 这就将node的值保持与number一致
// }
_this._binding[attrVal]._directives.push(new Watcher(
'input',
node,
_this,
attrVal,
'value'
))
return function() {
_this.$data[attrVal] = nodes[key].value; // 使number 的值与 node的value保持一致，已经实现了双向绑定
}
})(i));
}
if (node.hasAttribute('v-bind')) { // 如果有v-bind属性，我们只要使node的值及时更新为data中number的值即可
var attrVal = node.getAttribute('v-bind');
_this._binding[attrVal]._directives.push(new Watcher(
'text',
node,
_this,
attrVal,
'innerHTML'
))
}
}
}至此，我们已经实现了一个简单vue的双向绑定功能，包括v-bind, v-model, v-click三个指令。效果如下图
附上全部代码，不到150行
<!DOCTYPE html>
<head>
<title>myVue</title>
</head>
<style>
#app {
text-align: center;
}
</style>
<body>
<div id="app">
<form>
<input type="text" v-model="number">
<button type="button" v-click="increment">增加</button>
</form>
<h3 v-bind="number"></h3>
<form>
<input type="text" v-model="count">
<button type="button" v-click="incre">增加</button>
</form>
<h3 v-bind="count"></h3>
</div>
</body>
<script>
function myVue(options) {
this._init(options);
}
myVue.prototype._init = function (options) {
this.$options = options;
this.$el = document.querySelector(options.el);
this.$data = options.data;
this.$methods = options.methods;
this._binding = {};
this._obverse(this.$data);
this._complie(this.$el);
}
myVue.prototype._obverse = function (obj) {
var _this = this;
Object.keys(obj).forEach(function (key) {
if (obj.hasOwnProperty(key)) {
_this._binding[key] = {
_directives: []
};
console.log(_this._binding[key])
var value = obj[key];
if (typeof value === 'object') {
_this._obverse(value);
}
var binding = _this._binding[key];
Object.defineProperty(_this.$data, key, {
enumerable: true,
configurable: true,
get: function () {
console.log(`${key}获取${value}`);
return value;
},
set: function (newVal) {
console.log(`${key}更新${newVal}`);
if (value !== newVal) {
value = newVal;
binding._directives.forEach(function (item) {
item.update();
})
}
}
})
}
})
}
myVue.prototype._complie = function (root) {
var _this = this;
var nodes = root.children;
for (var i = 0; i < nodes.length; i++) {
var node = nodes[i];
if (node.children.length) {
this._complie(node);
}
if (node.hasAttribute('v-click')) {
node.onclick = (function () {
var attrVal = nodes[i].getAttribute('v-click');
return _this.$methods[attrVal].bind(_this.$data);
})();
}
if (node.hasAttribute('v-model') && (node.tagName == 'INPUT' || node.tagName == 'TEXTAREA')) {
node.addEventListener('input', (function(key) {
var attrVal = node.getAttribute('v-model');
_this._binding[attrVal]._directives.push(new Watcher(
'input',
node,
_this,
attrVal,
'value'
))
return function() {
_this.$data[attrVal] = nodes[key].value;
}
})(i));
}
if (node.hasAttribute('v-bind')) {
var attrVal = node.getAttribute('v-bind');
_this._binding[attrVal]._directives.push(new Watcher(
'text',
node,
_this,
attrVal,
'innerHTML'
))
}
}
}
function Watcher(name, el, vm, exp, attr) {
this.name = name; //指令名称，例如文本节点，该值设为"text"
this.el = el; //指令对应的DOM元素
this.vm = vm; //指令所属myVue实例
this.exp = exp; //指令对应的值，本例如"number"
this.attr = attr; //绑定的属性值，本例为"innerHTML"
this.update();
}
Watcher.prototype.update = function () {
this.el[this.attr] = this.vm.$data[this.exp];
}
window.onload = function() {
var app = new myVue({
el:'#app',
data: {
number: 0,
count: 0,
},
methods: {
increment: function() {
this.number ++;
},
incre: function() {
this.count ++;
}
}
})
}
</script>出处：LeetCode 算法第82题
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5 输出: 1->2->5示例 2:
输入: 1->1->1->2->3 输出: 2->3
判断相邻的两个节点的值是否相等，如果相等则记录这个值，继续往下判断，把所有相同的都删除。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function (head) {
if (head == null || head.next == null) {
return head;
}
var newHead = new ListNode(0);
newHead.next = head;
head = newHead;
while (head.next != null && head.next.next != null) {
if (head.next.val == head.next.next.val) {
var temp = head.next.val;
while (head.next != null && head.next.val == temp) {
head.next = head.next.next;
}
} else {
head = head.next;
}
}
return newHead.next;
};出处：LeetCode 算法第73题
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法**。**
示例 1:
输入: [ [1,1,1], [1,0,1], [1,1,1] ] 输出: [ [1,0,1], [0,0,0], [1,0,1] ]示例 2:
输入: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] 输出: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ]进阶:
- 一个直接的解决方案是使用 O(m**n) 的额外空间，但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
- 你能想出一个常数空间的解决方案吗？
遍历所有的元素，将元素为零的坐标对放入临时数组中，遍历临时数组，置行和列的元素为零。
var setZeroes = function (matrix) {
if (matrix.lenght == 0) {
return [];
}
var max_i = matrix.length;
var max_j = matrix[0].length;
var temp = [];
for (var i = 0; i < max_i; i++) {
for (var j = 0; j < max_j; j++) {
if (matrix[i][j] == 0) {
temp.push([i, j]);
}
}
}
for (var x = 0; x < temp.length; x++) {
var a = temp[x][0];
var b = temp[x][1];
for (var i = 0; i < max_i; i++) {
matrix[i][b] = 0;
}
for (var j = 0; j < max_j; j++) {
matrix[a][j] = 0;
}
}
};出处：LeetCode 算法第40题
给定一个数组
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次。说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]
和上一题一样，都是采用递归遍历的做法，但由于每个数字只能用一次，所以递归的时候不能递归当前的项，需要递归下一项。
var combinationSum2 = function (candidates, target) {
var strresult = []; // 定义一个字符串的数组用来去重
var result = [];
var temp = [];
var sum = 0;
candidates.sort(function (a, b) {
return a - b;
})
DFS(candidates, sum, 0, target, temp, result, strresult);
return result;
};
function copy(array) {
var result = [];
for (var i = 0, len = array.length; i < len; i++) {
result.push(array[i]);
}
return result;
}
function DFS(candidates, sum, level, target, temp, result, strresult) {
if (sum > target) {
return;
}
if (sum == target && strresult.indexOf(temp.join('')) < 0) {
result.push(copy(temp));
strresult.push(temp.join(''));
return;
}
for (var i = level; i < candidates.length; i++) {
sum += candidates[i];
temp.push(candidates[i]);
DFS(candidates, sum, i + 1, target, temp, result, strresult); // 递归下一项
temp.pop();
sum -= candidates[i];
}
}出处：LeetCode 算法第10题
给定一个字符串 (
s) 和一个字符模式 (p)。实现支持'.'和'*'的正则表达式匹配。'.' 匹配任意单个字符。 '*' 匹配零个或多个前面的元素。匹配应该覆盖整个字符串 (
s) ，而不是部分字符串。说明:
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符.和*。示例 1:
输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。示例 2:
输入: s = "aa" p = "a*" 输出: true 解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。示例 3:
输入: s = "ab" p = ".*" 输出: true 解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。示例 4:
输入: s = "aab" p = "c*a*b" 输出: true 解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。示例 5:
输入: s = "mississippi" p = "mis*is*p*." 输出: false
采用动态规划，进行解答
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function (s, p) {
var sLength = s.length;
var pLength = p.length;
var dp = [];
for (var i = 0; i <= sLength + 1; i++) {
dp[i] = [];
for (var j = 0; j <= pLength + 1; j++) {
dp[i][j] = false;
}
}
for (var i = 0; i <= sLength; i++) {
for (var j = 0; j <= pLength; j++) {
if (i == 0 && j == 0) {
dp[i][j] = true;
} else if (i == 0) {
dp[i][j] = p[j - 1] == '*' && dp[i][j - 2];
} else {
if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] == '*') {
if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
dp[i][j] = dp[i - 1][j - 2] || dp[i - 1][j] || dp[i][j - 2];
} else {
dp[i][j] = dp[i][j - 2];
}
}
}
}
}
return dp[sLength][pLength];
};浏览器的同源策略，出于防范跨站脚本的攻击，禁止客户端脚本（如 JavaScript）对不同域的服务进行跨站调用。
一般的，只要网站的 协议名protocol、 主机host、 端口号port 这三个中的任意一个不同，网站间的数据请求与传输便构成了跨域调用。
同源策略会限制以下几种行为：
- Cookie, LocalStorage和IndexDB无法获取
- DOM 和 JS 对象无法获取
- AJAX请求无法发送
cookie是一个可以验证身份的东西，目的是让服务器知道是谁发出的这次请求。如果请求了接口进行登录，服务端验证通过后会在响应头加入set-cookie字段，下次再发出请求时，浏览器会自动将cookie附加在请求中，服务端就能知道请求者的身份。下面有这个场景：
你登录了一个银行网站并登录，并获取到了服务端返回的cookie
这个时候，你打开了一个钓鱼网站，由于没有同源策略的限制，它在后台向服务端发送了请求，并且在请求中带着你的登陆信息，造成财产损失。这就是传说中的CSRF攻击方式
某一天你收到了一条短信，提示你你的银行账户有风险，你点击附带在短信里的链接(www.yinghang.com )进入了银行界面。由于是熟悉的银行界面，你输入了账户密码，去查看钱有没有少。
大意的你没有看清网站的地址不是正确的地址(www.yinhang.com )，而是错误的地址(www.yinghang.com )，你的账号密码就被盗取了。
这种攻击的原理就是攻击者在一个假的网站内通过iframe内嵌了一个真的网站，并通过获取DOM来获得你的输入，因为没有同源策略限制。
常见的跨域类型包括以下一些：
| URL | 说明 | 是否允许通信 |
|---|---|---|
| http://www.example.com/a.js https://www.example.com/b.js |
不同协议 | 不允许 |
| http://www.example1.com/a.js http://www.example2.com/b.js |
不同域名 | 不允许 |
| http://www.example.com/a.js http://192.168.1.1/b.js |
域名与域名所对应的IP | 不允许 |
| http://www.example.com/a.js http://x.example.com/b.js http://example.com/c.js |
主域相同，子域不同 | 不允许 |
| http://www.example.com:8080/a.js http://www.example.com/b.js |
同个域名，不同端口 | 不允许 |
| http://www.example.com/a.js http://www.example.com/b.js http://www.example.com/lab/c.js |
同域名同端口，不同文件目录 | 允许 |
原理：动态生成一个script标签，插入head中，浏览器会执行script标签中的代码，但只能实现get请求
具体原生实现
<script>
var script = document.createElement('script');
script.type = 'text/javascript';
script.src = 'http://www.example.com?name=michael&callback=onCallback';
document.head.appendChild(script);
function onCallback(res) {
console.log(JSON.stringify(res));
// 在这里处理数据
}
</script>
// 服务端返回，返回后执行onCallback函数
onCallback({resultCode: 0, data: {}});$.ajax({
url: 'http://www.example.com',
type: 'get',
dataType: 'jsonp',
jsonpCallback: 'onCallback',
data: {}
})Cross-Origin Reasource Sharing 跨域资源共享可以避开浏览器的同源策略，但CROS不仅仅支持GET请求，还支持其他请求
在服务器的返回信息里对请求头进行设置：
页面 http://www.example.com/a.html
页面中有一个iframe http://iframe.com/b.html
将两个页面的document.domain 设置成相同的域名，就可以在页面中拿到iframe中的数据
只能把document.domain设置成自身或更高一级的父域
//a.html
document.domain = 'example.com';
var iframe = document.createElement('iframe');
iframe.src = 'http://iframe.com/b.html';
iframe.style.display = 'none';
document.body.appendChild(iframe);
iframe.onload = function() {
var doc = iframe.contentDocument || iframe.contentWindow.document;
console.log(doc)
}
//b.html
document.domain = 'example.com';HTML5的新特性，允许来自不同源的脚本采用异步方式进行通信，实现跨域传递消息
使用方法：
postMessage(data, origin)
data: html5规范支持任意基本类型或可复制的对象，但部分浏览器只支持字符串，所以传参时最好用JSON.stringify()序列化
origin: 协议+主机+端口号，也可以设置为"*"，表示可以传递给任意窗口，如果要指定和当前窗口同源的话设置为"/"
// http://www.example.com/a.html
<iframe src="http://www.example2.com/b.html" style="display: none;" id="ifr"></iframe>
<script>
var iframe = document.getElementById('ifr');
iframe.onload = function() {
var data = {};
iframe.contentWindow.postMessage(JSON.stringify(data), 'http://www.example2.com');
};
// 接受传输的数据
window.addEventListener('message', function(e) {
console.log(e.data);
}, false);
</script>
// http://www.example2.com/b.html
<script>
window.addEventListener('message', function(e) {
console.log(e.data);
})
</script>出处：LeetCode 算法第25题
给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表：
1->2->3->4->5当 k = 2 时，应当返回:
2->1->4->3->5当 k = 3 时，应当返回:
3->2->1->4->5说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
先统计有几个k个元素，对每k个元素进行链表的翻转，再组成长链表
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
function ListNode(val) {
this.val = val;
this.next = null;
}
var reverseKItem = function (head, k) {
var start = head;
var tail = head;
var current = 0;
var prev = next = null;
while (head && current < k) {
next = head.next;
head.next = prev;
prev = head;
start = head;
current++;
head = next;
}
tail.next = next;
return [start, tail];
}
var reverseKGroup = function (head, k) {
if (!head || !head.next || k <= 1) {
return head;
}
// 计算链表的长度
var length = 0;
var tempNode = head;
while (tempNode) {
length++;
tempNode = tempNode.next;
}
var empty = new ListNode();
var prev = empty;
var i = 0;
while (head && head.next) {
if (k > (length - i)) break;
var [rHead, rTail] = reverseKItem(head, k);
prev.next = rHead;
prev = rTail;
head = rTail.next;
i += k;
}
return empty.next || head;
};
var head = new ListNode(1);
var aaa = head;
head.next = new ListNode(2);
head = head.next;
head.next = new ListNode(3);
head = head.next;
head.next = new ListNode(4);
head = head.next;
head.next = new ListNode(5);
console.log(reverseKGroup(aaa, 3));出处：LeetCode 算法第49题
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"], 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
遍历所有项，将字符串转成数组，进行排序，将排序后的数组作为key，用map存储所有同意类型的字符串。
var groupAnagrams = function (strs) {
var result = [];
var map = {};
for (var i = 0, len = strs.length; i < len; i++) {
var temp = strs[i].split('').sort();
if (!map[temp]) {
map[temp] = [];
map[temp].push(strs[i]);
} else {
map[temp].push(strs[i]);
}
}
for (var key in map) {
result.push(map[key]);
}
return result;
};出处：LeetCode 算法第74题
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 输出: true示例 2:
输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 输出: false
由于数组是按顺序递增的，所以我们可以通过二分查找法来进行搜索
var searchMatrix = function (matrix, target) {
if (matrix.length == 0) {
return false;
}
var n = matrix.length;
var m = matrix[0].length;
var left = 0;
var right = n * m - 1;
while (left <= right) {
var mid = Math.floor((left + right) / 2);
var current = matrix[Math.floor(mid / m)][mid % m];
if (current == target) {
return true;
} else if (current < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
};出处：LeetCode 算法第46题
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
类似的这种问题只能通过递归遍历的方式来获得所有可能的情况。与前面的组合总和的思路是一样的。
var permute = function (nums) {
if (nums.length === 0) {
return [];
}
var result = [];
var temp = [];
DFS(nums, 0, result, temp);
return result;
};
function copy(array) {
var result = [];
for (var i = 0, len = array.length; i < len; i++) {
result.push(array[i]);
}
return result;
}
function DFS(nums, level, result, temp) {
if (temp.length === nums.length) {
result.push(copy(temp));
};
for (var i = 0; i < nums.length; i ++) {
if (temp.indexOf(nums[i]) < 0) {
temp.push(nums[i]);
DFS(nums, i, result, temp);
temp.pop(nums[i]);
}
}
}使用vue的服务端渲染技术，开发与上线两套环境
https://github.com/louzhedong/vue-ssr-render
git clone https://github.com/louzhedong/vue-ssr-render
cd vue-ssr-render
npm install
开发环境运行 npm run dev
线上打包 npm run build
线上运行 npm start
或者采用pm2运行 pm2 start process.yml --env production
css中有好多实现居中的方式，在项目中经常不知道使用哪种方式会比较好，所以记录下来。
水平垂直居中包括行内元素居中，以及块级元素居中
行内元素html结构
<div class="outer">
<span class="inner"></span>
</div>
块级元素结构
<div class="outer">
<div class="inner"></div>
</div>
基础样式
<style>
.outer {
width: 400px;
height: 400px;
border: 1px solid red;
}
.outer .inner {
width: 50px;
height: 50px;
border: 1px solid blue;
}
</style>
.outer {
text-align: center;
}
当使用这种方式时，内部元素必须定义宽度，不然margin属性会无效
.outer .inner {
margin: auto;
}
前面这种方式需要为内部元素定义宽度，如果不想定义宽度，可以设置内部元素的display 为 table，它的宽度会由内部元素来撑开。
.outer .inner {
margin: auto;
display: table;
}
为内部元素设置display 为inline，将它转换为行内元素，再对父元素使用text-align: center 可以实现水平居中，缺点就是内部元素无法设置宽度。
.outer {
text-align: center;
}
.outer .inner {
display: inline;
}
方案三无法为内部元素设置宽度，但是采用inline-block，则可以为内部元素设置宽度。
.outer {
text-align: center;
}
.outer .inner {
display: inline-block;
}
这种方式不需要知道内部元素宽度。
.outer .inner {
position: relative;
left: 50%;
transform: translateX(-50%);
}
.outer {
position: relative;
}
.outer .inner {
position: absolute;
left: 50%;
margin-left: -25px;
}
用的最多的方式，但低版本浏览器会有兼容问题
.outer {
display: flex;
justify-content: center; // 主轴上居中
}
外部元素设置line-height
.outer {
line-height: 400px;
}
使用绝对定位将内部元素的顶部定位在中间，再通过margin-top 负值拉回高度，需要提前知道内部元素的高度
.outer {
position: relative;
}
.outer .inner {
position: absolute;
top: 50%;
margin-top: -25px;
}
这种方式不需要知道内部元素的高度，兼容性也很好
.outer {
position: relative;
}
.outer .inner {
position: absolute;
top: 0;
bottom: 0;
left: 0;
right: 0;
margin: auto;
}
前面水平居中的时候也出现过这种方式，也可以使用position: absolute方式，但要对应地将外部元素设置成position: relative
.outer .inner {
position: relative;
top: 50%;
transform: translateY(-50%);
}
.outer {
display: table-cell;
vertical-align: middle;
}
原理是新建一个inner的兄弟元素，高度撑开整个容器，再对inner使用vertical-align: middle 使元素居中，不需要知道内部元素的高度
html结构
<div class="outer">
<div class="inner"></div>
<div class="sibling"></div>
</div>
.outer .inner {
vertical-align: middle;
display: inline-block;
}
.outer .slibing {
height: 400px;
display: inline-block;
vertical-align: middle;
}
原理和上面的方式一样，只是通过伪元素去撑开高度
.inner {
display: inline-block;
vertical-align: middle;
}
.outer::before {
content: '';
height: 100%;
display: inline-block;
vertical-align: middle;
}
.outer {
display: flex;
align=items: center;
}
欢迎继续补充~
出处：LeetCode 算法第17题
给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
本题是一个组合题，通过递归遍历来找出所有的组合
解答
var arr = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
var letterCombinations = function (digits) {
var result = [];
if (digits.length === 0) {
return result;
}
var temp = ""
lettermix(digits, result, 0, temp);
return result;
};
function lettermix(digits, result, index, temp) {
if (index == (digits + "").length) {
result.push(temp);
return;
}
for (var i = 0, length = arr[(digits + "")[index]].length; i < length; i++) {
temp = temp + arr[(digits + "")[index]][i];
lettermix(digits, result, index + 1, temp);
temp = temp.substr(0, temp.length - 1);
}
}出处：LeetCode 算法第22题
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 *n = *3，生成结果为：
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
按正常的思路去思考会感觉无从下手，需要有一个转换的过程，有效组合中左括号和右括号的总数是相等的，而且在构建有效序列的时候左括号的数量始终都是不小于右括号的数量的，如果出现了左括号的数量小于右括号的数量，那本次解法就是错误的。思路是递归地构建序列，遍历所有组合，得到有效的组合。
var generateParenthesis = function (n) {
var result = [];
DFS(n, n, "", result);
return result;
};
function DFS(left, right, temp, result) {
if (left > right) {
return;
}
if (left === 0 && right === 0) {
result.push(temp);
} else {
if (left > 0) {
DFS(left - 1, right, temp + '(', result);
}
if (right > 0) {
DFS(left, right - 1, temp + ')', result);
}
}
}出处：LeetCode 算法第23题
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
通过数组构建，将链表中所有的元素存放到一个数组中，对数组进行排序，然后将数组构建成链表形式输出
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
var array = [];
for (var i = 0, length = lists.lnegth; i < length; i++) {
var temp = lists[i];
while (temp != null) {
array.push(temp.val);
temp = temp.next;
}
}
// array 包含了所有的元素
array.sort(function (a, b) { return a - b });
var result = new ListNode(0);
var head = result;
for (var i = 0, length = array.length; i < length; i++) {
var newNode = new ListNode(array[i]);
result.next = newNode;
result = result.next;
}
return head.next;
};出处：LeetCode 算法第31题
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3→1,3,2
3,2,1→1,2,3
1,1,5→1,5,1
从尾部遍历，找到第一个后者大于前者的，交换他们的值，对后面的数组进行顺序排序。如果无法找到，就对整个数组进行排序。
var nextPermutation = function (nums) {
var length = nums.length,
i = 0,
j = 0,
flag = false;
if (length === 0) {
return [];
}
for (i = length - 1; i >= 0; i--) {
for (j = length - 1; j > i; j--) {
if (!flag) {
if (nums[i] < nums[j]) {
var temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
quickSort(nums, i + 1, length - 1);
flag = true;
break;
}
}
}
}
if (!flag) {
quickSort(nums, i + 1, length - 1);
}
};
function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
function partition(arr, left, right) { //分区操作
var pivot = left, //设定基准值（pivot）
index = pivot + 1;
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}出处：LeetCode 算法第19题
给定一个链表，删除链表的倒数第 *n *个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
由于只能实现一遍扫描，所以我们可以使用两个指针，让一个指针先走一定的步数，使两个指针之间间隔n步，当前面的指针移动到链表尾部的时候，后面的指针刚好处于要删除的节点的前面，将它的next指向next.next就可以了。为了处理删除第一个节点的情况，我们在链表头部新建一个节点，使其指向第一个节点。
var removeNthFromEnd = function(head, n) {
var result = new ListNode(0);
result.next = head;
var second = result;
while(n > 1) {
head = head.next;
n--;
}
while(head.next != null) {
head = head.next;
second = second.next;
}
second.next = second.next.next;
return result.next;
};出处：LeetCode 算法第70题
假设你正在爬楼梯。需要 n 步你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
**注意：**给定 n 是一个正整数。
示例 1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 步 + 1 步 2. 2 步示例 2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 步 + 1 步 + 1 步 2. 1 步 + 2 步 3. 2 步 + 1 步
本题思路为动态规划，考虑最后一步的走法，有两种情况，走一步或者走两步，所以f(n) = f(n-1) + f(n-2)
方法一：不创建额外空间
var climbStairs = function (n) {
if (n === 1) {
return 1;
} else if (n === 2) {
return 2;
} else {
return climbStairs(n - 1) + climbStairs(n - 2);
}
};类似于Fibonacci数列，由于在内部做了大量重复的运算，有很差的时间复杂度
解法二：创建一个额外的数组
var climbStairs = function (n) {
var dp = [];
dp[1] = 1;
dp[2] = 2;
if (n >= 3) {
for (i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
}
return dp[n];
}时间复杂度为O(n)，但需要创建一个额外的数组空间。
出处：LeetCode 算法第39题
给定一个无重复元素的数组
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的数字可以无限制重复被选取。说明：
- 所有数字（包括
target）都是正整数。- 解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ]示例 2:
输入: candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]
整体思路还是采用递归遍历的方法，遍历所有可能的组合。由于在JS 中数组是引用类型，所有要实现一个copy函数来实现数组的复制。
var combinationSum = function (candidates, target) {
var result = [];
var temp = [];
var sum = 0;
candidates.sort(function (a, b) {
return a - b;
})
DFS(candidates, sum, 0, target, temp, result);
return result;
};
function copy(array) {
var result = [];
for (var i = 0, len = array.length; i < len; i++) {
result.push(array[i]);
}
return result;
}
function DFS(candidates, sum, level, target, temp, result) {
if (sum > target) {
return;
}
if (sum == target) {
result.push(copy(temp));
return;
}
for (var i = level; i < candidates.length; i++) {
sum += candidates[i];
temp.push(candidates[i]);
DFS(candidates, sum, i, target, temp, result);
temp.pop();
sum -= candidates[i];
}
}
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.