参考自algorithm-pattern
翻译为java代码
入门篇
算法快速入门
数据结构与算法
数据结构是一种数据的表现形式，如链表、二叉树、栈、队列等都是内存中一段数据表现的形式。 算法是一种通用的解决问题的模板或者思路，大部分数据结构都有一套通用的算法模板，所以掌握这些通用的算法模板即可解决各种算法问题。
后面会分专题讲解各种数据结构、基本的算法模板、和一些高级算法模板，每一个专题都有一些经典练习题，完成所有练习的题后，你对数据结构和算法会有新的收获和体会。
先介绍两个算法题，试试感觉~
示例 1
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。
思路：核心点遍历给定字符串字符，判断以当前字符开头字符串是否等于目标字符串
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
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
思路：这是一个典型的应用回溯法的题目，简单来说就是穷尽所有可能性，算法模板如下
result = []
public void backtrack(选择列表,路径):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(选择列表,路径)
撤销选择
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;
}
}
面试注意点
我们大多数时候，刷算法题可能都是为了准备面试，所以面试的时候需要注意一些点
- 快速定位到题目的知识点，找到知识点的通用模板，可能需要根据题目特殊情况做特殊处理。
- 先去朝一个解决问题的方向！先抛出可行解，而不是最优解！先解决，再优化！
- 代码的风格要统一，熟悉各类语言的代码规范。
- 命名尽量简洁明了，尽量不用数字命名如：i1、node1、a1、b2
- 常见错误总结
- 访问下标时，不能访问越界
- 空值 nil 问题 run time error
练习
数据结构篇
二叉树
二叉树遍历
前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树
中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树
后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点
注意点
- 以根访问顺序决定是什么遍历
- 左子树都是优先右子树
前序递归（DFS深度优先搜索-从上到下）
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深度优先搜索-从下到上（分治法）
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);
// 合并结果
arrayList.add(root.val);
arrayList.addAll(arrayListLeft);
arrayList.addAll(arrayListRight);
return arrayList;
}
}
注意点：
> ArrayList<Integer> arrayList = new ArrayList<>(); 语句不能定义在方法外
分治法应用
先分别处理局部，再合并结果
适用场景
- 归并排序
- 二叉树相关问题
分治法模板
- 递归返回条件
- 分段处理
- 合并结果
public ResultType Traversal(TreeNode root) {
ResultType result;
//递归返回条件
if (root == null) return result;
//分段处理
ResultType left = Traversal(root.left);
ResultType right = Traversal(root.right);
//合并结果
result = Merge(left, right);
return result;
}
典型示例
分治法遍历二叉树（同上）
归并排序
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);
// 合并结果
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];
}
}
常见题目示例
给定一个二叉树，找出其最大深度。
思路：分治法
public int TreeDepth(TreeNode root) {
// 递归返回条件
if(root == null) return 0;
// 分段处理
int leftDepth = TreeDepth(root.left);
int rightDepth = TreeDepth(root.right);
// 合并结果
return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
}
给定一个二叉树，判断它是否是高度平衡的二叉树。
思路：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1， 因为需要返回是否平衡及高度，要么返回两个数据，要么合并两个数据， 所以用-1 表示不平衡，>0 表示树高度（二义性：一个变量有两种含义）。
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);
// 合并结果
if(left != -1 && right != -1 && Math.abs(left - right) <= 1)
return Math.max(left, right) + 1;
else
return -1;
}
}
给定一个非空二叉树，返回其最大路径和。
思路：分治法。节点的最大贡献值（当前节点+贡献值较大的子树）。节点的最大路径（当前节点+左子树最大贡献值+右子树最大贡献值）。先分别计算左子树的最大贡献值，再计算右子树的最大贡献值，然后加上当前节点为最大路径，更新结果后返回当前节点的最大贡献值。
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;
// 分段处理
// 只有在最大贡献值大于 0 时，才会选取对应子节点
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
// 合并结果
// 更新最大结果，节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
// 返回该节点的最大贡献值
return node.val + Math.max(leftGain, rightGain);
}
}
lowest-common-ancestor-of-a-binary-tree
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
思路：分治法。有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点
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);
// 合并结果
if(left != null && right != null) return root;
if(left != null) return left;
if(right != null) return right;
return null;
}
}
BFS 层次应用
常见题目示例
binary-tree-level-order-traversal
给你一个二叉树，请你返回其按 层序遍历 得到的节点值，每一层输出一行。 （即逐层地，从左到右访问所有节点）。
思路：BFS层序遍历一样的代码，用一个队列记录一层的元素，然后扫描这一层元素添加下一层元素到队列（一个数进去出来一次，所以复杂度 O(logN)），不同的是，需要使用 # 来分隔每一层，如果出队元素为 # ，说明上一层已经全部出队列，下一层已经全部入队，使用迭代器添加进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
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
思路：同上，末尾对 arrayList 翻转即可。
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
给定一个二叉树，返回其节点值的锯齿形层次遍历。Z 字形遍历（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
思路：同上，迭代器迭代顺序每次相反即可。
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;
}
}
二叉搜索树应用
常见题目示例
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
思路：1. 中序遍历，如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
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
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
思路：DFS 遍历，若 val < node.val ，则插入到左子树，否则插入到右子树
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;
}
}
网友评论