js刷林扣 lintcode（2017年3月）
3.10
69.给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）
二叉树的层次遍历
样例
给一棵二叉树 {3,9,20,#,#,15,7} ：
3
/ \
9 20
/ \
15 7
返回他的分层遍历结果：
[
[3],
[9,20],
[15,7]
]
function levelOrder(arr){
var res=[]
var tempArr=[]
var levelNum=1 //每层的节点数
var levelTotal=1 //层的阶乘
for(var i=0;i<arr.length+1;i++){
if(arr[i]=='#'){arr[i]=undefined}
if(i<levelTotal){
tempArr.push(arr[i])
}else if(i==levelTotal){ //等于的时候退出子数组，往res中push
res.push(tempArr)
tempArr=[] //清空子数组
tempArr.push(arr[i])
levelNum*=2
levelTotal+=levelNum
}
}
return res
}
80.给定一个未排序的整数数组，找到其中位数。
中位数
中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。
样例
给出数组[4, 5, 1, 2, 3]， 返回 3
function median(arr){
var i=arr.length%2==0? arr.length/2:(arr.length+1)/2
return arr.sort()[i]
}
82.落单的数
给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
样例
给出 [1,2,2,1,3,4,3]，返回 4
function singleNumber(arr){
arr.sort()
var totalArr=[]
for(var i=0;i<arr.length+1;i+=2){
if(arr[i]!=arr[i+1]){
if(i==arr.length-1){return arr[i]}//如果arr[i]为最后一个自然数则返回他
if(arr[i+2]==arr[i+1]){return arr[i]}
}
}
}
看了下大多数的算法，都是用位操作符异或算的，既然js有sort()方法还是这样写好了，反正都得遍历。
3.13
96.链表划分
给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。
你应该保留两部分内链表节点原有的相对顺序。
链接
样例
给定链表 1->4->3->2->5->2->null，并且 x=3
返回 1->2->2->4->3->5->null
function partition(arr,num){
var pre=[],post=[]
for(var i in arr){
if(arr[i]>=num){
post.push(arr[i])
}else{
pre.push(arr[i])
}
}
return pre.concat(post)
}
3.14
97.二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的距离。
样例
给出一棵如下的二叉树:
1
/ \
2 3
/ \
4 5
这个二叉树的最大深度为3.
function maxDepth(len){
if(len%2==0){
depth++
return maxDepth(len/2)
}
return depth
}
思路：深度为2的n次方-1，传数组的长度+1，算几次幂就好了
100.删除排序数组中的重复数字
给定一个排序数组，在原数组中删除重复出现的数字，使得每个元素只出现一次，并且返回新的数组的长度。
不要使用额外的数组空间，必须在原地没有额外空间的条件下完成。
题目链接
样例
给出数组A =[1,1,2]，你的函数应该返回长度2，此时A=[1,2]。
function removeDuplicates(arr){
var i=0
while(i<arr.length){
if(arr[i+1]==arr[i]){
arr.splice(i+1,1)
}else{
i++
}
}
return arr
}
思路：遍历数组，删除一个元素后不需要改变i值
101.删除排序数组中的重复数字 II
跟进“删除重复数字”：
如果可以允许出现两次重复将如何处理？
function removeDuplicates(arr){
var i=0
var duplicateTimes=0
while(i<arr.length){
if(arr[i+1]==arr[i]){
duplicateTimes++
if(duplicateTimes>2){
arr.splice(i+1,1)
}
}else{
duplicateTimes=0
i++
}
}
return arr
}
思路：和上题相比，多加一个判断条件就ok了，但依旧是删除一个元素后i不变
3.15
109.数字三角形
给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。题目链接
样例：
比如，给出下列数字三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。
function minimumTotal(arr){
var sum=0
arr.forEach(function(a){
a.sort()
sum+=a[0]
})
return sum
}
思路:遍历数组，将每个子数组排序，取第零个相加
111. 爬楼梯
假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？
题目链接
样例
比如n=3，1+1+1=1+2=2+1=3，共有3中不同的方法
返回 3
function climbStairs(n){
var mtd=0
if(n==0||n==1){
return 1
}
else{
mtd=climbStairs(n-1)+climbStairs(n-2)
}
return mtd
}
思路：爬到第几层就是上一层在爬一层，也就是上上一层爬两层···以此类推，递归
3.17
133.最长单词
给一个词典，找出其中所有最长的单词。
题目链接
样例
在词典
{
"dog",
"google",
"facebook",
"internationalization",
"blabla"
}
中, 最长的单词集合为 ["internationalization"]
挑战
遍历两次的办法很容易想到，如果只遍历一次你有没有什么好办法？
function longestWords(arr){
let maxLen=0,res=[]
arr.forEach( (a) => {
if(a.length>=maxLen){
if(a.length>maxLen){
maxLen=a.length
res=[]
}
res.push(a)
}
})
return res
}
思路
遍历数组，比之前的大就清空结果数组，重新push
138.子数组之和
给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置
题目链接
样例
给出 [-3, 1, 2, -3, 4]，返回[0, 2] 或者 [1, 3].
function subarraySum(arr){
let res=[],startIndex=0,sum=0,posArr=[]
for(j=0;j<arr.length;j++){
for(let i=startIndex;i<arr.length;i++){
posArr.push(i)
sum+=arr[i]
if(sum==0){
res.push(posArr)
posArr=[]
startIndex++
break;
}
}
}
return res
}
function startAndEnd(arr){
let res=[]
arr.forEach((a) => {
let subArr=[]
subArr.push(a[0])
subArr.push(a[a.length-1])
res.push(subArr)
})
return res
}
let result=startAndEnd(subarraySum([-3, 1, 2, -3, 4]))
思路：有多少个元素就遍历几次，每次遍历时从指针所指元素开始，找到sum为0的元素就退出循环，下次指针指向下一个元素
3.20(春分)
140.x的平方根
实现 int sqrt(int x) 函数，计算并返回 x 的平方根。
题目链接
样例
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(10) = 3
let sqrtFn = (num) => Math.sqrt(num)
思路：没有思路，内置方法LOL
142.O(1)时间检测2的幂次
用 O(1) 时间检测整数 n 是否是 2 的幂次。
题目链接
样例
n=4，返回 true;
n=5，返回 false.
let checkPowerOf2 = (num) => {
let decimalRes=num.toString(2)&(num-1).toString(2)
return num>0&&decimalRes==0
}
思路：位操作，当前数并上他的上一个数，如为0则是2的幂数
3.21
156. 合并区间
给出若干闭合区间，合并所有重叠的部分。
题目链接
样例
给出的区间列表 => 合并后的区间列表：
[ [
[1, 3], [1, 6],
[2, 6], => [8, 10],
[8, 10], [15, 18]
[15, 18] ]
]
let merge=(intervals) => {
intervals.sort((a,b)=>{
//先排序
if(a[0]!=b[0]){return a[0]-b[0]}
return a[1]-b[1]
})
let len=intervals.length
let res=[],start,end
for(let i=0;i<len;i++){
let s=intervals[i][0],e=intervals[i][1]
if(!start) {start=s,end=e}
else if(s<=end){end=Math.max(end,e)}
else{
let part=[start,end]
res.push(part)
start=s
end=e
}
}
if(start){
let part=[start,end]
res.push(part)
}
return res
}
let arr=[
[1,3],[2,6],[8,10],[9,11]]
console.log(merge(arr)) //[1,6],[8,11]
思路：将区间从大到小排序，遍历找下个区间中的重合部分，push进新数组
157.判断字符串是否没有重复字符
实现一个算法确定字符串中的字符是否均唯一出现
题目链接
样例
给出"abc"，返回 true
给出"aab"，返回 false
挑战
如果不使用额外的存储空间，你的算法该如何改变？
let isUnique=(str) => {
for(let i=0;i<str.length;i++){
for(let j=i+1;j<str.length;j++){
if(str.charAt(i)==str.charAt(j)){
return false
}
}
}
return true
}
console.log(isUnique('abcd')) //true
思路：不占用存储空间，只能延长运行时间。遍历两层，找到相同的元素就返回false。
3.22
158.两个字符串是变位词
写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。题目链接
样例
给出 s = "abcd"，t="dcab"，返回 true.
给出 s = "ab", t = "ab", 返回 true.
给出 s = "ab", t = "ac", 返回 false.
挑战
O(n) time, O(1) extra space
let anagram = (str1,str2)=>{
if(str1.length!=str2.length) return false
for(let i=0;i<str1.length;i++){
if(str1.charAt(i)!=str2.charAt(str1.length-1-i)) return false
}
return true
}
let str1='abcd',str2='cdba'
console.log(anagram(str1,str2)) //true
思路：找对应的位置元素是否相同，不同则return false
165.合并两个排序链表
合并两个排序链表题目链接
样例
给出 1->3->8->11->15->null，2->null， 返回 1->2->3->8->11->15->null。
let mergeTwoLists=(arr1,arr2)=>{
let res=[].concat(arr1).concat(arr2)
res.sort((a,b)=>a-b)
return res
}
let arr1=[1,3,8,11,15]
let arr2=[2]
console.log(mergeTwoLists(arr1,arr2))
思路：连接两个数组，之后排序
166.链表倒数第n个节点
找到单链表倒数第n个节点，保证链表中节点的最少数量为n。题目链接
样例
给出链表 3->2->1->5->null和n = 2，返回倒数第二个节点的值1.
let nthToLast=(arr,p)=>{
if(p>arr.length) return 'error position'
return arr[arr.length-p]
}
let arr=[5,4,3,2,1]
console.log(nthToLast(arr,5)) //5
思路：js中没有链表的概念，数组很好取
3.23
172.删除元素
给定一个数组和一个值，在原地删除与值相同的数字，返回新数组的长度。
元素的顺序可以改变，并且对新的数组不会有影响
样例
给出一个数组 [0,4,4,0,0,2,4,4]，和值 4
返回 4 并且4个元素的新数组为[0,0,0,2]
let removeElement=(arr,num)=>{
let newArr=[]
arr.forEach((a)=>{
if(a==num){
newArr.push(a)
}
})
return newArr.length
}
let arr= [0,4,4,0,0,2,4,4]
console.log(removeElement(arr,4))//4
思路：遍历数组，找到一个符合条件的就push到新数组
3.24
181.将整数A转换为B
如果要将整数A转换为B，需要改变多少个bit位？题目链接
样例
如把31转换为14，需要改变2个bit位。
(31)10=(11111)2
(14)10=(01110)2
let bitSwapRequired=(n1,n2)=>{
let res=0
let num1=n1.toString(2)
let num2=n2.toString(2)
let maxL=Math.max(num1.length,num2.length)
let maxN=Math.max(num1,num2),minN=Math.min(num1,num2)
for(let i=maxL;i>0;i--){
//maxN和minN都是数字，先转化为字符串再遍历每个位置
if((''+maxN).charAt(i)!=(''+minN).charAt(i)){res++}
}
return res;
}
console.log(bitSwapRequired(19,31)) //2
思路：转化为2进制之后，按照字符串的类型遍历。注意一定是从尾部开始遍历。
185.矩阵的之字型遍历
给你一个包含 m x n 个元素的矩阵 (m 行, n 列), 求该矩阵的之字型遍历。
给你一个包含 m x n 个元素的矩阵 (m 行, n 列), 求该矩阵的之字型遍历。题目链接
样例
对于如下矩阵：
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10, 11, 12]
]
返回 [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12]
let permutationIndex=(arr)=>{
let res=[arr[0][0]]
let r=0,c=0
let LEN=arr[0].length*arr.length
for(let i=0;i<LEN;i++){
while(i<LEN&&r>=1&&c<arr[0].length-1){
res.push(arr[--r][++c])
}
if(i<LEN&&c<arr[0].length-1){
res.push(arr[r][++c])
}else if(i<LEN&&r<arr.length-1){
res.push(arr[++r][c])
}
while(i<LEN&&r<arr.length-1&&c>=1){
res.push(arr[++r][--c])
}
if(i<LEN&&r<arr.length-1){
res.push(arr[++r][c])
}else if(i<LEN&&c<arr[0].length-1){
res.push(arr[r][++c])
}
}
return res
}
思路：这个逻辑比之前的复杂多了，而且不好找规律，为啥要放简单题里！！我也是网上搜的java代码改成js了。。真心笨
3.27
211.字符串置换
具体不说了，和158变位词一个意思题目链接
212.空格替换
设计一种方法，将一个字符串中的所有空格替换成 %20 。你可以假设该字符串有足够的空间来加入新的字符，且你得到的是“真实的”字符长度。
你的程序还需要返回被替换后的字符串的长度。题目链接
let replaceBlank=(str)=>{
str=str.replace(/ /g,'%20')
console.log(str)
return str.length
}
console.log(replaceBlank("Mr John Smith")) //17
思路：这道题原意是让你遍历字符串，然后挪遍历位置。因为js有现有方法就直接用了,that's why i love JavaScript deeply~~
365.二进制中有多少个1
计算在一个 32 位的整数的二进制表式中有多少个 1 题目链接
let countOnes=(num)=>{
let str=num.toString(2)
let i=0,res=0
for(;i<str.length;i++){
if(str.charAt(i)==1){res+=1}
}
return res
}
console.log(countOnes(7))//3
思路：转换为二进制，遍历
373.奇偶分割数组
分割一个整数数组，使得奇数在前偶数在后。题目链接
let partitionArray=(arr)=>{
let i=0,j=arr.length-1
while(i<j){
while(arr[i]%2==1){
i++;
}
while(arr[j]%2==0){
j--;
}
if(i<j){
arr[i]=arr[i]+arr[j]
arr[j]=arr[i]-arr[j]
arr[i]=arr[i]-arr[j]
}
}
return arr
}
思路：指针一个在头部，一个在尾部，当两个指针将要重合的时候，停止遍历。
372.在O(1)时间复杂度删除链表节点
给定一个单链表中的一个等待被删除的节点(非表头或表尾)。请在在O(1)时间复杂度删除该链表节点题目链接
样例
给定 1->2->3->4，和节点 3，删除 3 之后，链表应该变为 1->2->4。
let deleteNode=(arr,n)=>{
let pos=arr.indexOf(n)
arr.splice(pos,1)
return arr
}
思路：因为js中没有指针和链表这两个概念，就当做数组来写，但复杂度不可能是o1。所以解题思路是找到索引，然后删除那个元素。
3.29
397.最长上升连续子序列
给定一个整数数组（下标从 0 到 n-1， n 表示整个数组的规模），请找出该数组中的最长上升连续子序列。（最长上升连续子序列可以定义为从右到左或从左到右的序列。）题目链接
let res=[],temp=[]
let longestIncreasingContinuousSubsequenc=function(arr,pos){
if(pos==arr.length-1) {
if(arr[pos]<arr[pos-1]){res.push(arr[pos])}
return res
}
for(let i=pos;i<arr.length;i++){
if(temp.length==0){
temp.push(arr[i])
return longestIncreasingContinuousSubsequenc(arr,i+1)
}
if(i>0&&i<arr.length-1&&arr[i-1]>arr[i]){
temp.push(arr[i])
}else{
if(temp.length>res.length){
res=temp
temp=[]
return longestIncreasingContinuousSubsequenc(arr,i)
}
}
}
return res
}
let arr=[5, 4, 2, 1, 9,8,7,6,5,4,3,2,9,5,2] // 9,8,7,6,5,4,3,2
console.log(longestIncreasingContinuousSubsequenc(arr,0))
思路：递归。存两个全局变量，比较数组长度，返回长度大的那个
3.30
407.加一
给定一个非负数，表示一个数字数组，在该数的基础上+1，返回一个新的数组。
该数字按照大小进行排列，最大的数在列表的最前面。题目链接
let temp=[]
let plusOne=(arr,pos)=>{
if(arr[pos]+1>=10){
arr[pos]=0
return plusOne(arr,pos-1)
}else{
if(pos<0){
arr.unshift(1)
}else{
arr[pos]+=1
}
return arr
}
}
let arr=[1,9,9,9]
console.log(plusOne(arr,arr.length-1)) //2000
思路：怎么想都是用递归逻辑比较清晰，值得注意的一点是，当pos小于0的时候，需要在数组头部unshift(1)。其实这道题可以偷个懒，就是先把数组变成数字加一再转换为数组lol。
3.31
408.二进制求和
给定两个二进制字符串，返回他们的和（用二进制表示）。相关链接
样例
a = 11
b = 1
返回 100
let addBinary=(a,b)=>{
let sum=(a+b+'').split('')
const len=sum.length
let i=len-1
while(i>0){
if(sum[i]>1){
if(sum[i]%2==0){
if(i>=1){
sum[i-1]=parseInt(sum[i-1])+1
}
sum[i]=0
}else{ //%2==1
sum[i-1]=parseInt(sum[i-1])+Math.floor(sum[i])
sum[i]=1
}
}
i--
}
if(sum[0]>1){
sum.unshift(Math.floor(sum[0]/2))
sum[1]=sum[1]%2
}
return sum.join('')
}
console.log(addBinary(111,10)) //1001
思路：先按照10进制相加，然后再遍历每位是否大于1，大于1则往前面一位加1，以此类推。
