fe-sadhu / data-structures-and-algorithms Goto Github PK

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  const dummyHead = new ListNode(null);
  let currentPoint = dummyHead;
  let l1Point = l1;
  let l2Point = l2;
  let prevPlus = 0;

  while(l1Point || l2Point) {
    l1Point = l1Point || new ListNode(0);
    l2Point = l2Point || new ListNode(0);
    const l1Val = l1Point.val;
    const l2Val = l2Point.val;
    let sum = l1Val + l2Val + prevPlus;
    prevPlus = 0;
    if (sum >= 10) {
      sum = sum - 10;
      prevPlus = 1;
    }
    currentPoint.next = new ListNode(sum);
    currentPoint = currentPoint.next;
    l1Point = l1Point.next;
    l2Point = l2Point.next;
  }

  prevPlus && (currentPoint.next = new ListNode(prevPlus));

  return dummyHead.next;
};

// 时间复杂度: O(n)  n 为 l1、l2 的更长度
// 空间复杂度: 若返回值算复杂度的话 O(n)

var strStr = function(haystack, needle) {
      if(!needle) return 0;
      let hayS = 0,
      len = needle.length;
  
      while(hayS < haystack.length) {
        if (haystack.substr(hayS, len) === needle) {
          return hayS;
        }
        hayS++;
      }
      return -1;
};

时间复杂度: O(n^2)
空间复杂度: O(1)

var isValidBST = function(root) {
    function helper(root, min, max) {
        if (!root) return true;
        if(root.val <= min || root.val >= max) return false;
        return helper(root.left, min, root.val) && helper(root.right, root.val, max)
    }
    return helper(root, -Infinity, Infinity);
};
时间复杂度 : O(n)，其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次。
空间复杂度 : O(n)，其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况则是 O(n)，一条链。

var isValidBST = function(root) {
    let stack = [];
    let pre = -Infinity;
    while(stack.length || root!==null){
        while(root!==null){
            stack.push(root);
            root = root.left
        };
        root = stack.pop();
        if(root.val<=pre){
            return false;
        }
        pre = root.val;
        root = root.right;
    }
    return true;
};

时间复杂度: O(n), 一个节点走一次
空间复杂度: O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
 var isValidBST = function(root) {
  if (!root) return false;
  let prev = -Infinity;
  let isValid = true;
  function dfs(node) {
      if(!node) return;
      if (!isValid) return;
      dfs(node.left);
      if (node.val > prev) {
          prev = node.val;
      } else {
          isValid = false;
      }
      dfs(node.right);
  }
  dfs(root);
  return isValid;
};

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

时间复杂度: O(1);
空间复杂度: O(1);

var connect = function(root) {
  if (!root) return null;
  
  let l = connect(root.left);
  let r = connect(root.right);
  while(l) {
      l.next = r;
      l = l.right;
      r = r.left;
  }
  return root;
};

var removeNthFromEnd = function(head, n) {
  const dummyHead = new ListNode(null, head);
  const len = getLengthByHead(head);

  if (len - n <= 0) { // 第一个节点
    return dummyHead.next.next;
  }

  let a = dummyHead.next;
  let count = 0;
  while(a) {
    if (len - count === n + 1) { // 找到前一个节点
      a.next = a.next.next;
      break;
    }
    count++;
    a = a.next;
  }
  return dummyHead.next;
};

function getLengthByHead(head) {
  let len = 0;
  while(head) {
    len++;
    head = head.next;
  }
  return len;
}

时间复杂度: O(L); 
空间复杂度: O(1);

var removeNthFromEnd = function(head, n) {
    let ret = new ListNode(0, head),
        slow = fast = ret;
    while(n--) fast = fast.next;
    if(!fast) return ret.next;
    while (fast.next) {
        fast = fast.next; 
        slow = slow.next
    };
    slow.next = slow.next.next;
    return ret.next;
};

时间复杂度: O(n);
空间复杂度: O(1);

