參考自algorithm-pattern
翻譯為java代碼
入門(mén)篇
算法快速入門(mén)
數(shù)據(jù)結(jié)構(gòu)與算法
數(shù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)的表現(xiàn)形式，如鏈表偎蘸、二叉樹(shù)庄蹋、棧、隊(duì)列等都是內(nèi)存中一段數(shù)據(jù)表現(xiàn)的形式迷雪。 算法是一種通用的解決問(wèn)題的模板或者思路限书，大部分?jǐn)?shù)據(jù)結(jié)構(gòu)都有一套通用的算法模板，所以掌握這些通用的算法模板即可解決各種算法問(wèn)題章咧。
后面會(huì)分專(zhuān)題講解各種數(shù)據(jù)結(jié)構(gòu)倦西、基本的算法模板、和一些高級(jí)算法模板赁严，每一個(gè)專(zhuān)題都有一些經(jīng)典練習(xí)題扰柠，完成所有練習(xí)的題后，你對(duì)數(shù)據(jù)結(jié)構(gòu)和算法會(huì)有新的收獲和體會(huì)疼约。
先介紹兩個(gè)算法題卤档，試試感覺(jué)~
示例 1
給定一個(gè) haystack 字符串和一個(gè) needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從 0 開(kāi)始)忆谓。如果不存在裆装，則返回 -1。
思路：核心點(diǎn)遍歷給定字符串字符倡缠，判斷以當(dāng)前字符開(kāi)頭字符串是否等于目標(biāo)字符串
public class Solution {
public static int strStr(String haystack, String needle) {
if(needle.length() == 0) return 0;
for(int i=0; i<haystack.length()-needle.length()+1; i++) {
int j;
for (j=0; j<needle.length(); j++)
if(haystack.toCharArray()[i+j] != needle.toCharArray()[j])
break;
if(needle.length() == j)
return i;
}
return -1;
}
}
public class Solution {
public static int findFirstPlace(String haystack, String needle) {
if(needle.length() == 0) return 0;
for(int start=0; start<haystack.length()-needle.length()+1; start++) {
if(haystack.substring(start,start+needle.length()).equals(needle))
return start;
}
return -1;
}
}
示例2
給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums哨免，返回該數(shù)組所有可能的子集（冪集）。
思路：這是一個(gè)典型的應(yīng)用回溯法的題目昙沦，簡(jiǎn)單來(lái)說(shuō)就是窮盡所有可能性琢唾，算法模板如下
result = []
public void backtrack(選擇列表,路徑):
if 滿(mǎn)足結(jié)束條件:
result.add(路徑)
return
for 選擇 in 選擇列表:
做選擇
backtrack(選擇列表,路徑)
撤銷(xiāo)選擇
import java.util.ArrayList;
public class Solution {
ArrayList<ArrayList<Integer>> result = new ArrayList();
public void backtrack(int start, ArrayList<Integer> curr, int[] nums) {
result.add(new ArrayList(curr));
for (int i = start; i < nums.length; ++i) {
// add i into the current combination
curr.add(nums[i]);
// use next integers to complete the combination
backtrack(i + 1, curr, nums);
// backtrack
curr.remove(curr.size() - 1);
}
}
public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
backtrack(0, new ArrayList<Integer>(), nums);
return result;
}
}
面試注意點(diǎn)
我們大多數(shù)時(shí)候，刷算法題可能都是為了準(zhǔn)備面試盾饮，所以面試的時(shí)候需要注意一些點(diǎn)
- 快速定位到題目的知識(shí)點(diǎn)采桃，找到知識(shí)點(diǎn)的通用模板懒熙，可能需要根據(jù)題目特殊情況做特殊處理。
- 先去朝一個(gè)解決問(wèn)題的方向普办！先拋出可行解工扎，而不是最優(yōu)解凹联！先解決雏掠，再優(yōu)化伤为！
- 代碼的風(fēng)格要統(tǒng)一驮樊，熟悉各類(lèi)語(yǔ)言的代碼規(guī)范。
- 命名盡量簡(jiǎn)潔明了乱陡，盡量不用數(shù)字命名如：i1斯撮、node1台妆、a1沙廉、b2
- 常見(jiàn)錯(cuò)誤總結(jié)
- 訪(fǎng)問(wèn)下標(biāo)時(shí)拘荡，不能訪(fǎng)問(wèn)越界
- 空值 nil 問(wèn)題 run time error
練習(xí)
數(shù)據(jù)結(jié)構(gòu)篇
二叉樹(shù)
二叉樹(shù)遍歷
前序遍歷：先訪(fǎng)問(wèn)根節(jié)點(diǎn)，再前序遍歷左子樹(shù)撬陵，再前序遍歷右子樹(shù)
中序遍歷：先中序遍歷左子樹(shù)珊皿，再訪(fǎng)問(wèn)根節(jié)點(diǎn)，再中序遍歷右子樹(shù)
后序遍歷：先后序遍歷左子樹(shù)袱结，再后序遍歷右子樹(shù)亮隙，再訪(fǎng)問(wèn)根節(jié)點(diǎn)
注意點(diǎn)
- 以根訪(fǎng)問(wèn)順序決定是什么遍歷
- 左子樹(shù)都是優(yōu)先右子樹(shù)
前序遞歸（DFS深度優(yōu)先搜索-從上到下）
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> arrayList = new ArrayList<>();
public ArrayList<Integer> PreOrderTraversal(TreeNode root) {
if (root == null) return arrayList;
arrayList.add(root.val);
PreOrderTraversal(root.left);
PreOrderTraversal(root.right);
return arrayList;
}
}
前序非遞歸
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
ArrayList<Integer> arrayList = new ArrayList<>();
public ArrayList<Integer> PreOrderTraversal(TreeNode root) {
if (root == null) return arrayList;
Deque<TreeNode> deque = new LinkedList<>();
deque.offerLast(root);
while(!deque.isEmpty()){
TreeNode treeNode = deque.pollFirst();
arrayList.add(treeNode.val);
if(treeNode.right !=null) deque.offerFirst(treeNode.right);
if(treeNode.left != null) deque.offerFirst(treeNode.left);
}
return arrayList;
}
}
中序非遞歸
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
ArrayList<Integer> arrayList = new ArrayList<>();
public ArrayList<Integer> InOrderTraversal(TreeNode root) {
if (root == null) return arrayList;
Deque<TreeNode> deque = new LinkedList<>();
TreeNode treeNode = root;
while(treeNode!=null || !deque.isEmpty()){
if(treeNode != null){
deque.offerFirst(treeNode);
treeNode = treeNode.left;
}else{
treeNode = deque.pollFirst();
arrayList.add(treeNode.val);
treeNode = treeNode.right;
}
}
return arrayList;
}
}
后序非遞歸
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
ArrayList<Integer> arrayList = new ArrayList<>();
public ArrayList<Integer> PostOrderTraversal(TreeNode root) {
if (root == null) return arrayList;
Deque<TreeNode> deque = new LinkedList<>();
deque.offerLast(root);
TreeNode preTreeNode = null;
while(!deque.isEmpty()){
TreeNode treeNode = deque.peekFirst();
if((treeNode.left==null&&treeNode.right==null) ||
(treeNode!=null && (preTreeNode==treeNode.left || preTreeNode==treeNode.right))){
arrayList.add(treeNode.val);
preTreeNode = deque.pollFirst();
}else{
if(treeNode.right != null)
deque.offerFirst(treeNode.right);
if(treeNode.left != null)
deque.offerFirst(treeNode.left);
}
}
return arrayList;
}
}
BFS層序遍歷
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
ArrayList<Integer> arrayList = new ArrayList<>();
public ArrayList<Integer> SequenceTraversal(TreeNode root) {
if(root == null) return arrayList;
Deque<TreeNode> deque = new LinkedList<>();
deque.offerLast(root);
while(!deque.isEmpty()){
TreeNode treeNode = deque.pollFirst();
arrayList.add(treeNode.val);
if(treeNode.left != null) deque.offerLast(treeNode.left);
if(treeNode.right !=null) deque.offerLast(treeNode.right);
}
return arrayList;
}
}
DFS深度優(yōu)先搜索-從下到上（分治法）
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> PostOrderTraversal(TreeNode root) {
ArrayList<Integer> arrayList = new ArrayList<>();
// 遞歸返回條件
if (root == null) return arrayList;
// 分段處理
ArrayList<Integer> arrayListLeft = PostOrderTraversal(root.left);
ArrayList<Integer> arrayListRight = PostOrderTraversal(root.right);
// 合并結(jié)果
arrayList.add(root.val);
arrayList.addAll(arrayListLeft);
arrayList.addAll(arrayListRight);
return arrayList;
}
}
注意點(diǎn)：
> ArrayList<Integer> arrayList = new ArrayList<>(); 語(yǔ)句不能定義在方法外
分治法應(yīng)用
先分別處理局部，再合并結(jié)果
適用場(chǎng)景
- 歸并排序
- 二叉樹(shù)相關(guān)問(wèn)題
分治法模板
- 遞歸返回條件
- 分段處理
- 合并結(jié)果
public ResultType Traversal(TreeNode root) {
ResultType result;
//遞歸返回條件
if (root == null) return result;
//分段處理
ResultType left = Traversal(root.left);
ResultType right = Traversal(root.right);
//合并結(jié)果
result = Merge(left, right);
return result;
}
典型示例
分治法遍歷二叉樹(shù)（同上）
歸并排序
public class Solution {
public void MergeSort(int[] array, int[] temp, int start, int end) {
// 遞歸返回條件
if (start >= end) return;
// 分段處理
int mid = (start + end) >> 1;
MergeSort(array, temp, start, mid);
MergeSort(array, temp, mid+1, end);
// 合并結(jié)果
Merge(array, temp, start, mid, end);
}
public void Merge(int[] array, int[] temp, int start ,int mid, int end) {
int leftStart = start;
int leftEnd = mid;
int rightStart = mid+1;
int rightEnd = end;
int index = start;
while(leftStart <= leftEnd && rightStart <= rightEnd)
if(array[leftStart] < array[rightStart])
temp[index++] = array[leftStart++];
else
temp[index++] = array[rightStart++];
while(leftStart <= leftEnd)
temp[index++] = array[leftStart++];
while(rightStart <= rightEnd)
temp[index++] = array[rightStart++];
for(index = start; index<=end; index++)
array[index] = temp[index];
}
}
常見(jiàn)題目示例
給定一個(gè)二叉樹(shù)垢夹，找出其最大深度。
思路：分治法
public int TreeDepth(TreeNode root) {
// 遞歸返回條件
if(root == null) return 0;
// 分段處理
int leftDepth = TreeDepth(root.left);
int rightDepth = TreeDepth(root.right);
// 合并結(jié)果
return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
}
給定一個(gè)二叉樹(shù)维费，判斷它是否是高度平衡的二叉樹(shù)果元。
思路：分治法，左邊平衡 && 右邊平衡 && 左右兩邊高度 <= 1犀盟， 因?yàn)樾枰祷厥欠衿胶饧案叨榷梗捶祷貎蓚€(gè)數(shù)據(jù)，要么合并兩個(gè)數(shù)據(jù)阅畴， 所以用-1 表示不平衡倡怎，>0 表示樹(shù)高度（二義性：一個(gè)變量有兩種含義）。
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
return getDepth(root) != -1;
}
public int getDepth(TreeNode root) {
// 遞歸返回條件
if(root == null) return 0;
// 分段處理
int left = getDepth(root.left);
int right = getDepth(root.right);
// 合并結(jié)果
if(left != -1 && right != -1 && Math.abs(left - right) <= 1)
return Math.max(left, right) + 1;
else
return -1;
}
}
給定一個(gè)非空二叉樹(shù)贱枣，返回其最大路徑和监署。
思路：分治法。節(jié)點(diǎn)的最大貢獻(xiàn)值（當(dāng)前節(jié)點(diǎn)+貢獻(xiàn)值較大的子樹(shù)）纽哥。節(jié)點(diǎn)的最大路徑（當(dāng)前節(jié)點(diǎn)+左子樹(shù)最大貢獻(xiàn)值+右子樹(shù)最大貢獻(xiàn)值）钠乏。先分別計(jì)算左子樹(shù)的最大貢獻(xiàn)值，再計(jì)算右子樹(shù)的最大貢獻(xiàn)值春塌，然后加上當(dāng)前節(jié)點(diǎn)為最大路徑晓避，更新結(jié)果后返回當(dāng)前節(jié)點(diǎn)的最大貢獻(xiàn)值簇捍。
public class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
public int maxGain(TreeNode node) {
// 遞歸返回條件
if (node == null) return 0;
// 分段處理
// 只有在最大貢獻(xiàn)值大于 0 時(shí)，才會(huì)選取對(duì)應(yīng)子節(jié)點(diǎn)
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
// 合并結(jié)果
// 更新最大結(jié)果俏拱，節(jié)點(diǎn)的最大路徑和取決于該節(jié)點(diǎn)的值與該節(jié)點(diǎn)的左右子節(jié)點(diǎn)的最大貢獻(xiàn)值
maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
// 返回該節(jié)點(diǎn)的最大貢獻(xiàn)值
return node.val + Math.max(leftGain, rightGain);
}
}
lowest-common-ancestor-of-a-binary-tree
給定一個(gè)二叉樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先暑塑。
思路：分治法。有左子樹(shù)的公共祖先或者有右子樹(shù)的公共祖先锅必，就返回子樹(shù)的祖先事格，否則返回根節(jié)點(diǎn)
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 遞歸返回條件
if(root == null || root == p || root == q) return root;
// 分段處理
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 合并結(jié)果
if(left != null && right != null) return root;
if(left != null) return left;
if(right != null) return right;
return null;
}
}
BFS 層次應(yīng)用
常見(jiàn)題目示例
binary-tree-level-order-traversal
給你一個(gè)二叉樹(shù)，請(qǐng)你返回其按 層序遍歷 得到的節(jié)點(diǎn)值况毅，每一層輸出一行分蓖。 （即逐層地，從左到右訪(fǎng)問(wèn)所有節(jié)點(diǎn)）尔许。
思路：BFS層序遍歷一樣的代碼么鹤，用一個(gè)隊(duì)列記錄一層的元素，然后掃描這一層元素添加下一層元素到隊(duì)列（一個(gè)數(shù)進(jìn)去出來(lái)一次味廊，所以復(fù)雜度 O(logN)）蒸甜，不同的是，需要使用 # 來(lái)分隔每一層余佛，如果出隊(duì)元素為 # 柠新，說(shuō)明上一層已經(jīng)全部出隊(duì)列，下一層已經(jīng)全部入隊(duì)辉巡，使用迭代器添加進(jìn)list
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Iterator;
public class Solution {
ArrayList<ArrayList<Integer> > levelOrder(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
if(pRoot == null) return arrayList;
deque.offerLast(null);
deque.offerLast(pRoot);
while(deque.size() != 1) {
TreeNode treeNode = deque.pollFirst();
if(treeNode == null) {
Iterator<TreeNode> iterator = deque.iterator();
while(iterator.hasNext())
list.add(((TreeNode)iterator.next()).val);
arrayList.add(new ArrayList<>(list));
list.clear();
deque.offerLast(null);
continue;
}
if(treeNode.left != null) deque.offerLast(treeNode.left);
if(treeNode.right != null) deque.offerLast(treeNode.right);
}
return arrayList;
}
}
binary-tree-level-order-traversal-ii
給定一個(gè)二叉樹(shù)恨憎，返回其節(jié)點(diǎn)值自底向上的層次遍歷。 （即按從葉子節(jié)點(diǎn)所在層到根節(jié)點(diǎn)所在的層郊楣，逐層從左向右遍歷）
思路：同上憔恳，末尾對(duì) arrayList 翻轉(zhuǎn)即可。
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Iterator;
import java.util.Collections;
public class Solution {
public ArrayList<ArrayList<Integer> > levelOrderBottom(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
if(pRoot == null) return arrayList;
deque.offerLast(null);
deque.offerLast(pRoot);
while(deque.size() != 1) {
TreeNode treeNode = deque.pollFirst();
if(treeNode == null) {
Iterator<TreeNode> iterator = deque.iterator();
while(iterator.hasNext())
list.add(((TreeNode)iterator.next()).val);
arrayList.add(new ArrayList<>(list));
list.clear();
deque.offerLast(null);
continue;
}
if(treeNode.left != null) deque.offerLast(treeNode.left);
if(treeNode.right != null) deque.offerLast(treeNode.right);
}
Collections.reverse(arrayList);
return arrayList;
}
}
binary-tree-zigzag-level-order-traversal
給定一個(gè)二叉樹(shù)净蚤，返回其節(jié)點(diǎn)值的鋸齒形層次遍歷钥组。Z 字形遍歷（即先從左往右，再?gòu)挠彝筮M(jìn)行下一層遍歷今瀑，以此類(lèi)推程梦，層與層之間交替進(jìn)行）。
思路：同上橘荠，迭代器迭代順序每次相反即可屿附。
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Iterator;
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
if(pRoot == null) return arrayList;
boolean leftToRight = true;
deque.offerLast(null);
deque.offerLast(pRoot);
while(deque.size() != 1) {
TreeNode treeNode = deque.pollFirst();
if(treeNode == null) {
Iterator<TreeNode> iterator = null;
if(leftToRight) iterator = deque.iterator();
else iterator = deque.descendingIterator();
leftToRight = !leftToRight;
while(iterator.hasNext())
list.add(((TreeNode)iterator.next()).val);
arrayList.add(new ArrayList<>(list));
list.clear();
deque.offerLast(null);
continue;
}
if(treeNode.left != null) deque.offerLast(treeNode.left);
if(treeNode.right != null) deque.offerLast(treeNode.right);
}
return arrayList;
}
}
二叉搜索樹(shù)應(yīng)用
常見(jiàn)題目示例
給定一個(gè)二叉樹(shù)，判斷其是否是一個(gè)有效的二叉搜索樹(shù)砾医。
思路：1. 中序遍歷拿撩，如果中序遍歷得到的節(jié)點(diǎn)的值小于等于前一個(gè) inorder，說(shuō)明不是二叉搜索樹(shù)
? 2. 分治法如蚜，判斷左 MAX < 根 < 右 MIN
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
int inOrder = Integer.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return false;
Deque<TreeNode> deque = new LinkedList<>();
TreeNode treeNode = root;
while(treeNode!=null || !deque.isEmpty()){
if(treeNode != null){
deque.offerFirst(treeNode);
treeNode = treeNode.left;
}else{
treeNode = deque.pollFirst();
if(treeNode.val <= inOrder) return false;
inOrder = treeNode.val;
treeNode = treeNode.right;
}
}
return true;
}
}
public class Solution {
public boolean isValidBSTCore(TreeNode node, int min, int max) {
if (node == null) return true;
int val = node.val;
if (! isValidBSTCore(node.left, min, val)) return false;
if (! isValidBSTCore(node.right, val, max)) return false;
if (val <= min) return false;
if (val >= max) return false;
return true;
}
public boolean isValidBST(TreeNode root) {
return isValidBSTCore(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
}
insert-into-a-binary-search-tree
給定二叉搜索樹(shù)（BST）的根節(jié)點(diǎn)和要插入樹(shù)中的值压恒，將值插入二叉搜索樹(shù)影暴。 返回插入后二叉搜索樹(shù)的根節(jié)點(diǎn)。 保證原始二叉搜索樹(shù)中不存在新值探赫。
思路：DFS 遍歷型宙，若 val < node.val ，則插入到左子樹(shù)伦吠，否則插入到右子樹(shù)
public class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
// insert into the right subtree
if (val < root.val) root.left = insertIntoBST(root.left, val);
// insert into the left subtree
else root.right = insertIntoBST(root.right, val);
return root;
}
}
