🔐 数据结构和算法 [ONGOING]

function calcSum(nums) {
  let sum = 0; // 1 次赋值 => O(1)
  let i = 0; // 1 次赋值 => O(1)
  // 循环 => O(n)
  while(i < nums.length){ //判断算作循环体内部 => O(1)
    sum = sum + nums[i]; // 求和、赋值 => O(2)
    i = i + 1; // 求和、赋值 => O(2)
  }
  return sum; // 函数返回不考虑
}

I/zygote64(21065): Do partial code cache collection, code=122KB, data=83KB
I/zygote64(21065): After code cache collection, code=122KB, data=83KB
I/zygote64(21065): Increasing code cache capacity to 512KB

扩容的量级应该是【常数】，还是【倍数】？
假设从零开始向数组中连续插入 n = m*I >> 2 个元素
即每 m 次插入数据就要扩容一次，每次扩容延长 I 的长度
连续的扩容操作为：
0、I、2I、3I、...、(m-1)*I 次耗时操作，总和为 O(n^2) 的复杂度，分摊复杂度为 O(n)
>> 分摊的概念，因为此处肯定是连续调用的，所以分摊的复杂度更有意义
也就是当 n 很大的时候，连续插入的操作中，扩容的操作每次就要 O(n)
从直观意义上来看，n 越大，常数扩容的次数是线性的关系
而倍增的话，每次插入 n = 2^m >> 2 个元素
会在第 1, 2, 4, 8, 16,..., 2^m 次扩容，总体耗时 O(n)
分摊给每次扩容只需要 O(1)
直观意义上来讲，n 越大，扩容越大，次数也就相比更小了
所以【倍增】的方式在复杂度上更优，扩容效率上，没有【常数】好，但是至少也有 50% 的使用率

var v = [10, 11, 12, 13, 15, 15, 16, 16, 18, 19]
var target = 16 // 实际要找比 16 刚小的后面的 15
var start = 0, end = 9 // 左右指针
// 向上取整保证左边界不动的情况，中间指针最后能上升到右边界
var getMiddle = (start, end) => start + math.ceil((end - start) / 2)
// loop 1
// [10, 11, 12, 13, 15, <15>, 16, 16, 18, 19]
middle = getMiddle(0, 9) = 5
v[middle] = 15 < target // 目标在右侧
start = middle = 5 // 小于目标值可能是边界，所以左边界移动到中间指针处
// [15, 16, 16, 18, 19]
// loop 2
// [15, 16, <16>, 18, 19]
middle = getMiddle(5, 9) = 7
v[middle] = 16 == target // 等于或者大于，都表示目标（刚好小于那个）在左边
end = middle - 1 = 7 - 1 = 6 // 中间指针当前不是边界，右指针至少在中间指针左侧
// [15, 16]
// loop 3
// [15, <16>]
middle = getMiddle(5, 6) = 6
v[middle] = 16 == target // 目标在左侧
end = middle - 1 = 6 - 1 = 5 //  和 loop 2 相同，右侧指针在中间指针左边
// [15]
// loop 4
// 循环终止
start == end == 5
// 输出判断（找到的这个值的下一个值是目标值，或者找不到）
v[start + 1] == target ? (start +) : -1

// Definition for singly-linked list.
function ListNode(val) {
  this.val = val;
  this.next = null;
}

-           6
-         /   \
-        3     8
-       / \   / \
-      2   4 7   9
前序：6324879
中序：2346789
后序：2437986

preOrderTraverse(cb: Function, node: BinaryTreeNode<T> | null): void {
  if (node == null) return
  cb(node.value) // 访问节点
  preOrderTraverse(cb, node.left) // 遍历左子树
  preOrderTraverse(cb, node.right) // 遍历右子树
}

inOrderTraverse(cb: Function, node: BinaryTreeNode<T> | null): void {
  if (node == null) return
  inOrderTraverse(cb, node.left) // 遍历左子树
  cb(node.value) // 访问节点
  inOrderTraverse(cb, node.right) // 遍历右子树
}

postOrderTraverse(cb: Function, node: BinaryTreeNode<T> | null): void {
  if (node == null) return
  postOrderTraverse(cb, node.left) // 遍历左子树
  postOrderTraverse(cb, node.right) // 遍历右子树
  cb(node.value) // 访问节点
}

preOrderTraverse2(cb: Function, node: BinaryTreeNode<T> | null): void {
  if (node == null) return
  let current = node
  // 遍历/迭代版本，有两个分支，遍历操作没办法同时进入两个分支处理，所以需要记录每个节点
  // 因此非递归的遍历需要用到栈
  let stack = []
  while (current || stack.length > 0) {
    // 左边一直走到最左边，顺路将全部节点先保存，方便回头处理，不然就丢了
    while (current) {
      cb(current.value) // 前序就是不管左右分支，我先输出当前值就是了
      stack.push(current)
      current = current.left
    }
    // 右侧分支可能下面仍然有左右分支，返回最上面即可(没有右分支的话，如果堆栈有，依然可以处理)
    // 一路向上返回就能遍历整个树了
    if (stack.length > 0) {
      let lastStore = stack.pop()
      // cb(current.value) // 如果中序遍历此时输出，下一步进入右侧分支处理
      // 这句的目的是再右侧子树有左树，需要再入栈（开始处理右侧分支了）
      current = lastStore.right
    }
  }
}
postOrderTraverse2(cb: Function, node: BinaryTreeNode<T> | null): void {
  if (node == null) return
  let current = node
  let stack = []
  let lastDeal = null
  // 后序的稍微复杂点，因为涉及到右侧树完成后才能输出
  // 相比上面的，开始处理右侧的时候不推出数据，而是右侧全都处理完才推出。
  // 增加了一个记忆变量，如果刚才处理的是右侧数据，表示右侧处理完了，如果刚才处理的不是，说明右侧还没有处理，其余的和前中序相同
  // 重点在怎么区分右侧树已经处理了，还是需要新进入
  while (current || stack.length > 0) {
    while (current) {
      stack.push(current)
      current = current.left
    }
    if (stack.length > 0) {
      let lastStore = stack[stack.length - 1]
      // 当前的状态是左边树遍历完了，这个时候从堆栈中最后一个判断
      // 一种情况是这个节点右侧是没有压入过堆栈，需要将右侧的重新走收集的流程
      // 另一种是右侧分支弹出，现在这个节点右侧的是上一个弹出的节点 lastDeal 说明右侧的分支已经弹完了，这个节点左右都处理了，可以输出这个根了
      if (lastStore.right && lastStore.right !== lastDeal) current = lastStore.right
      else {
        lastDeal = stack.pop()
        cb(lastDeal)
      }
    }
  }
}

-         8         ->         8
-       /   \                /   \
-      4     10             4     10
-     / \    / \           / \    /
-   (1)  5  9   (11)      3   5  9
-     \
-      3

-        (8)         ->        6           or        9
-       /   \                /   \                 /   \
-      4     10             4     10              4     10
-     / \    / \           / \    / \            / \     \ 
-    1   5  9   11        1   5  9   11         1   5     11
-         \                                          \
-          6                                          6