leetcode%26算法 - 《前端总结》

做题总结
leetcode题目回顾&思路总结
经典题目
其他题目
————————————————————————-
位运算
搜索
- 二分搜索
排序
排序时间复杂度与稳定性
- 时间复杂度
- 稳定性
动态规划
- 最少硬币找零问题
贪心算法
- 【最少】硬币找零问题

做题总结

递归是由大到小的层层递进
dp是由小到大的逐渐积累
穷举是不断遍历获取所有结果

leetcode题目回顾&思路总结

undone：5
toReview：

经典题目

236.[树]Lowest Common Ancestor of a Binary Tree

解法1：

1663.[经典] Smallest String With A Given Numeric Value

解法1：

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getSmallestString = function(n, k) {
    var arr=new Array(n).fill(1)
    var all=k-n
    for(var i=n-1;i>=0;i--){
        if(all>25){
            arr[i]=26
            all=all-25
        }else{
            arr[i]=all+1
            break
        }
    }
    return arr.map(it=>String.fromCharCode(it+96)).join('')
};

解法2[待更快速]：

78.[回溯]Subsets

解法1：

回溯算法

var subsets = function(nums) {
    var res=[]
    function pan(tem=[],index=0,n){
        res.push(tem.slice(0))
        for(var i=index;i<n.length;i++){
            tem.push(n[i])
            pan(tem,i+1,n)
            tem.pop()
        }
    }
    pan([],0,nums)
    return res
};

解法2：

类似70题方法3

264.Ugly Number II

解法1：

var nthUglyNumber = function(n) {
    let multiplicationList = [2,3,5]
    let Answer = [1]
    let i2=0
    let i3=0
    let i5 = 0
    while (Answer.length<n){
        let m2 = Answer[i2]*2
        let m3 = Answer[i3]*3
        let m5 = Answer[i5]*5
        let newAnswer = Math.min(m2,m3,m5)
        if(newAnswer===m2){
            i2++
        }
        if(newAnswer===m3){
            i3++
        }
        if(newAnswer===m5){
            i5++
        }
        Answer.push(newAnswer)
    }
    return Answer[n-1]
};

202.Happy Number

解法1：

我们可以用 map来记录所有出现过的数字，然后每出现一个新数字，在 map中查找看是否存在，若不存在则加入表中，若存在则跳出循环，并且判断此数是否为1，若为1返回true，不为1返回false，

22.[经典]Generate Parentheses

解法1：

枚举法，根据递归列举所有情况

function generateParenthesis(n) {
  const res = [];
  function go(l, r, s) {  // l: left remaining, r: right remaining
    if (l > r) return;  // The number of '(' should be always >= ')'
    if (l === 0 && r === 0) {
      res.push(s);
      return;
    }
    if (l > 0) go(l - 1, r, s + '(');
    if (r > 0) go(l, r - 1, s + ')');
  }
  go(n, n, '');
  return res;
}

5??.[经典]Longest Palindromic Substring

解法1：

回文字符串的中心要不是一个字符‘aba’,要不是两个字符‘aabb’，所以根据给定字符串的单个字符和双字符进行递归判断即可

var longestPalindrome = function (s) {
  if (s.length < 2) { return s[0] || '' }
  var max = 0
  var res = ''
  function pan(x, y) {
    if (x < 0 || y > s.length - 1) { return }
    if (x === y) {
      if (max < 1) {
        max = 1
        res = s[x]
      }
      pan(x, x + 1)
      pan(x + 1, x + 1)
    }
    if (x === y - 1) {
      if (max < 2 && s[x] === s[y]) {
        max = 2
        res = s.slice(x, y + 1)
      }
      if (s[x] !== s[y]) { return }
    }
    if (x - 1 >= 0 && y + 1 <= s.length - 1 && s[x - 1] === s[y + 1]) {
      pan(x - 1, y + 1)
    } else {
      res = y - x + 1 > max ? s.slice(x, y + 1) : res
      max = y - x + 1 > max ? y - x + 1 : max
    }
  }
  pan(0, 0)
  return res
};

322[DP]. Coin Change

解法1：

动态规划+缓存

解法2（时间更快的解）：

