一篇整理比較好的算法相關文章 Java語言

以下從Java角度解釋面試常見的算法和資料結構：字元串，連結清單，樹，圖，排序，遞歸 vs. 疊代，動态規劃，位操作，機率問題，排列組合，以及一些需要尋找規律的題目。

1. 字元串和數組

字元串和數組是最常見的面試題目類型，應當配置設定最大的時間。

關于字元串，首先需要注意的是和C++不同，Java字元串不是char數組。沒有IDE代碼自動補全功能，應該記住下面的這些常用的方法。

toCharArray() //獲得字元串對應的char數組
Arrays.sort()  //數組排序
Arrays.toString(char[] a) //數組轉成字元串
charAt(int x) //獲得某個索引處的字元
length() //字元串長度
length //數組大小
substring(int beginIndex) 
substring(int beginIndex, int endIndex)
Integer.valueOf() //string to integer
String.valueOf() /integer to string

字元串和數組本身很簡單，但是相關的題目需要更複雜的算法來解決。比如說動态規劃，搜尋，等等。

經典題目：

0) Rotate Array

1) Evaluate Reverse Polish Notation (Stack)

2) Longest Palindromic Substring (DP)

3) Word Break (DP)

3) Word Break II (DP, DFS)

4) Word Ladder (Queue, BFS)

5) Median of Two Sorted Arrays

6) Regular Expression Matching

7) Merge Intervals

8) Insert Interval

9) Two Sum

9) Two Sum II – Input array is sorted

9) Two Sum III - Data structure design

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 [Palantir]

22) Triangle

23) Distinct Subsequences Total

24) Maximum Subarray [Palantir, LinkedIn]

24) Maximum Product Subarray [LinkedIn]

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 [Google]

29) Palindrome Partitioning

29) Palindrome Partitioning II

30) Reverse Words in a String

31) Find Minimum in Rotated Sorted Array

31) Find Minimum in Rotated Sorted Array II

32) Find Peak Element

33) Min Stack

34) Majority Element

35) Combination Sum (DFS)

35) Combination Sum II (DFS)

36) Best Time to Buy and Sell Stock

36) Best Time to Buy and Sell Stock II

36) Best Time to Buy and Sell Stock III (DP)

36) Best Time to Buy and Sell Stock IV (DP)

37) Longest Common Prefix [Google]

38) Largest Number

39) Combinations (DFS)

40) Compare Version Numbers

41) Gas Station

42) Candy [Google]

43) Jump Game

44) Pascal's Triangle

44) Pascal’s Triangle II

45) Container With Most Water

46) Count and Say

47) Repeated DNA Sequences

48) House Robber

49) Dungeon Game (DP)

50) Number of Islands (DFS/BFS)

51) Surrounded Regions (BFS)

52) Max Points on a Line

53) Letter Combinations of a Phone Number (DFS)

54) Remove Element

55) Anagrams

56) Search for a Range

57) Simplify Path

58) Isomorphic Strings

59) Minimum Size Subarray Sum

60) Minimum Path Sum (DP)

61) Unique Paths (DP)

2. 連結清單

在Java中，連結清單的實作非常簡單，每個節點Node都有一個值val和指向下個節點的連結next。

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

連結清單兩個著名的應用是棧Stack和隊列Queue。在Java标準庫都都有實作，一個是Stack,另一個是LinkedList(Queue是它實作的接口)。

經典題目：

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

10) Intersection of Two Linked Lists

11) Remove Linked List Elements

12) Swap Nodes in Pairs

13) Reverse Linked List

3. 樹

這裡的樹通常是指二叉樹，每個節點都包含一個左孩子節點和右孩子節點，像下面這樣：

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

下面是與樹相關的一些概念：

二叉搜尋樹：左結點 <= 中結點 <= 右結點

平衡 vs. 非平衡：平衡二叉樹中，每個節點的左右子樹的深度相差至多為1（1或0）。

滿二叉樹（Full Binary Tree）：除葉子節點以為的每個節點都有兩個孩子。

完美二叉樹（Perfect Binary Tree）：是具有下列性質的滿二叉樹：所有的葉子節點都有相同的深度或處在同一層次，且每個父節點都必須有兩個孩子。

完全二叉樹（Complete Binary Tree）：二叉樹中，可能除了最後一個，每一層都被完全填滿，且所有節點都必須盡可能想左靠。

經典題目：

1) Binary Tree Preorder Traversal

2) Binary Tree Inorder Traversal [Palantir]

3) Binary Tree Postorder Traversal

4) Binary Tree Level Order Traversal

4) Binary Tree Level Order Traversal II