var buildTree = function(inorder, postorder) {
    if(!inorder.length) return null;
    const root = postorder[postorder.length -1];
    const rootIndexInInorder = inorder.findIndex(i => i === root);
    const leftTreeInorder = inorder.slice(0, rootIndexInInorder);
    const rightTreeInorder = inorder.slice(rootIndexInInorder + 1);
    const leftTreePostorder = postorder.slice(0, leftTreeInorder.length);
    const rightTreePostorder = postorder.slice(leftTreeInorder.length, -1);
    const node = new TreeNode(root);
    node.left = buildTree(leftTreeInorder, leftTreePostorder);
    node.right = buildTree(rightTreeInorder, rightTreePostorder);
    return node;
};

var levelOrder = function(root) {
    if (!root) return [];
    let res = [],
        item = [];
    let specil = 'specil';
    let queue = [root, specil],
        node;
    while((node = queue.shift()) !== undefined) {
        if (node === specil) {
            res.push(item);
            item = [];
            if (!queue.length) return res;
            queue.push(specil);
            continue;
        }
        item.push(node.val);
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
};

时间复杂度: O(n)
空间复杂度: O(n)

var detectCycle = function(head) {
  const visited = new Set();
  while (head !== null) {
    if (visited.has(head)) {
        return head;
    }
    visited.add(head);
    head = head.next;
  }
  return null;
};

var detectCycle = function(head) {
  while(head) {
    if (head.flag) {
      return head
    } else {
      head.flag = true;
      head = head.next
    }
  }
  return null
};

var maxDepth = function(root) {
    if(!root) {
        return 0;
    }
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};
时间复杂度: O(n), n 为二叉树节点的个数，每个节点在递归中只被遍历一次。
空间复杂度: O(height), height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

var maxDepth = function(root) {
    const flag = 'special';
    const queue = [root, flag]
    let node = null;
    let depth = 0;
    while ((node = queue.shift())) {
        if (node === flag) {
            depth++;
            if (!queue.length) {
                return depth;
            }
            queue.push(flag);
            continue;
        }
        node.left && queue.push(node.left)
        node.right && queue.push(node.right);
    }
    return depth;
};
时间复杂度: O(n), n = 节点数 + flag 数量
空间复杂度: O(n)

var removeDuplicates = function(nums) {
    let len = nums.length;
    for (let i = 0; i < len;) {
        if (i + 1 === len) break;
        let cur = nums[i];
        let next = nums[i + 1];
        if (cur === next) {
            nums.splice(i + 1, 1);
            len--;
            continue;
        }
        i++
    }
    return nums.length;
};

时间复杂度: 最好情况一个重复都没有 O(n), n 为数组长度。 最坏情况每个重复，O(n * splice 复杂度)
空间复杂度: O(1)

var removeDuplicates = function(nums) {
      if(!nums.length) return 0;
      let slow = 0;
      let fast = 1;
      const len = nums.length;
      while(fast < len) {
        if (nums[fast] !== nums[slow]) {
          slow++;
          nums[slow] = nums[fast];
        }
        fast++;
      }
      return slow + 1;
}

时间复杂度: O(n)，n 为数组长度
空间复杂度: O(1)

var reverseList = function(head) {
    const stack = [];
    while(head) {
        stack.push(head);
        head = head.next;
    }
    const dummy = new ListNode(null);
    let helper = dummy;
    while(stack.length) {
        helper.next = stack.pop();
        helper = helper.next;
    }
    helper.next = null;  // 记得赋 null，不然循环引用
    return dummy.next;

    let helper = null;
    while (head) {
        const next = head.next;
        head.next = helper;
        helper = head;
        head = next;
    }
    return helper;
};

时间复杂度: O(n);
空间复杂度: O(n);

var reverseList = function(head) {
     if (!head || !head.next) {
         return head;
     }
     const reversed = reverseList(head.next);
     head.next.next = head;
     head.next = null;  // 记得赋 null，不然循环引用
     return reversed;
};
时间复杂度: O(n) n 取决于递归的层数
空间复杂度: O(n);

var reverseList = function(head) {
    let helper = null;
    while (head) {
        const next = head.next;  // 缓存旧链表的下一个节点
        head.next = helper;  // 当前节点指向新链表的头节点
        helper = head; // 改变新链表的头节点
        head = next; // 改变旧链表为下一个节点
    }
    return helper;  // 返回新链表
};

时间复杂度: O(n);
空间复杂度: O(1);

var partition = function(head, x) {
  if (!head) return head;
  const dummySmallHead = new ListNode(0);
  const dummyLargeHead = new ListNode(0);
  let small = dummySmallHead;
  let large = dummyLargeHead;
  while(head) {
    if (head.val < x) {
      small.next = head;
      small = small.next;
    } else {
      large.next = head;
      large = large.next;
    }
    head = head.next;
  }
  small.next = dummyLargeHead.next;
  large.next = null; // 断环
  return dummySmallHead.next;
};
// 时间复杂度： O(n) 只遍历了一遍链表
// 空间复杂度： O(1) small、large 链表的节点都是复用原链表的，无创建额外空间

var reverse = function(x) {
    let rev = 0;
    while (x !== 0) {
        const digit = x % 10;
        x = ~~(x / 10); // 双重位运算取反，因为位运算的结果是整数，这里的作用就是去掉小数
        rev = rev * 10 + digit;
        if (rev < Math.pow(-2, 31) || rev > Math.pow(2, 31) - 1) {
            return 0;
        }
    }
    return rev;
};

时间复杂度: O(logx)  x 的十位数量
空间复杂度: O(1)

var countAndSay = function(n) {
  if (n < 1 || n > 30) return;

  let prev = '1';

  while(--n) {
    let res = '';
    let repeatTime = 1;
    for (let i = 0; i < prev.length; i++) {
      if (!prev[i + 1] || prev[i + 1] !== prev[i]) {
        res += repeatTime + prev[i];
        repeatTime = 1;
      } else {
        repeatTime++;
      }
    }
    prev = res;
  }

  return prev;
};

时间复杂度: O(n^2)
空间复杂度: O(1)

var reverseBetween = function(head, left, right) {
  const dummy = new ListNode(-1);
  dummy.next = head;
  let pre = dummy;
  for (let i = 0; i < left - 1; ++i) {
      pre = pre.next;
  }

  let cur = pre.next;
  for (let i = 0; i < right - left; ++i) {
      const next = cur.next;
      cur.next = next.next;
      next.next = pre.next;
      pre.next = next;
  }
  return dummy.next;
};

时间复杂度: O(n)
空间复杂度: O(1)

var reverseBetween = function(head, left, right) {
    // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
    const dummyNode = new ListNode(-1);
    dummyNode.next = head;

    let pre = dummyNode;
    // 从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
    for (let i = 0; i < left - 1; i++) {
        pre = pre.next;
    }

    // 从 pre 再走 right - left + 1 步，来到 right 节点
    let rightNode = pre;
    for (let i = 0; i < right - left + 1; i++) {
        rightNode = rightNode.next;
    }

    //切断出一个子链表（截取链表）
    let leftNode = pre.next;
    let curr = rightNode.next;

    // 切断链接
    pre.next = null;
    rightNode.next = null;

    // 反转链表的子区间
    reverseLinkedList(leftNode);

    // 接回到原来的链表中
    pre.next = rightNode;
    leftNode.next = curr;
    return dummyNode.next;
};

const reverseLinkedList = (head) => {
    let pre = null;
    let cur = head;

    while (cur) {
        const next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
};

时间复杂度: O(n)
空间复杂度: O(1)

 var plusOne = function(digits) {
  let len = digits.length - 1;
  while(len >= 0) {
        digits[len]++;
        if (digits[len] >= 10) {
           digits[len] = 0;
        } else {
           return digits;
        }
     len--;
  }
  digits.unshift(1)
  return digits;
};

时间复杂度: O(n) 最好的情况是 O(1)
空间复杂度: O(1)

var plusOne = function(digits) {
    return String((Number(digits.join('')) + 1)).split('');
};

var rotate = function(matrix) {
  for (let i = matrix.length - 1; i >= 0; i--) {
    let j = 0;
    while(j < matrix.length) {
      const item = matrix[i].shift();
      matrix[j].push(item);
      j++
    }
  }
};

时间复杂度: O(n^2)
空间复杂度: O(1)

var isPalindrome = function(head) {
  const vals = [];
  while (head !== null) {
      vals.push(head.val);
      head = head.next;
  }
  for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
      if (vals[i] !== vals[j]) {
          return false;
      }
  }
  return true;
};

时间复杂度: O(n);
空间复杂度: O(n);

const reverseList = (head) => {
  let prev = null;
  let curr = head;
  while (curr !== null) {
      let nextTemp = curr.next;
      curr.next = prev;
      prev = curr;
      curr = nextTemp;
  }
  return prev;
}

const endOfFirstHalf = (head) => {
  let fast = head;
  let slow = head;
  while (fast.next !== null && fast.next.next !== null) {
      fast = fast.next.next;
      slow = slow.next;
  }
  return slow;
}

var isPalindrome = function(head) {
  if (head == null) return true;

    // 找到前半部分链表的尾节点并反转后半部分链表
    const firstHalfEnd = endOfFirstHalf(head);
    const secondHalfStart = reverseList(firstHalfEnd.next);

    // 判断是否回文
    let p1 = head;
    let p2 = secondHalfStart;
    let result = true;
    while (result && p2 != null) {
        if (p1.val != p2.val) result = false;
        p1 = p1.next;
        p2 = p2.next;
    }        

    // 还原链表并返回结果
    firstHalfEnd.next = reverseList(secondHalfStart);
    return result;
};
时间复杂度: O(n)
空间复杂度: O(1)

var removeElements = function(head, val) {;
  const dummyHead = new ListNode(-1, head);
  let prev = dummyHead;
  while(head) {
    if (head.val === val) {
      prev.next = head.next;
    } else {
      prev = head;
    }
    head = head.next;
  }

  return dummyHead.next;
};

时间复杂度: O(n)
空间复杂度: O(1)

var deleteDuplicates = function(head) {
  if (!head || !head.next) return head;
  let slow = head;
  let fast = head.next;
  while(fast) {
    if (slow.val === fast.val) {
      slow.next = fast.next;
    } else {
      slow = slow.next;
    }
    fast = fast.next;
  }
  return head;
};
// 时间复杂度: O(n) n 为链表长度
// 空间复杂度: O(1)

const len = nums.length
const left = nums.slice(-k);
const right = nums.slice(0, len - k);
return [...left, ...right];

时间复杂度: slice 方法的时间复杂度
空间复杂度: O(n)

var rotate = function(nums, k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);

    function reverse (nums, start, end) {
      while(start < end) {
          const tmp = nums[start];
          nums[start] = nums[end];
          nums[end] = tmp;
          start++;
          end--;
      }
    }
    return nums;
};

