数据结构与算法

// 分治法模板
// 递归返回条件
// 分段处理
// 合并结果

func traversal(root *TreeNode) ResultType  {
    // nil or leaf
    if root == nil {
        // do something and return
    }

    // Divide
    ResultType left = traversal(root.Left)
    ResultType right = traversal(root.Right)

    // Conquer
    ResultType result = Merge from left and right

    return result
}

// 回溯法模板
result = []
func backtrack(选择列表,路径):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(选择列表,路径)
        撤销选择

var reverse = function(x) {
    if(typeof x !== 'number') return
    var MAX = Math.pow(2, 31) - 1,
        MIN = -Math.pow(2, 31)
    var reverseNum = Number(`${Math.abs(x)}`.split('').reverse().join(''))
    reverseNum = x > 0 ? reverseNum : (0 - reverseNum)
    if(MIN > reverseNum || reverseNum > MAX ) {
        return 0
    }
    return reverseNum
};

var reverse = function(x) {
    let rev = 0
    const MAX_VALUE = Math.pow(2, 31) - 1,
          MIN_VALUE = -Math.pow(2, 31)
    while(x != 0 ) {
        const pop = x % 10
        x = parseInt(x / 10)
        if(rev > MAX_VALUE / 10 || (rev === MAX_VALUE / 10) && pop > (MAX_VALUE % 10)) { return 0}
        if(rev < MIN_VALUE / 10 || (rev === MIN_VALUE / 10) && pop < (MIN_VALUE % 10)) { return 0}
        rev = rev * 10 + pop
    }
    return rev
};

var firstUniqChar = function(s) {
    var map = new Map()
    for(var i = 0; i < s.length; i++) {
        map.has(s[i]) ? map.set(s[i], map.get(s[i]) + 1) : map.set(s[i],1)
    }
    for(var i = 0; i < s.length; i++) {
        if(map.get(s[i]) === 1) return i
    }
    return -1
};

var isPalindrome = function(s) {
  s = s.replace(/[^A-Za-z0-9]/g,'').toLowerCase()
  var i = 0,
      j = s.length - 1
  while(i < j) {
      if(s[i] !== s[j]) return false
      i++
      j--

  }
  return true
};

// 时间复杂度 O(n)
// 空间复杂度 O(1) 一个变量，一个 hashMap
var romanToInt = function(s) {
    var map = {
        I: 1,
        V: 5,
        X: 10,
        L: 50,
        C: 100,
        D: 500,
        M: 1000
    }
    var num = 0
    for (var i = 0; i < s.length; ) {
        if (map[s[i + 1]] && map[s[i + 1]] > map[s[i]]) {
            num += map[s[i + 1]] - map[s[i]]
            i += 2
        } else {
            num += map[s[i]]
            i += 1
        }
    }
    return num
};

var romanToInt = function(s) {
    var hashNum = {
        "I":1,
        "V":5,
        "X":10,
        "L":50,
        "C":100,
        "D":500,
        "M":1000
    }
    var result = 0;
    for(let i = 0;i<s.length;i++){
        hashNum[s[i]] < hashNum[s[i+1]] ? result -= hashNum[s[i]] : result += hashNum[s[i]]
    }
    return result;
};

var myPow = function(x, n) {
    if(n === 0) return 1
    var base = n > 0 ? x : 1 / x
    var result = 1
    for(var i = 0; i < Math.abs(n); i++) {
        result *= base
    }
    return result
};

var myPow = function(x, n) {
    if(n === 0) return 1
    else if (n === 1) return x
    else if (n === -1) return 1 / x
    var base = n > 0 ? x : 1 / x
    var half = parseInt(n / 2)
    var result = myPow(x, half)
    if(n % 2 === 0) {
        result *= result
    } else {
        result = result * result * base
    }
    return result
};

var myPow = function(x, n) {
    if (n === 0) return 1
    if (n === 1) return x;
    if (n < 0) return 1 / myPow(x, -n)
    if (n % 2 === 1) return x * myPow(x, n - 1)
    return myPow(x * x, n / 2)
};