var coinChange = function(coins, amount) {
  var dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let idx = 1; idx <= amount; idx++) {
    for (let i = 0; i < coins.length; i++) {
      var coin = coins[i];
      if (idx - coin < 0) {
        continue
      }
      dp[idx] = Math.min(dp[idx], dp[idx - coin] + 1)
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
};

518[DP]. Coin Change 2

解法1：

相比于322，这题求的是组合数，基准应该是coin而不是amount，这点是最大的差异
现算出只用一个coin的情况下0-amount的结果，在算出coin增加时的dp结果


var change = function(amount, coins) {
      var dp = new Array(amount + 1).fill(0)
  dp[0] = 1
  for (let i = 0; i < coins.length; i++) {
    const coin = coins[i];
    for (let idx = 0; idx <=amount; idx++) {
      if (idx - coin < 0) { continue }
      dp[idx] = dp[idx] + dp[idx - coin]
    }
  }
  return dp[amount]
};

64[DP]. Minimum Path Sum

解法1(时间不够快)：

动态规划+缓存


var minPathSum = function (grid) {
  var map = new Array(grid.length)
  map[0] =[grid[0][0]]
  function pan(x, y) {
    if(!map[x]){map[x]=[]}
    if (map[x][y]) { return map[x][y] }
    if (x === 0 && y === 0) {
      console.log(x, y, map[x][y])
      return grid[x][y]
    }
    if (x === 0 && y !== 0) {
      map[x][y] = grid[x][y] + pan(x, y - 1)
      console.log(x, y, map[x][y])
      return map[x][y]
    }
    if (y === 0 && x !== 0) {
      map[x][y] = grid[x][y] + pan(x - 1, y)
      console.log(x, y, map[x][y])
      return map[x][y]
    }
    map[x][y] = grid[x][y] +
      Math.min(pan(x, y - 1), pan(x - 1, y))
    console.log(x, y, map[x][y])
    return map[x][y]
  }
  var res = pan(grid.length-1, grid[0].length-1)
  return res
};
console.log(minPathSum(
  [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
));

解法2：

动态规划+类似缓存
想比于方法一，减少了重复计算，提高算力

var minPathSum = function(grid) {
    if(grid.length === 0){
        return 0;
    }
    let m=grid.length, n = grid[0].length;
    for(let i = 1; i < n; i++){
        grid[0][i] += grid[0][i-1];
    }
    for(let i = 1; i < m; i++){
        grid[i][0] += grid[i-1][0];
    }
    for(let i = 1; i < m; i++){
        for(let j = 1; j < n; j++){
            grid[i][j]+= Math.min(grid[i-1][j], grid[i][j-1]);
        }
    }
    return grid[m-1][n-1];
};

70.[经典]Climbing Stairs

解法1：递归

爬楼梯直接思路递归法，登顶的最后一步有两种走法，也就是1步，后者2步。
所以可以得出公式f(n) = f(n-1) + f(n-2).


var ClimbingStairs {
   var  climbStairsWithRecursion(n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else {
            return climbStairsWithRecursion(n - 1) + climbStairsWithRecursion(n - 2);
        }
    }
}

解法2：动态规划

var climbStairs = function(n) {
    if(n==0 || n==1 || n==2) return n;
    var arr=[];
     arr[0]=1;
     arr[1]=2;
    for(var i=2 ; i< n;i++){
        arr[i]=arr[i-1]+arr[i-2];
    }
    return arr[n-1];
};

解法3

列举

let climbStairs = function (n) {
  const a = [1, 2]
  let res = 0
  // for (i = 1; i <= n; i++) {
  //   a.push(i)
  // }
  function b(arr, index) {
    for (let id = 0; id < 2; id++) {
      let attTemp = [...arr]
      attTemp.push(a[id])
      let sum = attTemp.reduce((t, num) => t + num)
      sum === n && console.log(attTemp);
      if (sum === n) {
        res++
        return
      }
      else if (sum > n) { return }
      b(attTemp, id)
    }
  }
  b([], 0)
  console.log(res);
  return res
};
climbStairs(5)

46. [回溯]Permutations

解法1：

其他题目

1:Two Sum

解法1：

双重循环，找到两数之和等于目标数

解法2：

空间换时间，创建map，key为数字，value为index，每次只需判断map[目标数-当前数]的值是否存在即可

2[链表]Add Two Numbers

解法1：

常规链表遍历

3.Longest Substring Without Repeating Characters

解法1：

创建map，记录每一个字母的index，当map已有记录时，说明有重复字母，记录此时的长度，并与此前记录的最大值作比较。若一直无重复，则返回整个字符串长度

7.Reverse Integer

解法1：

变成数组，反转去零。负数单独处理。

9.Palindrome Number

解法1：

变成字符串，split，反转，join，对比差异

11.Container With Most Water

解法1：

双重循环，逐一计算面积，取最大值。

解法2：

var maxArea = function(height) {
  let i = 0;
  let j = height.length - 1;
  let max = 0
  while(i<j) {
    let min = Math.min(height[i], height[j])
    max = Math.max(((j-i) * min), max)
    if (height[i] > height[j]) {
      j--
    } else {
      i++
    }
  }
  return max
};

双指针，先让index之差最大，计算面积，再取两者之中较高的，移动另一个（如果取低的，那么下次计算出的面积会在这次面积之内），相当于双指针同时变化，时间复杂度较低。

13.Roman to Integer

14.Longest Common Prefix

解法1：

应该想到：先比较数组中每个元素的第一位，如果都相同，则开始比较每个元素的第二位，依次类推；直到出现一个元素的某一位不在其他元素中都出现，此时返回这个元素之前的值

(非题目解法)：

创建map，映射数组首元素每个字母，过滤出数量是数组长度的元素，根据数组首元素遍历选出连续字符串

var temp = (arr) => {
  var a = {}
  for (var i = 0; i < arr[0].length; i++) {
    a[arr[0][i]] = 1
  }
  arr.slice(1, Infinity).forEach(it => {
    for (var i = 0; i < it.length; i++) {
      a[it[i]]++
    }
  });
  Object.keys(a).forEach(it => {
    if (a[it] !== arr.length) {
      delete a[it]
    }
  })
  var l = 0, max = 0, targetIndex = 0, targetMax = 0, isStart = true
  for (var i = 0; i < arr[0].length; i++) {
    if (a[arr[0][i]] === arr.length) {
      if (isStart) {
        l = i
        max++
        isStart = false
      } else {
        max++
      }
    } else {
      targetIndex = max > targetMax ? l : targetIndex
      targetMax = max > targetMax ? max : targetMax
      isStart = true
      max = 0
    }
  }
  return arr.length !== 1 ? arr[0].slice(targetIndex, targetIndex + targetMax) : arr[0]
}
console.log(temp(['a']))

19.[链表]Remove Nth Node From End of List

解法1：

根据n来遍历找到对应节点，做删除处理

20.Valid Parentheses

解法1：

创建栈，遇到左符号就push，遇到匹配的右符号就pop，完成后看栈是否为空

21.[链表经典递归]Merge Two Sorted Lists

解法1：


var mergeTwoLists = function(l1, l2) {
     if(!l1){
         return l2
     }
     else if(!l2){
         return l1
     }
      if(l1.val<l2.val){
          l1.next=mergeTwoLists(l1.next,l2)
          return l1
      }
      else{
          l2.next=mergeTwoLists(l2.next,l1)
          return l2
      }
};

23.[链表]Merge k Sorted Lists

解法1：

遍历列表，取出全部数值排序，创建新的链表进行填充

解法2：

function mergeLists(a, b) {
    const dummy = new ListNode(0);
    let temp = dummy;
     while (a !== null && b !== null) {
         if (a.val < b.val) {
             temp.next = a;
             a = a.next;
         } else {
             temp.next = b;
             b = b.next;
         }
         temp = temp.next;
     }
    if (a !== null) {
        temp.next = a;
    }
    if (b !== null) {
        temp.next = b;
    }
    return dummy.next;
}
var mergeKLists = function(lists) {
    if (lists.length === 0 ) {
        return null;
    }
    while(lists.length > 1) {
        let a= lists.shift()
        let b = lists.shift()
        let m = mergeLists(a,b)
        lists.push(m)
    }
    return lists[0];
}

24.[链表]Swap Nodes in Pairs

解法1：

递归思路值得研究

26.Remove Duplicates from Sorted Array

解法1：

按照索引依次去重

27.Remove Element

解法1：

按照索引依次去重

解法2：

创建map取keys

28.Implement strStr()

easy

33.Search in Rotated Sorted Array

easy

34.Find First and Last Position of Element in Sorted Array

easy

35.Search Insert Position

解法1：

遍历一次，判断左侧数值、自身数值、右侧数值的关系

36？.Valid Sudoku

39.Combination Sum

解法1：

给定index，产生tempArr，递归，当sum(tempArr)小于目标时，继续递归，大于目标时，结束。

42？.Trapping Rain Water

43.Multiply Strings

解法1：

大数相乘，转化为字符串，reverse，诸位相乘，创建res[],计算结果

48.Rotate Image

解法1：

根据index的关系变化创建数组进行操作。

49.Group Anagrams

解法1：

创建map，遍历元素，记录每个元素sort后的字符串。遍历map，

50.Pow(x, n)

easy

53.Maximum Subarray

解法1：

遍历一遍，每一步的sum值如果是正数，就与max比较。如果是负数就会重置（因为如果是负数，则意味着上次的sum更大，或者数组项都是负数）
然后再遍历一遍，看单个项中谁最大，与max比较。

58.Length of Last Word

easy

61.[链表]Rotate List

解法1：

根据k值找到最终的头，根据头部位置重新组合链表

62.Unique Paths

解法1：

只要是走到边缘，那么一定只有一种解法。基于这个事实，递归，利用[剩余x,剩余y]数组递归，直至到x=1或者y=1.

63.Unique Paths II

与62相似，遇到障碍物就return

66.Plus One

解法1：

从末尾加1，查看是否大于10，是的话诸位向上一位进1.

67.Add Binary

二进制诸位相加

69.Sqrt(x)

二分法寻找 n*n===x 的最接近值

71?.Simplify Path

var simplifyPath = function(path) {
    let stack = [];
    path = path.split('/');
    for (let i=0;i<path.length;i++) {
        if (path[i]=='.' || path[i]=='') continue;
        if (path[i]=='..') stack.pop();
        else stack.push(path[i]);
    }
    return '/'+stack.join('/');
};

75.Sort Colors

解法1：

因为只有这三种颜色（三个元素），所以只需要记录三种元素出现的次数，再根据次数重置数组即可

80.Remove Duplicates from Sorted Array II

删除排序数组中的重复项，重复次数最多5次

解法1：

index从2开始，如果arr[index]===arr[index+2]，原地删除数组中的这一项

解法2：

类似75题解法1

82?.[链表]Remove Duplicates from Sorted List II

83.[链表]Remove Duplicates from Sorted List

easy

88.Merge Sorted Array

解法1：

从两数组对应的结束位置向前遍历，谁大谁填入新数组的尾端

92.[链表]Reverse Linked List II

按部就班

94.[树中序遍历]Binary Tree Inorder Traversal

98.[树]Validate Binary Search Tree

左侧所有节点都比本节点小的，xxx,是bst

解法1：

var inorderTraversal = function (root) {
  var res = true
  function pan(node, leftMin = -Infinity, rightMax = Infinity) {
    if (!node) { return }
    if (node.left) {
      if (node.val > node.left.val && node.left.val > leftMin) {
        pan(node.left, leftMin || -Infinity, node.val)
      } else {
        res = false
      }
    }
    if (node.right) {
      if (node.val < node.right.val && node.right.val < rightMax) {
        pan(node.right, node.val, rightMax || Infinity)
      } else {
        res = false
      }
    }
  }
  pan(root)
  return res
};

100.[树]Same Tree

101?.[树]Symmetric Tree

100题的转换

102.[树]Binary Tree Level Order Traversal

解法1：

根据树的深度对应数组对应的index，这样可以用深度遍历

解法2：

广度遍历

103.[树]Binary Tree Zigzag Level Order Traversal

解法1：

深度遍历的时候根据树的深度做数组的push或unShift处理

104.[树]Maximum Depth of Binary Tree

105.[树]Construct Binary Tree from Preorder and Inorder Traversal

根据先中后序遍历在数组中的位置，进行处理

106.[树]Construct Binary Tree from Inorder and Postorder Traversal

类似105

107.[树]Binary Tree Level Order Traversal II

类似102

108.[树]Convert Sorted Array to Binary Search Tree

解法1：

找到数组中间元素，作为子树的root，递归左右两部分

109.[树]Convert Sorted List to Binary Search Tree

类似108

110?.[树]Balanced Binary Tree

没搞懂题目意思

111.[树]Minimum Depth of Binary Tree

easy,遍历即可

112.[树]Path Sum

easy

118.Pascal’s Triangle

解法1：

初始值为[1],下一级的length为上一级+1，当下一级index=0、length-1时为1，其他元素根据上一级的对应关系得出

120.[动态规划解法]Triangle

解法1：

递归列出所有可能，选出最短路径

解法2：

动态规划+缓存

125.Valid Palindrome

解法1：

split,toLowerCase,reverse,join后对比

129.[树]Sum Root to Leaf Numbers

相对easy

136.Single Number

easy

137.Single Number II

easy

141.[链表]Linked List Cycle

解法1：

var hasCycle = function(head) {
    let slow = head, fast = head
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if (slow === fast) { return true }
    }
    return false
};

142.[链表]Linked List Cycle II

解法1：

var detectCycle = function(head) {
    if(!head||!head.next){return null}
    var slow = head, fast = head
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if (slow == fast) {
            if(head!=slow){
              var dummy=head;
              while(dummy!=slow){
                dummy=dummy.next;
                slow=slow.next;
              }
              return dummy
            }
            return slow}
    }
    return null
};