时间复杂度: O(n)
空间复杂度: O(1)

var mergeTwoLists = function(l1, l2) {
    const dummy = new ListNode(null);
    let helper = dummy;

    while(l1 && l2) {
        if (l1.val < l2.val) {
            helper.next = l1;
            l1 = l1.next;
        } else {
            helper.next = l2;
            l2 = l2.next;
        }
        helper = helper.next;
    }

    l1 && (helper.next = l1);
    l2 && (helper.next = l2);

    return dummy.next;
};
时间复杂度: O(n)  n = Math.min(L1, L2)
空间复杂度: O(1)  最长开辟内存为两个链表节点总数

var mergeTwoLists = function(l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};
时间复杂度: O(n) n 为递归层数
空间复杂度: O(1) 最长开辟内存为两个链表节点总数

var isPalindrome = function(s) {
  const reg = /[A-Za-z0-9]/
  let i = 0;
  let j = s.length - 1;

  while(i < j) {
    const left = s[i];
    const right = s[j];

    if (reg.test(left) && reg.test(right)) {
      if (left.toUpperCase() === right.toUpperCase()) {
        i++;
        j--;
      } else {
        return false;
      }
    } else if (reg.test(left)) {
      j--;
    } else {
      i++;
    }
  }

  return true;
};

时间复杂度: O(n);
空间复杂度: O(1);

