基础的几类算法题

一、Arrays & Linked List

反转列表 https://leetcode-cn.com/problems/reverse-linked-list/
两两交换链表中的节点 https://leetcode-cn.com/problems/swap-nodes-in-pairs/
环形链表 https://leetcode-cn.com/problems/linked-list-cycle/
环形链表 II https://leetcode-cn.com/problems/linked-list-cycle-ii/
K 个一组翻转链表 https://leetcode-cn.com/problems/reverse-nodes-in-k-group/ （待补📌）

二、堆栈 & 队列

image.png

有效的括号 https://leetcode-cn.com/problems/valid-parentheses/
面试题：
用栈实现队列 https://leetcode-cn.com/problems/implement-queue-using-stacks/
用队列实现栈 https://leetcode-cn.com/problems/implement-stack-using-queues/
java中的栈：

Stack<Integer> stack =new Stack<>();
stack.push(1);
stack.peek();
stack.pop();
stack.isEmpty();

java中的队列

Queue<Integer> queue = new Queue<Integer>();
queue.offer(2);
queue.poll();
queue.peek();
queue.isEmpty();

三、优先队列

PriorityQueue 优先队列，正常入，按照优先级出（设置属性来规定优先级）
优先队列的实现机制
方法一：堆（heap）实现，堆也有很多种
方法二：二叉搜索树
面试题：数据流中的第 K 大元素 https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
解题方法的核心：使用堆存储前k个大的元素（可能是解决这种第k系列题目的通用想法？）
面试题：滑动窗口的最大值 https://leetcode-cn.com/problems/sliding-window-maximum/
方法一：使用大顶堆实现
方法二：使用双端队列维护一个严格递增的单调队列

四、映射（Map）&集合（set）

本质：通过hash函数将value映射到某个位置上，实现O(1)查找
实现：HashMap/TreeMap（二叉搜索树），HashSet/TreeSet
有效的字母异位词 https://leetcode-cn.com/problems/valid-anagram/)
两数之和 https://leetcode-cn.com/problems/two-sum/
可以使用双指针，也可以使用HashMap解决
三数之和 https://leetcode-cn.com/problems/3sum/ sort+一层循环+双指针遍历注意对‘不重复’的处理
四数之和 https://leetcode-cn.com/problems/4sum/ 同上

五、树、二叉树、二叉搜索树

二叉搜索树：根节点的值大于左子树，小于右子树
二叉搜索树的性质：中序遍历产生递增序列
验证二叉搜索树 https://leetcode-cn.com/problems/validate-binary-search-tree/
解法：中序遍历结果存储下来验证是否严格递增；或者，每次记录上一个返回的值，在中序遍历中判断是否严格递增
做了一些题目发现，相同的思路下，反而递归的方法又简单、又快
二叉搜索树的最近公共祖先 https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)
解法：谈到二叉搜索树一定和节点的大小关系有关，注意在最近公共祖先处会发生的变化：p、q两点开始分向left、right两边
二叉树的最近公共祖先 https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
解法：递归的思想！！！

六、递归和分治

Pow(x, n) https://leetcode-cn.com/problems/powx-n/ 注意n为负数的情况

七、贪心算法

总是做出对当前环境最优的选择
适用贪心的场景：问题能够分解成子问题来解决，子问题的最优解能够递推到最终问题的最优解。这种子问题最优解称为最优子结构。
买卖股票的最佳时机 II https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

八、广度有限搜索（bfs）与深度优先搜索（dfs）

感觉二叉树的前序遍历有点像深度有限搜索
广度优先搜索：一层一层地搜，可以使用队列来实现，对于树来说，是没有环存在的，但如果是图上的搜索，需要使用一个数组isVisit来记录当前的点是否已经被访问过

public void bfs(Graph graph, Node start, Node end){
       Queue<Node> queue;
       List visited;
       queue.offer(start);;
       visited.add(start);

       while (!queue.isEmpty()){
           Node node = queue.poll();
           visited.add(node);

           process(node);   //对当前元素进行处理
           nodes=generate_related_nodes(node);//获取node节点的相关后续节点，且他们没有被访问过
           queue.push(nodes);
       }

       //other processing work
   }

深度优先搜索可以使用递归或者栈来实现

#使用递归的方法（常用）
#伪代码
visited = set()
def dfs(node, visited):
  visited.add(node)
  #处理过程
  for next_node in node.children():
    if not next_node in visited:
      dfs(next_node, visited)

#使用迭代（栈）的方法
def dfs(self, tree):
  if tree.root is None:
    return []
  visited, stack = [], [tree.root]
  while stack:
    node  = stack.pop()
    visited.add(node)

    process(node)
    nodes = generate_related_nodes(node) #没有被访问过的子节点
    stack.push(nodes)

