算法结构

数据结构的存储方式

• 数据结构的存储方式只有两种:
  • 数组: 顺序存储
  • 链表: 链式存储
    • 散列表, 栈, 队列, 堆, 树, 图都是通过数组和链表的数据结构基础实现的数据结构上层建筑

常用数据结构

• 散列表: 通过散列函数将键映射到一个大数组里
  • 解决散列冲突的方法:
    • 拉链法:
      • 需要链表特性
      • 操作简单
      • 但是需要额外的存储空间存储指针
    • 线性探查法:
      • 需要数据特性
      • 使用数组是为了方便连续寻址
      • 不需要用来存储指针的额外存储空间,但是操作相对复杂一些
• 队列和栈两种数据结构既可以使用数组也可以使用链表实现:
  • 数组: 要处理扩容问题
  • 链表: 没有扩容问题,但是需要更多的内存存储节点指针
• 堆: 堆是一个用数组实现的树
  • 堆是一个完全二叉树
  • 用数组存储不需要节点指针
  • 操作简单
• 树: 常见的树是用链表实现的
  • 不一定是完全二叉树,所以不适合用数组存储
  • 通过链表可以实现不同巧妙设计的树来处理不同的问题:
    • 二叉搜索树
    • AVL树
    • 红黑树
    • 区间树
    • B树
• 图有两种表示方式:
  • 邻接矩阵: 二维数组
    • 判断连通性迅速
    • 可以通过进行矩阵运算来解决相关问题
    • 但是在图比较稀疏的情况下会耗费空间
  • 邻接表: 链表
    • 节省空间
    • 但是图相关操作的效率比邻接矩阵低下

数组和链表比较

数组

• 优点:
  • 数组是紧凑连续存储
  • 可以随机访问
  • 通过索引快速定位元素
  • 相对节约存储空间
• 缺点:
  • 因为数组连续存储,内存空间必须一次性分配足够
  • 如果数组需要需要扩容,则需要重新分配一块更大的空间,再把数据全部复制过去,时间复杂度为O(N)
  • 如果想要在数组中间进行插入和删除,每次必须要移动后面所有的元素以保持连续,时间复杂度为O(N)

链表

• 优点:
  • 链表元素不连续,使用指针指向下一个元素的位置
  • 不存在数组的扩容问题
  • 如果知道某一元素的前驱和后驱,操作指针即可删除该元素或者插入元素,时间复杂度为O(1)
• 缺点:
  • 链表因为存储空间不连续,无法根据一个索引算出对应的元素的地址,所以不能随机访问
  • 每个元素必须存储指向前后元素位置的指针,所以会消耗相对更多的存储空间

数据结构的基本操作

• 数据结构种类很多,目的都是为了在不同的应用场景,尽可能高效地增删改查
• 数据结构的基本操作 : 遍历+访问
• 数据结构的遍历+访问有两种形式:
  • 线性: for-while迭代
  • 非线性: 递归

数组遍历框架

• 线性迭代结构:

void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // 迭代访问arr[i]
    }
}

链表遍历框架

• 既有迭代结构又有递归结构:

/*
 * 基本的单链表节点
 */
 class ListNode {
    int val;
    ListNode next;
 }

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 迭代访问p.val
    }
}

void traverse(ListNode head) {
    // 递归访问 head.val
    traverse(head.next);
}

二叉树遍历框架

• 典型的非线性递归遍历结构:

/*
 * 基本的二叉树节点
 */
 class TreeNode {
    int val;
    TreeNode left, right;
 }

void traverse(TreeNode root) {
    // 递归访问左子节点和右子节点
    traverse(root.left);
    traverse(root.right);
}

• 二叉树的递归遍历方式和链表的递归遍历方式相似,并且二叉树结构和单链表结构也相似
• 二叉树框架可以拓展成为N叉树的遍历框架:

/*
 * 基本的N叉树节点
 */
 class TreeNode {
    int val;
    TreeNode[] children;
 }

 void traverse(TreeNode root) {
    // 递归访问各个子树
    for (TreeNode child : children) {
        traverse(child);
    }
 }

• N叉树的遍历又可以拓展为图的遍历. 因为图就是好几个N叉树的结合体

