算法学习笔记

# 总览

7 个数据结构：

• 数组
• 链表
• 栈
• 队列
• 哈希表
• 二叉树
• 堆

10 个算法：

• 递归
• 排序
• 二分查找
• 搜索
• 哈希算法
• 贪心算法
• 分治算法
• 回溯算法
• 动态规划
• 字符串匹配算法

# 数据结构的基本操作

数据结构的基本操作包括：增删查改，即遍历和访问。

数据结构的遍历和访问的两种形式：线性、非线性，线性以 for/while 迭代为代表，非线性以递归为代表。

1. 数组遍历框架（线性迭代）：

   void traverse(vector<int> arr){
       for(int i = 0; i < arr.size(); i++){
           // 迭代访问每个元素arr[i]
       }
   }
   
   void traverse(vector<int> arr){    
       for(auto &i : arr){
           // 迭代访问每个元素i
       }
   }
   

2. 链表遍历框架（迭代或者递归）：

   // 基本的单链表节点
   class ListNode {
       public:
           int val;
           ListNode *next;
   };
   
   void traverse(ListNode head){
       for(ListNode *p = heda; p != nullptr; p = p->next){
           // 迭代访问 p->val
       }
   }
   
   void traverse(ListNode head){
       traverse(head->next);
   }
   

3. 二叉树遍历框架，典型的非线性递归遍历结构：

   // 基本的二叉树节点
   struct TreeNode {
       int val;
       TreeNode* left;
       TreeNode* righe;
   };
   
   void traverse(TreeNode* root) {
       // 递归访问二叉树每个节点root
       traverse(root->left):
       traverse(root->right);
   }
   

4. 二叉树扩展为 N 叉树遍历结构：

   // 基本的 N 叉树节点
   class TreeNode {
       int val;
       vector<TreeNode*> children;
   };
   
   void traverse(TreeNode *root) {
       // 递归访问 N 叉树每个节点
       for (TreeNode *child : root->children)
           traverse(child);
   }
   

# 刷题顺序：

1. 数组、链表相关：单链表翻转、前缀和数组、二分搜索等基础算法。

2. 二叉树。

3. 回溯，动态规划、回溯算法等面试常考。

# 二叉树框架

void traverse(TreeNode *root) {
    // 前序位置
    traverse(root->left);
    // 中序位置
    traverse(root->right);
    // 后序位置
}