var maxProfit = function(prices) {
  let profit = 0;
  for (let i = 0; i < (prices.length - 1); i++) {
    if (prices[i + 1] > prices[i]) {
      profit += prices[i + 1] - prices[i];
    }
  }
  return profit
};

时间复杂度:  O(n)
空间复杂度: O(1)

var isValidSudoku = function(board) {
  const isNumber = (val) => val !== '.';
  const rowHash = [];
  const columnHash = [];
  const boxHash = [];
  for (let i = 0; i < 9; i++) {
    rowHash[i] = [];
    columnHash[i] = [];
    boxHash[i] = [];
  }
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3); // box 的索引
      const item = board[r][c];
      if (isNumber(item)) {
        if (rowHash[r].includes(item)) return false;
        if (columnHash[c].includes(item)) return false;
        if (boxHash[boxIndex].includes(item)) return false;
        rowHash[r].push(item);
        columnHash[c].push(item);
        boxHash[boxIndex].push(item);
      }
    }
  }
  return true;
};

时间复杂度: O(1); // 一次迭代遍历完 81 次
空间复杂度: O(1); // 开辟固定空间

var buildTree = function(preorder, inorder) {
  if (!preorder.length) {
    return null;
  }
  const index = inorder.findIndex(v => v === preorder[0]); // 可以用 hash 表优化，不用每次都遍历查找
  const leftInorder = inorder.slice(0, index);
  const rightInorder = inorder.slice(index + 1);
  const restPreorder = preorder.slice(1);
  const leftPreorder = restPreorder.slice(0, leftInorder.length);
  const rightPreorder = restPreorder.slice(index2);
  const root = new TreeNode(preorder[0]);
  root.left = buildTree(leftPreorder, leftInorder);
  root.right = buildTree(rightPreorder, rightInorder);
  return root;
};

