算法10题
更新时间:2023-12-16 11:02:01 阅读量: 教育文库 文档下载
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; 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的类,链表也可以作为一个队列使用(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 \ } } 第二步,定义一个队列
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(\ 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(\ queue.enqueue(n);
} } } } } 输出结果:
value: 2 value: 3 value: 5 Find value: 5 value: 4
实际中,基于Graph需要经常用到的算法:
?? 克隆Graph
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.动态编程
动态编程主要用来解决如下技术问题:
?? An instance is solved using the solutions for smaller instances; ?? 对于一个较小的实例,可能需要许多个解决方案;
?? 把较小实例的解决方案存储在一个表中,一旦遇上,就很容易解决; ?? 附加空间用来节省时间。
上面所列的爬台阶问题完全符合这四个属性,因此,可以使用动态编程来解决:
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=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 calculateProbability(50) = 0.97 10.组合和排列 组合和排列的主要差别在于顺序是否重要。 例1: 1、2、3、4、5这5个数字,输出不同的顺序,其中4不可以排在第三位,3和5不能相邻,请问有多少种组合? 例2: 有5个香蕉、4个梨、3个苹果,假设每种水果都是一样的,请问有多少种不同的组合? 基于它们的一些常见算法 ?? 排列 ?? 排列2 ?? 排列顺序 The following are top 10 algorithms related topics for coding interviews. As understanding those concepts requires much more effort, this list below only serves as an introduction. They are viewed from a Java perspective and the following topics will be covered: String/Array/Matrix, Linked List, Tree, Heap, Graph, Sorting, Recursion vs. Iteration, Dynamic Programming, Bit Manipulation, Probability, Combinations and Permutations, and other problems that need us to find patterns. 1. String/Array/Matrix First of all, String in Java is a class that contains a char array and other fields and methods. Without code auto-completion of any IDE, the following methods should be remembered. 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 Strings/arrays are easy to understand, but questions related to them often require advanced algorithm to solve, such as dynamic programming, recursion, etc. Classic problems: 1) Evaluate Reverse Polish Notation 2) Longest Palindromic Substring 3) Word Break 4) Word Ladder 5) Median of Two Sorted Arrays 6) Regular Expression Matching 7) Merge Intervals 8) Insert Interval 9) Two Sum 9) 3Sum 9) 4Sum 10) 3Sum Closest 11) String to Integer 12) Merge Sorted Array 13) Valid Parentheses 14) Implement strStr() 15) Set Matrix Zeroes 16) Search Insert Position 17) Longest Consecutive Sequence 18) Valid Palindrome 19) Spiral Matrix 20) Search a 2D Matrix 21) Rotate Image 22) Triangle 23) Distinct Subsequences Total 24) Maximum Subarray 25) Remove Duplicates from Sorted Array 26) Remove Duplicates from Sorted Array II 27) Longest Substring Without Repeating Characters 28) Longest Substring that contains 2 unique characters 29) Palindrome Partitioning 2. Linked List The implementation of a linked list is pretty simple in Java. Each node has a value and a link to next node. class Node { int val; Node next; Node(int x) { val = x; next = null; } } Two popular applications of linked list are stack and queue. 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; } } } It is worth to mention that Java standard library already contains a class called “Stack“, and LinkedListcan be used as a Queue (add() and remove()). (LinkedList implements the Queue interface) If you need a stack or queue to solve problems during your interview, you can directly use them. Classic Problems: 1) Add Two Numbers 2) Reorder List 3) Linked List Cycle 4) Copy List with Random Pointer 5) Merge Two Sorted Lists 6) Merge k Sorted Lists * 7) Remove Duplicates from Sorted List 8) Partition List 9) LRU Cache 3. Tree & Heap Tree here is normally binary tree. Each node contains a left node and right node like the following: class TreeNode{ int value; TreeNode left; TreeNode right; } Here are some concepts related with trees: ?? Binary Search Tree: for all nodes, left children <= current node <= right children ?? Balanced vs. Unbalanced: In a balanced tree, the depth of the left and right subtrees of every node differ by 1 or less. ?? Full Binary Tree: every node other than the leaves has two children. ?? Perfect Binary Tree: a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children. ?? Complete Binary Tree: a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible Heap is a specialized tree-based data structure that satisfies the heap property. The time complexity of its operations are important (e.g., find-min, delete-min, insert, etc). In Java, PriorityQueue is important to know. Classic problems: 1) Binary Tree Preorder Traversal 2) Binary Tree Inorder Traversal 3) Binary Tree Postorder Traversal 4) Word Ladder 5) Validate Binary Search Tree 6) Flatten Binary Tree to Linked List 7) Path Sum 8) Construct Binary Tree from Inorder and Postorder Traversal 9) Convert Sorted Array to Binary Search Tree 10) Convert Sorted List to Binary Search Tree 11) Minimum Depth of Binary Tree 12) Binary Tree Maximum Path Sum * 13) Balanced Binary Tree 4. Graph Graph related questions mainly focus on depth first search and breath first search. Depth first search is straightforward, you can just loop through neighbors starting from the root node. Below is a simple implementation of a graph and breath first search. The key is using a queue to store nodes. 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 \+ this.val; } } 2) 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; } } } 3) 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(\); 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(\+n); queue.enqueue(n); } } } } } Output: value: 2 value: 3 value: 5 Find value: 5 value: 4 Classic Problems: 1) Clone Graph 5. Sorting Time complexity of different sorting algorithms. You can go to wiki to see basic idea of them. Algorithm Average Worst Space Time Bubble sort n^2 Selection n^2 sort Insertion n^2 sort Quick sort n log(n) Time n^2 1 n^2 1 n^2 n^2 dependMerge sort n log(n) n log(n) s * BinSort, Radix Sort and CountSort use different set of assumptions than the rest, and so they are not “general” sorting methods. (Thanks to Fidel for pointing this out) Here are some implementations/demos, and in addition, you may want to check out how Java developers sort in practice. 1) Mergesort 2) Quicksort 3) InsertionSort. 6. Recursion vs. Iteration Recursion should be a built-in thought for programmers. It can be demonstrated by a simple example. Question: there are n stairs, each time one can climb 1 or 2. How many different ways to climb the stairs? Step 1: Finding the relationship before n and n-1. To get n, there are only two ways, one 1-stair from n-1 or 2-stairs from n-2. If f(n) is the number of ways to climb to n, then f(n) = f(n-1) + f(n-2) Step 2: Make sure the start condition is correct. 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; } The time complexity of the recursive method is exponential to n. There are a lot of redundant computations. f(5) f(4) + f(3) f(3) + f(2) + f(2) + f(1) f(2) + f(1) + f(2) + f(2) + f(1) It should be straightforward to convert the recursion to iteration. 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; } For this example, iteration takes less time. You may also want to check out Recursion vs Iteration. 7. Dynamic Programming Dynamic programming is a technique for solving problems with the following properties: ?? An instance is solved using the solutions for smaller instances. ?? The solution for a smaller instance might be needed multiple times. ?? The solutions to smaller instances are stored in a table, so that each smaller instance is solved only once. ?? Additional space is used to save time. The problem of climbing steps perfectly fit those 4 properties. Therefore, it can be solve by using dynamic programming. 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]; } Classic problems: 1) Edit Distance 2) Longest Palindromic Substring 3) Word Break 4) Maximum Subarray 8. Bit Manipulation Bit operators: OR (|) 1|0=1 AND (&) 1&0=0 XOR (^) 1^0=1 Left Shift (<<) Right Shift (>>) Not (~) 0010<<2=1000 1100>>2=0011 ~1=0 Get bit i for a give number n. (i count from 0 and starts from right) public static boolean getBit(int num, int i){ int result = num & (1< if(result == 0){ return false; }else{ return true; } } For example, get second bit of number 10. i=1, n=10 1<<1= 10 1010&10=10 10 is not 0, so return true; Classic Problems: 1) Find Single Number 2) Maximum Binary Gap 9. Probability Solving probability related questions normally requires formatting the problem well. Here is just a simple example of such kind of problems. There are 50 people in a room, what’s the probability that two people have the same birthday? (Ignoring the fact of leap year, i.e., 365 day every year) Very often calculating probability of something can be converted to calculate the opposite. In this example, we can calculate the probability that all people have unique birthdays. That is: 365/365 * 364/365 * 363/365 * ? * 365-n/365 * ? * 365-49/365. And the probability that at least two people have the same birthday would be 1 – this value. public static double caculateProbability(int n){ double x = 1; for(int i=0; i double pro = Math.round((1-x) * 100); return pro/100; } calculateProbability(50) = 0.97 10. Combinations and Permutations The difference between combination and permutation is whether order matters. Example 1: Given 5 numbers – 1, 2, 3, 4 and 5, print out different sequence of the 5 numbers. 4 can not be the third one, 3 and 5 can not be adjacent. How many different combinations? Example 2: Given 5 banaba, 4 pear, and 3 apple, assuming one kind of fruit are the same, how many different combinations? Class Problems: 1) Permutations 2) Permutations II 3) Permutation Sequence
正在阅读:
算法10题12-16
商务考察邀请函模板三篇03-10
《清稗类钞》服饰类04-12
法理学试卷A卷03-14
快递公司企划书01-02
国有企业ERP项目实施调查报告03-25
水平炉结晶器05-02
证券公司压力测试先进经验案例09-29
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 算法
- HD-SDI广播级高清监控解决方案
- 脚手架专项施工方案
- 2015年全国注册监理工程师延续注册-系统考试试题2
- word制作电子板报英语报 - 图文
- 浅谈深海矿产资源开采现状及发展形势
- ITopBottomBar 接口使用
- 国有企业担保管理暂行办法
- 九年级英语教学工作总结史上最全的
- 自考线性代数(经管类)章节作业
- 2015年中考数学试题分类汇编:圆(含答案解析)
- 东山二中高二年学业基础会考化学试卷(有答案)
- 汇编语言实现动态图形
- 体外诊断试剂生产企业许可证现场检查内容 - 图文
- AutoCAD(ITAT)模拟试题14
- 浅谈会计师事务所审计的风险控制
- 高数理工类习题册答案
- 最新-读《法伴我成长》心得体会 精品
- 临沂市小学数学复习课教学策略
- 分布式光伏电站建设项目投资可行性研究报告书
- 老年痴呆有哪些好的治疗方法