10.12 面试常见的十大算法

涵盖的主题包括：
*1）字符串/数组/矩阵，2）链表，3）树，4）堆，5）图，6）排序，7）动态编程，8）位操作，9）组合和排列，和10）数学问题。
*如果您需要简要回顾一下Java基础知识，我强烈建议您首先阅读“Simple Java”。如果要查看显示如何使用常用API的代码示例，可以使用JavaSED.com。

1.字符串/数组

算法问题的输入通常是字符串或数组。如果没有自动完成任何IDE，则应记住以下方法。

toCharArray() //get char array of a String
charAt(int x) //get a char at the specific index
length() //string length
length //array size 
substring(int beginIndex) 
substring(int beginIndex, int endIndex)
Integer.valueOf()//string to integer
String.valueOf()/integer to string
Arrays.sort()  //sort an array
Arrays.toString(char[] a) //convert to string
Arrays.copyOf(T[] original, int newLength)
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

经典问题： -
两个指针 -
1）旋转数组，字符串中的反向字
2）评估反向波兰表示法（堆栈）
3）同构字符串
4）字梯（BFS），字梯II（BFS）
5）中位数两个排序的数组
5）数组中的Kth最大元素
6）通配符匹配，正则表达式匹配
7）合并间隔，插入间隔
9）两个和，两个和II，两个和III，3Sum，4Sum
10）3Sum最近
11）字符串到整数
12）合并排序数组
13）有效括号
13）最长有效括号
14）实现strStr（）
15）最小尺寸子阵列和
16）搜索插入位置
17）最长连续序列
18）有效回文
19）之字形转换
20）添加二进制
21）最后一个字的长度
22 ）三角形
24）包含重复：I，II，III
25）从排序数组中删除重复：I，II，删除元素，移动零
27）最长子串而不重复字符
28）包含2个唯一字符的最长子字符串 [Google]
28）具有所有单词串联的子串
29）最小窗口子串
31）在旋转排序阵列中找到最小值：I，II
32）在旋转阵列中搜索：I，II
33）最小叠加
34）多数元素：I，II
35）公牛和奶牛
36）直方图中最大的矩形
37）最长的共同前缀 [谷歌]
38）最大的数字
39）简化路径
40）比较版本号
41）加油站
44）帕斯卡的三角形：I，II
45）容器与大多数水
45）糖果 [谷歌]
45）捕获雨水
46）计数和说
47）搜索范围
48）基本计算器，基本计算器II
49）组Anagrams
50）最短回文
51）矩形区域
52）汇总范围
53）增加三联体子序列
54）使用目标数字列表和算术运算
55）字符串的反向元音
56）翻转游戏，翻转游戏II
57）缺少数字，找到重复的数字，第一个缺失的正数
58）有效Anagram，组移位字符串
59）Top K常用元素
60）查找峰值元素
61）字模式，Word模式II
62）H指数，H指数II
63）回文对
64）一个编辑距离
65）争夺字符串
66）第一个坏版本
67）整数到英文单词
68）文本对齐
69）删除无效括号
70）交叉点的两个阵列，两个阵列II交叉口
71）滑动窗口最大，从数据流移动平均
72）猜数更高或更低

2.矩阵

解决矩阵相关问题的常用方法包括DFS，BFS，动态规划等。

经典问题：
1）设置矩阵零
2）螺旋矩阵
2）螺旋矩阵II
3）搜索2D矩阵
3）搜索2D矩阵II
4）旋转图像 [Palantir]
5）有效数独
6）最小路径和（DP） [谷歌]
7）独特路径（DP） [谷歌]
7）独特路径II（DP）
8）岛屿数量（DFS / BFS），岛屿数量II（不相交集合），无向图中的连通分量数量
9）环绕区域（BFS）
10）最大矩形
10）最大平方
11）单词搜索（DFS）
11）单词搜索II
13）范围总和查询2D - 不可变
14）矩阵中最长的路径（DFS）
15）所有建筑物的最短距离
16）生命游戏
17）油漆屋，油漆屋II
18）数独求解器（DFS）
19）墙和门（DFS / BFS）
20） Tic-Tac-Toe
21）最佳会面点

3.链接列表

在Java中，链表的实现非常简单。每个节点都有一个值和到下一个节点的链接。

class Node {
    int val;
    Node next;
 
    Node(int x) {
        val = x;
        next = null;
    }
}

链表的两个流行应用是堆栈和队列。

