1.链表
1.实现一个单向链表
/*
实现一个单向链表，满足以下条件：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
*/
var MyLinkedList = function() {
this.length = 0;
this.head = { val: null, next: null }
};
MyLinkedList.prototype.get = function(index) {
if(index<0 || index>(this.length-1)) {
return -1;
} else {
let i = 0;
let node = this.head;
while(i !== index) {
i++;
node = node.next //这里直接令node=node.next将不再影响this.head值
}
return node.val;
}
};
MyLinkedList.prototype.getNode = function(index) {
if(index<0 || index>(this.length-1)) {
return -1;
} else {
let i = 0;
let node = this.head;
while(i !== index) {
i++;
node = node.next
}
return node;
}
};
MyLinkedList.prototype.addAtHead = function(val) {
if(this.head.val === null) {
this.head.val = val;
this.head.next = null;
} else {
let node = this.head;
this.head = {}; //注意这里要先将this.head置空，改变其引用地址，否则直接修改会影响到原node值
this.head.next = node;
this.head.val = val;
}
this.length++;
};
MyLinkedList.prototype.addAtTail = function(val) {
if(this.head.val === null) {
this.addAtHead(val)
} else {
let node = this.getNode(this.length-1);
let tailNode = { val: val, next: null };
node.next = tailNode;
this.length++;
}
};
MyLinkedList.prototype.addAtIndex = function(index, val) {
if(index === this.length) {
this.addAtTail(val);
}
else if(index > this.length) {
return
}
else if(index <= 0) {
this.addAtHead(val);
}
else {
let prevNode = this.getNode(index-1);
let nextNode = this.getNode(index);
let node = { val: val, next: nextNode };
prevNode.next = node;
this.length++;
}
};
MyLinkedList.prototype.deleteAtIndex = function(index) {
if(index<0 || index>=this.length){
return
}
if(this.length === 1) {
this.head = { val: null, next: null };
this.length--;
} else {
if(index === 0) {
this.head = this.getNode(1);
this.length--;
} else {
let prevNode = this.getNode(index-1);
let node = this.getNode(index);
prevNode.next = node.next;
node = {}; //将删除节点置空
this.length--;
}
}
};
2.找出链表相交节点，假设均没有环
// 找出链表相交节点，假设均没有环
// 1. 双指针法
var getIntersectionNode = function(headA, headB) {
if(headA==null || headB==null) {
return null;
}
let p = headA;
let q = headB;
while(p.next !== q.next) {
if(p.next == null) {
p = headB;
} else {
p = p.next;
}
if(q.next == null) {
q = headA;
} else {
q = q.next;
}
}
if(p == q) {
return p
}
return p.next;
};
// 2. 取出长度，长度大的先走几步达到与长度短的相同，然后开始同步遍历，相同就停止；
// 若有相交节点则会返回相交节点，若无相交节点，最终均走到null，返回null
var getIntersectionNode = function(headA, headB) {
if(headA==null || headB==null) {
return null;
}
let a = 0, b=0;
let p = headA, q = headB;
while(p.next !== null) {
p = p.next;
a++;
}
while(q.next !== null) {
q = q.next;
b++;
}
let c = a - b;
if(c > 0) {
p = headA;
while(c !=0) {
p = p.next;
c--;
}
q = headB;
} else {
p = headA;
c = Math.abs(c);
q = headB;
while(c !=0) {
q = q.next;
c--;
}
}
while(p !== q) {
p = p.next;
q = q.next;
}
return p;
};
3.判断链表是否有环
思路：使用快慢两个指针，当链表含有环时，将不会走到null，则快指针终将在超出慢指针k个环路长度后追到慢指针：
var hasCycle = function(head) {
if(!head|| !head.next) {
return false;
}
let p = head;
let q = head;
while(q!==null && q.next!==null) {
p = p.next;
q = q.next.next;
if(p === q) {
return true;
}
}
return false;
};
进一步找到环的开始节点：
当快慢指针相遇后，快指针此时走了慢指针两倍距离，假设环长度为l，非环长度为n，相遇时距离环起点为m，则此时慢指针共走了(m+n)距离，快指针走了(m+n+kl)距离，其中k为快指针比慢指针多走的环路圈数。
m+n+kl = 2(m+n)
即，k*l = m+n
此时距离环起点慢指针已走了m步，若再走n步则相当于从环起点开始绕环行走了k圈又回到环起点！
而n正好为链表非环长度，此时令快指针从头开始一步一步走，则快指针走n步时也正好达环起点！
即当两指针初次相遇后，令快指针从链表头开始一步一步走，慢指针继续一步一步走，当它们再次相遇时，即为环起点！
var detectCycle = function(head) {
if(!head || !(head.next)) {
return null;
}
let slow = head, fast = head;
let flag = false;
while(fast!==null && fast.next!==null) {
slow = slow.next;
fast = fast.next.next;
if(slow === fast) {
flag = true;
break;
}
}
if(flag) {
fast = head;
while(fast !== slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
} else {
return null;
}
};
4.给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点
给定条件：n保证是有效的
思路：要删除倒数第n个节点，可给定两个指针，快指针和慢指针，让快指针先向前走n步，然后两个指针再一起走，当快指针走到null时，慢指针刚好走到倒数第n个节点。
又由于删除倒数第n个节点，就是让倒数第n+1个节点的next指向删除节点的next，因此两个指针一起走时可令快指针不走到null，而是走到最后一个节点，即此节点的next指向null，此时慢节点正好走到倒数第n+1个节点，假设为node，令node.next = node.next.next即可删除倒数第n个节点
此外需注意，当n等于链表长度时，快指针先走n步已走到null，此时慢指针为头结点，即为倒数第n个节点，而非倒数第n+1个节点，因此删除头结点即可，直接返回head.next
var removeNthFromEnd = function(head, n) {
let p = head, q = head;
while(n>0) {
p = p.next;
n--;
}
if(p === null) {
return head.next;
}
while(p.next !== null) {
p = p.next;
q = q.next;
}
q.next = q.next.next;
return head;
};
5.反转链表
反转一个单链表，例如：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
非递归思路：遍历链表，将每个链表元素，依次放到首位。
利用head去遍历链表，首先，令headNode=head，令nextNode=head.next取到第二个节点，然后令head.next=nextNode.head，即将head放到第二个节点位置，然后令nextNode.next=headNode，将原本第二个节点放到第一个位置，再令headNode=nextNode取得现在的第一个节点，此时head为第二个节点，按上述方法再将head放到第三个节点位置，将第三个节点指向headNode，即放到第一个位置，再令headNode等于第三个节点，仍取现在的第一个节点，循环往复，直至head移动到最后一个位置指向null，此时原最后一个节点放到了首位，完成链表的反转
var reverseList = function(head) {
if(head === null || head.next===null) {
return head;
}
let headNode = head;
while(head.next !== null) {
let nextNode = head.next;
head.next = nextNode.next;
nextNode.next = headNode;
headNode = nextNode;
}
return headNode;
};
递归思路：将最后一个节点的next指向前一个节点，再将前一个节点的next指向null，然后就反转了最后两个元素；再继续将前一个节点的next指向前前一个节点，将前前一个节点的next指向null，这样又完成了倒数第二个节点和倒数第三个节点的反转；最终完成所有元素的反转
var reverseList = function(head) {
if(head === null || head.next===null) {
return head;
}
const node = reverseList(head.next);
head.next.next = head;
head.next = null;
return node;
};
6.移除链表元素
题目描述：删除链表中等于给定值 val 的所有节点
思路：
首先判断头结点的值是否等于指定值，等于则令head=head.next，将头结点后移一位，直到删除所有等于指定值的头结点；
然后从头结点开始，判断下一个节点的值是否等于指定值(因为要删除一个节点需要令它的前一个节点指向它的后一个节点)，等于则删除，直到其后面的节点值不等于指定值；
若其后面的节点值不等于指定值，则将其后移一位，循环第二、三过程，直到链表结束
var removeElements = function(head, val) {
while(head && head.val === val) {
head = head.next;
}
let p = head;
while(p && p.next) {
while(p.next && p.next.val === val) {
p.next = p.next.next;
}
p = p.next;
}
return head
};
7.奇偶链表
题目描述：给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性
例如：
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
思路：首先判断链表长度是否小于等于二，是则直接返回head；
定义四个指针，p=head，q=head.next，r=head.next，s=null，其中p和q分别去遍历链表的奇数项和偶数项，并将其拆开，奇数项指向奇数项，偶数项指向偶数项；r用来保存偶数项第一项节点，等待遍历完成令奇数项最后一项的指针指向它；s用来保存奇数项和偶数项指向变化前的指向，避免形成闭环
var oddEvenList = function(head) {
if(!head || !head.next || !head.next.next) {
return head;
}
let p = head;
let q = head.next;
let r = head.next;
let s = null;
while(p && p.next && p.next.next) {
s = p.next.next;
p.next = p.next.next;
p = s;
if(q && q.next.next) {
s = q.next.next;
q.next = q.next.next;
q = s;
}
}
p.next = r;
q.next = null;
return head;
};
8.回文链表
题目描述：判断一个链表是否为回文链表
示例：
输入: 1->2
输出: false
输入: 1->2->2->1
输出: true
思路：判断一个链表是否为回文链表，即判断其正向返回值与反向返回值是否相同；定义两个字符串，一个正向str，一个方向str_reverse；遍历链表，正向字符串每次加上每个节点的值，反向字符串每次将节点的值放到最前面然后加上反向字符串的值，这样遍历完成后，正向字符串存储的为正向遍历的值，反向字符串存储的为链表反向的值，判断它们是否相等即可
var isPalindrome = function(head) {
let str = "";
let str_reverse = "";
while(head) {
str += head.val;
str_reverse = head.val + str_reverse;
head = head.next;
}
return str === str_reverse;
};
9.实现双向列表
var MyLinkedList = function() {
this.length = 0;
this.head = { val: null, prev: null, next: null }
};
MyLinkedList.prototype.get = function(index) {
if(index<0 || index>(this.length-1)) {
return -1;
} else {
let i = 0;
let node = this.head;
while(i !== index) {
i++;
node = node.next
}
return node.val;
}
};
MyLinkedList.prototype.getNode = function(index) {
if(index<0 || index>(this.length-1)) {
return -1;
} else {
let i = 0;
let node = this.head;
while(i !== index) {
i++;
node = node.next
}
return node;
}
};
MyLinkedList.prototype.addAtHead = function(val) {
if(this.head.val === null) {
this.head.val = val;
this.head.prev = null;
this.head.next = null;
} else {
let node = this.head;
this.head = { val: val, prev: null, next: node };
node.prev = this.head;
}
this.length++;
};
MyLinkedList.prototype.addAtTail = function(val) {
if(this.head.val === null) {
this.addAtHead(val)
} else {
let node = this.getNode(this.length-1);
node.next = { val: val, prev: node, next: null };
this.length++;
}
};
MyLinkedList.prototype.addAtIndex = function(index, val) {
if(index === this.length) {
this.addAtTail(val);
}
else if(index > this.length) {
return
}
else if(index <= 0) {
this.addAtHead(val);
}
else {
let prevNode = this.getNode(index-1);
let node = { val: val, prev: prevNode, next: prevNode.next };
prevNode.next = node;
node.next.prev = node;
this.length++;
}
};
MyLinkedList.prototype.deleteAtIndex = function(index) {
if(index<0 || index>=this.length){
return
}
if(this.length === 1) {
this.head = { val: null, prev: null, next: null };
this.length--;
} else {
if(index === 0) {
this.head = this.getNode(1);
this.head.prev = null;
} else if(index === this.length-1) {
let node = this.getNode(index-1);
node.next = null;
} else {
let node = this.getNode(index);
node.prev.next = node.next;
node.next.prev = node.prev;
}
this.length--;
}
};
10.合并两个有序链表
题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
思路：新建一个链表，头结点指向空，遍历比较两个排序链表，将较小的值放到新链表后，比较完成后查看两个链表是否仍有剩余，将剩余链表直接链接到新链表后方，返回时需注意返回新链表的第二个节点
var mergeTwoLists = function(l1, l2) {
let l3 = new ListNode();
let cur = l3;
while(l1 && l2) {
if(l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if(l1) {
cur.next = l1;
}
if(l2) {
cur.next = l2;
}
return l3.next;
};
10.两数相加
题目描述：给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和
给定条件：假设除了数字 0 之外，这两个数都不会以 0 开头
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
思路：新建链表指向两链表之和的链表，首先将两个链表对应位置遍历相加，相加时判断进位flag是否为true，为true则再加1；相加有进位时令flag=true，令和sum=sum%10，新建节点{val: sun, next: null}添加到新链表后方
当一个链表遍历完成后，判断另一个链表是否还有剩余，有剩余则判断此时flag是否为true，为true则遍历剩余节点，节点值加1形成新节点添加到新链表后方，直至flag不再为true；当flag不为true时，说明不再需要加进位，则直接将剩余链表放到新链表后方
当两个链表和剩余链表均遍历完成后，判断此时flag是否为true，为true则说明最后仍有进位，则需在新链表后方添加节点{ val: 1, next: null }
返回新链表的第二个节点(第二个节点才是和链表的第一个节点)
var addTwoNumbers = function(l1, l2) {
let l3 = new ListNode();
let cur = l3;
let sum = 0, flag = false;
while(l1 && l2) {
if(flag) {
sum = l1.val + l2.val + 1;
flag = false;
} else {
sum = l1.val + l2.val;
}
if(sum >= 10) {
flag = true;
sum = sum % 10;
}
cur.next = new ListNode(sum, null);
cur = cur.next;
l1 = l1.next;
l2 = l2.next;
}
while(l1) {
if(flag) {
sum = l1.val + 1;
if(sum >= 10) {
sum = sum % 10;
cur.next = new ListNode(sum, null);
cur = cur.next;
l1 = l1.next;
} else {
flag = false;
cur.next = new ListNode(sum, null);
cur = cur.next;
l1 = l1.next;
cur.next = l1;
break;
}
}else {
cur.next = l1;
break;
}
}
while(l2) {
if(flag) {
sum = l2.val + 1;
if(sum >= 10) {
sum = sum % 10;
cur.next = new ListNode(sum, null);
cur = cur.next;
l2 = l2.next;
} else {
flag = false;
cur.next = new ListNode(sum, null);
cur = cur.next;
l2 = l2.next;
cur.next = l2;
break;
}
}else {
cur.next = l2;
break;
}
}
if(flag) {
cur.next = new ListNode(1, null);
}
return l3.next;
};
11.扁平化多级双向链表
题目描述：多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中
多级链表如下图所示：
转化为：
思路：将多层链表逐层递减最终转换为单层；如例所示，即将三层转换为两层，再将两层转化为一层
遍历当前链表，查看当前节点是否含有子节点，含有则查看当前节点是否为当前层最后一个节点，即查看当前节点的next是否为null；若当前节点为当前层最后一个节点，则将子节点连接到当前节点即可；若当前节点不为当前层最后一个节点，则遍历子节点当前层，将最后的节点接入当前节点后面节点的前面；此时则将第二层转到了第一层，若原来子层仍含有子层，则此时转变为第二层；
然后令当前节点为后一个节点，继续遍历，直至将所有节点都连接到一层，扁平化完成
var flatten = function(head) {
let p = head;
while(p) {
if(p.child !== null) {
if(p.next !== null) {
let q = p.next;
p.next = p.child;
p.next.prev = p;
let r = p.next;
while(r.next !== null) {
r = r.next;
}
r.next = q;
q.prev = r;
p.child = null;
} else {
p.next = p.child;
p.next.prev = p;
p.child = null;
}
}
p = p.next;
}
return head;
};
12.旋转链表
题目描述：给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数
示例：
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
思路：首先求出链表长度len，求取过程中存储尾节点p；移动k位就相当于移动(k%len)位(无论k是否大于len)，而当k为len的整数倍时，相当于不做任何操作；
当k不为len的整数倍时，向右移动k位，相当于将由尾节点开始，长度为k的子链表放置到链表头部；即，将当前尾节点指向当前头结点，将倒数第k个节点设为头结点，并将倒数第k+1个节点的next指向null；
求长度时获得了尾节点p，令尾节点指向当前head，p.next=head；从头结点开始，向后走(len-k)步即走到倒数第k个节点，而我们要将第k个节点设为头结点，并将倒数第k+1个节点指向null，这只需我们获得倒数第k+1个节点即可(倒数第k个节点等于倒数第k+1个节点的next)，因此我们只需向后走(len-k+1)步，然后进行操作即可
var rotateRight = function(head, k) {
if(!head || !head.next) {
return head;
}
let len = 0;
let p = head;
while(p.next) {
len++;
p = p.next;
}
len = len+1;
k = k % len;
if(k === 0) return head;
k = len - k;
let q = head;
while(k>1) {
k--;
q = q.next;
}
p.next = head;
head = q.next;
q.next = null;
return head;
};
13.复制带随机指针的链表
题目描述：给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点，要求返回这个链表的 深拷贝
思路：遍历两次原链表，第一次复制每个节点的val和next，并将复制的新节点插入到原节点后面，这样即形成A->A'->B->B'->C->C'->...
第二次遍历原链表复制随机指针，假设原A的随机指针指向C，则A'随机指针应指向C'，即A.next.random=A.random.next，复制时需注意原链表节点的随机指针是否指向null，是的话A.next.random=null
复制完成后将链表拆开，一部分为原链表，一部分为新链表，注意将原链表指向改回来，即A.next=A.next.next，最后注意将原链表最后节点指向null
var copyRandomList = function(head) {
if(!head) {
return head;
}
let p = head;
let tmp = new Node(0, null, null);
while(p) {
tmp = new Node(p.val, p.next, null);
p.next = tmp;
p = p.next.next;
}
p = head;
while(p) {
if(p.random === null) {
p.next.random = null;
} else {
p.next.random = p.random.next;
}
p = p.next.next;
}
let newHead = head.next;
p = head;
let q = newHead;
while(q && q.next) {
p.next = p.next.next;
q.next = q.next.next;
p = p.next;
q = q.next;
}
p.next = null;
return newHead;
};
2.队列和栈
1.实现一个循环队列
要求：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
/**
* Initialize your data structure here. Set the size of the queue to be k.
* @param {number} k
*/
var MyCircularQueue = function(k) {
this.len = k;
this.queue = [];
};
/**
* Insert an element into the circular queue. Return true if the operation is successful.
* @param {number} value
* @return {boolean}
*/
MyCircularQueue.prototype.enQueue = function(value) {
console.log(this.queue)
let len = this.queue.length;
if(len === this.len) {
return false;
}
this.queue.push(value);
return true;
};
/**
* Delete an element from the circular queue. Return true if the operation is successful.
* @return {boolean}
*/
MyCircularQueue.prototype.deQueue = function() {
if(this.queue.length === 0) {
return false;
}
this.queue.shift();
return true;
};
/**
* Get the front item from the queue.
* @return {number}
*/
MyCircularQueue.prototype.Front = function() {
if(this.queue.length === 0) {
return -1
}
return this.queue[0];
};
/**
* Get the last item from the queue.
* @return {number}
*/
MyCircularQueue.prototype.Rear = function() {
if(this.queue.length === 0) {
return -1;
}
let len = this.queue.length;
return this.queue[len-1];
};
/**
* Checks whether the circular queue is empty or not.
* @return {boolean}
*/
MyCircularQueue.prototype.isEmpty = function() {
return this.queue.length === 0;
};
/**
* Checks whether the circular queue is full or not.
* @return {boolean}
*/
MyCircularQueue.prototype.isFull = function() {
return this.queue.length === this.len;
};
2.岛屿数量
题目描述：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量；岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成；此外，你可以假设该网格的四条边均被水包围。
示例：
输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释：所有通过上下左右连接起来的"1"算是一个岛屿
思路：深度优先遍历；
遍历整个二维数组，判断当前元素是否等于"1"，等于则令岛屿数目加1；
遍历此岛屿，将该元素置"0"，判断该元素其四周连接(上下左右)元素是否为"1"，为"1"则置"0"，继续判断为"1"的周围元素的周围元素是否为"1"，直到遇到"0"或边界为止(边界也为"0")；
这样对某一元素周围元素深度优先遍历后，其周围为"1"的元素将全被置"0"，当前岛屿遍历完毕；继续寻找其他岛屿，重复上述过程直至结束；
例：
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
处理一次后，岛屿个数加1，第一个岛屿遍历完成，原数组变为：
[
['0','0','0','0','0'],
['0','0','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
然后寻找到第二个岛屿，并遍历完成后：
[
['0','0','0','0','0'],
['0','0','0','0','0'],
['0','0','0','0','0'],
['0','0','0','1','1']
]
寻找第三个岛屿。并遍历完成后：
[
['0','0','0','0','0'],
['0','0','0','0','0'],
['0','0','0','0','0'],
['0','0','0','0','0']
]
此时不再有岛屿，且整个数组遍历完成，结束
var numIslands = function(grid) {
let height = grid.length;
if(height === 0) return 0;
let width = grid[0].length;
let count = 0;
for(let i=0; i<height; i++)
for(let j=0; j<width; j++) {
if(grid[i][j] === "1") {
count++;
isIsland(j, i, grid, width, height);
}
}
return count;
};
function isIsland(x, y, grid, w, h) {
if(x<0 || y<0 || x===w || y===h || grid[y][x]==='0') return;
grid[y][x] = '0';
isIsland(x-1, y, grid, w, h);
isIsland(x, y-1, grid, w, h);
isIsland(x+1, y, grid, w, h);
isIsland(x, y+1, grid, w, h);
}
3.设计最小栈
题目要求：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
/**
* initialize your data structure here.
*/
var MinStack = function() {
this.stack = [];
this.minStack = [];
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x);
if(this.minStack.length===0 || x<=this.getMin()) {
this.minStack.push(x);
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
let x = this.stack.pop();
if(x === this.getMin()) {
this.minStack.pop();
}
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
let len = this.stack.length;
return this.stack[len-1];
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
let len = this.minStack.length;
return this.minStack[len-1];
};
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/
4.有效的括号
题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意：空字符串可被认为是有效字符串。
示例：
输入: "{[]}"
输出: true
输入: "([)]"
输出: false
思路1：将给定字符串转换为数组，然后遍历数组；
依次判断遇到的字符，若为"("，"["或"{"，则push入一个临时数组；
当遇到")"，"]"或"}"时，则判断临时数组中最后一位是否为对应的"("，"["或"{"，若是，则将该元素从临时数组中pop掉，否则说明不符合条件，退出遍历，返回false；
当遍历完成后判断临时数组中是否仍含有元素，若是，则说明含有未能配对的括号，不满足条件，返回false。
var isValid = function(s) {
let arr = [...s];
let tmp = [];
for(let i=0; i<arr.length; i++) {
if(arr[i]==="(" || arr[i]==="[" || arr[i]==="{") {
tmp.push(arr[i]);
}
if(arr[i] === ")") {
if(tmp[tmp.length-1] === "(") {
tmp.pop();
} else {
return false;
}
}
if(arr[i] === "]") {
if(tmp[tmp.length-1] === "[") {
tmp.pop();
} else {
return false;
}
}
if(arr[i] === "}") {
if(tmp[tmp.length-1] === "{") {
tmp.pop();
} else {
return false;
}
}
}
return tmp.length===0 ? true : false
};
思路2：利用字符串替代，依次将()，[]，{}用空字符串替代，替代完毕后，若字符串长度为0则说明满足条件，否则不满足条件
var isValid = function(s) {
let len = s.length / 2;
for(let i=0; i<len; i++) {
s = s.replace("()", "");
s = s.replace("[]", "");
s = s.replace("{}", "");
}
return s.length===0 ? true : false
};
5.每日温度
题目描述：请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替
示例：
输入：temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
输出：res = [1, 1, 4, 2, 1, 1, 0, 0]
思路1：暴力解决法，查找剩余元素是否存在比当前值大的值，有则获得天数差，没有则当前位置为0
var dailyTemperatures = function(T) {
let days = [];
let len = T.length;
for(let i=0; i<len; i++) {
let idx = T.findIndex(item => item>T[0]);
if(idx === -1) { days.push(0) }
else { days.push(idx) };
T.shift();
}
return days;
};
思路2：将index入栈，然后比较下一个温度与栈顶index对应的温度，若大于，则在结果相应index处填入下一个温度的index与栈顶index的差，并将栈顶元素出栈(已找到至少等待天数)；并继续将下一个温度与栈顶index对应的温度比较，直至清空栈或小于栈顶index对应的温度
由于找到大于栈顶index对应温度的温度时就会将栈顶元素出栈，因此栈内index对应的温度是由大到小的，且说明到当前遍历的温度为止，仍没有温度大于栈内index对应的温度。当原温度列表遍历完毕后，栈内仍有元素，则说明未找到大于该index对应温度的温度，则结果中该index置0
var dailyTemperatures = function(T) {
let len = T.length;
let res = new Array(len).fill(0);
let stack = [];
for(let i=0; i<len; i++) {
while(stack.length!==0 && T[i]>T[stack[stack.length-1]]) {
let top = stack.pop();
res[top] = i - top;
}
stack.push(i);
}
return res;
};
6.逆波兰表达式求值
题目描述：根据[逆波兰表示法求表达式的值
示例：
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释:
该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
思路：定义一个stack栈用来存储运算需要的数据，遍历给定数组，当元素为"+"，"-"，"*"，"/"时，从stack栈顶取出两个元素进行相应运算并存回stack，当元素不为运算符号时，将元素转为数字存入stack栈内
运算时减法和除法需注意参与运算的数字的顺序
var evalRPN = function(tokens) {
let operator = ["+", "-", "*", "/"];
let stack = [];
let len = tokens.length;
for(let i=0; i<len; i++) {
if(operator.includes(tokens[i])) {
let a = stack.pop();
let b = stack.pop();
if(tokens[i] === "+") {
stack.push(a+b);
}
if(tokens[i] === "-") {
stack.push(b-a);
}
if(tokens[i] === "*") {
stack.push(a*b);
}
if(tokens[i] === "/") {
stack.push(parseInt(b/a));
}
} else {
stack.push(parseInt(tokens[i]));
}
}
return stack[0];
};
7.克隆图
题目描述：给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）
示例：
输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
思路：先拷贝节点的值，再拷贝相邻接点
定义一个哈希表(一个空对象)用来存储所有节点，先定义一个新节点，拷贝给定节点的值，然后将给定节点的值作为属性，新节点作为属性值，存入哈希表中，并将给定节点放入队列中；
接下来拷贝给定节点的相邻节点，取出队列中一个节点，查看其相邻节点的值是否已存储在哈希表属性中，若是，则将哈希表中对应的值(即对应相邻节点的新节点)追加到新节点的相邻接点数组中；若不存在，则生成一个只拷贝该相邻接点值的新节点，添加到哈希表中，并将相邻接点的新节点追加到新节点的相邻接点数组中，最后将相邻节点放入队列中；
不断取出队列中的值，重复以上操作，直至队列清空，最终返回给定节点的拷贝节点。
var cloneGraph = function(node) {
if(!node) return
let visited = {};
let newNode = new Node(node.val, []);
visited[node.val] = newNode;
let queue = [];
queue.push(node);
while(queue.length !== 0) {
let curNode = queue.pop();
for(let item of curNode.neighbors) {
if(visited.hasOwnProperty(item.val)) {
visited[curNode.val].neighbors.push(visited[item.val]);
} else {
let copyNode = new Node(item.val, []);
visited[curNode.val].neighbors.push(copyNode);
visited[item.val] = copyNode;
queue.push(item);
}
}
}
return newNode;
};
8.二叉树的中序遍历
题目描述：给定一个二叉树，返回它的中序遍历。
中序遍历：先左节点，再根节点，后右节点
示例：
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
思路一：递归方法
使用中序遍历的递归方法，不断递归遍历左节点，根节点和右节点，直到节点为null
var inorderTraversal = function(root) {
if(root === null) {
return []
}
let res = [];
res = [...res, ...inorderTraversal(root.left)];
res.push(root.val);
res = [...res, ...inorderTraversal(root.right)];
return res;
};
思路2：不使用递归
建立一个栈用来存储左子树节点，对每个传入的节点的左节点进行压栈处理；由于栈为先进后出，因此能够满足最底层的左节点先输出；
新建一个空数组，用来存储中序遍历的结果；
当遍历到最下层左节点时，此时栈顶即为该节点，将该元素出栈，值存入结果数组中；
若此节点含有右节点，则对此节点的右节点进行压栈处理，然后遍历到右节点最下层的左子节点，出栈存值，继续查看是否含有右节点，直至此节点遍历完成；
若不含有右节点，或右节点遍历完成，则此时栈顶元素为倒数第二层左节点，重复上述处理，直到栈被清空且当前节点指向null
var inorderTraversal = function(root) {
let stack = [];
let res = [];
while(root || stack.length!==0) {
while(root) {
stack.push(root);
root = root.left;
}
let top = stack.pop();
res.push(top.val);
root = top.right;
}
return res;
};
9.字符串解码
题目描述：给定一个经过编码的字符串，返回它解码后的字符串
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。
条件：
- k 保证为正整数
- 输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的
- 原始数据不包含数字，所有的数字只表示重复的次数 k
示例：
输入：s = "3[a2[c]]"
输出："accaccacc"
思路：定义一个栈stack，将所有遇到的"["的index存储起来，这样当遇到"]"时，stack的栈顶值即为"]"对应的"["index值(最后一个开始的括号总是最先闭合)；
获取该index与当前位置之间的字符串，即为需要重复的字符串，求出index前面的数字(注意数字可能不止一位)，即为要重复的次数；
将需要重复的字符串重复指定次数，并插入到原字符串代替 原字符串中编码内容(即k[encoded_string]部分)；
注意代替完成后，字符串长度会发生变化，需将当前位置改变为字符串代替完成后的位置
var decodeString = function(s) {
let stack = [];
for(let i=0; i<s.length; i++) {
if(s[i] === "[") {
stack.push(i);
}
if(s[i] === "]") {
let pos = stack.pop();
let data = s.slice(pos+1, i);
pos = pos-1;
let k = "";
while(pos>=0 && !isNaN(parseInt(s[pos]))) {
k = s[pos] + k;
pos--;
}
k = parseInt(k);
let str = "";
while(k>0) {
str += data;
k--;
}
s = s.slice(0, pos+1) + str + s.slice(i+1);
i = pos + str.length; //注意修改i的值
}
}
return s;
};
10.图像渲染
题目描述：有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
最后返回经过上色渲染后的图像。
示例：
输入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
思路：小岛数量变形题，同样使用DFS；
首先判断给出的新值是否等于旧值，等于则直接返回原图像，否则进行修改处理；
递归调用，递归返回条件为(sr<0 || sc<0 || sr===h || sc===w || img[sr][sc]!==oldColor)，即当前坐标超出图像范围或当前坐标值不等于给定坐标的旧值(只修改相连的等于给定坐标旧值的值)；递归修改该坐标上下左右四个相邻像素的值，直到最后全部修改完毕。
var floodFill = function(image, sr, sc, newColor) {
let h = image.length;
if(h === 0) return;
let w = image[0].length;
let oldColor = image[sr][sc];
if(oldColor !== newColor)
modifyColor(image, sr, sc, oldColor, newColor, w, h);
return image;
};
function modifyColor(img, sr, sc, o, n, w, h) {
if(sr<0 || sc<0 || sr===h || sc===w || img[sr][sc]!==o) return
img[sr][sc] = n;
modifyColor(img, sr-1, sc, o, n, w, h);
modifyColor(img, sr+1, sc, o, n, w, h);
modifyColor(img, sr, sc-1, o, n, w, h);
modifyColor(img, sr, sc+1, o, n, w, h);
}
11. 01 矩阵
题目描述：给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1 。
条件：
给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。
示例：
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
思路：首先创建结果矩阵，令原矩阵为0处仍为0，原矩阵为1处为w+h-2(w，h分别为原矩阵宽高，最大距离即为w+h-2)；
最近的0只可能在上下左右四个相邻元素，若都不为0，则在它们之中存在距离0最近的，因此只需与它们加1比较取最小值即可
var updateMatrix = function(matrix) {
let h = matrix.length;
if(h===0) return matrix
let w = matrix[0].length;
let tmp = [];
for(let i=0; i<h; i++) {
tmp[i] = [];
for(let j=0; j<w; j++) {
if(matrix[i][j] === 0) {
tmp[i][j] = 0;
} else {
tmp[i][j] = w+h-2;
}
}
}
for(let i=0; i<h; i++)
for(let j=0; j<w; j++) {
if(j>0) {
tmp[i][j] = Math.min(tmp[i][j], tmp[i][j-1]+1);
}
if(i>0) {
tmp[i][j] = Math.min(tmp[i][j], tmp[i-1][j]+1);
}
}
for(let i=h-1; i>=0; i--)
for(let j=w-1; j>=0; j--) {
if(j<w-1) {
tmp[i][j] = Math.min(tmp[i][j], tmp[i][j+1]+1);
}
if(i<h-1) {
tmp[i][j] = Math.min(tmp[i][j], tmp[i+1][j]+1);
}
}
return tmp;
};
12.钥匙和房间
题目描述：有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。
在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
最初，除 0 号房间外的其余所有房间都被锁住。
你可以自由地在房间之间来回走动。
如果能进入每个房间返回 true，否则返回 false
示例：
输入: [[1],[2],[3],[]]
输出: true
解释:
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true
思路：利用栈和BFS，以第0个房间作为起点，遍历每个房间的钥匙；
将钥匙0入栈，创建一个visited对象，将属性0置为true，将能打开的房间数目count置为1；
从栈顶取出一个钥匙，访问该钥匙能打开的房间，并遍历其中的钥匙，若钥匙已存在与visited中，则不做处理；若不存在，则count加1，放入visited，并将钥匙入栈；
依次从栈顶取出钥匙，按照上述步骤处理，直到栈被清空；
最后判断count是否等于房间长度，等于则说明房间都能打开，返回true，否则返回false。
var canVisitAllRooms = function(rooms) {
let len = rooms.length;
let count = 1;
let visited = { 0: true };
let stack = [0];
while(stack.length) {
let top = stack.pop();
let arr = rooms[top];
for(let i=0; i<arr.length; i++) {
if(!visited.hasOwnProperty(arr[i])) {
count++;
stack.push(arr[i]);
visited[arr[i]] = true;
}
}
}
return len===count
};
3.完全平方数
题目描述：给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例：
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4
思路：有一个数学定理，任何一个正整数都可以表示成不超过四个整数的平方之和，也就是说给定一个正整数n，组成它的完全平方数的个数只有1,2,3,4四种可能；此外有一个推论，当一个正整数n只能由四个完全平方数组成时，它必定满足n=4^a*(8b+7)
由此，我们可以先判断n是否只能由四个完全平方数组成；若为否，由于要返回最少的个数，因此接下来再判断n是否能由1个完全平方数组成；仍为否，判断n是否能由两个完全平方数组成；最后则只能由3个完全平方数组成
var numSquares = function(n) {
while(n%4 === 0) {
n = n / 4; //这里并不影响后续判断组成n的完全平方数的个数，因为任何完全平方数乘4仍为完全平方数
}
if(n%8 === 7) return 4;
for(let i=0; i*i<=n; i++) {
if(i*i === n) return 1;
}
for(let i=0; i*i<n; i++) {
if(Number.isInteger(Math.sqrt(n-i*i))) return 2;
}
return 3;
};
4.数组与字符串
数组与列表的区别：数组有索引，列表没有索引；数组在内存中是连续存储的，而列表则不一定
数组与链表的区别：
数组在内存中是连续存储的，而链表则不一定；
数组有索引，链表没有；
数组可以根据索引查找元素，链表只能从头结点遍历查找；
1.寻找数组的中心索引
题目描述：给定一个整数类型的数组 nums，请编写一个能够返回数组 “中心索引” 的方法。
我们是这样定义数组 中心索引 的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
示例：
输入：
nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
索引 3 (nums[3] = 6) 的左侧数之和 (1 + 7 + 3 = 11)，与右侧数之和 (5 + 6 = 11) 相等。
同时, 3 也是第一个符合要求的中心索引。
输入：
nums = [1, 2, 3]
输出：-1
思路：如果存在中心索引，那么其左侧的值相加等于其右侧的值相加，即数组总和减去该索引对应的值除以2应该等于其左侧值的和，也等于其右侧值的和；
我们先求出数组总和，然后再遍历数组，判断总和减去该索引对应的值再除以2是否等于该索引左侧所有值的和，等于则说明该索引即为中心索引，返回该索引；遍历完毕寻找不到则说明不存在，返回-1。
注意：第二次遍历判断时，要先判断，再计算左侧和，因为左侧的和不应该包括中心索引对应的值；
另外，当遍历到最后一个索引值时，若左侧之和恰好为0，则返回最后一个索引，默认其右侧无值的话，右侧和为0.
var pivotIndex = function(nums) {
let len = nums.length;
let sum = 0;
for(let i=0; i<len; i++) {
sum += nums[i];
}
let left = 0;
for(let i=0; i<len; i++) {
if((sum-nums[i])/2 === left) {
return i
}
left += nums[i];
}
return -1;
};
2.搜索插入位置
题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例：
输入: [1,3,5,6], 5
输出: 2
输入: [1,3,5,6], 2
输出: 1
思路一：将元素放入数组中，然后将数组重新排序，遍历数组，找到该元素index，返回即可
var searchInsert = function(nums, target) {
nums.push(target);
nums.sort((a, b) => a-b);
return nums.findIndex(item => item===target)
};
思路二：遍历原数组，由于原数组按升序排列，因此找到第一个大于或等于目标值的index返回即可；若没有元素大于或等于目标值，则目标值应被插入到最后，返回原数组长度即可。
var searchInsert = function(nums, target) {
let len = nums.length;
for(let i=0; i<len; i++) {
if(target <= nums[i])
return i;
}
return len;
};
3.合并区间
题目描述：
给出一个区间的集合，请合并所有重叠的区间
示例：
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
思路：首先将给定集合intervals按照所有区间起始位置进行升序(起始位置相同时按照结束位置进行升序)排列；
定义结果存储数组res，并初始化res=intervals[0]；
依次对intervals所有区间进行合并，遍历intervals集合，每次将res[res.length-1]区间与当前intervals[i]区间进行合并，i由1开始(因为res初始化为intervals[0])；
判断前一区间结束是否小于后一区间开始，若是则说明不重叠，直接返回后一区间，并追加到res数组；若否，则说明有重叠区间，取前一区间开始，前一区间结束和后一区间结束最大值，两者之间即为合并后区间，返回该区间，并将res最后一个元素代替为该区间。
var merge = function(intervals) {
if(intervals.length < 2) return intervals;
intervals.sort((a, b) => {
if(a[0] !== b[0])
return a[0]-b[0]
else
return a[1]-b[1]
});
let res = [intervals[0]];
for(let i=1; i<intervals.length; i++) {
let len = res.length;
let obj = mergeTwo(res[len-1], intervals[i]);
if(obj.flag) {
res.pop();
}
res.push(obj.arr);
}
return res;
};
function mergeTwo(arr1, arr2) {
let s1 = arr1[0], e1 = arr1[1];
let s2 = arr2[0], e2 = arr2[1];
if(e1 < s2) {
return { flag: false, arr: arr2};
} else {
return { flag: true, arr: [s1, Math.max(e1, e2)] };
}
}
4.旋转矩阵
题目描述：给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。不占用额外内存空间能否做到
示例：
给定 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) {
let h = matrix.length;
if(h<2) return matrix;
let w = matrix[0].length;
matrix = matrix.reverse();
for(let i=0; i<h-1; i++)
for(let j=i+1; j<w; j++) {
matrix[i][j] = matrix[i][j] + matrix[j][i];
matrix[j][i] = matrix[i][j] - matrix[j][i];
matrix[i][j] = matrix[i][j] - matrix[j][i];
}
return matrix;
};
思路2：将矩阵自下向上每一行的元素，依次放至每一行后面，例如将最后一行N个元素，分别放到N行后面，相当于在矩阵后添加一列；
全部添加完毕后，将每一行前N个元素删除，则剩余矩阵即为旋转后的矩阵。
var rotate = function(matrix) {
let N = matrix.length;
if(N<2) return matrix;
for(let i=N-1; i>=0; i--)
for(let j=0; j<N; j++) {
matrix[j].push(matrix[i][j]);
}
for(let i=0; i<N; i++){
matrix[i].splice(0, N);
}
return matrix;
};
5.零矩阵
题目描述：编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零
示例：
输入：
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出：
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
思路一：先遍历整个矩阵，将矩阵中为0的元素所在的行和列的索引值分别利用一个数组(zeroRow，zeroCol)存起来；
再次遍历矩阵，若该元素的行或列的索引在zeroRow或zeroCol中，则将该元素置0，否则说明该元素所在行列均没有0元素存在，保持元素值不变。
var setZeroes = function(matrix) {
let h = matrix.length;
if(h === 0) return matrix;
let w = matrix[0].length;
let zeroRow = [], zeroCol = [];
for(let i=0; i<h; i++)
for(let j=0; j<w; j++) {
if(matrix[i][j] === 0) {
if(!zeroRow.includes(i)) {
zeroRow.push(i);
}
if(!zeroCol.includes(j)) {
zeroCol.push(j);
}
}
}
for(let i=0; i<h; i++)
for(let j=0; j<w; j++) {
if(zeroRow.includes(i) || zeroCol.includes(j)) {
matrix[i][j] = 0;
}
}
return matrix;
};
思路二：将原矩阵复制一份，遍历判断新矩阵中元素是否为0，若是则将原矩阵对应行列置0，最终返回原矩阵；
复制一份是为了避免直接修改原矩阵，使得矩阵最终全为0;。
var setZeroes = function(matrix) {
let h = matrix.length;
if(h === 0) return matrix;
let w = matrix[0].length;
let newMatrix = JSON.parse(JSON.stringify(matrix));
for(let i=0; i<h; i++)
for(let j=0; j<w; j++) {
if(newMatrix[i][j] === 0) {
for(let i1=0; i1<h; i1++) {
matrix[i1][j] = 0;
}
for(let j1=0; j1<w; j1++) {
matrix[i][j1] = 0;
}
}
}
return matrix;
};
6.对角线遍历
题目描述：给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示
示例：
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,4,7,5,3,6,8,9]
解释:
思路：对角线上的元素满足脚标之和相等，如(0,1)(1,0)，(2,0)(1,1)(0,2)；
则每遍历一条对角线，就是将所有脚标之和等于该条对角线index(第1条，第2条等)的元素找出并按顺序存入结果数组；
顺序在对角线index为偶数时为自下向上(即y坐标不断减小)，在对角线index为奇数时，自上向下(即x坐标不断减小)；
遍历每条对角线，判断该对角线index为奇数还是偶数；
当index为奇数时，令x值取最大(min(index, w-1))，并令x不断减小，直至x等于0(到达最左端)或index-x等于h-1(到达最下端)；
当index为偶数时，令y值取最大(min(index, h-1))，并令y不断减小，直至y等于0(到达最上端)或index-y等于w-1(到达最右端)；
var findDiagonalOrder = function(matrix) {
let h = matrix.length;
if(h === 0) return matrix;
let w = matrix[0].length;
let res = [];
for(let i=0; i<h+w-1; i++) {
let xMax = i>w-1 ? w-1 : i;
let yMax = i>h-1 ? h-1 : i;
if(i%2 === 0) {
let y = yMax;
while(y>=0 && (i-y)<w) {
res.push(matrix[y][i-y]);
y--;
}
} else {
let x = xMax;
while(x>=0 && (i-x)<h) {
res.push(matrix[i-x][x]);
x--;
}
}
}
return res;
};
7.最长公共前缀
题目描述：编写一个函数来查找字符串数组中的最长公共前缀，如果不存在公共前缀，返回空字符串 ""
示例：
输入: ["flower","flow","flight"]
输出: "fl"
输入: ["dog","racecar","car"]
输出: ""
思路：首先找出字符串数组中最短的字符串，然后依次判断是否所有字符串均以该字符串为开头，是，则返回该字符串，否，将该字符串去掉末尾字符，再依次检测，直至找到所有字符串均相同的前缀，返回该前缀，或所有字符串找不到相同前缀，返回""
var longestCommonPrefix = function(strs) {
if(strs.length === 0) return ""
let str = strs[0];
let minLen = strs[0].length;
for(let i=1; i<strs.length; i++) {
if(strs[i].length < minLen) {
minLen = strs[i].length;
str = strs[i];
}
}
let flag;
for(let i=minLen; i>0; i--){
str = str.slice(0, i);
flag = true;
for(let j=0; j<strs.length; j++){
if(!strs[j].startsWith(str)) {
flag = false;
break;
}
}
if(flag) {
break;
}
}
if(!flag) return "";
return str;
};
8.翻转字符串里的单词
题目描述：给定一个字符串，逐个翻转字符串中的每个单词。
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
示例：
输入: " hello world! "
输出: "world! hello"
输入: "a good example"
输出: "example good a"
思路：去掉首尾空格，利用正则全局替换将多个空格替换为单个空格，再按空格切割为数组，之后反转数组，最后再以空格拼接数组为字符串，返回即可。
var reverseWords = function(s) {
return s.trim().replace(/\s+/g, " ").split(" ").reverse().join(" ");
};
9.实现 strStr()
题目描述：给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1
示例：
输入: haystack = "hello", needle = "ll"
输出: 2
输入: haystack = "aaaaa", needle = "bba"
输出: -1
思路：使用indexOf()或search()函数，测试结果indexOf用时72ms，search用时96ms
注：针对空字符串""，indexOf和search均返回0
var strStr = function(haystack, needle) {
if(needle === "") return 0;
// return haystack.search(needle)
return haystack.indexOf(needle)
};
10.反转字符串
题目描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[]的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 [ASCII]码表中的可打印字符。
示例：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
思路：利用reverse函数或双指针反转，双指针定义两个指针，一个从头开始，一个从尾开始，依次交换，直到相遇
运行结果，双指针运行132ms，reverse函数120ms
var reverseString = function(s) {
let len = s.length;
if(len < 2) return s;
let i=0, j=len-1;
let tmp = "";
while(i<j) {
tmp = s[i];
s[i] = s[j];
s[j] = tmp;
i++;
j--;
}
return s;
// return s.reverse();
};
11.长度最小的子数组
题目描述：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0
示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组
思路：利用双指针，定义两个指针，start和end，定义子数组之和sum；
开始start静止不动，end后移，sum不断累加end对应的数组值，由于给定为正整数数组，因此sum的值逐渐增大，当sum大于等于给定s时，end暂停，记录下此时子数组长度(end-start+1)；
start不断后移，并且sum值减去start对应的数组值，直到sum小于s，此过程中子数组不断缩小，要注意更新最小子数组长度；
end继续后移，直到sum再次大于等于s，重复上述步骤，不断更新最小子数组长度，直至end遍历到数组末尾；
初始子数组长度设置为给定数组长度加1(若数组中有子数组元素之和大于等于s，则子数组长度至多为给定数组长度)，最后判断最小子数组长度是否等于初始值，等于则说明整个数组之和仍小于s，返回0，否则返回最小子数组长度
var minSubArrayLen = function(s, nums) {
let start = 0, end = 0, sum = 0, ans = nums.length+1;
while(end < nums.length) {
sum += nums[end];
while(sum >= s) {
if((end-start+1) < ans)
ans = end - start + 1;
sum -= nums[start];
start++;
}
end++;
}
if(ans === nums.length+1) return 0;
return ans;
};
12.复原IP地址
题目描述：给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。
示例：
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
思路：每个整数最少一位，最多三位，四层循环，分别代表第一、二、三、四四个整数的长度，当它们相加等于字符串长度时，说明可能是有效的IP地址；
然后将原字符串按照四个长度切成四个子字符串，判断四个子字符串转成整数后是否符合IP地址规则，要求有小于255，除非长度为1否则不能以0为开始，满足则返回true，否则返回false；
当四个子字符串均满足要求时，说明为合法IP地址，放入结果数组中，若有一个不满足，则说明不合法，则继续循环寻找，直到结束。
var restoreIpAddresses = function(s) {
let res = [];
for(let a=1; a<4; a++)
for(let b=1; b<4; b++)
for(let c=1; c<4; c++)
for(let d=1; d<4; d++) {
if(a+b+c+d === s.length) {
let n1 = s.slice(0, a);
let n2 = s.slice(a, a+b);
let n3 = s.slice(a+b, a+b+c);
let n4 = s.slice(a+b+c);
if(valid(n1) && valid(n2) && valid(n3) && valid(n4)) {
res.push(n1 + "." + n2 + "." + n3 + "." + n4);
}
}
}
return res;
};
function valid(str) {
if(parseInt(str) <= 255) {
if(str[0]!=='0' || (str[0]==='0' && str.length===1)) {
return true;
}
}
return false;
}
13.数组快排
思路一：利用额外空间存储left和right，递归调用快排函数对left和right进行排序，直到排序数组为空则返回空数组，或排序数组长度为1返回原数组；最终将排好序的left和right以及参考数值pivot拼接起来返回即可
function quickSort(arr) {
if(arr.length === 0) return [];
if(arr.length === 1) return arr;
let pivot = arr[0];
let len = arr.length;
let left = [], right = [];
for(let i=1; i<len; i++) {
if(arr[i] <= pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
left = quickSort(left);
right = quickSort(right);
return [...left, pivot, ...right];
}
思路二：不占用额外空间，直接对数组进行操作；
选取最右端数组值为参考值，定义index初始化为最左端的索引，从最左端到最右端遍历比较每个值是否小于参考值，小于则将该值与index对应值交换，并将index加1(即，将小于参考值的数组值依次放到前面)；
遍历完成后将最右侧数组值与当前index对应值交换，则此时index左侧均为小于参考值的值，右侧均为大于参考值的值；
将数组左侧和右侧再递归调用排序函数进行排序，直至最终排序完成；
结束条件为要排序的子数组长度为0，即传入的左侧索引值大于右侧索引值。
function quickSort(left, right) {
if(left > right) return;
let pivot = arr[right];
let index = left;
for(let i=left; i<right; i++) {
if(arr[i] < pivot) {
swap(arr, i, index);
index++;
}
}
swap(arr, right, index);
quickSort(left, index-1);
quickSort(index+1, right);
}
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
quickSort(0, arr.length-1)
14.买卖股票的最佳时机
题目描述：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 :
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
思路：寻找最大利润，即寻找数组最大差值，且大值在小值右侧；
假设最大利润maxProfit最初为0，最小股价minPrice最初为最大值(Number.MAX_SAFE_INTEGER，保证股价不会超出此值)，然后遍历整个数组；
当股价小于当前最小股价时，将最小股价改为此值，否则判断当前股价减去最小股价是否大于当前最大利润，大于则更新最大利润；
这样遍历完毕即可找出最大利润。
var maxProfit = function(prices) {
let minPrice = Number.MAX_SAFE_INTEGER;
let maxProfit = 0;
for(let i=0; i<prices.length; i++) {
if(prices[i] < minPrice) {
minPrice = prices[i];
} else {
maxProfit = Math.max(maxProfit, prices[i]-minPrice);
}
}
return maxProfit;
};
15.数组中的第K个最大元素
题目描述：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 :
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
思路一：将数组降序排序，取第k-1个值即可
var findKthLargest = function(nums, k) {
nums.sort((a, b) => b-a);
return nums[k-1];
};
思路二：利用快排思想，取出一个值作为参考值，选取参考值时要随机选取，这样可以使平均复杂度降低，index初始化为0；
将大于参考值的值与index所在值交换，同时index右移，遍历完整个数组后，将参考值与index所在值交换，这样大于参考值的值都在参考值左侧，小于参考值的值都在参考值右侧；
判断当前参考值index是否等于k-1，等于则说明参考值即所求值；
否则，若index小于k-1，则说明在所求值在其右侧，对其右侧如上述步骤同样处理；
若index大于k-1，则说明所求值在其左侧，对其左侧如上述步骤同样处理；直至寻找到相应index。
var findKthLargest = function(nums, k) {
function quickSort(left, right) {
let random = Math.floor(Math.random() * (right-left+1)) + left;
let pivot = nums[random];
swap(random, right);
let index = left;
for(let i=left; i<right; i++) {
if(nums[i] > pivot) {
swap(index, i);
index++;
}
}
swap(index, right);
if(index === k-1) {
return nums[index];
}
let res;
if(index < k-1) {
res = quickSort(index+1, right);
}
if(index > k-1) {
res = quickSort(left, index-1);
}
return res;
}
function swap(i, j) {
let tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
return quickSort(0, nums.length-1);
};
16.数组拆分 I
题目描述：给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大
示例 1:
输入: [1,4,3,2]
输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4)
思路：将数组升序排列，相邻值相差最小，取第0,2，...,2n-2个元素相加即可得到最终结果
var arrayPairSum = function(nums) {
let sum = 0;
nums.sort((a, b) => a-b);
for(let i=0; i<nums.length; i=i+2) {
sum += nums[i];
}
return sum;
};
17.两数之和 II - 输入有序数组
题目描述：
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例：
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2
思路：设置两个指针，start=0，end=numbers.length-1，循环判断numbers[start]+numbers[end]是否等于target，等于则返回[start+1, end+1]；若小于target则start++；若大于target则end--。
var twoSum = function(numbers, target) {
if(numbers.length < 2) return -1;
let start = 0, end = numbers.length-1;
while(start < end) {
if(numbers[start]+numbers[end] === target) {
return [start+1, end+1];
}
if(numbers[start]+numbers[end] < target) {
start++;
}
if(numbers[start]+numbers[end] > target) {
end--;
}
}
return -1;
};
18.移除元素
题目描述：给你一个数组 nums 和一个值 val，你需要 原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例：
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
思路：给定一个slow指针，初始化为0，遍历数组，当数组元素不等于给定val时，nums[slow]=nums[i]，同时slow后移一位，最终返回slow的值
var removeElement = function(nums, val) {
let slow = 0;
for(let i=0; i<nums.length; i++) {
if(nums[i] !== val) {
nums[slow] = nums[i];
slow++;
}
}
return slow;
};
19.最大连续1的个数
题目描述：给定一个二进制数组， 计算其中最大连续1的个数
示例：
输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3
思路：设定一个指针slow=0，最大连续1长度maxLen=0，遍历数组，当数组元素等于1时，判断i-slow+1是否大于maxLen，大于则更新maxLen；若数组元素不等于1，则slow=i+1(当数组元素不等于1时，slow永远指向下一个元素，直到数组元素等于1)
var findMaxConsecutiveOnes = function(nums) {
let slow = 0;
let maxLen = 0;
for(let i=0; i<nums.length; i++) {
if(nums[i] === 1) {
if(i-slow+1 > maxLen) {
maxLen = i-slow+1;
}
} else {
slow = i+1;
}
}
return maxLen;
};
20.杨辉三角
题目描述：给定一个非负整数 numRows，生成杨辉三角的前 numRows 行
示例：
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
思路：从第三行开始，每行中间的元素为前一行相邻元素之和，然后再在开头和结尾添加1，即可完成杨辉三角
var generate = function(numRows) {
if(numRows === 0) return [];
if(numRows === 1) return [[1]];
if(numRows === 2) return [[1], [1, 1]];
let res = [[1], [1, 1]];
for(let i=2; i<numRows; i++) {
let arr = [];
for(let j=0; j<i-1; j++) {
arr.push(res[i-1][j] + res[i-1][j+1]);
}
arr.push(1);
arr.unshift(1);
res.push(arr);
}
return res;
};
21.杨辉三角 II
题目描述：给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行，你可以优化你的算法到 O(k) 空间复杂度吗？
示例:
输入: 3
输出: [1,3,3,1]
说明：第0行为[1]，第一行为[1,1]
思路：对于给定第k行，其第一个元素等于其上层第k-1行第一个元素和第二个元素之和，第二个元素等于其上层第二个和第三个元素之和，以此类推，只需令arr[0]=arr[0]+arr[1]，arr[1]=arr[1]+arr[2]..., arr[i]=arr[i]+arr[i+1]，一直到上一层相加完毕；假设上一层长度为n，则此时数组长度仍为n，且前n-1个元素分别是上层元素相邻元素之和，最后一个元素仍为1；最后在新数组前加入一个1即可；
循环调用此函数，直到达到要求的k行。
var getRow = function(rowIndex) {
if(rowIndex === 0) return [1];
if(rowIndex === 1) return [1, 1];
let arr = [1, 1];
function getK() {
for(let i=0; i<arr.length-1; i++) {
arr[i] = arr[i] + arr[i+1];
}
arr.unshift(1);
}
while(rowIndex > 1) {
getK();
rowIndex--;
}
return arr;
};
22.删除排序数组中的重复项
题目描述：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成
示例：
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
思路：设定慢指针slow=0，遍历nums数组，当nums[i]!==nums[slow]时，slow++，并令nums[slow]=nums[i]，最后返回slow+1；注意当nums长度为0时，直接返回0.
var removeDuplicates = function(nums) {
if(nums.length === 0) return 0;
let slow = 0;
for(let i=0; i<nums.length; i++) {
if(nums[slow] !== nums[i]) {
slow++;
nums[slow] = nums[i];
}
}
return slow+1;
};
23.移动零
题目描述：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例：
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
思路：遍历数组，判断元素是否为0，为0则删除该元素，并在数组后方push一个0；
注意每次删除当前0元素后，由于下一个元素index变成了当前index，因此需要将i--；另外，由于只需要遍历原数组长度，因此初始先设定len=nums.length，每次删除元素，i--后，len也要相应进行len--。
var moveZeroes = function(nums) {
let len = nums.length;
for(let i=0; i<len; i++){
if(nums[i] === 0) {
nums.splice(i, 1);
i--;
len--;
nums.push(0);
}
}
return nums;
};
24.无重复字符的最长子串
题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度
示例：
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串
思路：初始化最大不重复子串长度maxLen为0，初始化一个visited空数组；
遍历字符串，当visited中不含有当前字符时，说明没有重复字符，则visited数组push入该字符，并令maxLen=Math.max(maxLen, visited.length)，更新最大长度；
若visited中含有该字符，说明出现重复字符，则将visited第一次出现该字符及其前面的字符删除，重新push该字符，然后继续遍历，重复上述步骤，直到遍历完成
var lengthOfLongestSubstring = function(s) {
let maxLen = 0;
let visited = [];
for(let i=0; i<s.length; i++) {
let idx = visited.indexOf(s[i]);
if(idx !== -1) {
visited.splice(0, idx+1);
}
visited.push(s[i]);
maxLen = Math.max(maxLen, visited.length);
}
return maxLen;
};
5.二叉树
1.求根到叶子节点数字之和
题目描述：给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
示例：
输入: [1,2,3]
1
/ \
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
思路：深度优先遍历；
初始值设为0，判断当前节点是否为空节点，是则直接返回，不是则将此值乘10加上当前节点的值存起来设为当前值；
判断当前节点是否没有子节点，没有则说明到底，将当前值加入总和，返回；有子节点说明还未到底，继续递归遍历其子节点；
当所有节点被遍历完成，返回总和。
var sumNumbers = function(root) {
let sum = 0;
function dfs(root, cur) {
if(!root) return;
cur = cur*10 + root.val;
if(!root.left && !root.right) {
sum += cur;
return;
}
dfs(root.left, cur);
dfs(root.right, cur);
}
dfs(root, 0);
return sum;
};
3.二叉树的最大深度
题目描述：给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
思路：给定一个节点，假设它为叶子节点，即没有子节点，则它的最大深度为1；而若它含有子节点，则其最大深度为子节点最大深度加1。
var maxDepth = function(root) {
if(!root) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};
4.二叉树中的最大路径和
题目描述：给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例：
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
思路：给定一个节点，找到它的左侧子节点最大贡献值，右侧子节点最大贡献值；
由于可能是子节点获取到最大和，因此需要比较当前最大和与当前节点值+左子节点最大贡献值+右子节点最大贡献值，使最大和取两者之间最大值；
返回当前节点值+max(左子节点最大贡献值，右子节点最大贡献值)，即当前节点为父节点贡献的最大值(因为路径不能走入子节点再返回，因此只能选取一侧最大值)；
遍历完成，返回最大和。
var maxPathSum = function(root) {
let maxSum = Number.MIN_SAFE_INTEGER;
function dfs(root) {
if(!root) return 0;
let left = Math.max(0, dfs(root.left));
let right = Math.max(0, dfs(root.right));
maxSum = Math.max(maxSum, left+root.val+right);
return root.val+Math.max(left, right);
}
dfs(root);
return maxSum;
};
6.动态规划
1. 零钱兑换
题目描述：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1
示例：
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
输入: coins = [2], amount = 3
输出: -1
思路：假设总金额为S，需要的最少硬币数为F(S)，则：
F(S) = min(F(S-ci)) + 1，其中i=1,2,...,n，n为coins数组长度
也就是说构成总金额S最少需要的硬币数等于构成其依次减去所给硬币金额后金额最小硬币数加1；
例如假设给定coins[5,10]，给定金额10，则10依次减去5和10分别为5和0，构成0的硬币数为0，加1为1，构成5的最小硬币数为1，加1为2，最终比较1和2，得到结果为1；
如上例所示，假设我们已知F(0)和F(5)，则取它们最小值加1即可得到结果；
因此针对F(S)，假设我们已知F(0),F(1),...,F(S-1)，则我们将S减去所给硬币面额，然后由F(0),F(1),...,F(S-1)中找到它们对应的值，再比较出最小值，加1即可求得F(S)；
因此我们可定义一个数组dp，用来存储0-S分别对应的F(i)的值，然后用到哪个值直接取出即可；
dp初始化值除dp[0]外均为S+1(因为构成S的硬币数最多为S个，否则不能构成)，dp[0]=0是因为构成总额为0需要0个硬币；
我们从0开始，F(0)=0，然后利用循环来依次求取F(1)F(S)的值，例如到F(i)时，由于F(0)F(i-1)的值我们都已知了，直接找到对应值求取最小值加1即可；
最终判断F(S)是否大于S，大于则说明给定硬币无法构成金额S，返回-1，否则返回F(S)即dp[S]。
var coinChange = function(coins, amount) {
let dp = new Array(amount+1).fill(amount+1);
dp[0] = 0;
for(let i=1; i<=amount; i++) {
for(let j=0; j<coins.length; j++) {
if(coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i-coins[j]]+1);
}
}
}
return dp[amount]>amount ? -1 : dp[amount]
};
