数据结构的存储方式

数组 顺序存储

随机访问
内容空间一次性分配

链表 链式存储

通过某一元素的前驱和后驱，删除元素或插入元素
不能随机访问
消耗更多的存储空间

基本操作 遍历+访问

种类

线性 for/while
非线性 递归

数组遍历

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

链表遍历

  1. /* 基本的单链表节点 */
  2. class ListNode {
  3.     int val;
  4.     ListNode next;
  5. }
  7. void traverse(ListNode head) {
  8.     for (ListNode p = head; p != null; p = p.next) {
  9.         // 迭代访问 p.val
  10.     }
  11. }
  13. void traverse(ListNode head) {
  14.     // 递归访问 head.val
  15.     traverse(head.next);
  16. }

二叉树遍历

  1. /* 基本的二叉树节点 */
  2. class TreeNode {
  3.     int val;
  4.     TreeNode left, right;
  5. }
  7. void traverse(TreeNode root) {
  8.     traverse(root.left);
  9.     traverse(root.right);
  10. }

建议从树开始刷代码

动态规划解题框架

image.png

思维框架

明确base case —> 明确状态 —》 明确选择 —》定义dp数组

  1. # 初始化 base case
  2. dp[0][0][...] = base
  3. # 进行状态转移
  4. for 状态1 in 状态1的所有取值：
  5.     for 状态2 in 状态2的所有取值：
  6.         for ...
  7.             dp[状态1][状态2][...] = 求最值(选择1，选择2...)

斐波那契数列