代码面试最常用的10大算法

摘要：

面试也是一门学问，在面试之前做好充分的准备则是成功的必须条件，而程序员在代码面试时，常会遇到编写算法的相关问题，比如排序、二叉树遍历等等。

在程序员的职业生涯中，算法亦算是一门基础课程，尤其是在面试的时候，很多公司都会让程序员编写一些算法实例，例如快速排序、二叉树查找等等。

这篇文章总结了编码采访中的常见主题，包括_1）字符串/数组/矩阵，2）链表，3）树，4）堆，5）图，6）排序，7）动态编程，8）位操作， 9）组合和排列，以及10）数学。_将问题归为一类总是不容易的，因为问题可能属于多个类别。

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，Remove Element，移动零
 27）最长的子字符串而不重复字符
 28）包含2个唯一字符的最长的子字符串 [Google]
28）具有所有单词串联的子串
 29）最小窗口子串
31）在旋转排序数组中找到最小值：I，II
32）在旋转数组中搜索：I，II
33）最小堆栈
34）多数元素：I，II
35）公牛和母牛
 36）直方图中最大的矩形
 37）最长的公共前缀 [Google]
38）最大的数字
 39）简化路径
 40）比较版本号
 41）加油站
44）帕斯卡三角形：I，II
45）装满水的容器
 45）糖果 [谷歌]
45）诱捕雨水
 46）数数并说
 47）搜索范围
 48）基本计算器，基本计算器II
49）组字母图
 50）最短回文
 51）矩形区域
 52）摘要范围
 53）增加三重态子序列
 54）使用目标数字列表和算术运算
 55）字符串的反元音
 56）翻转游戏，翻转游戏II
57）缺少数字，找到重复的数字，第一个缺少正数
 58）有效字谜，组移位的字符串
 59）前K个常见元素
 60）查找峰值元素
 61）字模式，字型II
62）H-Index，H-Index 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） [ Google]
7）唯一路径（DP） [Google]
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）井字游戏
 21）最佳集合点

3.链表

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

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

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

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）回文链接列表
 17）使用数组实现队列
 18）链接列表中的删除节点
 19）k组中的反向节点

4.树，堆和树

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

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

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

二进制搜索树：对于所有节点，左子节点<=当前节点<=右子节点
平衡与不平衡：在平衡树中，每个节点的左右子树的深度相差1或更小。
完整的二叉树：除叶子外的每个节点都有两个孩子。
完美二叉树：完整的二叉树，其中所有叶子处于相同深度或相同级别，并且每个父级都有两个子级。
完整的二叉树：一个二叉树，其中每个级别（除了最后一个级别）都已完全填充，并且所有节点都尽可能地靠左

堆是满足堆属性的基于树的专用数据结构。其操作的时间复杂度很重要（例如，find-min，delete-min，insert等）。在Java中，必须了解PriorityQueue。

4.1树

1）二叉树的遍历：预订，中序，后序，级订单，级订单II，垂直顺序
 2）反转二叉树
 在BST 3）第K个最小元素
 4）二叉树最长连续序列
 5）确认二叉搜索树
 6）平铺二叉树到链表
 7）路径总和（DFS或BFS）
7）路径总和II（DFS）
8）从有序和后序遍历
 构造二叉树8）从有序和有序遍历构造二叉树
 9）将排序的数组转换为二叉搜索树 [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特里

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

4.4段树

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

5.图

与图相关的问题主要集中在深度优先搜索和呼吸优先搜索。深度优先搜索非常简单，您可以从根节点开始遍历所有邻居。

以下是图形和呼吸优先搜索的简单实现。关键是使用队列存储节点。

Define a GraphNode

class GraphNode{ 
	int val;
	GraphNode next;
	GraphNode[] neighbors;
	boolean visited;
 
	GraphNode(int x) {
		val = x;
	}
 
	GraphNode(int x, GraphNode[] n){
		val = x;
		neighbors = n;
	}
 
	public String toString(){
		return "value: "+ this.val; 
	}
}

Define a Queue

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

Breath First Search uses a Queue

public class GraphTest {
 
	public static void main(String[] args) {
		GraphNode n1 = new GraphNode(1); 
		GraphNode n2 = new GraphNode(2); 
		GraphNode n3 = new GraphNode(3); 
		GraphNode n4 = new GraphNode(4); 
		GraphNode n5 = new GraphNode(5); 
 
		n1.neighbors = new GraphNode[]{n2,n3,n5};
		n2.neighbors = new GraphNode[]{n1,n4};
		n3.neighbors = new GraphNode[]{n1,n4,n5};
		n4.neighbors = new GraphNode[]{n2,n3,n5};
		n5.neighbors = new GraphNode[]{n1,n3,n4};
 
		breathFirstSearch(n1, 5);
	}
 
	public static void breathFirstSearch(GraphNode root, int x){
		if(root.val == x)
			System.out.println("find in root");
 
		Queue queue = new Queue();
		root.visited = true;
		queue.enqueue(root);
 
		while(queue.first != null){
			GraphNode c = (GraphNode) queue.dequeue();
			for(GraphNode n: c.neighbors){
 
				if(!n.visited){
					System.out.print(n + " ");
					n.visited = true;
					if(n.val == x)
						System.out.println("Find "+n);
					queue.enqueue(n);
				}
			}
		}
	}
}

Output:

value: 2 value: 3 value: 5 Find value: 5
value: 4

经典问题：
1）复制图表
 2）课程表，课程表II，最小身高树
 3）重建行程
 4）图有效树

6.排序

不同排序算法的时间复杂度。您可以转到Wiki来查看它们的基本概念。

Algorithm	Average Time	Worst Time	Space
Bubble sort	n^2	n^2	1
Selection sort	n^2	n^2	1
Insertion sort	n^2	n^2
Quick sort	n log(n)	n^2
Merge sort	n log(n)	n log(n)	depends

要看

* BinSort，Radix Sort和CountSort与其他假设使用不同的假设集，因此它们不是“常规”排序方法。（感谢Fidel指出这一点）

这是一些实现/演示，此外，您可能想了解Java开发人员在实践中的排序方式。
1）Mergesort
2）Quicksort
3）InsertionSort。
4）最大间隙（桶排序）
5）颜色排序（计数排序）

7.动态编程

动态编程是一种用于解决具有以下属性的问题的技术：

使用较小实例的解决方案来解决实例。
对于较小实例的解决方案可能需要多次。
较小实例的解决方案存储在表中，因此每个较小实例仅解决一次。
额外的空间用于节省时间。

？
攀登台阶的问题完全适合这4个属性。因此，可以通过使用动态编程来解决。

public static int[] A = new int[100];
 
public static int f3(int n) {
	if (n <= 2)
		A[n]= n;
 
	if(A[n] > 0)
		return A[n];
	else
		A[n] = f3(n-1) + f3(n-2);//store results so only calculate once!
	return A[n];
}

经典问题：
1）编辑距离
 1）不同的
 子序列总数 2）最长的回文子串
 3）断字
 3）断字II
4）最大子数组
 4）最大乘积子数组
 5）回文分区
 5）回文分区II
6）强盗 [Google ]
6）抢劫犯II
6）抢劫犯III
7）跳跃游戏
 7）跳跃游戏II
8）最佳买卖股票
 时间8）最佳买卖股票
 时间 II 8）最佳买卖股票时间III
8 ）买卖股票IV的最佳时间
 9）地下城游戏
 10）最小路径总和
 11）唯一路径
 12）解码方式
 13）最长的公共
 子序列14）最长的公共子串
 15）最长的增长子序列
 16）硬币找零
 17）完美正方形

8.位操作

位运算符：
| OR (|) | AND (&) | XOR (^{) | Left Shift (<<) | Right Shift (>>) | Not (~) |

|-----------|-----------|-----------|-------------------|--------------------|-----------|

| 1|0=1 | 1&0=0 | 1}0=1 | 0010<<2=1000 | 1100>>2=0011 | ~1=0 |

得到第i个给定数字n。（我从0开始计数，从右开始）

public static boolean getBit(int num, int i){
	int result = num & (1<<i);
 
	if(result == 0){
		return false;
	}else{
		return true;
	}
}

例如，获取数字10的第二位。

i=1, n=10
1<<1= 10 1010&10=10 10 is not 0, so return true;

经典问题：
1）单个数字
 1）单个数字II
2）最大二进制间隙
 3）1个位数
 4）反转位
 5）重复的DNA序列
 6）数字范围的按位与
 7）两个整数的总和
 8）计数位
 9 ）字长的最大乘积
 10）格雷码

9.组合和排列

组合和排列之间的区别在于顺序是否重要。

范例1：

给定5个数字-1、2、3、4和5，打印出5个数字的不同顺序。4不能是第三个，3和5不能相邻。有多少种不同的组合？

范例2：

给定5个banaba，4个梨和3个苹果，假设一种水果是相同的，那么有多少种不同的组合？

类问题：
1）排列
 2）排列II
3）排列序列
 4）生成括号
 5）组合和（DFS），II（DFS），III（DFS），IV（DP）
6）组合（DFS）
7）字母组合电话号码（DFS）
8）恢复IP地址
 9）因素组合（DFS）

10.数学

解决数学问题通常需要我们从观察中找到规律性或重复模式。如果您没有任何想法，请首先列出一小部分数字的结果。

1）反转整数
 2）回文编号
3）的Pow（X，N），两个功率，三个功率，四电源
 4）亚群
 5）亚群II
6）馏分循环小数（谷歌）
7）的Excel工作表列号
 8）Excel工作表列标题
 9）因子尾随零
 10）快乐数
 11）计数素数
 12）加上1
13）除以两个整数
 14）乘以字符串
 15）一行上的最大点
 16）数组乘积（自我除外
 ）17）整数中断
 18）添加数字
 21）丑数，9 丑数II，超级丑数，求和最小的K对

更新：我决定在下面添加更多类别。

11. HashMap

1）最短单词距离II

附加问题：
1）自穿越
 2）修补阵列
 3）尼姆游戏
 4）灯泡切换器
 5）止痛栅栏
 6）嵌套列表权重总和

其他资源
1. 将您的代码共享到Github / BitBucket

菜单

分享

代码面试最常用的10大算法

摘要：

相关文章：

评论

第四章：实现 Servlet 容器的基本功能-MiniTomcat系列

MiniTomcat 项目大纲

打造属于你的 MiniTomcat：深入理解 Web 容器核心架构与实现之路

探索 Spring AOP：全面解析与实战应用

“被裁员”的阴影下，我们还能熬多久？

羽绒服割不动年轻人？Java代码教你“穿”出新选择！

项目开发全流程实战：经验、挑战与应对策略

拥抱改变，开启持续进步之旅

探秘软件公司岗位职责：从项目启动到交付的全流程解析

深入理解Servlet：从基础概念到高级特性与实战应用