Skip to content

Latest commit

 

History

History
28 lines (15 loc) · 1.84 KB

README.md

File metadata and controls

28 lines (15 loc) · 1.84 KB

DataStructureAndAlgorithm

算法实现与刷题代码。文件夹计划分为两个:BlankBoardOnlineExam。前者要求是白板能徒手写出来的水平;而后者题意偏应用,主要针对在线笔试。

题目思路套路及总结

以下内容不分顺序。

DFS

个人将DFS归为一种特殊的递归,大部分情况下DFS相当于暴力解,通过搜索问题的大部分子空间甚至所有子空间,根据根据符合题意的方向不断深入搜索。个人习惯使用的dfs函数有两个重要参数:idxpath,前者指示当前搜索的一个定位,后者表示从初始点到现在为止成功探索出来的路径。注意path不是res,但是可以看做是不完整的res,当满足条件时需要把path转成res或者加到res中去。

DFS在递归调用时通常使用线性访问的顺序来避免访问重复地点。

典型题目:Combination Sum III

BFS

BFS作为DFS的兄弟,同样是通过搜索问题子空间来得到解,不过个人习惯使用队列来实现BFS而不是递归。

典型题目:Friend Circles

Bit Option

题目中最常用的位操作不过于异或移位三中操作。

操作常用于提取某一位的数字,跟$1$相与相当于提取最低位,跟$2$相与相当于提取倒数第$2$位,跟$3$相与相当于提取低两位,以此类推。

异或操作常用来实现取反跟去重。跟$1$异或相当于取反,如$0\oplus{1}=1$、$1\oplus{1}=0$;去重的原理是因为任何数跟自身异或都等于$0$。