正文

代码最常用的10大算法

author  author  2022-08-26  246

关键词：

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

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

本文总结了程序员在代码面试中最常遇到的10大算法类型，想要真正了解这些算法的原理，还需程序员们花些功夫。

1.String/Array/Matrix

在Java中，String是一个包含char数组和其它字段、方法的类。如果没有IDE自动完成代码，下面这个方法大家应该记住：

toCharArray() //get char array of a String
Arrays.sort()  //sort an array
Arrays.toString(char[] a) //convert to 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

String/arrays很容易理解，但与它们有关的问题常常需要高级的算法去解决，例如动态编程、递归等。
下面列出一些需要高级算法才能解决的经典问题：

Evaluate Reverse Polish Notation
Longest Palindromic Substring
单词分割
字梯
Median of Two Sorted Arrays
正则表达式匹配
合并间隔
插入间隔
Two Sum
3Sum
4Sum
3Sum Closest
String to Integer
合并排序数组
Valid Parentheses
实现strStr()
Set Matrix Zeroes
搜索插入位置
Longest Consecutive Sequence
Valid Palindrome
螺旋矩阵
搜索一个二维矩阵
旋转图像
三角形
Distinct Subsequences Total
Maximum Subarray
删除重复的排序数组
删除重复的排序数组2
查找没有重复的最长子串
包含两个独特字符的最长子串
Palindrome Partitioning

2.链表

在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;
&nbsp;
    public void enqueue(Node n){
        if(first == null){
            first = n;
            last = first;
        }else{
            last.next = n;
            last = n;
        }
    }
&nbsp;
    public Node dequeue(){
        if(first == null){
            return null;
        }else{
            Node temp = new Node(first.val);
            first = first.next;
            return temp;
        }   
    }
}

值得一提的是，Java标准库中已经包含一个叫做Stack的类，链表也可以作为一个队列使用（add()和remove()）。（链表实现队列接口）如果你在面试过程中，需要用到栈或队列解决问题时，你可以直接使用它们。

在实际中，需要用到链表的算法有：

插入两个数字
重新排序列表
链表周期
Copy List with Random Pointer
合并两个有序列表
合并多个排序列表
从排序列表中删除重复的
分区列表
LRU缓存

3.树&堆

这里的树通常是指二叉树。

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

下面是一些与二叉树有关的概念：
二叉树搜索：对于所有节点，顺序是：left children <= current node <= right children；
平衡vs.非平衡：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树；
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点；
完美二叉树（Perfect Binary Tree）：一个满二叉树，所有叶子都在同一个深度或同一级，并且每个父节点都有两个子节点；
完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

堆（Heap）是一个基于树的数据结构，也可以称为优先队列（ PriorityQueue），在队列中，调度程序反复提取队列中第一个作业并运行，因而实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

下面列出一些基于二叉树和堆的算法：

二叉树前序遍历
二叉树中序遍历
二叉树后序遍历
字梯
验证二叉查找树
把二叉树变平放到链表里
二叉树路径和
从前序和后序构建二叉树
把有序数组转换为二叉查找树
把有序列表转为二叉查找树
最小深度二叉树
二叉树最大路径和
平衡二叉树

4.Graph

与Graph相关的问题主要集中在深度优先搜索和宽度优先搜索。深度优先搜索非常简单，你可以从根节点开始循环整个邻居节点。下面是一个非常简单的宽度优先搜索例子，核心是用队列去存储节点。

技术分享

第一步，定义一个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; 
    }
}

第二步，定义一个队列

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

第三步，使用队列进行宽度优先搜索

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

实际中，基于Graph需要经常用到的算法：

克隆Graph

对我有用[10] 丢个板砖[2] 引用 | 举报 | 管理

回复次数：293

: 关注; hjknet; 柔软的胖纸; 本版等级：

#1 得分：0回复于： 2014-04-24 19:08:30

5.排序

不同排序算法的时间复杂度，大家可以到wiki上查看它们的基本思想。