143.[链表]Reorder List

解法1：

这道链表重排序问题可以拆分为以下三个小问题：
1. 使用快慢指针来找到链表的中点，并将链表从中点处断开，形成两个独立的链表。
2. 将第二个链翻转。
3. 将第二个链表的元素间隔地插入第一个链表中。

144.[树]Binary Tree Preorder Traversal

先序遍历

145?.[树]Binary Tree Postorder Traversal

后序遍历

148.[链表]Sort List

解法1：

遍历链表，取出数值，重新构建

151.Reverse Words in a String

easy

153.Find Minimum in Rotated Sorted Array

easy

154.Find Minimum in Rotated Sorted Array II

easy

155?.[实现栈]Min Stack

160.[链表]Intersection of Two Linked Lists

解法1：

先算出两链表长度之差，再对其数组同时进行遍历

167.Two Sum II - Input array is sorted

解法1：

二分法寻找匹配组合

168.Excel Sheet Column Title

解法1：

26进制对应26字母（十进制转26进制），依次相加（利用String.fromCharCode）

169.Majority Element

解法1：

利用map

171.Excel Sheet Column Number

168反操作，26进制转10进制

189.Rotate Array

easy

191.Number of 1 Bits

解法1：

转二进制，过程中判断每一位的数值

203.[链表]Remove Linked List Elements

