一.哈希表
定義
鍵值映射關(guān)系
<img src="https://mmbiz.qpic.cn/mmbiz_png/Z6bicxIx5naLDQzfJtARmicCd4F6ASYliaibastwh0eUlfWtHFU7I7zSmtzRfDgg25fic8eCx7QZkrTibs8yKjCAQ1oQ/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1" alt="img" style="zoom:33%;" />
時間復(fù)雜度
寫入 O(1)
讀取 O(1)
擴(kuò)容 O(n)
哈希函數(shù)
把key轉(zhuǎn)成index尋找值
index = HashCode ("001121") % Array.length = 7
<img src="https://mmbiz.qpic.cn/mmbiz_png/Z6bicxIx5naLDQzfJtARmicCd4F6ASYliaib9ywjXKqGDwR8iaNia8BHhPcYt6rwMI5L2EyAMTIql226icxIGicicV1Kdpw/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1" alt="img" style="zoom:33%;" />
實戰(zhàn)題目
242. 有效的字母異位詞
/*
1.暴力 sort 遍歷比較
時間復(fù)雜度 O(nlogn)
空間復(fù)雜度 O(1)
2.哈希表 比較字母出現(xiàn)的頻次
或者26個大小的數(shù)組，一邊自增富腊，一邊自減。所有的都為0則相等。
時間復(fù)雜度O(n)
空間復(fù)雜度O(26)
*/
public class ValidAnagram {
/**
* 解法1 排序后比較
*
* 分別將兩個字符串排序入愧，然后比較
*
* 時間復(fù)雜度：O(nlogn)
* 空間復(fù)雜度：O(1)
*/
public boolean isAnagram(String s, String t){
if (s.length() != t.length()) return false;
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1, str2);
}
/**
* 解法2 計數(shù)器
*
* 用計數(shù)器統(tǒng)計每個字符出現(xiàn)的次數(shù)
*
* 時間復(fù)雜度：O(n)
* 空間復(fù)雜度：O(1)
*/
public static boolean isAnagram2(String s, String t){
if (s.length() != t.length()) return false;
int[] table = new int[26];
for (int i = 0; i < s.length(); i++) {
//當(dāng)前字符 - a孝赫，a = 97
table[s.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
table[t.charAt(i) - 'a']--;
//減 1 之后出現(xiàn)次數(shù)小于就說明就在 s 中從未出現(xiàn)的字符
if (table[t.charAt(i) - 'a'] < 0) return false;
}
return true;
}
}
49. 字母異位詞分組
/*
方法一：
用HashMap接收最后的結(jié)果萤晴，
對原數(shù)組字符串進(jìn)行遍歷，轉(zhuǎn)成字符數(shù)組试和，排序，轉(zhuǎn)成字符串
key為排序后的字符串纫普，value為原來的元素阅悍。
返回HashMap.values。
時間復(fù)雜度 O(NKlogK) N是字符串?dāng)?shù)組個數(shù) K為字符串最大長度
空間復(fù)雜度 O(NK) 開辟的ans哈希表
方法二：建議課后背誦
和方法一一個意思昨稼。只是用26個數(shù)組去接节视。沒什么意義。只是時間復(fù)雜度小假栓。不用排序寻行。
時間復(fù)雜度 O(N * (K > 26 ? K : 26)) N是字符串?dāng)?shù)組個數(shù) K為字符串最大長度
空間復(fù)雜度 O(NK)
*/
/*
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList();
Map<String, List> ans = new HashMap<String, List>();
for (String s : strs) {
char[] ca = s.toCharArray(); // 每個元素變成字符串?dāng)?shù)組
Arrays.sort(ca); // 數(shù)組排序
String key = String.valueOf(ca); // 轉(zhuǎn)成字符串作為Key。key: 排序后的數(shù)組 value：字母異位詞的集合
if (!ans.containsKey(key)) ans.put(key, new ArrayList()); // 結(jié)果里沒有這個key匾荆，就放入key拌蜘，值為數(shù)組
ans.get(key).add(s); // 數(shù)組里加原來這個元素
}
return new ArrayList(ans.values());
}
}
*/
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList();
Map<String, List> ans = new HashMap<String, List>();
int[] count = new int[26];
for (String s : strs) {
Arrays.fill(count, 0); // 數(shù)組每個值賦0
for (char c : s.toCharArray()) count[c - 'a']++; // 字母對應(yīng)位自增
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < 26; i++) {
sb.append('#');
sb.append(count[i]); // #2#1#0#0
}
String key = sb.toString(); // 轉(zhuǎn)成字符串作為密鑰
if (!ans.containsKey(key)) ans.put(key, new ArrayList()); // 相同key，放一個數(shù)組里
ans.get(key).add(s);
}
return new ArrayList(ans.values());
}
}
1. 兩數(shù)之和
/*
找出數(shù)組中兩個數(shù)字滿足目標(biāo)值的兩個數(shù)字
方法一：暴力迭代
i -> 0, len - 2
j -> i+1, len - 1
nums[i] + nums[j] == target
時間復(fù)雜度O(n^2)
空間復(fù)雜度O(n)
方法二： 利用哈希表牙丽，兩次迭代
第一次简卧，將所有數(shù)字放入哈希表中，
第二次烤芦，遍歷哈希表举娩，查找目標(biāo)值-當(dāng)前值的結(jié)果是否在哈希中
時間復(fù)雜度O(n * 2)
空間復(fù)雜度O(n)
方法三：利用哈希表，一次迭代
其實只需要一次构罗，先判斷目標(biāo)值-當(dāng)前值的結(jié)果是否在哈希中铜涉，
不存在，在把值放進(jìn)去绰播。
時間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)
*/
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
二.樹
定義
樹是n個節(jié)點的有限集骄噪。
在非空樹中，有如下特點：
有且一個根節(jié)點
當(dāng)n>1時蠢箩，其余節(jié)點可分為m個互不相交的有限集链蕊，每一個集合本身又是一個樹事甜，并稱為根的子樹。
樹的遍歷
（1）深度優(yōu)先
前序：根左右
<img src="https://mmbiz.qpic.cn/mmbiz_png/Z6bicxIx5naLDQzfJtARmicCd4F6ASYliaib40oOC9T5IzJjSPAcrhUDicVG9HdKGVEwySEC3EvX1NqdricI68Arqm6g/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1" alt="img" style="zoom:33%;" />
中序：左根右
<img src="https://mmbiz.qpic.cn/mmbiz_png/Z6bicxIx5naLDQzfJtARmicCd4F6ASYliaibnS3Lgz89n4peOQL0dpOibjibhyUtqdKbMFNtwn4DTfOO7fFRcqhWH1Zg/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1" alt="img" style="zoom:33%;" />
后序：左右根
<img src="https://mmbiz.qpic.cn/mmbiz_png/Z6bicxIx5naLDQzfJtARmicCd4F6ASYliaibM9ibtl8CeLLhDykSFKJAwsljsBOCMqAKVNr4FMO1UC8RUrXYyd9Nb4Q/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1" alt="img" style="zoom:33%;" />
實現(xiàn)方式：遞歸或棧滔韵。
（2）廣度優(yōu)先
層序：一層一層遍歷逻谦。
<img src="https://mmbiz.qpic.cn/mmbiz_png/Z6bicxIx5naLDQzfJtARmicCd4F6ASYliaib81wdmp22Bz3N1Ju6TtB2oiaIgpDFdBrTCXYic3czK5mEfTxcoA59gY1w/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1" alt="img" style="zoom:33%;" />
實現(xiàn)方式：隊列。
三.二叉樹
二叉樹
二叉陪蜻，顧名思義邦马，這種樹的每個節(jié)點最多有2個孩子節(jié)點。注意宴卖，這里是最多有2個滋将，也可能只有1個，或者沒有孩子節(jié)點症昏。
滿二叉樹?
一個二叉樹的所有非葉子節(jié)點都存在左右孩子随闽，并且所有葉子節(jié)點都在同一層級上，那么這個樹就是滿二叉樹肝谭。
完全二叉樹
對一個有n個節(jié)點的二叉樹掘宪，按層級順序編號，則所有節(jié)點的編號為從1到n攘烛。如果這個樹所有節(jié)點和同樣深度的滿二叉樹的編號為從1到n的節(jié)點位置相同魏滚，則這個二叉樹為完全二叉樹。
倒數(shù)第二層滿坟漱，最后一層全靠左
img
二叉查找樹
定義
二叉查找樹在二叉樹的基礎(chǔ)上增加了以下幾個條件：
如果左子樹不為空鼠次，則左子樹上所有節(jié)點的值均小于根節(jié)點的值。
如果右子樹不為空芋齿，則右子樹上所有節(jié)點的值均大于根節(jié)點的值须眷。
左、右子樹也都是二叉查找樹沟突。
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom: 33%;" />
作用
- 查找==》二分查找花颗。
- 排序==》中序遍歷。
實現(xiàn)方式
- 鏈表惠拭。
- 數(shù)組：對于稀疏二叉樹來說扩劝，數(shù)組表示法是非常浪費空間的。
實戰(zhàn)題目
589. N叉樹的前序遍歷
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> res = new ArrayList<Integer>();
Stack<Node> stack = new Stack<Node>();
if(root == null)
return res;
stack.push(root);
while(!stack.isEmpty())
{
Node node = stack.pop();
res.add (node.val);
for(int i = node.children.size()-1;i>= 0;i--)
{
stack.add(node.children.get(i));
}
}
return res;
}
}
590. N叉樹的后序遍歷
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
//迭代實現(xiàn)：直接反轉(zhuǎn)先序結(jié)果即可
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> res_pre = new ArrayList<>();
if(root == null)
return res_pre;
Stack<Node> s = new Stack<>();
s.push(root);
while(!s.isEmpty()){
Node n = s.pop();
res_pre.add(n.val);
for(Node node : n.children)
s.push(node);
}
Collections.reverse(res_pre);
return res_pre;
}
}
429. N叉樹的層序遍歷
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(Node root) {
helper(root, 1);
return res;
}
public void helper(Node root, int level) {
if (root == null) return;
if (res.size() < level) res.add(new ArrayList<Integer>());
res.get(level - 1).add(root.val);
for (Node child : root.children)
helper(child, level + 1);
}
}
104. 二叉樹的最大深度
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
112. 路徑總和
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if (root.left == null && root.right == null) return root.val == sum;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
94. 二叉樹的中序遍歷
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
* [1,null,2,3]
* 二叉樹的中序遍歷职辅。題目說不讓用遞歸棒呛。這題只能用棧。
中序遍歷：左-根-右
* 方法一：遞歸
* 時間復(fù)雜度 O(n)
* 空間復(fù)雜度 O(n)
* 方法二：棧的遍歷域携。建議背誦簇秒。
指針不為空，棧不為空秀鞭，就不結(jié)束趋观。
指針不為空扛禽，就一直找左兒子，放左兒子
直到左兒子沒了皱坛，就開始彈编曼。放入結(jié)果中。然后指右兒子剩辟。
* 時間復(fù)雜度 O(n)
* 空間復(fù)雜度 O(n)
方法三：莫里斯遍歷
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
// 結(jié)果鏈表
List<Integer> res = new ArrayList<>();
// 棧：工具人角色
Stack<TreeNode> stack = new Stack<>();
// curr 當(dāng)前指針掐场，從根開始
TreeNode curr = root;
// 指針不為Null且棧非空
while (curr != null || !stack.isEmpty()) {
// 放的步驟：指針不為null。將左邊的都放先進(jìn)去贩猎。當(dāng)沒有左兒子了熊户，就開始彈。
while (curr != null) {
// 把指針放進(jìn)去
stack.push(curr);
// 指向左子樹
curr = curr.left;
}
// 彈出棧頂值吭服，值放入結(jié)果鏈表敏弃。指針指向右兒子。
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
}
/*
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
public void helper(TreeNode root, List<Integer> res) {
// 根不為空
if (root != null) {
// 左子樹不為空
if (root.left != null) {
// 就放左子樹
helper(root.left, res);
}
// 然后放中間數(shù)
res.add(root.val);
// 右子樹不為空噪馏，就放右子樹
if (root.right != null) {
helper(root.right, res);
}
}
}
}*/
22. 括號生成
/*
生成所有n個有效括號
輸入：n = 3
輸出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
*/
// 遞歸
// public class Solution {
// ArrayList<String> res = new ArrayList<>();
// public List<String> generateParenthesis(int n) {
// // 初始條件
// generate(0, 0, n, "");
// // 結(jié)束條件
// return res;
// }
// // 處理
// private void generate(int leftCnt, int rightCnt, int n, String s) {
// // 下鉆
// // 如果左、右括號等于n個绿饵，將值放入結(jié)果中
// if (leftCnt == n && rightCnt == n) {
// res.add(s);
// return;
// }
// // 只要左括號沒有達(dá)到n個欠肾，就可以加
// if (leftCnt < n) generate(leftCnt + 1, rightCnt, n, s + "(");
// // 右括號數(shù)量如果小于左括號，就可以加
// if (rightCnt < leftCnt) generate(leftCnt, rightCnt + 1, n, s + ")");
// // 清除全局臨時變量
// }
// public static void main(String[] args) {
// System.out.println(new Solution().generateParenthesis(3));
// }
// }
// 遞歸拟赊。確保括號有效性刺桃。只要要求左括號先行于右括號。
class Solution {
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
dfs(n, n, "");
return res;
}
private void dfs(int left, int right, String curStr) {
if (left == 0 && right == 0) { // 左右括號都不剩余了吸祟，遞歸終止
res.add(curStr);
return;
}
// 第一次會進(jìn)去瑟慈。第二次會有兩個分叉
if (left > 0) { // 如果左括號還剩余的話，可以拼接左括號
dfs(left - 1, right, curStr + "(");
}
// 第一次是進(jìn)不去的屋匕，因為左右是相等的葛碧。第二次進(jìn)入后，左右等號數(shù)量又相等了过吻。
if (right > left) { // 如果右括號剩余多于左括號剩余的話进泼，可以拼接右括號
dfs(left, right - 1, curStr + ")");
}
}
}
98. 驗證二叉搜索樹
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
方法一：根據(jù)定義，左子樹必須小于當(dāng)前節(jié)點
右子樹必須大于當(dāng)前節(jié)點
時間復(fù)雜度 O(n)
空間復(fù)雜度 O(n)
方法二：中序遍歷是遞增的纤虽，用臨時變量去接乳绕，每次都比較
*/
public class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
// 判斷是否是有效二叉搜索樹，左子樹小于當(dāng)前節(jié)點逼纸，右子樹大于當(dāng)前節(jié)點
public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
// null符合要求
if (root == null) return true;
if (root.val >= maxVal || root.val <= minVal) return false;
// 左邊這個：有效的是左節(jié)點與最大值洋措。右邊這個：有效的是右節(jié)點與最小值。
return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
}
}
// 通過中序遍歷來驗證
class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
// 訪問左子樹
if (!isValidBST(root.left)) {
return false;
}
// 訪問當(dāng)前節(jié)點：如果當(dāng)前節(jié)點小于等于中序遍歷的前一個節(jié)點杰刽，說明不滿足BST菠发，返回 false王滤；否則繼續(xù)遍歷。
if (root.val <= pre) {
return false;
}
pre = root.val;
// 訪問右子樹
return isValidBST(root.right);
}
}
104. 二叉樹的最大深度
public class MaximumDepthOfBinaryTree {
/**
* 解法1 遞歸
*
* 遞歸循環(huán)做的事情：先求左子樹深度雷酪，再求右子樹深度淑仆，然后取兩者最大，再加上自身一層的深度
*
* 時間復(fù)雜度: O(n)
* 空間復(fù)雜度: 最壞時樹完全不平衡 O(n)哥力，最好時樹完全平衡 O(logn)
* @param root：根節(jié)點
* @return 樹的最大深度
*/
public int maxDepth(TreeNode root) {
//遞歸終止條件：葉子節(jié)點無左右子節(jié)點
if (root == null)
return 0;
else {
//左子樹深度
int leftHeight = maxDepth(root.left);
//右子樹深度
int rightHeight = maxDepth(root.right);
// + 1 表示每次遞歸結(jié)束蔗怠，求深度的時候，要把自身所在一層深度加上
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
class Solution {
public int maxDepth(TreeNode root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
105. 從前序與中序遍歷序列構(gòu)造二叉樹
public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
/**
* 解法1 遞歸
*
* 前序便利的第一個元素一定是樹的根吩跋，然后這個根將中序遍歷分成左右兩顆子樹寞射，再通過移動指針遞歸兩個子樹，不停給左右子節(jié)點賦值锌钮，最后完成樹的構(gòu)建
*
* @param preOrder: 前序遍歷
* @param inOrder: 中序遍歷
* @return 構(gòu)建好樹返回根節(jié)點
*/
public TreeNode buildTree(int[] preOrder, int[] inOrder){
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < inOrder.length; i++)
map.put(inOrder[i], i);
return build(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1, map);
}
/**
* @param pre : 前序遍歷 preOrder
* @param ps : preOrder start
* @param pe : preOrder end
* @param in : 中序遍歷 inOrder
* @param is : inOrder start
* @param ie : inOrder end
* @param map : inOrder map - key: 中序遍歷數(shù)組元素 value: 元素數(shù)組下表
* @return 構(gòu)建完成返回根節(jié)點
*/
private TreeNode build(int[] pre, int ps, int pe, int[] in, int is, int ie, Map<Integer, Integer> map) {
if (ps > pe || is > ie) return null;
//前序遍歷的第一個元素一定是樹的根
TreeNode root = new TreeNode(pre[ps]);
//找到這個根在中序遍歷中的位置桥温，它將中序遍歷分成了左右兩顆子樹
int rootIndex = map.get(root.val);
//距離 = 根在中序遍歷中的位置 - 左子節(jié)點的位置
int distance = rootIndex - is;
/**
* ps + 1 : 前序遍歷中 - 左子樹的開始節(jié)點
* ps + distance : 前序遍歷中 - 左子樹的結(jié)束節(jié)點
* is : 中序遍歷中 - 左子樹的開始節(jié)點
* rootIndex - 1 : 中序遍歷中 - 左子樹的結(jié)束節(jié)點
*/
root.left = build(pre, ps + 1, ps + distance, in, is, rootIndex - 1, map);
/**
* ps + distance + 1 : 前序遍歷中 - 右子樹的開始節(jié)點
* pe : 前序遍歷中 - 右子樹的結(jié)束節(jié)點
* rootIndex + 1 : 中序遍歷中 - 右子樹的開始節(jié)點
* ie : 中序遍歷中 - 右子樹的結(jié)束節(jié)點
*/
root.right = build(pre, ps + distance + 1, pe, in, rootIndex + 1, ie, map);
return root;
}
}
111. 二叉樹的最小深度
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class MinimumDepthOfBinaryTree {
/**
* 解法1 遞歸
*
* 取左子樹的深度和右子樹的深度兩者最小為樹的最小深度
*
* 時間復(fù)雜度：O(n)
* 空間復(fù)雜度：最壞 O(n)，最好 O(logn)
*
* @param root: 根節(jié)點
* @return 返回二叉樹的最小深度
*/
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left != null && root.right!= null)
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
else
//如果左子節(jié)點為空或者右子節(jié)點為空梁丘，那么 root 有一個葉子節(jié)點也算是一層侵浸，所以取 max，再加上當(dāng)前節(jié)點所在的一層
//如果左右子節(jié)點都為空氛谜，那么返回節(jié)點所在的一層
return Math.max(minDepth(root.left), minDepth(root.right)) + 1;
}
}