class Stack{
    Node top; 
 
    public Node peek(){
        if(top != null){
            return top;
        }
 
        return null;
    }
 
    public Node pop(){
        if(top == null){
            return null;
        }else{
            Node temp = new Node(top.val);
            top = top.next;
            return temp;    
        }
    }
 
    public void push(Node n){
        if(n != null){
            n.next = top;
            top = n;
        }
    }
}

Queue:

class Queue{
    Node first, last;
 
    public void enqueue(Node n){
        if(first == null){
            first = n;
            last = first;
        }else{
            last.next = n;
            last = n;
        }
    }
 
    public Node dequeue(){
        if(first == null){
            return null;
        }else{
            Node temp = new Node(first.val);
            first = first.next;
            return temp;
        }   
    }
}

Java标准库包含一个名为“ Stack ” 的类。Java SDK中的另一个类是LinkedList，它可以用作队列（add（）和remove（））。（LinkedList实现了Queue接口。）如果在访问期间需要堆栈或队列来解决问题，则可以使用它们。
经典问题：
0）使用数组实现堆栈
1）添加两个数字
2）重新排序列表
3）链接列表循环
4）使用随机指针复制列表
5）合并两个排序列表
6）奇数偶数链接列表
7）从排序中删除重复项列表
7）从排序列表II中删除重复项
8）分区列表
9）LRU高速缓存
10）两个链接列表的交集
11）删除链接列表元素
12）交换节点对
13）反向链接列表，反向链接列表II，打印链接列表反转顺序
14）从列表末尾删除第N个节点（快速慢指针）
15）使用队列实现堆栈
15）使用堆栈实现队列
16）Palindrome链接列表
17）使用数组实现队列
18）删除链接列表中的
节点19）k-Group中的反向节点

4.Tree, Heap and Trie

树通常是指二叉树。每个节点包含一个左节点和右节点，如下所示：

class TreeNode{
    int value;
    TreeNode left;
    TreeNode right;
}

以下是与树有关的一些概念：

• 二进制搜索树：对于所有节点，左子节点<=当前节点<=右子节点
• 平衡与不平衡：在平衡树中，每个节点的左右子树的深度相差1或更小。
• 完整二叉树：叶子以外的每个节点都有两个子节点。
• 完美二叉树：完整的二叉树，其中所有叶子处于相同的深度或相同的水平，并且每个父亲都有两个孩子。
• 完整二进制树：一个二叉树，其中除了可能是最后一个级别之外，每个级别都被完全填充，并且所有节点都尽可能地左节点。
  Heap是一种专门的基于树的数据结构，它满足堆属性。其操作的时间复杂性很重要（例如，find-min，delete-min，insert等）。在Java中，PriorityQueue非常重要。

4.1树

1）二叉树的遍历：预订，中序，后序，级订单，级订单II，垂直顺序
2）反向二进制树
3）第K在BST最小元素
4）二叉树最长连续序列
5）确认二叉搜索树
6）拼合二叉树到链表
7）路径和（DFS或BFS）
7）路径和（II）（DFS）
8）从顺序和后序遍历
构造二叉树8）从预序和顺序遍历构造二叉树
9）将排序数组转换为二进制搜索Tree [Google]
10）将排序列表转换为二叉搜索树[Google]
11）二叉树的最小深度
12）二叉树最大路径和*
13）平衡二叉树
14）对称树
15）二叉搜索树迭代器
16）二叉树右侧视图
17）二进制搜索树的最低公共祖先
18）二叉树的最低公共祖先
19）验证二进制树的预序序列化
20）在每个节点中填充下一个右指针
21）在每个节点中填充下一个右指针II）
21）唯一二进制搜索树（DP）
21）唯一二进制搜索树II（DFS）
22）根与叶数的总和（DFS）
23）计算完整的树节点
24）最近的二进制搜索树值
25）二叉树路径
26）二进制树的最大深度
27恢复二进制搜索树
28）相同的树
29）序列化和反序列化二进制树
30）在BST中的顺序继承者
31）找到二叉树的叶子
32）最大的BST子树

4.2堆

1）合并k个排序的数组 [Google]
2）合并k个排序列表*
3）从数据流中找到中位数
4）会议室II，会议室
5）范围增加

4.3 Trie

1）实现Trie（前缀树）
2）添加和搜索Word - 数据结构设计（DFS）

4.4段树

1）范围总和查询 - 可变
2）天际线问题