解法1：

用递归清晰一点

205.Isomorphic Strings

解法1：

创建2个map，相同index时判断map里重复的字母index是否相同

var isIsomorphic = function(s, t) {
    if (s.length !== t.length) {
        return false;
    }
    if (s === t) {
        return true;
    }
    const obj1 = {};
    const obj2 = {};
    for(let i = 0; i < s.length; i++) {
        const letter = s[i];
        const tLetter = t[i];
        if (!obj2[tLetter]) {
            obj2[tLetter] = letter;
        }
        if (!obj1[letter]) {
            obj1[letter] = tLetter;
        }
        if (obj1[letter] !== tLetter || obj2[tLetter] !== letter) {
            return false;
        }
    }
    return true;
};

206.[链表]Reverse Linked List

215.Kth Largest Element in an Array

解法1：

数组排序

217.Contains Duplicate

easy

219.Contains Duplicate II

222.[树]Count Complete Tree Nodes

225？.[实现队列]Implement Stack using Queues

226.[树]Invert Binary Tree

231.Power of Two

解法1：

数字不断除2，除到小于等于1，看是否等于1

232.Implement Queue using Stacks

实现队列

234.[链表]Palindrome Linked List

easy

235.[树]Lowest Common Ancestor of a Binary Search Tree

解法1：

根据BST找位置关系

237.[链表]Delete Node in a Linked List

257.[树]Binary Tree Paths

easy

258.Add Digits

easy

260.Single Number III

easy

263.Ugly Number

解法1：

/**
 * @param {number} num
 * @return {boolean}
 */
var isUgly = function(num) {
    if(num==0){
      return false;
    }
      n=num;
    while(n%2==0){
        n=n/2;
    }
    while(n%3==0){
        n=n/3;
    }
    while(n%5==0){
        n=n/5;
    }
    if(n==1){
        return true;
    }
    else{
        return false;
    }
};

268.Missing Number

解法1：

var missingNumber = function(nums) {
    // construct array of size n+1, to leave a spot for the missing element.
    // Assign each val to -1 so we can see which position was not filled
    // O(n)
    const res = new Array(nums.length+1).fill(-1);
    // "sort" the elements by assigning to the array based on val
    // O(n)
    for(const num of nums) {
        res[num] = num;
    }
    // the remaining -1 index is the missing value
    // O(n-1)
    return res.indexOf(-1);
};

283.Move Zeroes

解法1：

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    var count=0;
    for(var i=0;i<nums.length;i++){
        if(nums[i]!=0){
            nums[count]=nums[i]
            count++
        }
    }
    for(var i=count;i<nums.length;i++){
        nums.splice(i,1,0)
    }
    return nums
};

287.Find the Duplicate Number

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    var arr=new Array(nums.length-1);
    for(var i=0;i<nums.length;i++){
        if(arr[nums[i]]==1){
            return nums[i]
        }
        else {arr[nums[i]]=1;
        }
    }
};

326.Power of Three

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfThree = function(n) {
    if(n === 0) return false 
    while(n % 3 === 0){
        n = n / 3 
    }
    return n === 1 ? true : false 
};

328.[链表]Odd Even Linked List

按部就班

338.[看不懂] Counting Bits

解法1：

342. Power of Four

类似326

