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

摘要

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

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

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

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

1. 字符串/数组

算法问题的输入通常是字符串或数组。在没有 IDE 自动完成的情况下，应记住以下常用方法：

toCharArray() // 获取 String 的 char 数组
charAt(int x) // 获取特定索引处的 char
length() // 字符串长度
length // 数组大小 
substring(int beginIndex) 
substring(int beginIndex, int endIndex)
Integer.valueOf() // 字符串转整数
String.valueOf() // 整数转字符串
Arrays.sort()  // 数组排序
Arrays.toString(char[] a) // 转换为字符串
Arrays.copyOf(T[] original, int newLength)
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

经典问题：

2. 矩阵

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

经典问题：

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 接口。）如果在面试过程中需要堆栈或队列来解决问题，则可以使用它们。

经典问题：

4. 树、堆与字典树

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

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

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

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

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

4.1 树

4.2 堆

4.3 字典树 (Trie)

4.4 段树

5. 图

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

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

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) 广度优先搜索使用队列

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

经典问题：

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	1
Quick sort	n log(n)	n^2	log(n)
Merge sort	n log(n)	n log(n)	depends

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

这是一些实现/演示，此外，您可能想了解 Java 开发人员在实践中的排序方式。

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); // 存储结果，因此只计算一次！
    return A[n];
}

经典问题：

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;

经典问题：

9. 组合和排列

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

范例 1：

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

范例 2：

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

类问题：

10. 数学

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

11. HashMap

最短单词距离 II

附加问题：

其他资源

将您的代码共享到 Github / BitBucket

说明： 本文引用的部分题目链接及内容源自 2012-2016 年期间的整理，部分 LeetCode 题目编号或名称可能随平台更新有所变化，但核心算法思想与分类依然具有参考价值。

本文地址：https://1diff.fun/archives/dai-ma-mian-shi-zui-chang-yong-de-10-da-suan-fa.html

如果对本文有什么问题或疑问都可以在评论区留言，我看到后会尽量解答。

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

摘要

1. 字符串/数组

2. 矩阵

3. 链表

4. 树、堆与字典树

4.1 树

4.2 堆

4.3 字典树 (Trie)

4.4 段树

5. 图

6. 排序

7. 动态规划

8. 位操作

9. 组合和排列

10. 数学

11. HashMap

其他资源

相关文章

发表评论

表情类型

目录