// The JSArray describes JavaScript Arrays
//  Such an array can be in one of two modes:
//    - fast, backing storage is a FixedArray and length <= elements.length();
//       Please note: push and pop can be used to grow and shrink the array.
//    - slow, backing storage is a HashTable with numbers as keys.
class JSArray: public JSObject {
 public:
  // [length]: The length property.
  DECL_ACCESSORS(length, Object)

  // Number of element slots to pre-allocate for an empty array.
  static const int kPreallocatedArrayElements = 4;
};

var rotate = function(nums, k) {
  // 如果 k === nums.length，就不用循环了
  k = k % nums.length
  for(var i = 0; i < k; i++) {
      nums.unshift(nums.pop())
  }
  return nums
};

var rotate = function(nums, k) {
    var l = nums.length
    k = k % l
    nums.unshift(...nums.splice(l - k, k))
    return nums
};

Add(value)
	n <- node(value)
	if head = ø
		head <- n
		tail <- n
	else
		tail.next <- n
		tail <- n
	end if
end Add

class Node{
  constructro(val) {
    this.next = null
    this.val = val;
  }
}

class LinkedList {
  constructor() {
    this.head = new Node('head')
  }

  // 用于查找
  find(val) {
    let currentNode = this.head;
    while(currentNode && currentNode.val !== item) {
      currentNode = currentNode.next
    }
    return currentNode === null ? -1 : currentNode
  }
  
  // 指定元素向后插入节点
  // val: 新节点的 value
  // node: 插入位置
  insert(val, node) {
    const currtNode = this.find(node)
    if (currtNode === -1) {
      console.log('未找到插入位置')
      return
    }
    const newNode = new Node(val)
    newNode.next = currtNode.next
    currtNode.next = newNode
  }
  // 删除节点
  // 要删除的节点
  remove(node) {
    Object.assign(node, node.next)
  }
}

// 给定一个链表: 1->2->3->4->5, 和 n = 2.
// 当删除了倒数第二个节点后，链表变为 1->2->3->5.