344. Reverse String

easy

345. Reverse Vowels of a String

解法1：

一遍扫描所有字符，记录所有元音字母和它们出现的位置到一个数组中；再扫描这个数组，将元音字母逆序填回原来的字符串相应位置。

解法2：

维护两个指针分别从字符串头和尾扫描，每次交换两个指针扫到的元音字母，于是只需遍历一遍字符串就可以完成元音字母逆序。

349. Intersection of Two Arrays

解法1：

分别遍历，第一次遍历创建map记录每个元素，设map[x]=1,二次遍历查map

350. Intersection of Two Arrays II

类似349

367. Valid Perfect Square

var isPerfectSquare = function(num) {
    for(i=1;!((i*i<num)&&((i+1)*(i+1)>num));i++){
        if(i*i==num){
        return true
        }
        else if(i*i>num){
          i=Math.floor(i*0.5);
        }
        else if(i*i<num){
          i=i*2;
        }
     }
    return false
};

383. Ransom Note

true

var canConstruct = function(ransomNote, magazine) {
    let arr = [];
  for(let i = 0; i< ransomNote.length; i++){
      let index = magazine.indexOf(ransomNote[i]);
      if(index === -1) return false;
       magazine = magazine.substring(0, index) + magazine.substring(index + 1);
  }
return true;
};

387. First Unique Character in a String

解法1：

遍历map，再遍历看哪个元素的map值是1

389. Find the Difference

解法1：

t做元素map，遍历s减去map里的值，剩下的就是结果

392. Is Subsequence

解法1：

双指针，遍历一次

404.[树] Sum of Left Leaves

easy

409. [经典]Longest Palindrome

解法1：

412. Fizz Buzz
easy

414?. Third Maximum Number

415. Add Strings

大数相加

429.[树]N-ary Tree Level Order Traversal

n叉树的遍历，可分为深度遍历（按照树的深度），也可以广度遍历

441. Arranging Coins

i*(i+1)/2

/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function(n) {
    if(n==1){return 1}
    if(n==0){return 0}
    for(i=2;;i++){
        if((1+i)*i*0.5>n){
            break;
        }
    }
    return i-1
};

442？. Find All Duplicates in an Array

445. Add Two Numbers II

类似415

448. Find All Numbers Disappeared in an Array

创建一个数组，元素作为index push，然后看那些们没有元素，就是缺少的

451？. Sort Characters By Frequency

453. Minimum Moves to Equal Array Elements

每次将n-1个元素+1，最少几次所有元素相同

解法1：

数组排序，计算每个元素与min值的差距，累计差距

461？. Hamming Distance

462. Minimum Moves to Equal Array Elements II

解法1：

类似453，取中位数

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function(nums) {
    nums.sort((a, b) => a-b);
    const med = nums[Math.floor(nums.length / 2)];
    let moves = 0;
    for (let i = 0; i < nums.length; i++) {
        const diff = Math.abs(nums[i] - med);
        moves += diff;
    }
    return moves;
};

476. Number Complement

easy

485. Max Consecutive Ones

easy

500. Keyboard Row

easy

504. Base 7

返回七进制数

110（10）-> 215（7）

507. Perfect Number

easy

509. Fibonacci Number

解法1：

/**
 * @param {number} n
 * @return {number}
 */
let results = {}
var fib = function(n) {
   if(results[n]) {
     return results[n]
   }
   if(n < 2) {
     return n
   }
   let res = fib(n - 1) + fib(n - 2) 
    results[n] = res
   return res
};

513.[树] Find Bottom Left Tree Value

解法1：

遍历，根据分支向左偏移的count寻找节点
也可中序遍历，根据deep，找到最深deep的第一个遍历节点

520. Detect Capital

easy

540. Single Element in a Sorted Array

easy

557. Reverse Words in a String III

easy

559. [树]Maximum Depth of N-ary Tree

easy

561?.[经典] Array Partition I

575. Distribute Candies

easy

589. [树] N-ary Tree Preorder Traversal

类似429

590. [树] N-ary Tree Postorder Traversal

类似429

599. Minimum Index Sum of Two Lists

easy

606. [树] Construct String from Binary Tree

基于遍历

617. [树] Merge Two Binary Trees

622?.[实现循环队列] Design Circular Queue

633. [较为经典]Sum of Square Numbers

解法1：（可以用二分法改进）

/**
 * @param {number} c
 * @return {boolean}
 */
var judgeSquareSum = function(c) {
    var c1=Math.sqrt(c*0.5);
    var c2=Math.floor(Math.sqrt(c));
    for(var i=0;i<=c1;i++){
        for(var s=c2;s>=c1;s--){
            if(i*i+s*s==c){
                return true;
            }
            else if(i*i+s*s>c){
            }
            else{
                break;
            }
        }
    }
    return false
};

解法2：

/**
 * @param {number} c
 * @return {boolean}
 */
var judgeSquareSum = function (c) {
    if (c < 0) return false;
    let i = 0;
    let j = Math.trunc(Math.sqrt(c));
    while (i <= j) {
        let powSum = i * i + j * j;
        if (powSum === c) {
            return true
        } else if (powSum > c) {
            j--
        } else {
            i++;
        }
    }
    return false;
};

637.[树] Average of Levels in Binary Tree

解法1：

遍历完树的深度，再计算

692. [经典]Top K Frequent Words

解法1：

