编程面试的10大算法概念汇总

文章由LinuxBoy分享于2019-03-31 10:03:26热评（404）

编程面试的10大算法概念汇总

以下是在编程面试中排名前10的算法相关的概念，我会通过一些简单的例子来阐述这些概念。由于完全掌握这些概念需要更多的努力，因此这份列表只是作为一个介绍。

本文将从Java的角度看问题，包含下面的这些概念：

1. 字符串
2. 链表
3. 树
4. 图
5. 排序
6. 递归 vs. 迭代
7. 动态规划
8. 位操作
9. 概率问题
10. 排列组合

1. 字符串

如果IDE没有代码自动补全功能，所以你应该记住下面的这些方法。

toCharArray()// 获得字符串对应的char数组
Arrays.sort() // 数组排序
Arrays.toString(char[] a)// 数组转成字符串
charAt(intx)// 获得某个索引处的字符
length()// 字符串长度
length// 数组大小

2. 链表

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

class Node {
int val;
Node next;

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

链表两个著名的应用是栈Stack和队列Queue。

栈：

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;
}
}
}

队列：

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;
}
}
}

3. 树

这里的树通常是指二叉树，每个节点都包含一个左孩子节点和右孩子节点，像下面这样：

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

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

平衡 vs. 非平衡：平衡二叉树中，每个节点的左右子树的深度相差至多为1（1或0）。
满二叉树（Full Binary Tree）：除叶子节点以为的每个节点都有两个孩子。
完美二叉树（Perfect Binary Tree）：是具有下列性质的满二叉树：所有的叶子节点都有相同的深度或处在同一层次，且每个父节点都必须有两个孩子。
完全二叉树（Complete Binary Tree）：二叉树中，可能除了最后一个，每一层都被完全填满，且所有节点都必须尽可能想左靠。

译者注：完美二叉树也隐约称为完全二叉树。完美二叉树的一个例子是一个人在给定深度的祖先图，因为每个人都一定有两个生父母。完全二叉树可以看成是可以有若干额外向左靠的叶子节点的完美二叉树。疑问：完美二叉树和满二叉树的区别？（参考：http://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html）

4. 图

图相关的问题主要集中在深度优先搜索（depth first search）和广度优先搜索（breath first search）。

下面是一个简单的图广度优先搜索的实现。

breath-first-search

1) 定义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;
}
}

2) 定义一个队列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;
}
}
}

3) 用队列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);
}
}
}
}
}

输出：

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

5. 排序

下面是不同排序算法的时间复杂度，你可以去wiki看一下这些算法的基本思想。

Algorithm	Average Time	Worst Time	Space
冒泡排序	n^2	n^2	1
选择排序	n^2	n^2	1
Counting Sort	n+k	n+k	n+k
Insertion sort	n^2	n^2
Quick sort	n log(n)	n^2
Merge sort	n log(n)	n log(n)	depends

另外，这里有一些实现/演示：: Counting sort、Mergesort、 Quicksort、 InsertionSort。

编程面试的10大算法概念汇总