数据结构框架思维

数据结构框架思维

数据结构的存储方式只有两种：数组和链表，其余都可以用这两种数据结构实现

• 数组：顺序存储
• 链表：链式存储

思维方式：

• 自顶向下
• 自底向上
• 从抽象到具体
• 子问题拆分

数组遍历框架

function traverseArr(arr) {
  for (let i = 0; i < arr.length; i++) {
    // todo
  }
}

链表遍历框架

• 迭代法：

function traverseLinkedList(head) {
  for (let p = head; p !== null; p = p.next) {
    // todo
  }
}

function traverseLinkedList(head) {
  let p = head;
  while (p !== null) {
    // todo

    p = p.next;
  }
}

• 递归法：

function traverseLinkedList(head) {
  let p = head;
  if (p === null) {
    return;
  }

  // todo
  p = p.next;
  traverseLinkedList(p)
}

树遍历框架

// 二叉树
function traverseTree(root) {
  // 前序遍历位置
  traverse(root.left);
  // 中序遍历位置
  traverse(root.right);
  // 后序遍历位置
}

// N叉树
function traverseNTree(root) {
  // 前序遍历位置
  for (let child of root.children) {
    traverseNTree(root)
  }
  // 后序遍历位置
}

• 前序遍历

  function preorder(root) {
      traverse(root);
      traverse(root.left)
      traverse(root.right)
  }
  

• 中序遍历

  function inorder(root) {
      traverse(root.left);
      traverse(root);
      traverse(root.right)
  }
  

• 后序遍历

  function postorder(root) {
      traverse(root.left);
      traverse(root.right);
      traverse(root);
  }
  

递归

归去来兮

function recursion(level, params) {
  // 递归终止条件
  if (level > MAX_LEVEL) {
    process_result
    return
  }

  // 处理当前层逻辑
  process(level, data)

  // 递归调用下一层
  recursion(level + 1, newParams)

  // 清理当前层
}

二分查找

// 普通二分查找
function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid
    } else if (arr[mid] < target) {
      left = mid + 1
    } else if (arr[mid] > target) {
      right = mid - 1
    }
  }

  return -1
}

// 搜索左侧边界的二分查找
function leftBoundBinarySearch1(arr, target) {
  let left = 0, right = arr.length;

  while (left < right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      right = mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else if (arr[mid] > target) {
      right = mid;
    }
  }

  return arr[left] === target ? left : -1
}

function leftBoundBinarySearch2(arr, target) {
  let left = 0, right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      right = mid - 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else if (arr[mid] > target) {
      right = mid - 1;
    }
  }

  if (left >= arr.length || arr[left] !== target) {
    return -1;
  }

  return left
}


// 搜索右侧边界的二分查找
function rightBoundBinarySearch1(arr, target) {
  let left = 0, right = arr.length;

  while (left < right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      left = mid + 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else if (arr[mid] > target) {
      right = mid;
    }
  }
  if (left == 0) return -1;

  return arr[left - 1] === target ? (left - 1) : -1;
}

function rightBoundBinarySearch2(arr, target) {
  let left = 0, right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      left = mid + 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else if (arr[mid] > target) {
      right = mid - 1;
    }
  }
  if (right < 0 || arr[right] !== target) return -1;

  return right;
}

位运算

位运算 (opens new window)

异或运算 ^
A 和 B 数据交换
A = A ^ B
B = A ^ B
A = A ^ B

提取数字二进制中最右侧的1
C & (~C + 1)

消除右侧的1
x & (x - 1 )

JS二进制操作
按位取反：~D


随机数：
[0, 1）: Math.random()
[0, N）： Math.random()*N
[0, N-1]: ~~Math.random()*N