/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 */
var topKFrequent = function(words, k) { 
    const freq = words.reduce((acc,curr)=> ( (acc.hasOwnProperty(curr))? acc[curr] += 1 : acc[curr] = 1 ,acc),{});
    const sortedWords = Object.keys(freq).sort((a, b) => {
        if (freq[a] > freq[b]) {
            return -1
        } else if (freq[a] < freq[b]) {
            return 1
        }
        return a < b ? -1 : 1
        // const n = freq[b] - freq[a];
        // if (n !== 0) return n;
        // return a > b ? 1 : -1
    })
    return sortedWords.slice(0,k);
    /* 
        create a hashTable where we can store each
        word and how many times it repeats,
        iterate through the hashTable and find k greatest
        numbers and sort them in alphabetic order
    */
//     const map = new Map();
//     for (let i = 0; i < words.length; i ++) {
//         if (!map.has(words[i])) map.set(words[i], 0);
//         map.set(words[i], map.get(words[i]) + 1);
//     }
//     const mostFrequent = [...map.keys()].sort((a, b) => {
//         let n = map.get(b) - map.get(a);
//         if (n !== 0) return n;
//         return a > b ? 1 : -1
//     });
//     console.log( mostFrequent )
//     return mostFrequent.slice(0, k);
};

693. Binary Number with Alternating Bits

easy

700.[树]Search in a Binary Search Tree

easy

701.[树] Insert into a Binary Search Tree

easy

703？. [实现什么东东]Kth Largest Element in a Stream

704. Binary Search

easy

707？.[实现链表] Design Linked List

709. To Lower Case

easy

724. Find Pivot Index

错误解法（但可以参考做法）

var pivotIndex = function (nums) {
  var l = -1
  var lSum = 0
  var r = nums.length
  var rSum = 0
  if (r === 0) { return -1 }
  while (l != r) {
    if (lSum >= rSum) {
      r--
      rSum = rSum + nums[r]
    } else {
      l++
      lSum = lSum + nums[l]
    }
  }
  if (lSum == rSum) {
    console.log(l);
    return l
  }
  console.log(-1);
  return -1
};

正确解法

var pivotIndex = function(nums) {
    let left = 0
    let right = nums.reduce((a, b) => a + b, 0)
    for(let i=0; i<nums.length; i++){
        right -= nums[i]
        if(left === right) return i
        left += nums[i]
    }
    return -1
};

728. Self Dividing Numbers

解法核心片段

 while(num1>=1){           
   if(num%(num1%10)!=0){
      return false;
   }
           num1=(num1-num1%10)/10;
   }
  return true;

747. Largest Number At Least Twice of Others

easy

771. Jewels and Stones

easy

783.[树] Minimum Distance Between BST Nodes

解法1：

796. Rotate String

easy

830. Positions of Large Groups

解法1：

/**
 * @param {string} s
 * @return {number[][]}
 */
var largeGroupPositions = function(s) {
  var start=true
  var res=[]
  var item=[]
  for(var i=0;i<s.length;i++){
      if(start){
          if (s[i] == s[i + 1] && s[i] == s[i + 2]) {
              item.push(i)
              // if(s.length==3){
              //     item.push(i+2)
              //     return [item]
              // }
              start=false
              i=i+1
          }
      }else{
          if(s[i]!=s[i+1]){
              item.push(i)
              res.push(item)
              item=[]
              start=true
          }
      }
  }
  return res
};

867. Transpose Matrix

解法1：

/**
 * @param {number[][]} A
 * @return {number[][]}
 */
var transpose = function(a) {
    return a[0].map(function(item1,index1){
             return a.map(function(item){
                 return item[index1]
             })
        })
};

868. Binary Gap

解法1：

双重循环计算每个起始位的gap，算出最大值

解法2（有待更好的解法）：

872.[树] Leaf-Similar Trees

基于遍历

876.[链表] Middle of the Linked List

889.[树] Construct Binary Tree from Preorder and Postorder Traversal

类似105

905. Sort Array By Parity

easy

908. [经典]Smallest Range I

解法1：


const smallestRangeI = (A, K) => {
  let leftMax = Number.MIN_SAFE_INTEGER, // 左区间最大值
      rightMax = Number.MAX_SAFE_INTEGER; // 右区间最小值
  for (let i = 0; i < A.length; i++) {
    leftMax = Math.max(leftMax, A[i] - K);
    rightMax = Math.min(rightMax, A[i] + K);
  }
  return rightMax > leftMax ? 0 : leftMax - rightMax;
};

922. Sort Array By Parity II

easy

938.[树] Range Sum of BST

根据BST的特性进行递归

961. N-Repeated Element in Size 2N Array

easy

965.[树]Univalued Binary Tree

解法1：

判断自身和左右节点是否相等，是的话返回量子节点的递归结果，不等返回false

977. Squares of a Sorted Array

解法1：

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    const result = new Array(nums.length).fill(0);
    let start = 0, end = nums.length - 1;
    let index = nums.length - 1;
    while(start <= end) {
        const startNum = nums[start], endNum = nums[end];
        if(Math.abs(startNum) > Math.abs(endNum)) {
            result[index] = Math.pow(startNum, 2);    
            start++;
        }
        else {
            result[index] = Math.pow(endNum, 2);    
            end--;            
        }
        index--;
    }

989. Add to Array-Form of Integer

解法1：

var addToArrayForm = function(num, k) {
    return (BigInt(num.join(''))+BigInt(k)).toString().split('')
};

993.[树] Cousins in Binary Tree

解法1：

当两节点深度相同且父节点不是同一节点时，为true
遍历每个节点，当左右节点为x、y时，返回true
否则查看遍历结果，看x所在深度内有无y

1002. Find Common Characters

解法1：

var commonChars = function(A) {
    let res = A[0].split('')
    for (string of A) {
        let localString = string.split('')
        res = res.filter(s => {
            let idx = localString.indexOf(s)
            if (idx === -1) return false
            localString[idx] = NaN
            return true
        })
    }
    return res
};

1008.[树] Construct Binary Search Tree from Preorder Traversal

