牛客算法题

算法题"/>

牛客算法题

数据结构与算法

合并两个有序数组

思路：A数组有足够的空间。三指针，一个指向A数组元素的末尾i，一个指向B数组元素的末尾j，一个指向A数组的最后。比较i和j指向的元素谁大，大的放在A数组最后K的位置上。然后跟着移动指针。

判断条件: while(k>=0&&i>=0&&j>=0)这里一定要等于0

代码：

public void merge(int A[], int m, int B[], int n) {if(m==0){for(int i=0; i<n; i++){A[i] = B[i];}}else {if(n==0)return;else{int i = m-1, j=n-1, k=m+n-1;while(k>=0 && i>=0 && j>=0){if(A[i]>=B[j]){A[k--] = A[i--];}else{A[k--] = B[j--];}}//A的数组先结束。 if(i==-1){for(int l=0; l<j+1; l++){A[l] = B[l];}}else{return;} }}}

合并区间

给出一组区间，请合并所有重叠的区间。请保证合并后的区间按区间起点升序排列。

输入：[[10,30],[20,60],[80,100],[150,180]]

返回：[[10,60],[80,100],[150,180]]

思路：先按照数组起点升序排序，如果第二个数组起点比第一个数组的终点大则合并。

function merge( intervals ) {// write code hereif(intervals.length===0)return [];intervals.sort((a, b)=>a.start-b.start);let pre = intervals[0]let cur;let res = [];for(let i=1; i<intervals.length; i++){cur = intervals[i];if(cur.start <= pre.end){//如果有交集，合并区间pre.end = Math.max(cur.end, pre.end);}else{res.push(pre);pre = cur;}}res.push(pre)//将最后一组推进去return res;
}

合法的括号序列

思路：入栈，查看栈顶元素与当前将要入站的元素是否匹配，匹配则将栈顶stack[stack.length-1](JS没有isEmpty()函数，我恨)出栈。

function isValid( s ) {// write code hereif(s.length%2!==0)return false;let stack = [];var c;for(var i=0; i<s.length; i++){c = s.charAt(i);if((c===')' && stack[stack.length-1]==='(') || (c===']' && stack[stack.length-1]==='[')||(c==='}' && stack[stack.length-1]==='{')){stack.pop();}else{stack.push(c);}}return stack.length===0;
}
module.exports = {isValid : isValid
};

链表

链表中环的入口节点

/** function ListNode(x){*   this.val = x;*   this.next = null;* }*/function detectCycle( head ) {// write code hereif(head===null || head.next===null)return null;var slow = head;var fast = findMeet(head);if(fast===null){return null;}else{//找到相遇节点后，设置快慢指针都走一步while(slow!=fast){slow = slow.next;fast = fast.next;}return slow;} 
}
//找相遇的节点
function findMeet(head){if(head===null || head.next===null)return null;var slow = head;var fast = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast===slow)return fast;}return null;
}
module.exports = {detectCycle : detectCycle
};

删除链表倒数第n个结点

思路：双指针，快指针先走n-1步，如果块指针走到空了，说明要删除的是头结点，直接返回head.next

/** function ListNode(x){*   this.val = x;*   this.next = null;* }*//*** * @return ListNode类*/function removeNthFromEnd( head ,  n ) {let slow = head, fast = head;while(n>0){fast = fast.next;n--;}if(!fast){slow = slow.next;return slow;}while(fast.next){slow = slow.next;fast = fast.next;}slow.next = slow.next.next;return head;
}

两个链表的公共结点

思路：A,B指针指向链表1和链表2， A走完链表1再从链表2的头部开始走， B走完链表2再从链表1的头部开始走,如果有相同结点就会相遇。

如果没有相同的结点，a,b走完了两个链表，则a==b==null,退出循环直接返回null。

function FindFirstCommonNode(pHead1, pHead2)
{// write code herelet A = pHead1, B = pHead2;//如果没有相同的结点，a,b走完了两个链表，则a==b==null,退出循环直接返回nullwhile(A!==B){不能用A.next判断，要先判断A不为空才能判断A.nextA = (A=== null)? pHead2: A.next;B = (B=== null)? pHead1: B.next;}return A;
}

两个链表生成相加链表

9->3->7

6->3

生成：1->0->0->0

思路：先将两个链表进行逆转，再相加。最后生成的链表再逆转一次

/** function ListNode(x){*   this.val = x;*   this.next = null;* }*//*** @return ListNode类*/function addInList( head1 , head2 ) {if(!head1) return head2;if(!head2) return head1;let head = new ListNode(-1);//这里不要赋值为null，否则在return head.next可能会null.nextlet p = h1, q = h2, cur = head, carry=0,sum=0;while(p || q || carry !==0){sum = (p?p.val:0) + (q?q.val:0) + carry;cur.next = new ListNode(sum%10);carry = Math.floor(sum/10);cur = cur.next;p = p?p.next:null;q = q?q.next:null;}return reverse(head.next);
}function reverse(node){if(!node)return node;let pre = null, cur = node;while(cur!==null){let temp = cur.next;cur.next = pre;pre =  cur;cur = temp;  }return pre;
}

单链表的排序

输入：1->3->2->4->5

输出：1->2->3->4->5

思路：先把所有节点放入数组，对数组排序，然后在原来的链表上修改值

function sortInList( head ) {// write code herelet cur = head;let arr = []while(cur){arr.push(cur.val);cur = cur.next;}arr.sort((a,b)=>a-b)let res = head;let dummy = res;arr.forEach(item=>{res.val = item;res = res.next;})return dummy;
}

 合并两个排序的链表

function Merge(pHead1, pHead2){// write code hereif(!pHead1)return pHead2;if(!pHead2)return pHead1;if(pHead1.val<=pHead2.val){pHead1.next = Merge(pHead1.next, pHead2);return pHead1;}else{pHead2.next = Merge(pHead1, pHead2.next);return pHead2;}
}

合并k个已排序的链表 

思路：将多个链表两两先合并（合并两个排序链表）。

function mergeKLists( lists ) {// write code hereif(lists.length===0)return null;return mergeHelper(lists, 0, lists.length-1);
}function mergeHelper(lists, lo, hi){if(hi===lo)return lists[lo];let mid = lo + Math.floor((hi - lo)/2);let l1 = mergeHelper(lists, lo, mid);let l2 = mergeHelper(lists, mid+1, hi);return merge2Lists(l1, l2);
}
function merge2Lists(l1, l2){if(!l1)return l2;if(!l2)return l1;if(l1.val <= l2.val){l1.next = merge2Lists(l1.next, l2);return l1;}else{l2.next = merge2Lists(l1, l2.next);return l2;}
}

链表内指定区间翻转 

思路：

• 先局部翻转

• 再将已经反转好的局部链表与其他节点建立连接，重构链表。

function reverseBetween( head ,  m ,  n ) {// write code herelet dummy = new ListNode(-1);dummy.next = head;let pre = dummy, p1, p2;//走到m的前一个for(let i=0; i<m-1; i++){pre = pre.next;}p1 = pre.next;p2 = pre;//走到第n个for(let i=0; i<n-m+1; i++){p2 = p2.next;}//记下第n+1个用来后续连接。let rightNode = p2.next;reverse(p1, p2);pre.next = p2;p1.next = rightNode;return dummy.next;
}
function reverse(l1, l2){let pre = null;let cur = l1while(pre!==l2){let temp = cur.next;cur.next = pre; pre = cur;cur = temp;}
}

二叉树

重建二叉树

给定前序和中序遍历的数组，重建二叉树

/* function TreeNode(x) {this.val = x;this.left = null;this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{// write code hereif(!pre.length || !vin.length)return null;let curNode = new TreeNode(pre.shift());let index = vin.indexOf(curNode.val);curNode.left = reConstructBinaryTree(pre, vin.slice(0, index));curNode.right = reConstructBinaryTree(pre, vin.slice(index+1))return curNode;
}

二叉树的之字形层序遍历

思路：使用两个先进后出的栈，栈1先右子结点进，栈二先左子节点进。返回的是[[], [],[]]类型的数组。

/** function TreeNode(x) {*   this.val = x;*   this.left = null;*   this.right = null;* }*//*** * @param root TreeNode类 * @return int整型二维数组*/
function zigzagLevelOrder( root ) {// write code hereif(root===null)return [];//栈1先右进，栈2先左进var stack1 = [root];var stack2 = [];var res = [];while(stack1.length!==0 || stack2.length!==0){var row = [];if(stack1.length!==0){while(stack1.length!=0){var cur = stack1.pop();row.push(cur.val);if(cur.left!=null){stack2.push(cur.left);}if(cur.right!=null){stack2.push(cur.right);}}}else{while(stack2.length>0){var cur = stack2.pop();row.push(cur.val);if(cur.right!=null){stack1.push(cur.right);}if(cur.left!=null){stack1.push(cur.left);}}}res.push(row);}return res;
}
module.exports = {zigzagLevelOrder : zigzagLevelOrder
};

二叉树中和为某个值的路径

function pathSum(root, sum){let res = [];if(!root)return res;let path = [];dfs(root, sum, path, res);return res;
}//不用作node空判断退出循环，因为如果node.left和right都为空了就会退出递归。
function dfs(node, sum, res, path){path.push(node.val);if(node && !node.left && !node.right && node.val===sum){res.push(path)}//    通过slice复制每个支路path的路径if(node.left) dfs(node.left, sum - node.val, res, path.slice())if(node.right) dfs(node.right, sum - node.val, res, path.slice())
}

function hasPathSum( root ,  sum ) {// write code hereif(!root)return false;if(root.val>sum)return false;return dfs(root, sum);
}
function dfs(node, sum){
//     if(!node)return false;if(node && !node.left && !node.right && sum===node.val)return true;return dfs(node.left, sum-node.val)|| dfs(node.right, sum-node.val);
}

平衡二叉树

平衡二叉树：是一颗空树或者它的左右两个子树的高度差不超过1

思路：

helper:

当节点左右子树的深度差<1,则返回当前子树的深度加上1：max(left, right)+1;

当左右子树深度差>2, 则返回-1， 代表此子树不是平衡树

终止条件：当root为空，直接返回0

function isBalanced(pRoot){let flag = helper(pRoot);if(flag===-1){return false;}else{return true;}
}function helper(root){if(!root)return 0;let left = helper(root.left)if(left===-1)return -1;let right = helper(root.right);if(right===-1)return -1;return Math.abs(left-right)>1 ? -1 : Math.max(left, right) +1}

二叉树中两个节点的公共祖先

高度

思路：

1. 先判断root结点是否等于o1或者o2,是的话直接返回root.val,不是则直接继续

2. 遍历二叉树

3.有四种情况：

• 左右都找到了。说明 o1 和 o2 分居在 root 的两侧，那么最低公共祖先为 root，返回 root
• 左边没找到右边也没找到。返回 null。
• 左边没找到右边找到了。说明 p 和 q 全都在 root 的右侧，加上我们在第一步就知道 root 不等于 p 也不等于 q，所以最低公共祖先在 root 的右子树，返回右子树。
• 左边找到了右边没找到。说明 p 和 q 全都在 root 的左侧，加上我们在第一步就知道 root 不等于 p 也不等于 q，所以最低公共祖先在 root 的左子树，返回左子树。

function lowestCommonAncestor( root ,  o1 ,  o2 ) {// write code herereturn helper(root, o1, o2).val; 
}
function helper(root, o1, o2){if(root===null || root.val===o1 || root.val===o2)return root;let leftSon = helper(root.left, o1, o2);let rightSon = helper(root.right, o1, o2);if(leftSon && rightSon){//如果此根节点的左右结点分别等于o1,o2，直接返回此根节点的值return root;}else if(!leftSon && !rightSon){//如果左边没找到，右边也没找到，返回nullreturn null;}else if(!leftSon && rightSon){//右边找到了，左边没找到return rightSon;}else{//左边找到了，右边没找到return leftSon;}
}

二叉搜索树的最近公共祖先

左子树都比根节点小，右子树都比根节点大

思路：//也就是只三种情况：

        //1.root比p,q都大,到root的左子树找

        //2.root比p,q都小,到root的右子树找

        //3.（proot）、（root为根节点，p或q为子节点）,返回root

* function TreeNode(val) {*     this.val = val;*     this.left = this.right = null;* }*/
var lowestCommonAncestor = function(root, p, q) {if(!root)return root;while(root){if(root.val>p.val && root.val>q.val){root = root.left;}else if(root.val<p.val && root.val<q.val){root = root.right;}else{break;}}return root;
};

 判断对称二叉树

function isSymmetric( root ) {if (!root)return true;return isSame(root.left, root.right);
}function isSame(a, b){if(!a && !b){return true;}else {if(!a||!b) return false;}return a.val===b.val && isSame(a.left, b.right) && isSame(a.right, b.left);
}

 二叉树的右视图

站在二叉树右边，能看到的结点

深度遍历，先遍历右子树，如果当前层数=数组长度，说明是这一层需要添加的第一个节点（右结点）。再递归

var rightSideView = function(root) {let list = [];let deep = 0;helper(root, list, deep); return list;
};function helper(node, list, deep){if(!node)return;if(list.length===deep){//如果当前层数=数组长度，说明是这一层需要添加的第一个节点。list.push(node.val);     }deep++;helper(node.right, list, deep);helper(node.left, list, deep);
}

反转字符串

/*** 反转字符串* @param str string字符串 * @return string字符串*/
function solve( str ) {// write code herelet len = str.length;if(len===0)return str;let str1 = "";let i=0, j=len-1;while(j>=0){str1 += str[j--];}return str1;
}
module.exports = {solve : solve
};

//简洁
function solve( str ) {return str.split('').reverse().join("");
}
module.exports = {solve : solve
};

顺时针打印数组

function spiralOrder( matrix ) {// write code hereif (!matrix.length) return []let left = 0;let top = 0;let right = matrix[0].length-1;let bottom = matrix.length-1;let arr = new Array((right+1)*(bottom+1));let cnt = 0while(left<=right && top<=bottom){for(let i=left; i<=right; i++){arr[cnt++] = matrix[top][i];}top++;for(let i=top; i<=bottom; i++){arr[cnt++] = matrix[i][right];}right--;for(let i=right; i>=left&&top<=bottom; i--){//逆着回来的时候记得两个条件都要判断arr[cnt++] = matrix[bottom][i];}bottom--;for(let i=bottom; i>=top&&left<=right; i--){arr[cnt++] = matrix[i][left];}left++;}return arr;
}

fibonacci数列

1.递归

2.动态规划

2.
function Fibonacci(n)
{// write code herelet dp = new Array(n+1);dp[0] = 0;dp[1] = 1;for(let i=2; i<=n; i++){dp[i] = dp[i-1]+dp[i-2];}return dp[n]
}

判断回文

思路：双指针

function judge( str ) {// write code herelet i=0, j=str.length-1;while(i<=j){if(str[i++]!==str[j--]){return false;}}return true;
}

15. 最长回文子串

public class Solution {//返回长度public int getLongestPalindrome(String A, int n) {// write code hereif(n==0||n==1)return n;char[] c = A.toCharArray();int len1,len2,len;int start = 0, end = 0, maxLen = 0;for(int i=0; i<n; i++){len1 = helper(c, i, i, n);len2 = helper(c, i, i+1, n);len = Math.max(len1,len2);if(len > maxLen){maxLen = len;}}return maxLen;}//返回子串public int getLongestPalindrome(String A, int n) {// write code hereif(n==0||n==1)return n;char[] c = A.toCharArray();int len1,len2,maxLen;int start = 0, end = 0;for(int i=0; i<n; i++){len1 = helper(c, i, i, n);len2 = helper(c, i, i+1, n);maxLen = Math.max(len1,len2);if(maxLen > end-start){start = i - (maxLen-1)/2;end = i + maxLen/2;}}return A.subString(start, end+1);}public int helper(char[] c, int left, int right, int n){int L = left, R = right;while(L>=0 && R<n && c[L]==c[R]){L--;R++;}return R-L-1;}
}

三数之和

思路：先排序，for循环先定位一个num[i]，再分别用L,R指针指向i+1和最后一个数，和大于0时R--，小于0时L++

function threeSum( num ) {// write code hereconst len = num.length;if(len<3)return new Array(0);num.sort(function(a,b){return a-b})let res = [];for(let i=0; i< len; i++){let L = i+1;let R = len-1;let sum = 0;if(i>0 && num[i]===num[i-1])continue;while(L<R){sum = num[i] + num[L] + num[R];if(sum===0){res.push([num[i], num[L], num[R]]);while(L<R && num[L]===num[L+1])L++;//跳过重复的相等的时候才要考虑。while(L<R && num[R]===num[R-1])R--;L++;R--;}else if(sum>0){R--;}else{L++;}}}return res;
}

最长无重复子数组

输入：[1,2,3,1,2,3,2,2]

返回值：3

说明：最长子数组为[1,2,3]  

 思路：因为哈希表可以用键来存储数组元素，用值来存储数组元素的位置，这样碰到重复元素后把j的坐标移到重复的元素后一位。并更新键值

function maxLength( arr ) {// write code hereif(!arr)return 0;if(arr.length===1)return 1;let maxLen = 0;let map = new Map();for(let i=0, j=0; i<arr.length; i++){if(map.has(arr[i])){j = Math.max(j,map.get(arr[i])+1);//把j的坐标移到重复的元素后一位。}map.set(arr[i], i);maxLen = Math.max(maxLen, i-j+1);}return maxLen;
}

包含min的最小栈

 输入：[[1,3],[1,2],[1,1],[3],[2],[3]]

1-入栈

2-出栈

3-最小栈

输出：[1,2]

思路：一个主栈，直接作入栈出栈操作；

           一个辅助栈，

            入栈操作：当辅助栈为空直接压入，不为空则判断当前元素与辅助栈栈顶元素大小。比栈顶元素小则入栈，比栈顶元素大则将辅助栈的栈顶元素再压一次。

            出栈操作：和主栈一起将栈头pop出

function getMinStack( op ) {// write code herelet stack1 = [];//主栈let stack2 = [];//辅助栈let res = [];//结果输出一维数组let len = op.length;for(let i=0; i<len; i++){
//         入栈操作if(op[i][0]===1){stack1.push(op[i][1]);if(!stack2.length){//如果辅助栈为空，直接入栈stack2.push(op[i][1]);}else{//辅助栈不为空if(op[i][1]<stack2[stack2.length-1]){//要入栈的元素比辅助栈栈顶元素小，加入辅助栈stack2.push(op[i][1]);}else{//要入栈的元素比辅助站栈顶元素大，将辅助栈栈顶元素再压入一次stack2.push(stack2[stack2.length-1]);}}}else if(op[i][0]===2){//出栈操作stack1.pop();stack2.pop();}else{//最小栈元素res.push(stack2[stack2.length-1])}}return res;
}
module.exports = {getMinStack : getMinStack
};

数组中的第K大 

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(1<=K<=n)，请返回第K大的数(包括重复的元素，不用去重)，保证答案存在。

function findKth( a ,  n ,  K ) {// write code hereif(a===null || K>a.length)return -1;helper(a, 0, n-1, n-K);return a[n-K];
}function helper(a, begin, end, k){if(begin>=end)return;let index = quickSort(a, begin, end);if(index>k){helper(a, begin, index-1, k);}else if(index<k){helper(a, index+1, end, k);}else{return;}
}function quickSort(arr, begin, end){let flag=arr[begin], i=begin , j=end;while(i<j){while(i<j && arr[j]>=flag){j--;}if(i<j){arr[i] = arr[j];}while(i<j && arr[i]<=flag){i++;}if(i<j){arr[j] = arr[i];}}arr[i] = flag;return i;
}

字符串出现次数的 TopK

如果次数相同的则按照字典书序书输出

function topKstrings( strings ,  k ) {// write code herestrings = strings.sort();//按字典排序let map = new Map();for(let item of strings){if(map.has(item)){map.set(item, map.get(item)+1);}else{map.set(item, 1);}}let res = [];map.forEach((value,key)=>{res.push([key, value]);})res.sort((a, b)=> b[1] - a[1])return res.slice(0,k);
}

位运算

数组中出现超过一半的数字

思路：

1. 先排序，再找中位数

2. 投票法：先定一个target和计数器，遍历，如果当前的数和target不一样则计数器减一。计数器为0时，就换当前数为target。因为最终的target是出现最多的，所以计数器不会为0，最后返回的一定是它。

function MoreThanHalfNum_Solution(numbers)
{// write code here
// 排序法
//     let len = numbers.length;
//     numbers.sort((a,b)=>a-b)
//     return numbers[Math.floor((len-1)/2)]//投票法if(!Array.isArray(numbers))return -1let target = numbers[0];let cnt = 1;for(let i=1; i<numbers.length; i++){if(numbers[i]!==target){cnt--}else{cnt++}if(cnt===0){target = numbers[i];cnt = 1;}}return target; 
}

 数组中只出现一次的数（其他的出现k次）

思路：因为其余的数都是出现k次，只有一个出现一次。对每一比特位进行加和再除k求余。其他出现k次的数都余0

[5，4, 1，1, 5, 1, 5 ]

101

100

001

001

101

001

101

------对每一位先求和，再除k取余

100

function foundOnceNumber( arr ,  k ) {let res = 0;for(let i=0; i<32; i++){let sum = 0;for(let k of arr){//依次右移num，同1相与，计算每一位上1的个数sum += (k>>i)&1}if(sum%k!==0){res += 1<<i;//因为只出现一次，所以取余的值是1，再位移}}return res;
}

 数组中只出现一次的两个数字（其余都出现两次）

【1,1,3,3,5,5,a,b】

思路1：通过数组和键值进行统计

思路2：

先对整个数组求异或得到c，可以知道c其实就是a^b=c。那么对于c，假如c二进制的第一位是1，其实就代表a二进制的第一位是1（或0），b二进制的第一位是0（或1），总而言之如果第一位的c等于1，那么a和b在第一位肯定不相等。

找到整个数组异或后的数的第一位不为0的位，根据这位对数组分成两组，分别包含a和b。再分别对两个数组分别异或得到a,b

function FindNumsAppearOnce( array ) {// write code here//先把数组里所有数字进行异或，结果是那两个只出现一次的两个数的异或let xor = 0;for(let k of array){xor ^= k;}let flag = 0;//用于记录xor第一个是1的位数for(let i=0; i<32; i++){if(((xor>>i)&1)===1){flag = i;break;}}let a=0, b=0;for(let k of array){if(((k>>flag)&1)===1){a ^= k;}else{b ^= k;}}return [a, b].sort((a,b)=>a-b)
}

动态规划

1.01背包问题

0-1 背包问题：给定 n 种物品和一个容量为 c 的背包，物品 i 的重量是 wi，其价值为 vi 。

思路：

声明一个 大小为  m[n][c] 的二维数组，m[ i ][ j ] 表示 在面对第 i 件物品，且背包容量为  j 时所能获得的最大价值 ：

（1）j < w[i] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿

（2）j>=w[i] 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。

如果拿取，m[ i ][ j ]=m[ i-1 ][ j-w[ i ] ] + v[ i ]。 这里的m[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品，背包容量为j-w[i]时的最大价值，也是相当于为第i件物品腾出了w[i]的空间。

如果不拿，m[ i ][ j ] = m[ i-1 ][ j ] , 同（1）

最后比较这两种情况哪种价值最大：

if(j>=w[i])
    m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
else
    m[i][j]=m[i-1][j];

//处理输入输出
let line;
line = readline().split(' ');
let N = parseInt(line[0]);
let p = parseInt(line[1]);let W = [];
let V = [];
for(let i=0;i<N;i++){let line=readline().split(" ");let v=parseInt(line[0]);let w=parseInt(line[1]);V.push(v);W.push(w);
}//function
let dp = new Array(N+1);
for(let i=0; i<=N; i++){dp[i] = new Array(p+1).fill(0);
}for(let i=1; i<=N; i++){for(let j=1; j<=p; j++){if(j>=W[i-1]){dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-W[i-1]]+V[i-1]);}else{dp[i][j] = dp[i-1][j];}}
}
print(dp[N][p])

2.拼硬币

给你k种面值的硬币，面值分别为c1, c2 ... ck，每种硬币的数量无限，再给一个总金额amount，最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。

思路：
dp[i]表示总金额为i时需要的最少的硬币个数。
状态转移方程：假设coins=[1,2,5]
dp[i] = 1 + dp[i-1] # i-1元加上一枚1元总共的硬币数
dp[i] = 1 + dp[i-2] # i-2元加上一枚两元
dp[i] = 1 + dp[i-5] # i-5元加上一枚5元
从中取最小的，dp[i] = min(1 + dp[i-coin] for coin in coins if i >= coin)
或写为：dp[i] = min(dp[i], 1 + dp[i-coin]) ​
初始化状态：dp[0]=0，0分无法用任何面额的硬币来表示

let line = readline().split(' ');
let coins = [];
for(let i=0; i<line.length-1; i++){coins.push(parseInt(line[i]));
}
let value = parseInt(line[line.length-1]);
let res;dp[0] = 0;
for(let i=1; i<=value; i++){for(let j=0; j<coins.length; j++){if(i>=coins[j]){dp[i] = Math.min(dp[i], dp[i-coins[j]]+1)}}
}
//如果dp[value]等于value+1(value个一元硬币还要再加上一个),
print(dp[value]===value+1 ? -1 : dp[value]);

最长公共子序列（LCS）

如果出现c[i-1][j]等于c[i][j-1]的情况，说明最长公共子序列有多个，故两边都要进行递归

返回LCS：递归过程，从最后往前。链接

/*** longest common subsequence* @param s1 string字符串 the string* @param s2 string字符串 the string* @return string字符串，如果没有公共子序列则返回-1*/
function LCS( s1 ,  s2 ) {// write code hereif(s1.length===0 || s2.length===0)return '-1';let m = s1.length, n = s2.length;let res = '';var dp = new Array(m+1);for(let i=0; i<=m; i++){dp[i] = new Array(n+1).fill(0);}for(let i=1; i<m+1; i++){for(let j=1; j<n+1; j++){if(s1.charAt(i-1)==s2.charAt(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]);}}}//从后往前找子序列while(m>0 && n>0){if(s1[m-1]===s2[n-1]){res = s1[m-1]+res;m--;n--;}else{if(dp[m][n-1]>=dp[m-1][n]){n--;}else{m--;}}}return res==="" ? -1:res;
}
module.exports = {LCS : LCS
};

 最长公共子串

思路：用一个maxLen记录最长的dp[][], 用index记录下标，随时更新。

/*** @return string字符串*/
function LCS( str1 ,  str2 ) {// write code hereif(str1.length===0||str2===0)return "-1";let len1 = str1.length, len2 = str2.length;let dp = new Array(len1);let maxLen = 0, endIndex=0;for(let i=0; i<len1; i++){dp[i] = new Array(len1).fill(0);}for(let i=0; i<len1; i++){for(let j=0; j<len2; j++){if(str1.charAt(i)===str2.charAt(j)){if(i===0 || j===0){dp[i][j] = 1;}else{dp[i][j] = dp[i-1][j-1] + 1;}}if(dp[i][j]>maxLen){maxLen = dp[i][j];endIndex = i;}}}return str1.substring(endIndex-maxLen+1, endIndex+1);
}
module.exports = {LCS : LCS
};

链表

3. 最长递增子序列

输入：[2,1,5,3,6,4,8,9,7]

返回值：[1,3,4,8,9]

动态规划解法o（N*N）

function LIS( arr ) {let dp = new Array(arr.length).fill(1);let maxLen = 0;//计算长度for(let i=1; i<arr.length; i++){for(let j=0; j<i; j++){if(arr[i] > arr[[j]){dp[i] = Math.max(dp[i], dp[j]+1);maxLen = math.max(maxLen, dp[i]);}}}//拼成子串let res = new Array(maxLen);for(let i=arr.length-1; i>=0; i++){if(arr[i]===maxLen)res[--maxLen] = arr[i];}return res;}

 贪心+二分搜索o(NlogN)

function LIS( arr ) {// write code herelet dp = [arr[0]];//用于记录子序列的let len = [1];//用于记录长度的let curIndex = 0;//记录当前dp里面有多少个数字（是索引，真实长度要+1）for(let i=1; i<arr.length; i++){// 如果数组当前元素大于dp数组的最后一个数，直接添加到dp数组后面//第二种情况时，curIndex没有变化，是在这个范围内的某个位置插入变化的值，所以不用管curIndexif(arr[i] > dp[curIndex]){//记录序列dp[++curIndex] = arr[i];//记录长度len[i] = curIndex + 1;}else{let l = 0, r = curIndex;while(l<r){let mid = Math.floor((l + r) / 2);//这里一定要floorif(dp[mid] > arr[i]){r = mid;//这里不能mid-1,要不然会有r===l的情况使l更新不了}else{l = mid + 1;}}//curIndex没有变化，是在这个范围内的某个位置插入变化的值，所以不用管curIndexdp[l] = arr[i];len[i] = l+1;}}//从后往前找到递增子串let res = new Array(curIndex+1);for(let i=len.length-1; i>=0; i--){if(len[i] === curIndex+1){res[curIndex] = arr[i];curIndex--;}}return res;
}

4. 高楼扔鸡蛋

f(n,k)表示n层楼，手里还有k个鸡蛋时，至少需要试多少次才能找到临界楼层。

双蛋：

 先假设，最小的次数为x次。
　　首先在x层摔，那么会出现两个结果：
　　1、碎了，为了找出那一层碎了，第二个鸡蛋必须从1~x-1进行遍历的摔
　　2、没碎，那么第二次就在x+(x-1)楼层摔。

为什么是x+x-1楼层呢？
首先我们已经假设了通过x步我们就能得到答案，现在我们在x层已经用了一次了，那么就只剩下x-1步了。所以我们选择x+(x-1)层，如果碎了，我们就能通过x-2步，遍历x+1~x+(x-1)-1的所有楼层。

　    3、如果在x+(x-1)楼碎了，那么同1，遍历x+1~x+(x-1)-1
　　4、没碎，那么同2，就在x+(x-1)+(x-2)层摔

x+(x-1)+(x-2)+...+1>=100===>(x+1)x/2>=100

//o(k*N*N) 超时解法
public int superEggDrop(int k, int n) {int[][] dp = new int[k+1][n+1];for(int i=1; i<=n; i++){dp[1][i] = i;//只有一个鸡蛋时，有多少层就试多少层dp[0][i] = 0;//一个鸡蛋都没有，全为0}for(int i=1; i<=k; i++){dp[i][0] = 0;}for(int i=2; i<=k; i++){//从第二个鸡蛋开始试for(int j=1; j<=n; j++){int res = Integer.MAX_VALUE;for(int x=1; x<=j; x++){//x小于当前的层数res = Math.min(res, Math.max(dp[i-1][x-1], dp[i][j-x])+1);}dp[i][j] = res;}}return dp[k][n];}

另一个思路 ：(救命我真的看不懂)

假设dp[k][j] =N ---代表k个鸡蛋，操作数为j时，包含F楼层（目标层）的最大层数为N。按照层数j=1,2,3,4...不断迭代，第一个>=N的dp[k][j]的j就是所求的最小移动次数。

状态转移方程：

设dp[k][j] = NN，dp[k][j]可以由两个状态转换过来。在在[1,NN]中随便选1层 X 扔鸡蛋，有两种情况：

1. 碎了：那么F一定在[0, x-1]中。这时dp[k][j]的状态就退化成了dp[k-1][j-1] , 即k-1个鸡蛋，操作数为j-1, 即 dp[k-1][j-1] 代表 [0,X-1]；

2. 没碎：F一定在[X,NN]中,这时dp[k][j]的状态就退化成dp[k][j-1].

在回顾一下dp[k][j]的含义， dp[k][j] 代表了 [0,N]这样一个区间
dp[k][j-1]代表[X,NN] - > [0,NN-X] -> dp[k][j-1] = NN - X
dp[k-1][j-1] 代表[0,X-1] -> dp[k-1][j-1] = X - 1
但是dp[k][j] = NN = (X - 1) + (NN - X) + 1 = dp[k][j-1] + dp[k-1][j-1] + 1

这就是为啥有这个1

var superEggDrop = function(k, n) {let dp = new Array(k+1).fill(0).map(()=>new Array(n+1).fill(0));for(let i=1; i<=n; i++){dp[0][i] = 0;for(let j=1; j<=k; j++){dp[j][i] = dp[j][i-1] + dp[j-1][i-1] +1;if(dp[j][i] >= n) return i;}}return n
};

 5.编辑距离

s1字符串经过多少次变换变成s2字符串

let s1 = readline()
let s2 = readline()
let len1 = s1.length
let len2 = s2.length
let dp = new Array(len2+1).fill(0).map(()=>new Array(len1+1).fill(0))for(let i=0; i<=len1; i++){dp[0][i] = i;
}
for(let j=0; j<=len2; j++){dp[j][0] = j;
}for(let i=1; i<=len1; i++){for(let j=1; j<=len2; j++){if(s1[i-1]===s2[j-1]){dp[i][j] = dp[i-1][j-1]}else{dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1}}
}
print(dp[len1][len2])

最小编辑代价 

如果两个字符串的当前字符相等，则什么都不做dp[i][j]=dp[i-1][j-1]

function minEditCost( str1 ,  str2 ,  ic ,  dc ,  rc ) {// write code herelet len1 = str1.length, len2 = str2.length;let dp = new Array(len1+1).fill(0).map(x=>new Array(len2+1).fill(0))//由str1变为空字符串for(let i=0; i<=len1; i++){dp[i][0] = i * dc;}//由空字符串变为str2for(let i=0; i<len2; i++){dp[0][i] = i * ic;}for(let i=1; i<=len1; i++){for(let j=1; j<=len2; j++){if(str1[i-1]===str2[j-1]){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = Math.min(dp[i-1][j-1]+rc, Math.min(dp[i][j-1]+ic, dp[i-1][j]+dc));}}}return dp[len1][len2];
}

6. 打家劫舍

6.1 打家劫舍1

var rob = function(nums) {let len = nums.length;if(len<=1) return len === 0 ? 0 : nums[0];let dp = new Array(len+1);dp[0] = 0;dp[1] = nums[0]for(let i=2; i<=len; i++){//抢(i-1)以及抢(i-2)+(i)中选最大的dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i-1]);}return dp[len]
};

 6.2 打家劫舍2

地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。

环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个单排排列房间子问题：

1. 在不偷窃第一个房子的情况下（即 nums[1:]nums[1:]），最大金额是 p_1p 
2. 在不偷窃最后一个房子的情况下（即 nums[:n-1]nums[:n−1]），最大金额是 p_2p 

综合偷窃最大金额： 为以上两种情况的较大值，即 max(p1,p2)。

var rob = function(nums) {let len = nums.length;if(len<=1) return len === 0 ? 0 : nums[0];let dp1 = new Array(len+1);//不偷第一家let dp2 = new Array(len+1);//不偷最后一家//分为两个dp,一个是不偷第一家，一个是不偷最后一家的情况dp1[0] = dp2[0] = 0;dp1[1] = 0;dp2[1] = nums[0];for(let i=2; i<=len; i++){dp1[i] = Math.max(dp1[i-1], dp1[i-2]+nums[i-1]);if(i<len){dp2[i] = Math.max(dp2[i-1], dp2[i-2]+nums[i-1]);}else{dp2[i] = dp2[i-1];}}return Math.max(dp1[len], dp2[len])
};

接雨水问题

输入：[3,1,2,5,2,4]

返回值：5

说明：数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水

思路：

1. 找到数组中从下标 i 到最左端最高的条形块高度 left_max。

2. 找到数组中从下标 i 到最右端最高的条形块高度 right_max。

扫描数组arr 并更新答案：
累加 到 ans 上

function maxWater(arr){let len = arr.length;if(len<3)return 0;let leftMax = new Array(len);let rightMax = new Array(len);let res = 0;leftMax[0] = arr[0];for(let i=1; i<len; i++){leftMax[i] = Math.max(arr[i], leftMax[i-1]);}rightMax[len-1] = arr[len-1];for(let i=len-2; i>=0; i--){rightMax[i] = Math.max(arr[i], rightMax[i+1]);}for(let i=0; i<len; i++){res += (Math.min(leftMax, rightMax)-arr[i] )}return res;
}

 岛屿数量

 思路：

dfs()

• 用深度搜索.从（i, j）向上下左右(i+1,j),(i-1,j),(i,j+1),(i,j-1) 做深度搜索

• 终止条件：
  1. (i, j) 越过矩阵边界;
  2. grid[i][j] == 0，代表此分支已越过岛屿边界。

• 搜索岛屿的同时，执行 grid[i][j] = '0'，即将岛屿所有节点删除，以免之后重复搜索相同岛屿。

主循环

• 遍历整个矩阵，当遇到 grid[i][j] == '1' 时，从此点开始做深度优先搜索 dfs，岛屿数 count + 1 且在深度优先搜索中删除此岛屿。

function solve( grid ) {let cnt = 0;for(let i=0; i<grid.length; i++){for(let j=0; j<grid[0].length; j++){if(grid[i][j]==='1'){dfs(i,j,grid);cnt++;}}}return cnt
}    
function dfs(x, y, grid){if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y]==='0')return;grid[x][y] = '0'dfs(x-1, y, grid);dfs(x+1, y, grid);dfs(x, y-1, grid);dfs(x, y+1, grid);
}

买卖股票的最佳时机

输入：[7,1,5,3,6,4]
输出：5

function maxProfit( prices ) {let minPrice = Number.MAX_VALUE;let maxProfit = 0;for(let i=0; i<prices.length; i++){minPrice = Math.min(price[i], minPrice);maxProfit = Math.max(maxProfit, price[i]-minPrice);}return maxProfit;
}

击鼓传花

K(K>=3)个人在玩一个击鼓传花的小游戏。每击一次鼓，拿着花的要将花交给别人，不能留在自己手中。游戏开始前花在小猿手中，求击了N次鼓后，这朵花又回到小猿手中的方案数，请输出这个数模1000000007后的结果。

思路：

f(i,p)表示击鼓i次后是不是在自己手上。p===0表示在自己手上，p===1不在手上。

f(i,0) = f(i-1, 1)

f(i,1) = f(i-1, 0)*(k-1) + f(i-1, 1)*(k-2)

当f ( i , 0 )表示第i个状态的时候在手里，那么i − 1状态的时候一定不在手里。

如果f ( i , 1 ) 表示第i个状态不在手里，那么i − 1状态的时候可以在手里，也可以不在手里，在手里有k − 1种情况（即，将自己手里的花传给其他人），不在手里有k − 2 种情况（即，既不在自己手里也不在上一轮的人手里）

边界条件f(0,0)=1(即游戏开始前在自己手中)。f(0,1)=0

//只通过50%
let input = readline().split(' ');
let k = parseInt(input[0]),n = parseInt(input[1]);
let dp = new Array(n+1).fill(0).map(()=>new Array(2).fill(0))
dp[0][1] = 0;
dp[0][0] = 1;
for(let i=1; i<=n; i++){dp[i][0] = dp[i-1][1]%1000000007;dp[i][1] = dp[i-1][0]*(k-1)%1000000007+dp[i-1][1]*(k-2)%1000000007;
}
print (dp[n][0]);

 矩阵的最小路径和

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和

function minPathSum( matrix ) {// write code herelet n = matrix.length;let m = matrix[0].length;if(!matrix || n<=0 || m<=0){return 0;}let dp = new Array(n).fill(0).map(x=>new Array(m).fill(0));dp[0][0] = matrix[0][0];for(let i=1; i<n; i++){//边界：只能竖着走dp[i][0] = dp[i-1][0] + matrix[i][0];}for(let j=1; j<m; j++){//边界：只能横着走dp[0][j] = dp[0][j-1] + matrix[0][j];}for(let i=1; i<n; i++){for(let j=1; j<m; j++){dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);}}return dp[n-1][m-1];
}

正则表达式

1.判断是否符合格式：XXX-XXX-XXXX

function matchesPattern(str) {let reg = /^\d{3}-\d{3}-\d{4}$/return reg.test(str)   
}

2.返回字符串中连续的三个数字

function captureThreeNumbers(str) {let reg = /\d{3}/;let res = str.match(reg);if(res){return res[0];}return false;}

3.给千分位加上逗号

function addComma(num){//没有小数if(num.toString().indexOf('.')===-1){return num.toLocaleString();}else{// 如果是小数，则保留两位小数//\d{3}+\.表示3个数字或者3的倍数个数字,后面跟着.return num.toFixed(2).replace(/(\d{1,3})(?=(\d{3})+\.)/g, '$1,')}
}

字符串转驼峰

var str = 'test_align_center'
var res; 
var reg = /_(\w)/g
if (reg.test(str)) {res = str.toLowerCase().replace(reg, function (match, p1) {return p1.toString().toUpperCase()})
} else {reg2 = /^[A-Z]/g;res = str.replace(reg2, function (match) {return match.toLowerCase()})
}
console.log(res)

字符串去重 

var str = "aaaabbbbbccccc";
var reg = /(\w)\1*/g;
console.log(str.replace(reg,"$1"));//abc

JS基础

1. 将函数 fn 的执行上下文改为 obj，返回 fn 执行后的值

输入：alterContext(function() {return this.greeting + ', ' + this.name + '!'; }, {name: 'Rebecca', greeting: 'Yo' })

输出：Yo, Rebecca!

function alterContext(fn, obj) {return fn.call(obj)
}

2. 保留精度的乘法

 输入：3     0.00001

 输出：0.00003

//1.先转换成字符串
//2.计算小数后面有几位
//3.最大的小数位
//4.乘
function multiply(a, b){let str1 = a.toString();let str2 = b.toString();let len1 = (str1.indexOf('.')==-1)? 0 : (str1.length-str1.indexOf('.')-1);let len2 = (str2.indexOf('.')==-1)? 0 : (str2.length-str2.indexOf('.')-1);var maxLen = Math.max(len1, len2);return parseFloat(a*b).toFixed(maxLen);
} 

大数加法

function solve( s ,  t ) {let len1 = s.length - 1, len2 = t.length - 1;var carry = 0, sum = 0;let res = '';let c1, c2;while (len1 >= 0 || len2 >= 0 || carry !== 0) {c1 = len1>=0 ? Number(s.charAt(len1--)) : 0;c2 = len2>=0 ? Number(t.charAt(len2--)) : 0;sum = c1 + c2 + carry;carry = Math.floor(sum / 10);res = "" + Math.floor(sum % 10) + res;}return res;
}

3. 二进制转换

输入：65

输出：01000001

function convertToBinary(num) {let left;let res = [];while(num){left = num % 2;num = Math.floor(num/2);res.unshift(left);}while(res.length<8){res.unshift(0);}return res.join("");
}

4.多进制转换

function solve( M ,  N ) {// write code herereturn M.toString(N).toUpperCase()
}

柯里化 

实现：add(1,2,3), add(1)(2)(3)

function curryAdd(){// 将参入的类数组转为数组let arg = Array.prototype.slice.call(arguments);//在函数内部声明一个函数，利用闭包特性保存arg并收集所有的参数值let add = function(){arg.push(...arguments);return add;}add.toString = function(){return arg.reduce((a,b)=>{return a+b})}return add;
}

使用闭包

实现函数 makeClosures，调用之后满足如下条件：
1、返回一个函数数组 result，长度与 arr 相同
2、运行 result 中第 i 个函数，即 result[i]()，结果与 fn(arr[i]) 相同

function makeClosures(arr, fn){let res = [];for(let i=0; i<arr.length; i++){res[i] = function(){return fn(arr[i])}}
}//利用bind方法
function makeClosures(arr, fn){let res = [];for(let i=0; i<arr.length; i++){fn.bind(null, arr[i])}
}

验证IP地址

/*** 验证IP地址* @param IP string字符串 一个IP地址字符串* @return string字符串*/
function solve( IP ) {// write code hereif(IP.split('.').length>1){let arr = IP.split('.');if(arr.length===4){for(let i=0; i<arr.length; i++){if(parseInt(arr[i])<0 || parseInt(arr[i])>255 || arr[i].indexOf(0)===0){return "Neither";}}}return "IPv4";}else if(IP.split(':').length > 1){let arr = IP.split(':');for(let i=0; i<arr.length; i++){if(arr[i].length>4 || !arr[i].length){return "Neither";}}return "IPv6"}
}

 移除数组中的元素 

 直接在原数组

function removeWithoutCopy(arr, item) {let len = arr.length;for(let i=0; i<len; i++){if(arr[i]===item){arr.splice(i,1)i--len--;}}return arr;
}

 重新返回新数组

function remove(arr, item) {return arr.filter(p=>{return p!==item;})
}

 统计字符串

统计字符串中每个字符的出现频率，返回一个 Object，key 为统计字符，value 为出现频率
1. 不限制 key 的顺序
2. 输入的字符串参数不会为空
3. 忽略空白字符

输入：'hello world'

输出：{h: 1, e: 1, l: 3, o: 2, w: 1, r: 1, d: 1}

function count(str) {let res = {}str = str.replace('/\s/g', '');for(let i=0; i<str.length; i++){res[str[i]] = res[str[i]]  ? ++res[str[i]] : 1;}return res;
}

扁平化数组 （二维转一维，多维转一维）

 扁平化去重排序数组

var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];

编写一个程序将数组扁平化去并除其中重复部分数据，最终得到一个升序且不重复的数组

var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];
var res = [...new Set(arr.join().split(',').map(Number))];
res.sort((a,b)=>a-b)
console.log(res)

如何实现一个new

1. 首先创建一个空对象，空对象_proto_属性指向构造函数的原型对象

[Object.create()方法创建一个新对象，使用现有的对象来提供新创建的对象的__proto__。]

2. 把新创建的空对象的this指向构造函数，并给空对象添加属性。

3. 如果构造函数返回一个引用类型的值，则返回这个值；否则返回新创建的对象。

function _new(fn, ...arg){var obj = Object.create(fn.prototype);const result = fn.apply(obj, ...args);return result instanceof Object ? result : obj;
}

a==1 && a==2 && a==3为true成立的情况

var a = ?;
if(a == 1 && a == 2 && a == 3){conso.log(1);
}

 1、当执行a == 1 && a == 2 && a == 3 时，会从左到右一步一步解析，首先 a == 1，会进行上面转换，每一步都调用toString方法

所以只要改原形的toString()方法

const a = {i:1,toString(){return a.i++;}
}
if(a == 1 && a == 2 && a == 3){conso.log(1);
}

判断两个对象的内容是否相同

let obj1 = {a: 1,b: {c: 2}}let obj2 = {b: {c: 3},a: 1}console.log(isObjectValueEqual(obj1, obj2))//falsefunction isEqual(a, b){if(a===b)return true;//如果引用对象地址相同，返回true//获取a、b的键值数组let propA = Object.getOwnPropertyNames(a);let propB = Object.getOwnPropertyNames(b);if(propA.length!==propB.length)return false;for(let key in a){if(b.hasOwnProperty(a[key])){//判断b中是否有a的键，没有则返回falseif(typeof a[key] === 'Object'){if(!isEqual(a[key], b[key]))return false;}else if(a[key] !== b[key]){return false;}}else{return false;}}    return true;
}

实现sleep函数

//用回调
function sleep(callback,time){setTimeout(callback, time)
}//用promise
const sleep = function(time){return new Promise(resolve=>setTimeout(resolve, time))
}sleep().then(()=>{console.log(1)
})

 给定两个数组，计算他们的交集

let map = {}
let res= [];for(let item of nums1){if(map[item]){map[item]++;}else{map[item] = 1;}
}for(let item of nums2){if(map[item]>0){res.push(item);map[item]--;}
}

扁平化数组 （二维转一维，多维转一维）

[1, [2, 3, [4, 5]]]  ------>    [1, 2, 3, 4, 5]

 思路：遍历数组每一项，若值为数组则递归遍历，否则concat

//利用reduce+递归
function flatten(arr){return arr.reduce((result, item)=>{return result.concat(Array.isArray(item)? flatten(item) : item);}, []);
}

//join+split+map
function flatten(arr){return arr.join().split(",").map(item=>{return parseInt(item)})
}

//扩展运算符:若arr中含有数组则使用一次扩展运算符，直至没有为止(不是很懂这个方法)
function flatten(arr){while(arr.some(item=>Array.isArray(item))){arr = [].concat(...arr)}return arr;
}

21. 数组去重

//1.扩展运算符+set
function unique(arr){return [...new Set(arr)]//通过展开操作符将set转为数组
}//2.创建一个新数组，利用indexOf(arr[i])是否存在于新数组中，不存在则添加
function unique(arr){let res = [];for(let i=0; i<arr.length; i++){if(res.indexOf(arr[i])===-1){res.push(arr[i]);}}
}//3.先对数组排序，如果判断前后的元素是否相同，不同则加到res里面
function unique(arr){if(!arr.length)return arr.sort();let res = [arr[0]];for(let i=0; i<arr.length; i++){if(arr[i] !== arr[i-1]){res.push(arr[i]);}}return res;
}//4.通过filter
function unique(arr){retrun arr.filter((item, index)=>{//indexOf(item)会返回多个含有item的下标，如果等于第一个返回的下标==当前索引就返回这个元素return arr.indexOf(item, 0)===index;})
}

实现简单的迭代器 

const iter = function(arr){let nextIndex  = 0;return {next:()=>{return nextIndex<arr.length? {value:arr[nextIndex], done: false}:{value:undefined, done: true}}}
}const it = iter(['aaa', 'ccc']);
console.log(it.next()); //{value:"aaa",done:false}
console.log(it.next()); //{value:"ccc",done:false}
console.log(it.next()); //{value:undefined,done:true}

 实现一个once函数，传入函数参数只执行一次

function once(func){var tag = true;return function(){if(tag===true){func.apply(null, arguments);tag = false;}return undefined;}
}

将原生的Ajax封装成promise 

var myAjax = function(url){return new Promise((resolve, reject)=>{var xhr = new XMLHttpRequest();xhr.open('get', url);xhr.send(data);xhr.onreadystatechange = function(){if(xhr.status===200 && readyState==4){var json = JSON.parse(xhr.responseText);resolve(json);}else if(readyState==4 && xhr.status!==200){reject('error');}};            })
}

lazyMan

  function lazyMan(name) {this.taskList = [];this.introduce(name);}lazyMan.prototype = {_bind: function (method, fn) {if (method === 'sleepFirst') {this.taskList.unshift(fn);} else {this.taskList.push(fn);}},next: function () {if (this.taskList.length > 0) {var fn = this.taskList.shift();fn && fn();}},introduce: function (name) {var me = this;this._bind('introduce', function () {me.log('Hi! This is ' + name + '!');me.next();});setTimeout(function () {me.next();}, 0);return this;},sleep: function (sec) {var me = this;this._bind('sleep', function () {me.log('Wake up after' + sec);setTimeout(() => {me.next();}, sec * 1000);});return this;},eat: function (str) {var me = this;this._bind('eat', function () {me.log('Eat' + str + '~');me.next();});return this;},sleepFirst: function (sec) {var me = this;this._bind('sleepFirst', function () {me.log('Wake up after' + sec);setTimeout(() => {me.next();}, sec * 1000);});return this;},log: function (str) {console.log(str);}};var lm = function (name) {return new lazyMan(name);};lm('Hank').sleepFirst(2).eat('lunch').sleep(3).eat('dinner')

 promise方法

    class Lazy {constructor(name) {this.sleepFirstTime = 0;this.promise = Promise.resolve().then(() => this.sleepFirstTime && this._sleep(this.sleepFirstTime)).then(() => {console.log(`Hi! This is ${name}!`);});}sleepFirst(time) {this.sleepFirstTime = time;return this;}eat(food) {this.promise = this.promise.then(() => {console.log(`Eat ${food}~`);});return this;}sleep(time) {this.promise = this.promise.then(() => this._sleep(time));return this;}_sleep(time) {return new Promise((next) => {setTimeout(() => {console.log(`Wake up after ${time}`);next();}, time);});}}function LazyMan(name) {return new Lazy(name);}LazyMan(“Hank”).sleepFirst(2000).sleep(2000).eat(“supper”)