算法题目

• 数据结构是工具,算法是通过合适的工具解决特定问题的方法:
  • 学习算法之前,需要了解常用的数据结构的特性和缺陷
• 从二叉树题目开始研究算法问题:
  • 二叉树最容易培养框架思维
  • 大部分算法问题,本质上都是树的遍历问题
• 先研究树相关问题,试着从框架上看问题:
  • 基于框架进行抽取和扩展
  • 既可以看别人解法时快速理解核心逻辑
  • 也有助于自己写解法时找到思路方向

二叉树

• 二叉树的基本框架:

void traverse(TreeNode root) {
    // 前序遍历
    ...
    
    traverse(root -> left);
    
    // 中序遍历
    ...

    traverse(root -> right);

    // 后序遍历
    ... 
}

• 题目 : 求二叉树中的最大路径和

int ans = INT_MIN;
int oneSideMax(TreeNode* root) {
  if (root == nullptr) {
      return 0;
  }
  int left = max(0, oneSideMax(root -> left));
  int right = max(0, oneSideMax(root -> right));
  ins ans = max(ans, left + right + root -> val);
  return max(left, right) + root ->val;
}

这就是一个后序遍历

• 题目 : 根据前序遍历和中序遍历的结果还原一棵二叉树

TreeNode buildTree(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
  if (preStart > preEnd || inStart > inEnd) {
      return null;
  }
  TreeNode root = new TreeNode(preOrder[preStart]);
  int inRoot = inMap.get(root -> val);
  int numsLeft = intRoot - inStart;
  root -> left = buildTree(preOrder, preStart + 1, preStart + numsLeft, inOrder, instart, inRoot -1, inMap);
  root -> right = buildTree(preOrder, preStart + numsLeft + 1, preEnd, inOrder, inRoot + 1, inEnd, inMap);
  return root;
}

函数中的多个参数是为了控制数组的索引,本质上该算法就是一个前序遍历

• 题目 : 恢复一棵BST

void traverse(TreeNode* node) {
  if (! node) {
      return;
  }
  traverse(node -> left);
  if (node -> val < prev -> val) {
      s = (s == null) ? prev : s;
      t = node;
  }
  prev = node;
 traverse(node -> right)
}

这就是一个中序遍历

• 可以发现 : 只要涉及递归的问题,都是树的问题

动态规划

• 大部分动态规划问题就是在遍历一棵树:
  • 掌握好树的遍历操作
  • 熟练怎么把思路转换成代码
  • 熟练提取别人解法的核心思路

• 动态规划中的凑零钱问题: 直接的解法就是遍历一棵N叉树

def coinChange(coin: List[int], amount: int):
  def dp(n):
      if n == 0: return 0
      if n < 0: return -1
  
      res = float("INF")
      for coin in coins:
          subproblem = dp(n - coin)
          # 如果子问题无解,则跳过循环
          if subproblem == -1: continue
          res = min(res, 1 + subproblem)
      return res if res != float("INF") else -1
  return dp(amount)

• 这个代码本质上就是一个N叉树的遍历:

def dp(n):
  for coin in coins:
      dep(n - coin)

回溯算法

• 回溯算法就是个N叉树的前后遍历问题

• N皇后问题:

void backTrack(int[] nums, List<Integer> track) {
  if (track.size == nums.length) {
      res.add(new LinkList(track));
      return;
  }
  for (int id= 0; i < nums.length; i ++) {
      if(track.contains(nums[i])) {
          continue;
      }
      track.add(nums[i]);
      // 进入下一层决策树
      backTrack(nums, track);
      track.removeLast();
  }
}

• 这个代码的N叉树遍历框架:

void backTrack(int[] nums, List<Integer> track) {
  for (int i = 0; i < nums.length; i++) {
      backTrack(nums, track);
  }
}

算法框架思维总结

• 数据结构的基本存储方式:
  • 链式
  • 顺序
• 数据结构的基本操作:
  • 增
  • 删
  • 改
  • 查
• 数据结构的遍历方式:
  • 迭代
  • 递归
• 算法题目:
  • 结合框架思维,从树开始研究算法题
  • 理解掌握树的结构之后,再去看回溯算法,动态规划和分治算法