2019LeetCode暑期打卡活动 Week 7 基本数据结构
一些基础数据结构的LeetCode题目
LeetCode 1 两数之和
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int n = nums.length;
for (int i = 0; i < n; i ++ ) {
if (map.containsKey(target - nums[i])) {
return new int[]{i, map.get(target - nums[i])};
} else {
map.put(nums[i], i);
}
}
return new int[]{0, 0};
}
}
LeetCode 187 重复的DNA序列
这道题的关键在于，挑选一些数据结构满足快速地进行如下两个操作
1. 插入一个字符串
2. 统计字符串出现的次数
可选方案 trie树 hashmap
第一步 把所有长度等于10的字符串添加进去
第二步 统计次数大于等于2 的输出
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
Map<String, Integer> map = new HashMap<>();
List<String> res = new ArrayList<>();
if (s.length() < 10) return res;
for (int i = 0; i + 10 <= s.length(); i ++ ) {
String str = s.substring(i, i + 10);
int cnt = map.getOrDefault(str, 0);
map.put(str, cnt + 1);
if (cnt == 1) res.add(str); // 本该统计大于等于2的，但为了避免重复计算，可以在等于的时候
}
return res;
}
}
LeetCode 706 设计哈希映射
之前基础课里的哈希表应该说是哈希集合，只存储key值而不是键值对
此处的代码是从大佬摘过来的https://www.acwing.com/activity/content/code/content/104588/
class MyHashMap {
class Node {
int key;
int value;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
next = null;
}
}
// 冲突解决：拉链法和开放地址法
// 本设计：拉链法，在哈希表中的每个位置上，用链表存储所有映射到该位置的元素。
// 最好要画图理解这个方法
private int size = 31;
private Node[] hashTable;
public MyHashMap() {
hashTable = new Node[size];
}
/**
* 可能需要遍历，遍历完成以后都没有找到合适的 key，就放在最后
*/
public void put(int key, int value) {
Node node = hashTable[key % size];
Node pre = node;
// 如果找不到，就初始化一个结点
if (node == null) {
hashTable[key % size] = new Node(key, value);
return;
}
// 有冲突，就接到后面
while (node != null) {
// 有一样的 key ，就更新 value
if (node.key == key) {
node.value = value;
return;
}
// 否则一个结点一个结点找下去
pre = node;
node = node.next;
}
pre.next = new Node(key, value);
}
public int get(int key) {
Node node = hashTable[key % size];
while (node != null) {
if (node.key == key) {
return node.value;
}
node = node.next;
}
return -1;
}
public void remove(int key) {
Node node = hashTable[key % size];
Node pre = node;
while (node != null) {
if (node.key == key) {
// 如果要删除的元素正好在开始
if (pre.key == node.key) {
hashTable[key % size] = node.next;
return;
}
pre.next = node.next;
return;
}
pre = node;
node = node.next;
}
}
}
// 作者：Willis
// 链接：https://www.acwing.com/activity/content/code/content/104588/
// 来源：AcWing
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
下面这个大佬是利用了题目给出的条件https://www.acwing.com/activity/content/code/content/95591/
class MyHashMap {
int[] entry;
boolean[] valid;
public MyHashMap() {
entry = new int[1000010];
valid = new boolean[1000010];
}
public void put(int key, int value) {
entry[key] = value;
valid[key] = true;
}
public int get(int key) {
return valid[key] == true ? entry[key] : -1;
}
public void remove(int key) {
valid[key] = false;
}
}
LeetCode 652 发现重复子树
思路：
- 查找重复子树，也就是看相同的树结构有没有出现过两次及以上
- 如何检查树结构，从二叉树的序列化出发
- 我们用前序或者后序遍历+标记空节点的方式来将二叉树序列化，查找相同的树结构，也就是查找相同的子串
- 故我们可以在序列化后采用DNA那道题用
hashmap的方法来做，记录在一个哈希表<String, Integer>中 - 每个结点会遍历一次，遍历节点的过程中，要拷贝当前字符串到答案，拷贝的时间复杂度为
o(n)，所以总的时间复杂度为o(n^2)
class Solution {
HashMap<String, Integer> tree = new HashMap<>();
List<TreeNode> res = new ArrayList<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
dfs(root);
return res;
}
public String dfs(TreeNode root) {
if (root == null) return "#";
StringBuilder sb = new StringBuilder();
sb.append(root.val).append(",").append(dfs(root.left)).append(",").append(dfs(root.right));
String str = sb.toString();
tree.put(str, tree.getOrDefault(str, 0) + 1);
if (tree.get(str) == 2) {
res.add(root);
}
return str;
}
}
时间复杂度的优化
用一个hashmap hash 来记录从字符串到数字的映射HashMap<String, Integer> 字符串到数字的映射可以采用cnt来打标记，也就是映射到(1~n)
再用一个hashmap tree 来记录遍历结点时重复字符串的数量
此时的时间复杂度是o(n)
class Solution {
HashMap<Integer, Integer> tree = new HashMap<>();
HashMap<String, Integer> hash = new HashMap<>();
List<TreeNode> res = new ArrayList<>();
int cnt = 0;
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
hash.put("#", ++cnt); // "#"对应标号1
dfs(root);
return res;
}
public String dfs(TreeNode root) {
if (root == null) return String.valueOf(hash.get("#"));
StringBuilder sb = new StringBuilder();
String left = dfs(root.left);
String right = dfs(root.right);
sb.append(root.val).append(",").append(left).append(",").append(right);
String str = sb.toString();
if (!hash.containsKey(str)) {
hash.put(str, ++cnt);
}
int strHashCode = hash.get(str);
tree.put(strHashCode, tree.getOrDefault(strHashCode, 0) + 1);
if (tree.get(strHashCode) == 2) {
res.add(root);
}
return String.valueOf(strHashCode);
}
}
LeetCode 560 和为K的子数组
读题发现，没有单调性，故不能使用双指针算法
思路：前缀和+ 哈希
前缀和公式 a[L] + a[L + 1] + ... + a[R] = s[R] - s[L - 1]
枚举终点
for (int i = 0; i < n; i ++ ) {
j = 0 ~ i - 1
s[i] - s[j] = K
s[j] = s[i] - K
即寻找有多少个j满足s[j] = s[i] - K
可以用哈希表来计数
}
枚举区间的终点，用哈希表来记录终点前的前缀和出现次数，以当前点为终点的和为k的子数组的出现次数即为当前前缀和减去k后的前缀和的次数。
class Solution {
public int subarraySum(int[] nums, int k) {
HashMap<Integer, Integer> preSum = new HashMap<>();
int sum = 0;
int n = nums.length;
int res = 0;
preSum.put(0, 1);
for (int i = 0; i < n; i ++ ) {
sum += nums[i];
if (preSum.containsKey(sum - k)) {
res += preSum.get(sum - k);
}
preSum.put(sum, preSum.getOrDefault(sum,0) + 1);
}
return res;
}
}
LeetCode 547 省份数量
考察并查集
并查集主要有两个操作(时间复杂度都为logn约为O(1))
1. 合并两个集合
2. 判断两个点是否在同一个集合中
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
是并查集裸题
class Solution {
int[] p;
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
p = new int[n];
for (int i = 0; i < n; i ++ ) {
p[i] = i;
}
int res = n;
for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < i; j ++ ) {
if (isConnected[i][j] == 0) continue;
if (find(i) != find(j)) {
p[find(i)] = find(j);
res -- ;
}
}
}
return res;
}
public int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
}
LeetCode 684 冗余连接
找出树中多余的边
我们从前往后扫描所有的点，如果到了a,b发现这两个点已经在连通部分的点集合里了，那么这条边就是冗余的
class Solution {
int[] p;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
p = new int[n + 1];
for (int i = 0; i <= n; i ++ ) p[i] = i;
for (int[] e : edges) {
int a = e[0];
int b = e[1];
if (find(a) == find(b)) return new int[]{a, b};
p[find(a)] = find(b);
}
return new int[]{-1, -1};
}
}
LeetCode 692 top k frequent words
数据结构： 堆
支持一些快速操作
1. 查找最大值O(1)
2. 插入一个数O(logn)
3. 删除一个数O(logn) 手写的能任意删除（否则只能删除堆顶）
4. 修改一个数O(logn) 手写堆才有的功能
堆的两个操作 up() down()
要求时间复杂度O(nlogk) 不是O(nlogn)
目标：找出出现次数最多的k个单词
用小根堆 让小根堆的大小只能等于k，要添加时，无脑加入，若size > k 则弹出最小的
下面是抄来的自己写比较器
// 2.构建小根堆 这里需要自己构建比较规则 此处为 lambda 写法 Java 的优先队列默认实现就是小根堆
PriorityQueue<String> minHeap = new PriorityQueue<>((s1, s2) -> {
if (count.get(s1).equals(count.get(s2))) {
return s2.compareTo(s1);
} else {
return count.get(s1) - count.get(s2);
}
});
//比较器规则不使用 lambda 写法如下
PriorityQueue<String> minHeap = new PriorityQueue<>(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
if (count.get(s1).equals(count.get(s2))) {
return s2.compareTo(s1);
} else {
return count.get(s1) - count.get(s2);
}
}
});
作者：qi-ye-jun
链接：https://leetcode.cn/problems/top-k-frequent-words/solution/xiao-gen-dui-huo-zhe-hashbiao-pai-xu-by-9uj06/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public List<String> topKFrequent(String[] words, int k) {
HashMap<String, Integer> map = new HashMap<>();
List<String> res = new ArrayList<>();
// 字典序需要在构造比较器时考虑到
PriorityQueue<String> heap = new PriorityQueue<String>((o1, o2) -> {
if (map.get(o1) == map.get(o2)) {
return o2.compareTo(o1);
} else {
return map.get(o1) - map.get(o2);
}
});
for (String str : words) {
map.put(str, map.getOrDefault(str, 0) + 1);
}
for (String str : map.keySet()) {
heap.offer(str);
if (heap.size() > k) heap.poll();
}
// 因为是小根堆，所以需要反转输出
for (int i = k - 1; i >= 0; i -- ) {
res.add(0, heap.poll());
}
return res;
}
}
LeetCOde 295 数据流中的中位数
分析：是一个动态维护有序序列的的问题
动态维护有序序列 —— 手写平衡树
此问题 —— 对顶堆来实现
小根堆维护较大的一些数
大根堆维护较小的一些数
然后人为规定 上面的小根堆个数比下面最多少一个
class MedianFinder {
PriorityQueue<Integer> up = new PriorityQueue<>();
PriorityQueue<Integer> down = new PriorityQueue<>((o1, o2) ->(o2 - o1));
int size;
public MedianFinder() {
size = 0;
}
public void addNum(int num) {
if (down.isEmpty() || down.peek() <= num) up.offer(num);
else {
down.offer(num);
up.offer(down.poll());// 默认上面的比下面多，下面加一个后，需要往上面挪一个
}
// 调整个数，保证上面比下面最多多1
if (up.size() > down.size() + 1) {
down.offer(up.poll());
}
size ++ ;
}
public double findMedian() {
if ((size & 1) == 1) return up.peek();
else return (up.peek() + down.peek()) / 2.0;
}
}
LeetCode 352 数据流变成不相交的区间
如何快速维护一些数值范围区间
并没有说明，一个数只会出现一次
使用的数据结构为 平衡树（利用java里的TreeMap存储区间，具体用两个这样的结构，left，right。left为区间左端点到右端点的映射，right为区间右端点到左端点的映射。）
参考大佬https://www.acwing.com/solution/content/1828/
当我们插入x时，我们查看左边x - 1 和右边x + 1
首先 判断x是否已经存在，若存在，则continue
其他分情况讨论
a. 左右都存在 将x、x + 1和x - 1三个合并
b. 左边存在，右边不存在 将x - 1和x合并
c. 左边不存在，右边存在 将x + 1和x合并
d. 左右都不存在 [x, x]
class SummaryRanges {
TreeMap<Integer, Integer> left, right;
public SummaryRanges() {
left = new TreeMap<>();
right = new TreeMap<>();
}
public void addNum(int val) {
// floorEntry()找到小于或等于val的最大的区间左端点
Map.Entry<Integer, Integer> me = left.floorEntry(val);
if (me != null && val <= me.getValue()) { // val存在于区间
return ;
}
Integer s = right.get(val - 1);
Integer t = left.get(val + 1);
// ------s------(val-1)------val-----(val+1)-------t-------
if (s != null && t != null) {
left.remove(val + 1);
right.remove(val - 1);
left.put(s, t);
right.put(t, s);
} else if (s != null) {
right.remove(val - 1);
left.put(s, val);
right.put(val, s);
} else if (t != null) {
left.remove(val + 1);
left.put(val, t);
right.put(t, val);
} else {
left.put(val, val);
right.put(val, val);
}
}
public int[][] getIntervals() {
int[][] res = new int[left.size()][2];
int idx = 0;
for (Map.Entry<Integer, Integer> num : left.entrySet()){
res[idx][0] = num.getKey();
res[idx ++ ][1] = num.getValue();
}
return res ;
}
}