var reverseString = function(s) {
 let i = s.length - 1;
    while(i > 0) {
        const f = s.shift();
        s.splice(i, 0, f);
        i--
    }
};

时间复杂度: O(n)
空间复杂度： O(1)

var reverseString = function(s) {
  let i = 0, x = s.length -1;
    while (i < x) {
        [s[i], s[x]] = [ s[x], s[i] ]
        i++
        x--
    }
};

时间复杂度: O(n);  比思路一的优势是少迭代一半
空间复杂度: O(1)

var swapPairs = function(head) {
  if (!head) return null;
  if (!head.next) return head;
  let p = head;
  let n = head.next;
  let fix = new ListNode(0);
  const newHead = n;

  while(true) {
    fix.next = n;
    p.next = n.next;
    n.next = p;
    fix = p;
    p = p.next;
    if (!p) {
      // 代表链表节点数是双数，我们已经处理完了所有节点，直接返回
      return newHead
    }
    n = p.next;
    if (!n) {
      // 代表链表节点数是单数，最后一个节点不用处理，直接返回
      return newHead;
    }
  }
}

var swapPairs = function(head) {
  if (!head) return null;
  if (!head.next) return head;
  let p = head;
  let fix = new ListNode(0);
  const newHead = n;

  while(p && p.next) {
    const n = p.next;
    fix.next = n;
    p.next = n.next;
    n.next = p;
    fix = p;
    p = p.next;
  }

  return newHead;
};

