2022年个最常见的Java算法.docx

《2022年个最常见的Java算法.docx》由会员分享，可在线阅读，更多相关《2022年个最常见的Java算法.docx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品学习资源代码面试最常用的 10 大算法发表于 2021-04-10 11:34| 16225次阅读 | 来源 ProgramCreek|279 条评论 | 作者 X WangJava 面试算法排序二叉树归并排序职业生涯摘要： 面试也是一门学问，在面试之前做好充分的预备就是胜利的必需条件，而程序员在代码面试时，常会遇到编写算法的相关问题，比如排序、二叉树遍历等等；在程序员的职业生涯中，算法亦算是一门基础课程，特别是在面试的时候，很多公司都会让程序员编写一些算法实例，例如快速排序、二叉树查找等等；本文总结了程序员在代码面试中最常遇到的10 大算法类型，想要真正明白这些算法的原理，仍需程序员们花

2、些功夫；1.String/Array/Matrix在 Java 中， String 是一个包含 char 数组和其它字段、方法的类；假如没有IDE 自动完成代码，下面这个方法大家应当记住：toCharArray /get char array of a String Arrays.sort /sort an array Arrays.toStringchar a /convert to string charAtint x /get a char at the specific index length /string lengthlength /array size substringint

3、 beginIndexsubstringint beginIndex, int endIndexInteger.valueOf/string to integer String.valueOf/integer to stringString/arrays很简洁懂得，但与它们有关的问题常常需要高级的算法去解决，例如动态编程、递归等；下面列出一些需要高级算法才能解决的经典问题：欢迎下载精品学习资源Evaluate Reverse Polish Notation Longest Palindromic Substring单词分割字梯Median of Two Sorted Arrays正就表达式匹协

4、作并间隔插入间隔Two Sum 3Sum 4Sum3Sum Closest String to Integer 合并排序数组Valid Parentheses实现 strStrSet Matrix Zeroes搜寻插入位置Longest Consecutive Sequence Valid Palindrome螺旋矩阵搜寻一个二维矩阵旋转图像三角形Distinct Subsequences Total Maximum Subarray删除重复的排序数组删除重复的排序数组2查找没有重复的最长子串包含两个特殊字符的最长子串Palindrome Partitioning2. 链表在 Java 中实现

5、链表是特别简洁的，每个节点都有一个值，然后把它链接到下一个节点；class Node 欢迎下载精品学习资源int val；Node next ；Nodeint x val = x；next = null；比较流行的两个链表例子就是栈和队列；栈iftop .= nullreturn top；return null；public Node pop欢迎下载精品学习资源iftop = nullreturn null；elseNode temp = new Nodetop.val；top = top.next；return temp；public void pushNode nifn .= nulln.

6、next = top；top = n ；队列 iffirst = nullfirst = n；欢迎下载精品学习资源last = first；elselast.next = n；last = n； ；public Node dequeueiffirst = nullreturn null；elseNode temp = new Nodefirst.val；first = first.next；return temp；值得一提的是， Java 标准库中已经包含一个叫做Stack 的类，链表也可以作为一个队列使用 和 remove ）； 链表实现队列接口）假如你在面试过程中，需要用到栈或队列

7、解决问题时，你可以直接使用它们；在实际中，需要用到链表的算法有：插入两个数字重新排序列表链表周期欢迎下载精品学习资源Copy List with Random Pointer合并两个有序列表合并多个排序列表从排序列表中删除重复的分区列表LRU 缓存3. 树& 堆这里的树通常是指二叉树；class TreeNodeint value；TreeNode left；TreeNode right；下面是一些与二叉树有关的概念：二叉树搜寻：对于全部节点，次序是：left children = current node = right children ；平稳 vs. 非平稳：它是一棵空树或它的左右两个子

8、树的高度差的肯定值不超过1 ， 并且左右两个子树都是一棵平稳二叉树；满二叉树：除最终一层无任何子节点外，每一层上的全部结点都有两个子结点； 完善二叉树 的结点数都达到最大个数，第h 层全部的结点都连续集中在最左边，这就是完全二叉树；堆Heap ）是一个基于树的数据结构，也可以称为优先队列 val = x；欢迎下载精品学习资源GraphNodeint x, GraphNode n val = x；neighbors = n；public String toStringreturn value: + this.val；其次步，定义一个队列class QueueGraphNode first, la

9、st；public void enqueueGraphNode n iffirst = nullfirst = n；last = first；elselast.next = n；last = n；欢迎下载精品学习资源public GraphNode dequeueiffirst = nullreturn null；elseGraphNode temp = new GraphNodefirst.val,first.neighbors；first = first.next；return temp；第三步，使用队列进行宽度优先搜寻public class GraphTest public stati

