算法训练营-第二周-哈希树堆图
2020-08-24 本文已影响0人
我是阿喵酱
一.哈希表
定义
键值映射关系
<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%;" />
时间复杂度
写入 O(1)
读取 O(1)
扩容 O(n)
哈希函数
把key转成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%;" />
实战题目
242. 有效的字母异位词
/*
1.暴力 sort 遍历比较
时间复杂度 O(nlogn)
空间复杂度 O(1)
2.哈希表 比较字母出现的频次
或者26个大小的数组，一边自增，一边自减。所有的都为0则相等。
时间复杂度O(n)
空间复杂度O(26)
*/
public class ValidAnagram {
/**
* 解法1 排序后比较
*
* 分别将两个字符串排序，然后比较
*
* 时间复杂度：O(nlogn)
* 空间复杂度：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 计数器
*
* 用计数器统计每个字符出现的次数
*
* 时间复杂度：O(n)
* 空间复杂度：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++) {
//当前字符 - a，a = 97
table[s.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
table[t.charAt(i) - 'a']--;
//减 1 之后出现次数小于就说明就在 s 中从未出现的字符
if (table[t.charAt(i) - 'a'] < 0) return false;
}
return true;
}
}
49. 字母异位词分组
/*
方法一：
用HashMap接收最后的结果，
对原数组字符串进行遍历，转成字符数组，排序，转成字符串
key为排序后的字符串，value为原来的元素。
返回HashMap.values。
时间复杂度 O(NKlogK) N是字符串数组个数 K为字符串最大长度
空间复杂度 O(NK) 开辟的ans哈希表
方法二：建议课后背诵
和方法一一个意思。只是用26个数组去接。没什么意义。只是时间复杂度小。不用排序。
时间复杂度 O(N * (K > 26 ? K : 26)) N是字符串数组个数 K为字符串最大长度
空间复杂度 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(); // 每个元素变成字符串数组
Arrays.sort(ca); // 数组排序
String key = String.valueOf(ca); // 转成字符串作为Key。key: 排序后的数组 value：字母异位词的集合
if (!ans.containsKey(key)) ans.put(key, new ArrayList()); // 结果里没有这个key，就放入key，值为数组
ans.get(key).add(s); // 数组里加原来这个元素
}
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); // 数组每个值赋0
for (char c : s.toCharArray()) count[c - 'a']++; // 字母对应位自增
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(); // 转成字符串作为密钥
if (!ans.containsKey(key)) ans.put(key, new ArrayList()); // 相同key，放一个数组里
ans.get(key).add(s);
}
return new ArrayList(ans.values());
}
}
1. 两数之和
/*
找出数组中两个数字满足目标值的两个数字
方法一：暴力迭代
i -> 0, len - 2
j -> i+1, len - 1
nums[i] + nums[j] == target
时间复杂度O(n^2)
空间复杂度O(n)
方法二： 利用哈希表，两次迭代
第一次，将所有数字放入哈希表中，
第二次，遍历哈希表，查找目标值-当前值的结果是否在哈希中
时间复杂度O(n * 2)
空间复杂度O(n)
方法三：利用哈希表，一次迭代
其实只需要一次，先判断目标值-当前值的结果是否在哈希中，
不存在，在把值放进去。
时间复杂度：O(n)
空间复杂度：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个节点的有限集。
在非空树中，有如下特点：
-
有且一个根节点
-
当n>1时，其余节点可分为m个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。
树的遍历
（1）深度优先
前序：根左右
<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%;" />
实现方式：递归或栈。
（2）广度优先
层序：一层一层遍历。
<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%;" />
实现方式：队列。
三.二叉树
二叉树
二叉，顾名思义，这种树的每个节点最多有2个孩子节点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点。
满二叉树?
一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。
完全二叉树
对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。
倒数第二层满，最后一层全靠左
img
二叉查找树
定义
二叉查找树在二叉树的基础上增加了以下几个条件：
-
如果左子树不为空，则左子树上所有节点的值均小于根节点的值。
-
如果右子树不为空，则右子树上所有节点的值均大于根节点的值。
-
左、右子树也都是二叉查找树。
<img src="https://hexo-1257630696.cos.ap-singapore.myqcloud.com/img/640" alt="img" style="zoom: 33%;" />
作用
- 查找==》二分查找。
- 排序==》中序遍历。
实现方式
- 链表。
- 数组：对于稀疏二叉树来说，数组表示法是非常浪费空间的。
实战题目
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;
}
};
*/
//迭代实现：直接反转先序结果即可
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]
* 二叉树的中序遍历。题目说不让用递归。这题只能用栈。
中序遍历：左-根-右
* 方法一：递归
* 时间复杂度 O(n)
* 空间复杂度 O(n)
* 方法二：栈的遍历。建议背诵。
指针不为空，栈不为空，就不结束。
指针不为空，就一直找左儿子，放左儿子
直到左儿子没了，就开始弹。放入结果中。然后指右儿子。
* 时间复杂度 O(n)
* 空间复杂度 O(n)
方法三：莫里斯遍历
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
// 结果链表
List<Integer> res = new ArrayList<>();
// 栈：工具人角色
Stack<TreeNode> stack = new Stack<>();
// curr 当前指针，从根开始
TreeNode curr = root;
// 指针不为Null且栈非空
while (curr != null || !stack.isEmpty()) {
// 放的步骤：指针不为null。将左边的都放先进去。当没有左儿子了，就开始弹。
while (curr != null) {
// 把指针放进去
stack.push(curr);
// 指向左子树
curr = curr.left;
}
// 弹出栈顶值，值放入结果链表。指针指向右儿子。
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);
}
// 然后放中间数
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, "");
// // 结束条件
// return res;
// }
// // 处理
// private void generate(int leftCnt, int rightCnt, int n, String s) {
// // 下钻
// // 如果左、右括号等于n个，将值放入结果中
// if (leftCnt == n && rightCnt == n) {
// res.add(s);
// return;
// }
// // 只要左括号没有达到n个，就可以加
// if (leftCnt < n) generate(leftCnt + 1, rightCnt, n, s + "(");
// // 右括号数量如果小于左括号，就可以加
// 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;
}
// 第一次会进去。第二次会有两个分叉
if (left > 0) { // 如果左括号还剩余的话，可以拼接左括号
dfs(left - 1, right, curStr + "(");
}
// 第一次是进不去的，因为左右是相等的。第二次进入后，左右等号数量又相等了。
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; }
* }
方法一：根据定义，左子树必须小于当前节点
右子树必须大于当前节点
时间复杂度 O(n)
空间复杂度 O(n)
方法二：中序遍历是递增的，用临时变量去接，每次都比较
*/
public class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
// 判断是否是有效二叉搜索树，左子树小于当前节点，右子树大于当前节点
public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
// null符合要求
if (root == null) return true;
if (root.val >= maxVal || root.val <= minVal) return false;
// 左边这个：有效的是左节点与最大值。右边这个：有效的是右节点与最小值。
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;
}
// 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
if (root.val <= pre) {
return false;
}
pre = root.val;
// 访问右子树
return isValidBST(root.right);
}
}
104. 二叉树的最大深度
public class MaximumDepthOfBinaryTree {
/**
* 解法1 递归
*
* 递归循环做的事情：先求左子树深度，再求右子树深度，然后取两者最大，再加上自身一层的深度
*
* 时间复杂度: O(n)
* 空间复杂度: 最坏时树完全不平衡 O(n)，最好时树完全平衡 O(logn)
* @param root：根节点
* @return 树的最大深度
*/
public int maxDepth(TreeNode root) {
//递归终止条件：叶子节点无左右子节点
if (root == null)
return 0;
else {
//左子树深度
int leftHeight = maxDepth(root.left);
//右子树深度
int rightHeight = maxDepth(root.right);
// + 1 表示每次递归结束，求深度的时候，要把自身所在一层深度加上
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. 从前序与中序遍历序列构造二叉树
public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
/**
* 解法1 递归
*
* 前序便利的第一个元素一定是树的根，然后这个根将中序遍历分成左右两颗子树，再通过移动指针递归两个子树，不停给左右子节点赋值，最后完成树的构建
*
* @param preOrder: 前序遍历
* @param inOrder: 中序遍历
* @return 构建好树返回根节点
*/
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: 中序遍历数组元素 value: 元素数组下表
* @return 构建完成返回根节点
*/
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);
//距离 = 根在中序遍历中的位置 - 左子节点的位置
int distance = rootIndex - is;
/**
* ps + 1 : 前序遍历中 - 左子树的开始节点
* ps + distance : 前序遍历中 - 左子树的结束节点
* is : 中序遍历中 - 左子树的开始节点
* rootIndex - 1 : 中序遍历中 - 左子树的结束节点
*/
root.left = build(pre, ps + 1, ps + distance, in, is, rootIndex - 1, map);
/**
* ps + distance + 1 : 前序遍历中 - 右子树的开始节点
* pe : 前序遍历中 - 右子树的结束节点
* rootIndex + 1 : 中序遍历中 - 右子树的开始节点
* ie : 中序遍历中 - 右子树的结束节点
*/
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 递归
*
* 取左子树的深度和右子树的深度两者最小为树的最小深度
*
* 时间复杂度：O(n)
* 空间复杂度：最坏 O(n)，最好 O(logn)
*
* @param root: 根节点
* @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
//如果左子节点为空或者右子节点为空，那么 root 有一个叶子节点也算是一层，所以取 max，再加上当前节点所在的一层
//如果左右子节点都为空，那么返回节点所在的一层
return Math.max(minDepth(root.left), minDepth(root.right)) + 1;
}
}