var swapPairs = function(head) {
  if(!head || !head.next) return head;
  const dummy = new ListNode(0, head.next);
  head.next = swapPairs(dummy.next.next); // 后指针指向的是已经两两交换过后的链表
  dummy.next.next = head;
  return dummy.next;
};

var singleNumber = function(nums) {
    const hash = {}
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] in hash) {
            hash[nums[i]]++
            continue;
        }
        hash[nums[i]] = 1;
    }
    for (let k in hash) {
        if (hash[k] === 1) {
            return k;
        }
    }
};

时间复杂度: O(n)
空间复杂度: O(n)

var singleNumber = function(nums) {
    nums.sort();

    for (let i = 0; i < nums.length - 1;) {
        if (nums[i] !== nums[i + 1]) {
            return nums[i];
        }
        i += 2;
    }
    return nums[nums.length - 1];
};

时间复杂度: O(nlogn)
空间复杂度: O(1)

var singleNumber = function(nums) {
  let xor = 0;
  for (let i = 0; i < nums.length; i++) {
    xor = xor ^ nums[i];
  }
  return xor;
};

时间复杂度: O(n);
空间复杂度: O(1);

var rotateRight = function(head, k) {
  if (!k) {
    return head;
  }
  if (!head) {
    return head;
  }
  const forOptimizing = k;
  let fast = new ListNode(0, head);
  let slow = new ListNode(0, head);
  while(fast.next && k--) {
    fast = fast.next;
  }
  if (k !== -1) {
    // 代表 k 还没结束，链表就走到头了，也就是链表向右移动了链表总数个位置。也就相当于没移动，我们接着移动剩余的 properK 个。
    const properK = forOptimizing % (forOptimizing - k);
    return rotateRight(head, properK);
  }
  while(fast.next) {
    // 指针步进直到 fast 指向最后一个节点
    fast = fast.next;
    slow = slow.next;
  }
  if (slow.next === head) {
    // 链表往右移动链表总数，其实就等于自身
    return head;
  }
  const newHead = slow.next;
  slow.next = null;
  fast.next = head;
  return newHead;
};

var rotateRight = function(head, k) {
  if (!k || !head || !head.next)  {
    return head;
  }
  let lastNode = head;
  let len = 1;
  while(lastNode.next) {
    lastNode = lastNode.next;
    len++;
  }
  lastNode.next = head; // 成环

  let cut = len - (k % len);
  while(--cut) {
    head = head.next;
  }
  const newHead = head.next;
  head.next = null // 切断
  return newHead;
};
// 时间复杂度： O(n) 最坏情况为遍历 链表节点数 * 2 - 1 次
// 空间复杂度： O(1)

var containsDuplicate = function(nums) {
  const already = [];
  let len = nums.length
  while(len--) {
    if (already.includes(nums[len])) {
      return true;
    }
    already.push(nums[len])
  }
  return false;
};

时间复杂度: O(n);
空间复杂度: O(n);

var containsDuplicate = function(nums) {
  nums.sort() // O(nlogn)
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] === nums[i + 1]) {
      return true;
    }
  }
  return false;
};

时间复杂度: O(nlogn) >>> sort 快排复杂度，其实每个引擎厂商都不一样，这里取 v8 实现
空间复杂度: O(1)

var pathSum = function(root, target) {
  
  const ret = [];
  const path = [];

  function dfs(node, target) {
      if (!node) return;
      // 节点存在，入路径数组进行处理
      path.push(node.val);
      // 叶子节点且值相等
      if (!node.left && !node.right && node.val === target) {
          ret.push(path.slice());
      }
      dfs(node.left, target - node.val);
      dfs(node.right, target - node.val);
      // 左右节点处理完了，证明该节点处理完了，出路径数组回溯
      path.pop();
  }
  dfs(root, target);
  return ret;
};