10、c void mainString args GraphNode n1 = new GraphNode1 ；GraphNode n2 = new GraphNode2 ；GraphNode n3 = new GraphNode3 ；GraphNode n4 = new GraphNode4 ；GraphNode n5 = new GraphNode5 ；n1.neighbors = new GraphNoden2,n3,n5；欢迎下载精品学习资源n2.neighbors = new GraphNoden1,n4；n3.neighbors = new GraphNoden1,n4,n5；n4.n

11、eighbors = new GraphNoden2,n3,n5n5.neighbors = new GraphNoden1,n3,n4；breathFirstSearchn1, 5；public static void breathFirstSearchGraphNode root, int x ifroot.val = xSystem.out.printlnfind in root；Queue queue = new Queue ；root.visited = true；queue.enqueueroot ；whilequeue.first .= nullGraphNode c = Gra

12、phNode queue.dequeue ；forGraphNode n: c.neighborsif.n.visitedSystem.out.printn + ；n.visited = true；欢迎下载精品学习资源ifn.val = xSystem.out.printlnFind +n；queue.enqueuen ；输出结果：value: 2 value: 3 value: 5 Find value: 5value: 4实际中，基于Graph 需要常常用到的算法：克隆 Graph5. 排序不同排序算法的时间复杂度，大家可以到wiki 上查看它们的基本思想；BinSort 、Radix S

13、ort和 CountSort使用了不同的假设，全部，它们不是一般的排序方法；下面是这些算法的详细实例，另外，你仍可以阅读：Java 开发者在实际操作中是如何排序的 ；归并排序快速排序插入排序6. 递归和迭代下面通过一个例子来说明什么是递归；欢迎下载精品学习资源问题：这里有 n 个台阶，每次能爬1 或 2 节，请问有多少种爬法？ 步骤 1 ：查找 n 和 n-1 之间的关系为了获得 n，这里有两种方法：一个是从第一节台阶到n-1 或者从 2 到 n-2 ；假如 fn 种爬法刚好是爬到n 节，那么 fn=fn-1+fn-2；步骤 2 ：确保开头条件是正确的f0 = 0 ；f1 = 1 ；publi

14、c static int fint nifn return n；int x = fn-1 + fn-2；return x；递归方法的时间复杂度指数为n，这里会有很多冗余运算；f5f4 + f3f3 + f2 + f2 + f1f2 + f1 + f2 + f2 + f1该递归可以很简洁地转换为迭代；public static int fint n if n 欢迎下载精品学习资源return n；int first = 1, second = 2；int third = 0；for int i = 3； i third = first + second；first = second；second

15、 = third；return third；在这个例子中，迭代花费的时间要少些；关于迭代和递归，你可以去这里看看；7. 动态规划动态规划主要用来解决如下技术问题：通过较小的子例来解决一个实例；对于一个较小的实例，可能需要很多个解决方案；把较小实例的解决方案储备在一个表中，一旦遇上，就很简洁解决； 附加空间用来节约时间；上面所列的爬台阶问题完全符合这四个属性，因此，可以使用动态规划来解决：public static int A = new int100；欢迎下载精品学习资源public static int f3int n if n An= n ；ifAn 0return An；elseAn =

16、 f3n-1 + f3n-2；/store results so onlycalculate once.return An；一些基于动态规划的算法：编辑距离最长回文子串单词分割最大的子数组8. 位操作 位操作符：从一个给定的数 n 中找位 i int result = num & 1；欢迎下载精品学习资源ifresult = 0return false；elsereturn true；例如，猎取 10 的其次位：i=1, n=10 11= 101010&10=1010 is not 0, so return true；典型的位算法：Find Single Number Maximum Bina

17、ry Gap9. 概率通常要解决概率相关问题，都需要很好地格式化问题，下面供应一个简洁的例子：有 50 个人在一个房间，那么有两个人是同一天生日的可能性有多大？ double x = 1；欢迎下载精品学习资源forint i=0； ix *= 365.0-i/365.0；double pro = Math.round1-x * 100；return pro/100；结果：calculateProbability50 = 0.9710. 组合和排列组合和排列的主要差别在于次序是否重要；例 1：1、2 、3、 4、5 这 5 个数字，输出不同的次序，其中邻，请问有多少种组合？ 例 2：4 不行以排在第三位， 3 和 5 不能相有 5 个香蕉、 4 个梨、 3 个苹果，假设每种水果都是一样的，请问有多少种不同的组合？基于它们的一些常见算法排列排列 2排列次序来自： ProgramCreek欢迎下载