算法Day01-算法研习指导之算法框架思维

淡淡的烟草味﹌ 2023-02-18 09:40 72阅读 0赞

### 算法框架思维 ###

*  数据结构的存储方式
 *   *   *  常用数据结构
         *  数组和链表比较
         *   *   *  数组
                 *  链表
 *  数据结构的基本操作
 *   *   *  数组遍历框架
         *  链表遍历框架
         *  二叉树遍历框架
 *  算法题目
 *   *   *  二叉树
         *  动态规划
         *  回溯算法
 *  算法框架思维总结

# 数据结构的存储方式 #

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

### 常用数据结构 ###

*  **散列表:** 通过散列函数将键映射到一个大数组里
    
     *  **解决散列冲突的方法:**
        
         *  **拉链法:**
            
             *  需要链表特性
             *  操作简单
             *  但是需要额外的存储空间存储指针
         *  **线性探查法:**
            
             *  需要数据特性
             *  使用数组是为了方便连续寻址
             *  不需要用来存储指针的额外存储空间,但是操作相对复杂一些
 *  **队列和栈两种数据结构既可以使用数组也可以使用链表实现:**
    
     *  **数组:** 要处理扩容问题
     *  **链表:** 没有扩容问题,但是需要更多的内存存储节点指针
 *  **堆:** 堆是一个用数组实现的树
    
     *  堆是一个**完全二叉树**
     *  用数组存储不需要节点指针
     *  操作简单
 *  **树:** 常见的树是用链表实现的
    
     *  不一定是完全二叉树,所以不适合用数组存储
     *  通过链表可以实现不同巧妙设计的树来处理不同的问题:
        
         *  **二叉搜索树**
         *  **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);
>     	}
>     }

# 算法框架思维总结 #

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