var removeNthFromEnd = function(head, n) {
  let first = head; // 慢指针
  for (let i = 0; i < n; i++) {
    first = first.next;
  }
  if (!first) return head.next; // 当链表长度为n时，删除第一个节点

  let second = head; // 快指针
  while (first.next) {
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  return head;
};

var removeElements = function(head, val) {
  const newHead = new ListNode(-1)
  newHead.next = head
  let cur = newHead
  while (cur.next !== null) {
    if (cur.next.val === val) {
      cur.next = cur.next.next
    } else {
      cur = cur.next
    }
  }
  return newHead.next
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    // 字符串拼接，比对结果
    let forwardStr = '',
        reverseStr = '';
    while(head) {
        const nodeVal = head.val;
        forwardStr = forwardStr + nodeVal
        reverseStr = nodeVal + reverseStr
        head = head.next;
    }
    return forwardStr === reverseStr
};

class ListNode {
    constructor (val) {
        this.val = val
        this.next = null
    }
}
var isPalindrome = function(head) {
  let pointer = head;;

  function reverseLinkList (head) {
    if (!head) return true;
    // 递归逆序遍历
    const res = reverseLinkList(head.next) && (pointer.val === head.val);
    // pointer 指针不断向后指，进行正序遍历
    pointer = pointer.next;
    console.log(pointer)
    return res;
  }

  return reverseLinkList(head);
};

// 测试用例
var nodeA = new ListNode(1);
var nodeB = new ListNode(2);
var nodeC = new ListNode(1);
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = null;
isPalindrome(nodeA)

var isPalindrome = function(head) {
  if(!head || !head.next) return true;
  let fastRef = head,
      slowRef = head,
      cur = head,
      pre = null;
  while(fastRef && fastRef.next) {
    slowRef = slowRef.next;
    fastRef = fastRef.next.next;    
    const nextTemp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = nextTemp;    
  }
  //  快指针已经到结尾
  if (fastRef) {
    // 奇数个
    slowRef = slowRef.next;
  }
  while(pre) {
    if (pre.val !== slowRef.val) return false;
    pre = pre.next;
    slowRef = slowRef.next;
  }
  return true;
};

var hasCycle = function(head) {
  if(!head || !head.next) return false
  let slowRef = head,
      fastRef = head
  while(fastRef && fastRef.next) {
    fastRef = fastRef.next.next
    slowRef = slowRef.next
    if(fastRef === slowRef) return true
  }
  return false
};

var hasCycle = function(head) {
    if(!head || !head.next) return false
    const hashMap = new Map()
    while(head) {
      if(hashMap.has(head)) return true
      hashMap.set(head, head.val)
      head = head.next
    }
  return false
};

var hasCycle = function(head) {
  if(!head || !head.next) return false
  const symbol = Symbol()
  while(head) {
    if(head.val === symbol) return true
    head.val = symbol
    head = head.next
  }
  return false
};

var deleteNode = function(node) {
  Object.assign(node, node.next)
};

var deleteNode = function(node) {
  node.val = node.next.val
  node.next = node.next.next
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // 如果链表为空或者只有一个节点，返回 head
    if(!head || !head.next) return head;
    let [prev, cur] = [null, head]
    while(cur) {
        const nextTemp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nextTemp;
    }
    return prev;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(!head || !head.next) return head;
    var next = head.next;
    var reverserHead = reverseList(next);
    next.next = head;
    head.next = null;
    return reverserHead;
};

var reverseList = function(head) {
    let reverse = (prev, cur) => {
        if (!cur) return prev;
        const nextTeamp = cur.next;
        cur.next = prev;
        return reverse(cur, nextTeamp);
    }
    return reverse(null, head)
};

var removeNthFromEnd = function(head, n) {
  let first = head,second = head;
  while(n > 0) {
    first = first.next;
    n--;
  }
  if(!first) return head.next;
  while(first.next) {
    second = second.next;
    first = first.next;
  }
  second.next = second.next.next;
  return head;
};

// 双指针法
var mergeTwoLists = function(l1, l2) {
  // 创建一个新节点
  const head = new ListNode(-1)
  let cur = head
  // 如果两个链表都非空
  while(l1 && l2) {
    if(l1.val <= l2.val) {
      cur.next = l1
      l1 = l1.next
    }
    else {
      cur.next = l2
      l2 = l2.next
    }
    cur = cur.next
  }
  // l1 或 l2剩下的元素
  cur.next = l1 || l2
  return head.next
};

// 两树相加
var addTwoNumbers = function(l1, l2) {
  var nodeList2num = function(node) {
    var str = ''
    while(node) {
      str = `${node.val}${str}` 
      node = node.next
    }
    return BigInt(str)
  }
  var num2nodeList = function(num) {
    var head = new ListNode(-1)
    var cur = head
    for(var i = (`${num}`.length) - 1; i >= 0; i--) {
      cur.next = new ListNode(`${num}`[i])
      cur = cur.next
    }
    return head.next
  }
  return num2nodeList(nodeList2num(l1) + nodeList2num(l2))
};

class Stack {
  constructor() {
    this.data = []
  }
  push(item) {
    this.data.push(item)
  }
  pop() {
    return this.data.pop()
  }
  get length() {
    return this.data.length
  }
}

class Queue {
  constructor() {
    this.data = []
    this.head = 0
    this.tail = 0
  }
  enqueue(item) {
    this.data[this.tail++] = item
  }
  dequeue() {
    if(this.head === this.tail) {
      return null
    }
    return this.data[++this.head]
  }
  get length() {
    return this.tail - this.head
  }
}

var CQueue = function() {
    class Stack {
        constructor() {
            this.data = []
        }
        push(item) {
            this.data.push(item)
        }
        pop() {
            return this.data.pop()
        }
        peek() {
            return this.data[this.data.length - 1]
        }
        isEmpty() {
            return this.data.length === 0
        }
        get length() {
            return this.data.length
        }
    }    
    this.stack1 = new Stack()
    this.stack2 = new Stack()
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    this.stack1.push(value)
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    if(this.stack2.isEmpty()) {
        if(this.stack1.isEmpty()) return -1
        while(!this.stack1.isEmpty()) {
            this.stack2.push(this.stack1.pop())
        }
    }
    return this.stack2.pop()
};

/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

function isValid(s) {
    var map = new Map([
        ['(', ')'],
        ['{', '}'],
        ['[', ']'],
    ])
    var stack = []
    for(var i = 0; i < s.length; i++) {
        if(map.has(s[i])) {
            stack.push(s[i])
        } else if(!stack.length || map.get(stack.pop()) !== s[i]) {
            return false
        }
    }
    return !stack.length
};

// 解法1的变化 不用 hashMap
var isValid = function (s) {
  let map = {
    '(': -1,
    ')': 1,
    '[': -2,
    ']': 2,
    '{': -3,
    '}': 3
  }
  let stack = []
  for (let i = 0; i < s.length; i++) {
    if (map[s[i]] < 0) {
      stack.push(s[i])
    } else {
      let last = stack.pop()
      if (map[last] + map[s[i]] != 0) return false
    }
  }
  if (stack.length > 0) return false
  return true
};

class Node {
  data: any;
  left?: Node;
  right?: Node;
  constructor({data, left, right}) {
    this.data = data
    this.left = left
    this.right = right
  }
}

/**
 * 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) {
        this.minStack.push(x)
    } else {
       var min = Math.min(this.minStack[this.minStack.length - 1], x)
       this.minStack.push(min)
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.stack.pop()
    this.minStack.pop()
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1]
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.minStack[this.minStack.length - 1]
};

/**
 * @param {number[]} nums
 */
var Solution = function(nums) {
    this.nums = nums
    this.originalNums = nums.slice(0)
};

/**
 * Resets the array to its original configuration and return it.
 * @return {number[]}
 */
Solution.prototype.reset = function() {
    this.nums = this.originalNums.slice(0)
    return this.nums
};

/**
 * Returns a random shuffling of the array.
 * @return {number[]}
 */
Solution.prototype.shuffle = function() {
    for(var i = this.nums.length - 1; i > 0 ; i--) {
        var targetIndex = Math.floor(Math.random() * (i + 1))
        var tmp = this.nums[i]
        this.nums[i] = this.nums[targetIndex]
        this.nums[targetIndex] = tmp
    }
    return this.nums
};

var sortedArrayToBST = function(nums) {
    var helper = function(left, right) {
        if (left > right)
            return null
        var p = parseInt((left + right) / 2)
        // 中间的数一定是最中间的
        var root = new TreeNode(nums[p])
        // p - 1 和 p + 1 是为了间隔开 parent
        // 不断递归
        root.left = helper(left, p - 1)
        root.right = helper(p + 1, right)
        return root
    }
    return helper(0, nums.length - 1)
};

var generateParenthesis = function(n) {
  var result = []
  var helper = function(str = '', l = 0, r = 0) {
    if(str.length === n * 2) {
      result.push(str)
      return
    }
    if(l < n) {
      helper(`${str}(`, l + 1, r)
    }
    if(r < l) {
      helper(`${str})`, l, r + 1)
    }
  }
  helper()
  return result
};

// 动态规划版本的斐波那契数列
var fib = function(N) {
    if(N < 2) {
        return N
    }
    for(var i = 2; i<= N; i++) {
      if(i < 2) {
        arr[i] = i
      } else {
        arr[i] = arr[i - 1] + arr[i - 2]
      }
    }
    return arr[N]
};

function lcs(word1, word2) {
    var m = word1.length
      , n = word2.length
      , max = 0
      , maxColumn = 0
      , lcsarr = []
    for (var i = 0; i < m; ++i) {
        lcsarr[i] = []
        for (var j = 0; j < n; ++j) {
            if (word1[i] === word2[j]) {
                if (i === 0 || j === 0) {
                    lcsarr[i][j] = 1
                } else {
                    lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1
                }
            } else {
                lcsarr[i][j] = 0
            }
            if (max < lcsarr[i][j]) {
                max = lcsarr[i][j]
                maxColumn = j
            }
        }
    }
    var str = ''
    if (max === 0)
        return ''
    else {
        for (; max > 0; max--,
        maxColumn--) {
            str = word2[maxColumn] + str
        }
        return str
    }
}

var longestCommonSubsequence = function(text1, text2) {
    var len1 = text1.length,
        len2 = text2.length,
        arr = []
    for(var i = 0; i <= len1; i++) {
        // 初始化二维数组
        arr[i] = []
        for(var j = 0; j <= len2; j++) {
            if (i === 0 || j === 0) {
                arr[i][j] = 0
                continue
            }
            if(text1[i - 1] === text2[j - 1]) {
                arr[i][j] =  arr[i - 1][j - 1] + 1
            } else {
                arr[i][j] = Math.max(arr[i][j - 1], arr[i - 1][j])
            }
        }
    }
    return arr[len1][len2]
};

// 递归版本
function knapsack(capacity, size, value, n) {
  //   背包满了 或者 保险箱空了
  if (n === 0 || capacity === 0) return 0;
  //   如果容积 大于 剩余的容量，看看下一件物品呢
  if (size[n - 1] > capacity) {
    return knapsack(capacity, size, value, n - 1);
  } else {
    return Math.max(
      value[n - 1] + knapsack(capacity - size[n - 1], size, value, n - 1),
      knapsack(capacity, size, value, n - 1)
    );
  }
}

// DP 版本
function knapsack(capacity, n, sizes, values) {
  var K = []
  // 多建一行
  for(var i = 0; i <= n; i++) {
    K[i] = []
    for(var  w = 0; w <= capacity; w++) {
      // 容积为0，或者物品为0，对应第一行或者第一列
      if(i === 0 || w === 0) K[i][w] = 0
      // 第 i - 1 个物品放不下
      // 不偷
      else if (sizes[i - 1] > w) {
        K[i][w] = K[i - 1][w]
      } else {
        // 够放，偷还是不偷？
        K[i][w] = Math.max(K[i - 1][w - sizes[i - 1]] + values[i - 1] +, K[i - 1][w])
      }
    } 
  }
  return K[n][capacity]
}

// 贪心算法
function maxSum(arrs) {
  var max_sum = arrs[0],
      pre_sum = arrs[0]
  for(var i = 1; i < arrs.length; i++) {
    pre_sum = Math.max(arrs[i], pre_sum + arrs[i])
    max_sum = Math.max(max_sum, pre_sum)
  }
  return max_sum
}

// 动态规划？
function maxSum(arrs) {
  var max_sum = arrs[0],
    pre = 0;
  for (var i = 0; i < arrs.length; i++) {
    pre = Math.max(pre + arrs[i], arrs[i])
    max_sum = Math.max(max_sum, pre)
  }
  return max_sum;
}

// LeetCode 视频图解 动态规划版本
function maxSum(nums) {
  for (var i = 1; i < nums.length; i++) {
    // 前一个元素大于 0 ？
    if (nums[i - 1] > 0) {
      nums[i] += nums[i - 1];
    }
  }
  return Math.max(...nums);
}

// 判断是否有增益效果
function maxSum(nums) {
  var sum = nums[0],
       max = nums[0]
  for(var i = 1; i < nums.length; i++) {
    // 之前的值大于0，
    if(sum > 0) {
      // 正数 + 一个正数或者负数 
      sum += nums[i]
    } else {
      // 如果之前的值小于0，不要之前的值了，
      // 负数加上一个正数，< 正数
      // 负数加上一个负数 < 负数
      sum = nums[i]
    }
    max = Math.max(sum, max)
  }
  return max
}

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {
        const temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

function bubbleSort(nums) {
    var numElements = nums.length
    var temp
    for( var outer = numElements; outer >= 2; --outer) {
        for( var inner = 0; inner <= outer - 2; ++inner) {
            if(nums[inner] > nums[inner + 1]) {
                temp = nums[inner]
                nums[inner] = nums[inner + 1]
                nums[inner + 1] = temp
            }
        }
    }
    return nums
}

function selectionSort(arr) {
    var minIndex
    var tmp 
    for(var i = 0; i < arr.length - 1; i++) {
        minIndex = i
        for(var j = i + 1;j < arr.length; j++) {
            // 卧槽 还有比我小的
            if(arr[j] < arr[minIndex] ) {
              minIndex = j
            }
        }
        tmp = arr[i]
        // 交换这俩货
        arr[i] = arr[minIndex]
        arr[minIndex] = tmp
    }
    return arr
}