技术分享

BinSort、Radix Sort和CountSort使用了不同的假设，所有，它们不是一般的排序方法。
下面是这些算法的具体实例，另外，你还可以阅读：Java开发者在实际操作中是如何排序的。

归并排序
快速排序
插入排序

6.递归和迭代

下面通过一个例子来说明什么是递归。

问题：

这里有n个台阶，每次能爬1或2节，请问有多少种爬法？

步骤1：查找n和n-1之间的关系

为了获得n，这里有两种方法：一个是从第一节台阶到n-1或者从2到n-2。如果f(n)种爬法刚好是爬到n节，那么f(n)=f(n-1)+f(n-2)。

步骤2：确保开始条件是正确的

f(0) = 0;
f(1) = 1;

public static int f(int n){
    if(n <= 2) return n;
    int x = f(n-1) + f(n-2);
    return x;
}

递归方法的时间复杂度指数为n，这里会有很多冗余计算。

f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(2) + f(2) + f(1)

该递归可以很简单地转换为迭代。

public static int f(int n) {
  
    if (n <= 2){
        return n;
    }
  
    int first = 1, second = 2;
    int third = 0;
  
    for (int i = 3; i <= n; i++) {
        third = first + second;
        first = second;
        second = third;
    }
  
    return third;
}

在这个例子中，迭代花费的时间要少些。关于迭代和递归，你可以去这里看看。

7.动态规划

动态规划主要用来解决如下技术问题：

通过较小的子例来解决一个实例；
对于一个较小的实例，可能需要许多个解决方案；
把较小实例的解决方案存储在一个表中，一旦遇上，就很容易解决；
附加空间用来节省时间。
上面所列的爬台阶问题完全符合这四个属性，因此，可以使用动态规划来解决：

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

一些基于动态规划的算法：
编辑距离
最长回文子串
单词分割
最大的子数组

8.位操作

位操作符：
技术分享

从一个给定的数n中找位i（i从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;

典型的位算法：
Find Single Number
Maximum Binary Gap

9.概率

通常要解决概率相关问题，都需要很好地格式化问题，下面提供一个简单的例子：
有50个人在一个房间，那么有两个人是同一天生日的可能性有多大？（忽略闰年，即一年有365天）

算法：

public static double caculateProbability(int n){
    double x = 1; 
  
    for(int i=0; i<n; i++){
        x *=  (365.0-i)/365.0;
    }
  
    double pro = Math.round((1-x) * 100);
    return pro/100;
}

结果：calculateProbability(50) = 0.97

10.组合和排列

组合和排列的主要差别在于顺序是否重要。

例1：

1、2、3、4、5这5个数字，输出不同的顺序，其中4不可以排在第三位，3和5不能相邻，请问有多少种组合？

例2：

有5个香蕉、4个梨、3个苹果，假设每种水果都是一样的，请问有多少种不同的组合？

基于它们的一些常见算法
排列
排列2
排列顺序

最常用的10大算法

1.String/Array/Matrix在Java中，String是一个包含char数组和其它字段、方法的类。如果没有IDE自动完成代码，下面这个方法大家应该记住：toCharArray()//getchararrayofaStringArrays.sort()//sortanarrayArrays.toString(char[]a)//converttostringcharAt(intx)// 查看详情

数据结构-图图的常用算法(代码片段)

手工模拟图的各大常用算法。文章目录1图的遍历算法1.1BFS算法（广度优先遍历）1.2DFS算法（深度优先遍历）2最短路径问题2.1BFS算法（求无权图的单源最短路径）2.2Dijkstra算法（求带权图的单源最短路径... 查看详情

排序算法大汇总(代码片段)

排序算法大汇总排序算法是最基本最常用的算法，也是各大上市公司经常会被问道的面试知识点之一，不同的排序算法在不同的场景或应用中会有不同的表现，我们需要对各种排序算法熟练才能将它应用到实际... 查看详情

轻松看懂机器学习十大常用算法(machinelearningtop10commonlyusedalgorithms)