1022.[树]Sum of Root To Leaf Binary Numbers

基于遍历

1047. Remove All Adjacent Duplicates In String

easy

1089. Duplicate Zeros

easy

1108. Defanging an IP Address

easy

1122.[较经典] Relative Sort Array

————————————————————————-

位运算

左移 <<

10 << 1 // -> 20

左移就是将二进制全部往左移动，10 在二进制中表示为 1010 ，左移一位后变成 10100 ，转换为十进制也就是 20

右移 >>

10 >> 1 // -> 5

算数右移就是将二进制全部往右移动并去除多余的右边，10 在二进制中表示为 1010 ，右移一位后变成 101 ，转换为十进制也就是 5

右移很好用，比如可以用在二分算法中取中间值

13 >> 1 // -> 6

按位操作

按位与 &

每一位都为 1，结果才为 1

8 & 7 // -> 0
// 1000 & 0111 -> 0000 -> 0

按位或 |

其中一位为 1，结果就是 1

8 | 7 // -> 15
// 1000 | 0111 -> 1111 -> 15

按位非 ~

其中一位为 1，结果就是 1

~1的计算步骤：
将1(这里叫：原码)转二进制 ＝ 00000001
按位取反 ＝ 11111110
发现符号位(即最高位)为1(表示负数)，将除符号位之外的其他数字取反 ＝ 10000001
末位加1取其补码 ＝ 10000010
转换回十进制 ＝ -2

负数：补码(x) = -x - 1，正数：补码(x) = x

按位异或 ^

每一位都不同，结果才为 1

8 ^ 7 // -> 15
8 ^ 8 // -> 0
// 1000 ^ 0111 -> 1111 -> 15
// 1000 ^ 1000 -> 0000 -> 0

从以上代码中可以发现按位异或就是不进位加法

面试题：两个数不使用四则运算得出和

这道题中可以按位异或，因为按位异或就是不进位加法，8 ^ 8 = 0 如果进位了，就是 16 了，所以我们只需要将两个数进行异或操作，然后进位。那么也就是说两个二进制都是 1 的位置，左边应该有一个进位 1，所以可以得出以下公式 a + b = (a ^ b) + ((a & b) << 1) ，然后通过迭代的方式模拟加法

function sum(a, b) {
    if (a == 0) return b
    if (b == 0) return a
    let newA = a ^ b
    let newB = (a & b) << 1
    return sum(newA, newB)
}

搜索

二分搜索

const binarySearch = function (array, item) {
    var low = 0, //{2}
        high = array.length - 1, //{3}
        mid, element;
    while (low <= high) { //{4}
        mid = Math.floor((low + high) / 2); //{5}
        element = array[mid]; //{6}
        if (element < item) { //{7}
            low = mid + 1; //{8}
        } else if (element > item) { //{9}
            high = mid - 1; //{10}
        } else {
            return mid; //{11}
        }
    }
    return -1; //{12}
};
var arr = [0, 1, 3, 4, 5, 6, 8, 9].sort()
console.log(arr, binarySearch(arr, 3));

排序

冒泡排序

每个循环逐渐把大的放后面

const array = [1, 3, 2, 6, 4, 5, 9, 8, 7];
const sort = (arr) => {
  let result = [...arr];
  let temp;
  for(let i = 0; i < result.length - 1; i++){
    for(let j = 0; j < result.length - 1 -i; j++){
      if(result[j] > result[j + 1]){
        temp = result[j];
        result[j] = result[j + 1];
        result[j + 1] = temp;
      }
    }
  }
  return result;
}
const newArr = sort(array);
console.log(newArr); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + 1 ，去掉常数项以后得出时间复杂度是 O(n * n)

插入排序

每个循环逐渐把小的放前面
插入排序的原理如下。第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。
leetcode%26算法 - 图143
以下是实现该算法的代码

const array = [1, 3, 2, 6, 4, 5, 9, 8, 7];
const sort = (arr) => {
  let result = [...arr];
  let temp;
  for(let i = 0; i < result.length; i++){
    let j = i;
    while(result[j - 1] > result[j] && j>=0){
      temp = result[j - 1];
      result[j - 1] = result[j];
      result[j] = temp;
      j--;
    }
  }
  return result;
}
const newArr = sort(array);
console.log(newArr); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + 1 ，去掉常数项以后得出时间复杂度是 O(n * n)

选择排序

也是每个循环逐渐把小的数放前面，与插排不同的是，插排每个循环都可能调换目标数位置（逐渐前移），选排是每个循环确定一个循环内最小数，循环结束后前移。

选择排序的原理如下。遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。
leetcode%26算法 - 图144
以下是实现该算法的代码

function selection(array) {
  if (!checkArray(array)) return
  for (let i = 0; i < array.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      minIndex = array[j] < array[minIndex] ? j : minIndex;
    }
    swap(array, i, minIndex);
  }
  return array;
}
var example=[8,94,15,88,55,76,21,39];
function selectSort(arr){
    var len=arr.length;
    var minIndex,temp;
    console.time('选择排序耗时')；
    for(i=0;i<len-1;i++){
        minIndex=i;
        for(j=i+1;j<len;j++){
            if(arr[j]<arr[minIndex]){
                minIndex=j;
            }
        }
    temp=arr[i];
    arr[i]=arr[minIndex];
    arr[minIndex]=temp;
    }
    console.timeEnd('选择排序耗时');
    return arr;
}
console.log(selectSort(example));

该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + 1 ，去掉常数项以后得出时间复杂度是 O(n * n)

希尔排序

归并排序