二叉树的层序遍历 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
采用bfs来解决，每次将栈中的全部元素poll即为该层的元素，然后在poll的过程中将其孩子节点offer进去
二叉树的最大深度 https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
递归，dfs
二叉树的最小深度 https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
一定要注意读题，看其对最小深度的定义
可以使用递归的方法，也可以使用bfs，每层遍历的过程中判断是否为叶子节点来断定是否停止；也可以使用dfs的方法
括号生成 https://leetcode-cn.com/problems/generate-parentheses/
① 做题时的误区：想要找到一种从n-1对括号生成n对括号的方法，但是总是会有重复的，然后就陷入了找去重方法的死循环中，及时后来想搜索来解决，还是在思考去重的问题
② 但搜索根本不会产生重复的组合方式，搜索的本质是一种枚举，可以产生所有的组合方式，搜索配合剪枝才是正确的解决思路
③ 判断括号是否合法：任何一个时刻左括号的数量要大于等于右括号的数量

九、剪枝

剪枝是搜索中经常用到的优化策略，关键在于重复的步骤如何进行有效的标记和判定
N 皇后 https://leetcode-cn.com/problems/n-queens/
N皇后 II https://leetcode-cn.com/problems/n-queens-ii/
N皇后问题的重点在于剪枝，使用空间换时间的方式，使用一些数组或者set来标识当前位置是否已经是禁用位置，巧妙的地方是对斜线位置的处理：对于位置[i][j]，可以通过i+j和i-j的唯一性确定其位于哪两条斜线上
有效的数独 https://leetcode-cn.com/problems/valid-sudoku/ 双层循环模拟即可
解数独 https://leetcode-cn.com/problems/sudoku-solver/ 双层循环DFS，开辟额外的空间用于判断当前可供选择的值以及用来判断是否合法

十、二分查找

前提条件：sorted（单调递增或者递减）；bounded（存在上下界）；accessible by index（能够通过索引访问）
x 的平方根 https://leetcode-cn.com/problems/sqrtx/
两种解法：二分；牛顿迭代法
题目中要求输出的结果的整数部分即可，可以尝试将代码写全，输出指定精度的结果

@Test
    public void test5(){
        int num=1;
        while (num!=-1){
            Scanner in = new Scanner(System.in);
            num = in.nextInt();
            System.out.println(mySqrt(num,0.0001));
        }

    }
    public double mySqrt(int num, double accuracy){
        double left = 0;
        double right = num;
        while(right>=left){
            double middle = (left+right)/2;
            if(Math.abs(middle*middle-num)<=accuracy) return middle;
            if(middle*middle>num) right=middle;
            else left=middle;
        }
        return -1;
    }

十一、字典树（Trie）

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计
优点：最大限度地减少无谓的字符串比较，查询效率比哈希表高
Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的
Trie树使用一条边来代表一个字母，单词的长度和寻找该单词找过的路径的长度相同

字典树的结构
字典树的基本数据结构

字典树的数据结构
实现 Trie (前缀树) https://leetcode-cn.com/problems/implement-trie-prefix-tree/

public class Trie {
    class TrieNode{
        TrieNode[] next;
        boolean isEnd;

        public TrieNode(){
            isEnd=false;
            next = new TrieNode[26];
        }
    }

    private TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode node = root;
        for(char c : word.toCharArray()){
            if(node.next[c-'a']==null){
                node.next[c-'a']=new TrieNode();
            }
            node = node.next[c-'a'];
        }
        node.isEnd=true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = root;
        for(char c : word.toCharArray()){
            node = node.next[c-'a'];
            if(node == null) return false;

        }
        return node.isEnd;

    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for(char c : prefix.toCharArray()){
            node = node.next[c-'a'];
            if(node == null) return false;

        }
        return true;
    }
}

单词搜索 https://leetcode-cn.com/problems/word-search/
dfs+回溯即可解决
单词搜索 II https://leetcode-cn.com/problems/word-search-ii/)
相当于在上一个题的基础上，一次要判断多个单词，先把所有的单词构建成一棵Trie树，然后DFS判断单次是否在矩阵中可以找到（待补📌）

十二、位运算

异或的一个重要特征，x^x=0
位运算的常用操作：
x&1 == 0 x&1==1 用来判断奇偶
x=x&(x-1) 清零最低位的1
x&-x 得到最低位的1
✅位运算经常用在数1的个数相关的题目中
位1的个数 https://leetcode-cn.com/problems/number-of-1-bits/
用上面的式子就可以很好的解决
2的幂 https://leetcode-cn.com/problems/power-of-two/ 做法同上
比特位计数 https://leetcode-cn.com/problems/counting-bits/
合理利用前面已经算出来的结果（dp+位运算）
N皇后 II https://leetcode-cn.com/problems/n-queens-ii/
之前的方法是使用数组（col[]、pie[]、na[]）来记录位置的占用情况，这里借助位运算，使用三个int类型的数值进行记录，col比较好理解占用的位置置1即可，对于int类型的pie和na实际上记录的是当前行的每个位置上的元素是否在之前结果的对角线方向上，转换到新行的时候，pie左移，na右移