...过本篇文章可以对ML的常用算法有个常识性的认识，没有代码，没有复杂的理论推导，就是图解一下，知道这些算法是什么，它们是怎么应用的，例子主要是分类问题。每个算法都看了好几个视频，挑出讲的最清晰明了有趣的，... 查看详情

常用的排序算法(代码片段)

...移动的次数最少（N次）数组的左边始终保持有序不稳定代码voidselectSort 查看详情

电子金融交易所最常用的订单匹配算法都有哪些？

】电子金融交易所最常用的订单匹配算法都有哪些？【英文标题】：Whicharetheordermatchingalgorithmsmostcommonlyusedbyelectronicfinancialexchanges?电子金融交易所最常用的订单匹配算法有哪些？【发布时间】：2012-10-1804:52:04【问题描述】：电子... 查看详情

java常用排序算法/程序员必须掌握的8大排序算法

本文由网络资料整理而来，如有问题，欢迎指正！分类：1）插入排序（直接插入排序、希尔排序）2）交换排序（冒泡排序、快速排序）3）选择排序（直接选择排序、堆排序）4）归并排序5）分配排序（基数排序）所需辅助空间... 查看详情

不容错过，数据分析中最常用的10大python库

...航老师《统计学习方法（第二版）》课件&算法代码全公开了01、Pandas在数据分析师的日常工作中，70%到80%都涉及到理解和清理数据，也就是数据探索和数据挖掘。Pandas主要用于数据分析，这是最常用的Python... 查看详情

sh打印我们最常用的5大cli命令。(代码片段)

查看详情

学习java绝对要懂的，java编程中最常用的几种排序算法！

今天给大家分享一下Java中几种常见的排序算法的Java代码推荐一下我的Java学习羊君前616，中959，最后444.把数字串联起来！，群里有免费的学习视频和项目给大家练手。大神有空时也会带带大家的，学Java的过程中一定要... 查看详情

面试中的10大排序算法总结(代码片段)

...门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。一般在面试中最常考的是快速排序... 查看详情

java实现的常用5大排序算法

排序算法很多地方都会用到，近期又重新看了一遍算法，并自己简单地实现了一遍，特此记录下来，为以后复习留点材料。　　废话不多说，下面逐一看看经典的排序算法：　　1、Java排序算法之选择排序　　选择排序的基本思... 查看详情

常用排序算法(代码片段)

一、冒泡排序冒泡排序是最简单的排序算法。假设数组一共有n个元素，元素最大下标为n-1，冒泡排序的具体做法是：第一趟在序列(A[0]~A[n-1])中从前往后进行两个相邻元素的比较，若前者大，则交换，... 查看详情

深度学习最常用的10个激活函数！（数学原理+优缺点）

点上方人工智能算法与Python大数据获取更多干货在右上方 ··· 设为星标 ★，第一时间获取资源仅做学术分享，如有侵权，联系删除转载于：机器之心激活函数是神经网络模型重要的组成部分，本文作者Sukan... 查看详情

c/c++编程中最常用的算法-穷举搜索(代码片段)

算法中，最常用的应该就是穷举搜索算法了吧，也许你已经使用过了，只是自己不知到而已！讲述一道题目，你就会知道什么是穷举算法了！我国古代数学家张丘建在《算经》一书中曾提出过著名的“百钱... 查看详情

机器学习十大常用算法

找出一本大书中最常用的 10 个单词 [重复]

】找出一本大书中最常用的10个单词[重复]【英文标题】：Findthe10mostfrequentlyusedwordsinalargebook[duplicate]【发布时间】：2013-07-0616:35:21【问题描述】：我知道这已经在论坛上被问过几次，我没有找到任何可以被认为是最合适的解决方... 查看详情

数据结构和算法-五大常用算法:分治算法(代码片段)

原文链接：（转载请注明出处）https://dmego.me/2016/10/16/hanoi一．起源：　　汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64... 查看详情