我们现在写一个方法来得到a跟b组合后的有序数组，这个方法很简单，用两个指针i,j分别指向两个数组，然后开始遍历，比较a[i]和a[j]的大小，将小的那个放入新的有序数组。当任意一个数组遍历完，循环结束，将剩下的值全部放入新的有序数组:

const merge = (arr1, arr2) => {
  const length1 = arr1.length;
  const length2 = arr2.length;
  const newArr = [];
  let i = 0;
  let j = 0;
  while(i < length1 && j < length2) {
    if(arr1[i] <= arr2[j]) {
      newArr.push(arr1[i]);
      i++;
    } else {
      newArr.push(arr2[j]);
      j++;
    }
  }
  // arr2还剩一些
  if(i === length1 && j < length2) {
    while(j < length2) {
      newArr.push(arr2[j]);
      j++;
    }
  }
  // arr1还剩一些
  if(j === length2 && i < length1) {
    while(i < length1) {
      newArr.push(arr1[i]);
      i++;
    }
  }
  return newArr;
}
// 测试一下
const a = [1 ,2, 6, 8];
const b = [3, 4, 9];
const result = merge(a, b);
console.log(result);   //  [1, 2, 3, 4, 6, 8, 9]

可以看出，如果a,b自身是有序数组，得到的结果就是有序数组。

然后我们递归的将待排序数组分成左右两个数组，一直分到数组只含有一个元素为止，因为数组只含有一个元素，我们就可以认为他是有序的。

const mergeSort = (arr) => {
  const length = arr.length;
  if(length <= 1) {
    return arr;
  }
  const middle = Math.floor(length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}
// 测试一下
const a = [2, 1, 3, 6, 4, 5, 9, 8, 7];
// 测试下
let result = mergeSort(a);
console.log(result);   // [1, 2, 3, 4, 5, 6, 7, 8, 9]

如[3,2,6,4,7,5,9]的数组，会像如图分组，直至每组只有一个数，每次每组后归并可以得到一个组内有序的小组，再向上层归并，最终得到有序数组。

快速排序

以某一基准值为基准（一般是第一个或者最后一个数，这里以最后一个数为例），在数组前后各建立一个指针（l,r）,当l<r时，先进行l—操作，找到第一个大于基准的数，找到后再r—，找到第一个大于基准的数，两个数调换位置，这样，l的左侧和r的右侧都分别小于基准值和大于基准值。直到l=r，若l位置的值大于基准值，则与基准值换位置。此时，l=r这个位置及其左边都小于基准值，右边都大于基准值。再进行递归迭代。

const quickSort = (array) => {
    const sort = (arr, left = 0, right = arr.length - 1) => {
        if (left >= right) {//如果左边的索引大于等于右边的索引说明整理完毕
            return
        }
        let i = left
        let j = right
        const baseVal = arr[j] // 取无序数组最后一个数为基准值
        while (i < j) {      //把所有比基准值小的数放在左边大的数放在右边
            while (i < j && arr[i] <= baseVal) { //找到一个比基准值大的数交换
                i++
            }
            arr[j] = arr[i] // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
            while (j > i && arr[j] >= baseVal) { //找到一个比基准值小的数交换
                j--
            }
            arr[i] = arr[j] // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
        }
        arr[j] = baseVal // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
        sort(arr, left, j - 1) // 将左边的无序数组重复上面的操作
        sort(arr, j + 1, right) // 将右边的无序数组重复上面的操作
    }
    const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组
    sort(newArr)
    return newArr
}

堆排序

排序时间复杂度与稳定性

时间复杂度

稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

动态规划

用动态规划解决问题时，要遵循三个重要步骤：
(1) 定义子问题；
(2) 实现要反复执行而解决子问题的部分（这一步要参考前一节讨论的递归的步骤）；
(3) 识别并求解出边界条件。
能用动态规划解决的一些著名的问题如下。

最少硬币找零问题

function MinCoinChange(coins) {
    var coins = coins;
    var cache = {};
    this.makeChange = function (amount) {
        var me = this;
        if (!amount) {
            return [];
        }
        if (cache[amount]) {
            return cache[amount];
        }
        var min = [], newMin, newAmount;
        for (var i = 0; i < coins.length; i++) {
            var coin = coins[i];
            newAmount = amount - coin;
            if (newAmount >= 0) {
                newMin = me.makeChange(newAmount);
            }
            //如果余额大于等于零，或者newMin不是空数组
            if (
                newAmount >= 0 &&
                (newMin.length < min.length - 1 || !min.length)
                && (newMin.length || !newAmount)
            ) {
                min = [coin].concat(newMin);
                console.log('new Min ' + min + ' for ' + amount);
            }
        }
        return (cache[amount] = min);
    };
}
var minCoinChange = new MinCoinChange([1, 5, 10, 25]);
console.log(minCoinChange.makeChange(36));

思路分析：给定面额x，将x减去不同面值，如果余数为负则非正常结果，为正则继续以此面额作为新的x，不断向下遍历，过程中不断对每个余数的最小解做缓存，有缓存直接利用。
eg[1,3,5],x=4
1、4-1
1.1、3—- 3-1
1.1.1、 2—-2-1
1.1.1.1、1
1.1、3—- 3-3
2、4-3
2.1、1
3、4-5 pass

贪心算法

【最少】硬币找零问题

function MinCoinChange(coins) {
    var coins = coins; //{1}
    this.makeChange = function (amount) {
        var change = [], total = 0;
        for (var i = coins.length; i >= 0; i--) { //{2}
            var coin = coins[i];
            while (total + coin <= amount) { //{3}
                change.push(coin);           //{4}
                total += coin;               //{5}
            }
        }
        return change;
    };
}

思路：将面额先用最大面值减到不能减，之后再换小一号面值
缺点是不一定是最优，也不一定有解，有点是快速