public class Queens {
    int res= 0;
    public int totalNQueens(int n) {
        if(n<=0) return 0;
        dfs(n,0,0,0,0);
        return res;
    }
    public void dfs(int n, int row, int col, int pia, int na){
        if(row==n){
            res+=1;
            return;
        }
//计算当前可用的位置，注意使用的是32位的int，要消除n位之前的那些0对bits的影响
        int bits = (~(col|pia|na))&((1<<n)-1);
        while (bits!=0){
//获取当前选定的1的位置
            int pos= bits&(-bits);
            dfs(n,row+1,col|pos,(pia|pos)<<1,(na|pos)>>1);
//去掉最后一个1
            bits=bits&(bits-1);
        }

    }
}

写位运算的公式的时候，一定要使用括号，因为它的运算优先级较低，防止出现错误

十三、动态规划

🧡通过递归+记忆化来推导出动态规划的方法
状态的定义
状态转移方程，如何初始化也很重要，一般都是初始化第一行
最优子结构
不同路径 https://leetcode-cn.com/problems/unique-paths/ 数学方法即可解决
不同路径 II https://leetcode-cn.com/problems/unique-paths-ii/ 动态规划，注意特例（起始点和重点是障碍的情况）
爬楼梯 https://leetcode-cn.com/problems/climbing-stairs/
三角形最小路径和 https://leetcode-cn.com/problems/triangle/
乘积最大子数组 https://leetcode-cn.com/problems/maximum-product-subarray/
关于买卖股票的题目
买卖股票的最佳时机 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
买卖股票的最佳时机 II https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
买卖股票的最佳时机 III https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
买卖股票的最佳时机 IV https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
最佳买卖股票时机含冷冻期 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
买卖股票的最佳时机含手续费 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
扩展情况：由于题目中要求不能同时持有多股，所以第三维只有0和1两种情况（持有或者没有），但是如果允许最多同时持有k股的话，最后一维有k种，同样要再多一维循环来进行表示
如果能够正确的对状态进行定义，那么就算是成功了一半；从上面的系列题目，可以考虑下面的方法：
方法一：从dp[i]一维开始考虑，表示以i为终点，结果的情况。枚举每一个可能执行的动作以及产生的结果，考虑执行这个动作对之前的状态有什么样的要求？需要什么样的辅助信息（状态）？此时可能会发现一维的dp不能满足要求，此时根据需要的赋值信息进行维度的扩充即可
方法二：先思考递归的方法，从递归方法种找灵感
最长递增子序列 https://leetcode-cn.com/problems/longest-increasing-subsequence/
一共三种方法：暴力dfs寻找；dp；维护一个最长上升子序列的数组
零钱兑换 https://leetcode-cn.com/problems/coin-change/
最好的思考过程：先想如何递归解决，然后转化为动态规划
（经常用到的方法：考虑最后一步采用什么样的动作，然后再思考用不用添加额外的维度来存储需要的信息）

十四、并查集

之前看过了，也做了笔记 https://www.jianshu.com/p/a380c8ad5b88

岛屿数量 https://leetcode-cn.com/problems/number-of-islands/ DFS或者并查集

十五、LRU Cache

LRU（Least Recently used）最近最少使用，一半使用双向链表来实现，O(1)实现查询（第一个）、修改和更新

image.png
LRU 缓存机制 https://leetcode-cn.com/problems/lru-cache/
需要使用HashMap，然后自己实现一个双向链表。使用虚拟的头尾节点会更容易解决问题

布隆过滤器（Bloom Filter）

一个很长的二进制向量和一个映射函数
布隆过滤器用于检索一个元素是否在集合中，如果判断不在，则该元素一定不在集合中；如果判断在，则该元素有一定的几率不在集合中
*优点：空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难

image.png
filter的作用与缓存类似，在查询之前加了一步筛选的操作，挡掉一些对不存在的元素的查询。与cache相同，后边都要跟一个真正的存储系统

基础的几类算法题

一、Arrays & Linked List

二、堆栈 & 队列

三、优先队列

四、映射（Map）&集合（set）

五、树、二叉树、二叉搜索树

六、递归和分治

七、贪心算法

八、广度有限搜索（bfs）与深度优先搜索（dfs）

九、剪枝

十、二分查找

十一、字典树（Trie）

十二、位运算

十三、动态规划

十四、并查集

十五、LRU Cache

布隆过滤器（Bloom Filter）

推荐阅读更多精彩内容