5) Validate Binary Search Tree

6) Flatten Binary Tree to Linked List

7) Path Sum (DFS or BFS)

7) Path Sum II (DFS)

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

14) Symmetric Tree

15) Binary Search Tree Iterator

16) Binary Tree Right Side View

17) Implement Trie (Prefix Tree)

18) Add and Search Word - Data structure design (DFS)

4. 圖

圖相關的問題主要集中在深度優先搜尋（depth first search）和廣度優先搜尋（breath first search）。深度優先搜尋很簡單，廣度優先要注意使用queue. 下面是一個簡單的用隊列Queue實作廣度優先搜尋。

public class GraphTest {
	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);
				}
			}
		}
	}
}

經典題目：

1) Clone Graph

2) Course Schedule (DFS/BFS)

5. 排序

下面是不同排序算法的時間複雜度，你可以去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
快速排序(Quick sort)	n log(n)	n^2
歸并排序(Merge sort)	n log(n)	n log(n)	depends

* 另外還有BinSort, RadixSort和CountSort 三種比較特殊的排序。

經典題目：

1) Mergesort

2) Quicksort

3) InsertionSort.

4) Maximum Gap (Bucket Sort)

6. 遞歸 vs. 疊代

對程式員來說，遞歸應該是一個與生俱來的思想（a built-in thought），可以通過一個簡單的例子來說明。

問題：

有n步台階，一次隻能上1步或2步，共有多少種走法。

步驟1:找到走完前n步台階和前n-1步台階之間的關系。

為了走完n步台階，隻有兩種方法：從n-1步台階爬1步走到或從n-2步台階處爬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;
}

遞歸方法的時間複雜度是指數級，因為有很多備援的計算：

f(5)

f(4) + f(3)

f(3) + f(2) + f(2) + f(1)

f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)

f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + 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;
}

這個例子疊代花費的時間更少，你可能複習一個兩者的差別Recursion vs Iteration。

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

經典題目：

1) Edit Distance

2) Longest Palindromic Substring

3) Word Break

3) Word Break II

4) Maximum Subarray

4) Maximum Product Subarray

5) Palindrome Partitioning

5) Palindrome Partitioning II

6) Candy [Google]

7) Jump Game

8) Best Time to Buy and Sell Stock III (DP)

8) Best Time to Buy and Sell Stock IV (DP)

9) Dungeon Game (DP)

10) Minimum Path Sum (DP)

11) Unique Paths (DP)

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

用一個題目來了解這些操作－

獲得給定數字n的第i位：(i從0計數并從右邊開始)

public static boolean getBit(int num, int i){
	int result = num & (1<<i);
 
	return (result == 0)；
}

例如，獲得數字10的第2位：

i=1, n=10

1<<1= 10

1010&10=10

10 is not 0, so return true;

經典題目：

1) Single Number

1) Single Number II

2) Maximum Binary Gap

3) Number of 1 Bits

4) Reverse Bits

5) Repeated DNA Sequences

6) Bitwise AND of Numbers Range

9. 機率問題

解決機率相關的問題通常需要先分析問題，下面是一個這類問題的簡單例子：

一個房間裡有50個人，那麼至少有兩個人生日相同的機率是多少？（忽略閏年的事實，也就是一年365天）

計算某些事情的機率很多時候都可以轉換成先計算其相對面。在這個例子裡，我們可以計算所有人生日都互不相同的機率，也就是：365/365 * 364/365 * 363/365 * … * (365-49)/365，這樣至少兩個人生日相同的機率就是1 – 這個值。

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個數字，用java寫一個方法，列印出所有不同的排列，如：51234、41235等。要求："4"不能在第三位，"3"與"5"不能相連。

例2：

5個香蕉，4個梨子，3個蘋果。同一種水果都是一樣的，這個些水果排列成不同的組合有多少情況？

經典題目：

1) Permutations

2) Permutations II

3) Permutation Sequence

4) Generate Parentheses

11. 其他類型的題目

主要是不能歸到上面10大類的。需要尋找規律，然後解決問題的。

經典題目:

1) Reverse Integer

2) Palindrome Number

3) Pow(x,n)

4) Subsets

5) Subsets II

6) Fraction to Recurring Decimal [Google]

7) Excel Sheet Column Number

8) Excel Sheet Column Title

9) Factorial Trailing Zeroes

10) Happy Number

11) Count Primes

文章轉載自：http://www.javased.com/static/coding-interview.html

一篇整理比較好的算法相關文章 Java語言

繼續閱讀

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

面試題解析：你接口測試是怎麼做的？

測試面試題整理

軟體測試經典面試題（小題彙總）

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希