```js

时间复杂度：O(n) n 为节点数
空间复杂度：O(n) 非尾递归，n 为树的深度

var longestCommonPrefix = function(strs) {
    let res = strs[0];
    for (let i = 1; i < strs.length; i++) {
        res = findCommonPrefix(res, strs[i]);
        if (res === '') return res;
    }
    return res;
};

function findCommonPrefix (str1, str2) {
    let common = '';
    for (let i = 0; i < str1.length; i++) {
        if (str1[i] !== str2[i]) {
            return common;
        }
        common += str1[i]
    }
    return common;
}

时间复杂度: O(m*n)   m 是所有元素的平均长度、n 是数组长度
空间复杂度: O(1)

var isAnagram = function(s, t) {
  if (s.length !== t.length) {
    return false;
  }

  // 26 个英文字母
  const arr = new Array(26).fill(0);

  for (let i = 0; i < s.length; i++) {
    arr[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
  }

  for (let j = 0; j < t.length; j++) {
    const index = t.charCodeAt(j) - 'a'.charCodeAt(0);
    arr[index]--;
    if (arr[index] < 0) {
      return false;
    }
  }

  return true;
};

时间复杂度: O(n)
空间复杂度: O(1)   // 26 个字母

var isAnagram = function(s, t) {
  if (s.length !== t.length) {
    return false;
  }

  // 26 个英文字母
  const hash = {};

  for (let i = 0; i < s.length; i++) {
    if (hash.hasOwnProperty(s[i])) {
      hash[s[i]]++;
      continue;
    };
    hash[s[i]] = 1;
  }

  for (let j = 0; j < t.length; j++) {
    if (!hash.hasOwnProperty(t[j])) {
      return false;
    }
    hash[t[j]]--;
    if (hash[t[j]] < 0) {
      return false;
    }
  }

  return true;
};

时间复杂度: O(n)
空间复杂度: O(n)

var isAnagram = function(s, t) {
    return s.length == t.length && [...s].sort().join('') === [...t].sort().join('')
};

时间复杂度: O(nlogn) sort 的时间复杂度
空间复杂度: O(n)  视字符的长度而定，并且 sort 方法根据不同厂商的实现也有空间复杂度

var sortedArrayToBST = function(nums) {
  if (!nums.length) return null;
  if (nums.length === 1) return new TreeNode(nums[0]);
  const mid = Math.floor(nums.length / 2);
  const root = new TreeNode(nums[mid])
  root.left = sortedArrayToBST(nums.slice(0, mid))
  root.right = sortedArrayToBST(nums.slice(mid + 1));
  return root;
};

时间复杂度: O(n) 每个节点只会遍历到一次
空间复杂度: O(n) 递归栈带来的线性内存消耗

var isSymmetric = function(root) {
    // 定义: 判断两棵树根节点值是否相等 且 左子节点的右子节点（如果有）必须等于右子节点的左子节点，左子节点的左子节点必须等于右子节点的右子节点。 如果不符合则返回 false。
    // 出口： 除了定义的 false 条件外，左右节点为空返回 true。
    function helper(left, right) {
        if (!left && !right) return true;
        else if (!left || !right) return false;

        if (left.val !== right.val) {
            return false
        }
        return helper(left.left, right.right) && helper(left.right, right.left)
    }
    return helper(root.left, root.right)
};
时间复杂度: O(n)  每个节点遍历一次
空间复杂度: O(H)  每层节点占一个递归栈

var isSymmetric = function(root) {
  if(!root) return true;
  const queue = [root.left, root.right];

  while(queue.length) {
    let l = queue.shift();
    let r = queue.shift();
    if(!l && !r) continue;
    if(!l || !r) return false;
    if(l.val !== r.val) return false;

    queue.push(l.left);
    queue.push(r.right);

    queue.push(r.left);
    queue.push(l.right);
  }
  return true;
}
时间复杂度: O(n);
空间复杂度: O(n);

var getIntersectionNode = function(headA, headB) {
  if (headA === null || headB === null) {
    return null;
  }
  let pA = headA, pB = headB;
  while (pA !== pB) {
    pA = pA === null ? headB : pA.next;
    pB = pB === null ? headA : pB.next;
  }
  // 要么同时指向相交的第一个几点，要么同时指向 null
  return pA;
};

var twoSum = function(nums, target) {
    const cache = [];
    for(let i = 0; i < nums.length; i++) {
        let diff = target - nums[i]
        if (diff in cache) {
            return [i, cache[diff]];
        }
        cache[nums[i]] = i;
    }
};

时间复杂度: O(n)
空间复杂度: O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function(nums) {
    if (!nums.length) {
        return null;
    }
    let max = -Infinity, maxIndex;
    nums.forEach((item, index) => {
        if (item > max) {
            max = item;
            maxIndex = index;
        }
    })
    const root = new TreeNode(max);
    root.left = constructMaximumBinaryTree(nums.slice(0, maxIndex));
    root.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1));
    return root;
};

var moveZeroes = function(nums) {
  let l = nums.indexOf(0);
  if (l === -1) return nums;
  for (let r = l + 1; r < nums.length; r++) {
    if (nums[r] !== 0) {
      nums[l] = nums[r];
      nums[r] = 0;
      l++;
      r = l;
    }
  }
};

时间复杂度: O(n);
空间复杂度: O(1);

var moveZeroes = function(nums) {
    for(let i = nums.length - 1; i >= 0; i--) {
        if (nums[i] === 0) {
            nums.splice(i, 1);
            nums.push(0);
        }
    }
};

  if (!root) return []; // 出口条件，传个空节点，返回空数组
  // [根节点, ...preorderTraversal(左孩子), ...preorderTraversal(右孩子)]
  return [root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)];

  if (!root) return [];

  const stack = [{
    color: 'white', // 未遍历到就是 'white'，遍历到了该节点就变颜色为 'gray'
    node: root
  }];
  const res = [];

  while(stack.length) {
    const {color, node} = stack.pop(); // 节点出栈、待处理
    if (color === 'gray') {
      // 遍历到了该节点，则对其做出处理，此处是保存进返回值里
      res.push(node.val);
    } else {
      // 节点入栈
      // 因为栈是先进后出，假如我们想前序遍历 根左右 的话，入栈顺序就得反过来。
      // 同理，想要中序遍历、后续遍历，改变入栈顺序就行。
      node.right && stack.push({color: 'white', node: node.right});
      node.left && stack.push({color: 'white', node: node.left});
      stack.push({color: 'gray', node}); // 本轮走到了该节点，颜色改变
    }
  }
  return res;

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    const Layer_Sign = 'layer';
    const queue = [root, Layer_Sign];
    const ret = root ? [root.val] : [];
    let node = null;
    while(node = queue.shift()) {
        if (node === Layer_Sign) {
            if(!queue.length) {
                break;
            }
            queue.push(Layer_Sign);
            continue;
        }
        ret.push(node.left ? node.left.val : null);
        ret.push(node.right ? node.right.val : null);
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
    return JSON.stringify(ret);
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    const arr = JSON.parse(data);
    if (!arr.length) return null;
    const root = new TreeNode(arr[0]);

    const queue = [root];
    let pointer = 1; // 指向当前节点的左孩子
    let node;
    while(node = queue.shift()) {
        if (arr[pointer] !== null && arr[pointer] !== undefined) {
            const leftNode = new TreeNode(arr[pointer]);
            node.left = leftNode;
            queue.push(leftNode);
        }
        if (arr[pointer + 1] !== null && arr[pointer + 1] !== undefined) {
            const rightNode = new TreeNode(arr[pointer + 1]);
            node.right = rightNode;
            queue.push(rightNode);
        }
        pointer += 2;
    }
    return root;
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */