daicy
发布于 2019-04-17 / 904 阅读
0
0

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

摘要:

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

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

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

更新列表可在此处获得。您可以下载PDF版本

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两个总和III3Sum4Sum
10)3Sum最接近
11)字符串到整数
12)合并排序的数组
13)有效括号
13)最长有效括号
14)实现strStr()
15)最小大小的子数组总和
16)搜索插入位置
17)最长连续序列
18)有效回文
19)之字形转换
20)添加二进制数
21)最后一个字的长度
22)三角
24)包含重复项:IIIIII
25)从已排序数组中删除重复项:IIIRemove Element移动零
27)最长的子字符串而不重复字符
28)包含2个唯一字符的最长的子字符串 [Google]
28)具有所有单词串联的子串
29)最小窗口子串
31)在旋转排序数组中找到最小值:III
32)在旋转数组中搜索:III
33)最小堆栈
34)多数元素:III
35)公牛和母牛
36)直方图中最大的矩形
37)最长的公共前缀 [Google]
38)最大的数字
39)简化路径
40)比较版本号
41)加油站
44)帕斯卡三角形:III
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-IndexH-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. 二进制搜索树:对于所有节点,左子节点<=当前节点<=右子节点
  2. 平衡与不平衡:在平衡树中,每个节点的左右子树的深度相差1或更小。
  3. 完整的二叉树:除叶子外的每个节点都有两个孩子。
  4. 完美二叉树:完整的二叉树,其中所有叶子处于相同深度或相同级别,并且每个父级都有两个子级。
  5. 完整的二叉树:一个二叉树,其中每个级别(除了最后一个级别)都已完全填充,并且所有节点都尽可能地靠左

是满足堆属性的基于树的专用数据结构。其操作的时间复杂度很重要(例如,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.图

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

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

呼吸优先搜索

  1. 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; 
	}
}
  1. 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;
		}	
	}
}
  1. 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来查看它们的基本概念。

AlgorithmAverage TimeWorst TimeSpace
Bubble sortn^2n^21
Selection sortn^2n^21
Insertion sortn^2n^2
Quick sortn log(n)n^2
Merge sortn log(n)n log(n)depends

要看

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

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

7.动态编程

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

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


攀登台阶的问题完全适合这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

相关文章:

  1. LeetCode – Word Ladder II(Java)
  2. 如何回答面试中的编码问题?
  3. LeetCode – LRU缓存(Java)
  4. LeetCode –自我后的小数计数(Java)

评论