Skip to content

Commit ce9b46e

Browse files
sunsheadsunshead
committed
week 2
1 parent ccb8652 commit ce9b46e

8 files changed

Lines changed: 152 additions & 1 deletion

‎Week02/NOTE.md‎

Lines changed: 20 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,20 @@
1-
学习笔记
1+
# 第二周学习笔记
2+
3+
## HashMap源码分析
4+
5+
### 父类与接口
6+
HashMap类继承了AbstractMap这一抽象类，因而具有Map的所有方法；同时它也实现了Serializable这一接口，
7+
因而HashMap对象可以被表示为字节序列存储或传输。
8+
9+
### 底层逻辑结构与构造函数
10+
HashMap的逻辑结构是数组+链表/红黑树。当链表长度小于8的时候，发生碰撞时会增加链表的长度；当链表长度大于8时，
11+
会先判断数组容量，如果小于64会先进行扩容，如果大于64则将链表转化为红黑树以提升效率。
12+
构造方法一共有四个，其中重要的参数有二：
13+
1. initialCapacity：默认情况下初始容量是16，当储存的数据不断增多时需要进行扩容操作。
14+
2. loadFactor：默认情况下负载因子是0.75。该值越大，数组扩容的可能性就越小，占用空间虽然会更小，但是
15+
每个元素对应的链表会更长，查询时间也会因此增加；反之数组扩容可能性大，相对占用内存大，但是查询时间会降低。
16+
可以说，负载因子是空间和时间的一种折中。
17+
18+
### 时间复杂度
19+
理想状态下时间复杂度为O(1)，但是实际运用中数组元素对应的链表查找的时间复杂度为O(k),只能通过优化hash算法
20+
来尽量接近O(1)。

‎Week02/problems/1_two-sum.java‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
class Solution {
2+
public int[] twoSum(int[] nums, int target) {
3+
int[] res = new int[2];
4+
if (nums == null || nums.length < 2) {
5+
return res;
6+
}
7+
Map<Integer, Integer> map = new HashMap<>();
8+
for (int i = 0; i < nums.length; i++) {
9+
int complement = target - nums[i];
10+
if (map.containsKey(complement)) {
11+
res = new int[]{ map.get(complement), i };
12+
}
13+
map.put(nums[i], i);
14+
}
15+
return res;
16+
}
17+
}

‎Week02/problems/242_valid-anagram.js‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
var isAnagram = function(s, t) {
2+
if (s.length !== t.length) {
3+
return false;
4+
}
5+
let count = new Array(26).fill(0);
6+
for (let i = 0; i < s.length; i++) {
7+
count[s.charCodeAt(i) - 97]++;
8+
count[t.charCodeAt(i) - 97]--;
9+
}
10+
for (let num of count) {
11+
if (num !== 0) {
12+
return false;
13+
}
14+
}
15+
return true;
16+
};

‎Week02/problems/264_ugly-number-ii.java‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
class Solution {
2+
public int nthUglyNumber(int n) {
3+
int[] uglyNums = new int[n];
4+
uglyNums[0] = 1;
5+
int index2 = 0, index3 = 0, index5 = 0;
6+
for (int i = 1; i < n; i++) {
7+
uglyNums[i] = Math.min(uglyNums[index2] * 2, Math.min(uglyNums[index3] * 3, uglyNums[index5] * 5));
8+
if (uglyNums[i] == uglyNums[index2] * 2) {
9+
index2++;
10+
}
11+
if (uglyNums[i] == uglyNums[index3] * 3) {
12+
index3++;
13+
}
14+
if (uglyNums[i] == uglyNums[index5] * 5) {
15+
index5++;
16+
}
17+
}
18+
return uglyNums[n-1];
19+
}
20+
}

‎Week02/problems/347_top-k-frequent-elements.java‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
class Solution {
2+
public List<Integer> topKFrequent(int[] nums, int k) {
3+
List<Integer> res = new ArrayList<Integer>();
4+
if (nums == null || nums.length < k) {
5+
return res;
6+
}
7+
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
8+
HashMap<Integer, Integer> map = new HashMap<>();
9+
for (int num : nums) {
10+
map.put(num, map.getOrDefault(num, 0) + 1);
11+
}
12+
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
13+
pq.offer(entry);
14+
}
15+
while (k-- > 0) {
16+
int ele = pq.poll().getKey();
17+
res.add(ele);
18+
}
19+
return res;
20+
}
21+
}

‎Week02/problems/49_group-anagrams.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
class Solution {
2+
public List<List<String>> groupAnagrams(String[] strs) {
3+
if (strs == null || strs.length == 0) {
4+
return new ArrayList();
5+
}
6+
Map<String, List> map = new HashMap<>();
7+
for (String str : strs) {
8+
char[] char_arr = str.toCharArray();
9+
Arrays.sort(char_arr);
10+
String key = new String(char_arr);
11+
if (!map.containsKey(key)) {
12+
map.put(key, new ArrayList());
13+
}
14+
map.get(key).add(str);
15+
}
16+
return new ArrayList(map.values());
17+
}
18+
}

‎Week02/problems/589_n-ary-tree-preorder-traversal.java‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
class Solution {
2+
public List<Integer> preorder(Node root) {
3+
List<Integer> res = new ArrayList<>();
4+
Stack<Node> stack = new Stack<>();
5+
if (root != null) {
6+
stack.push(root);
7+
}
8+
while (!stack.isEmpty()) {
9+
Node curr = stack.pop();
10+
res.add(curr.val);
11+
Collections.reverse(curr.children);
12+
for (Node c: curr.children) {
13+
if (c != null) {
14+
stack.push(c);
15+
}
16+
}
17+
}
18+
return res;
19+
}
20+
}

‎Week02/problems/94_binary-tree-inorder-traversal.java‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
class Solution {
2+
public List<Integer> inorderTraversal(TreeNode root) {
3+
List<Integer> res = new ArrayList<>();
4+
if (root == null) {
5+
return res;
6+
}
7+
Stack<TreeNode> stack = new Stack<>();
8+
TreeNode curr = root;
9+
while (curr != null || !stack.isEmpty()) {
10+
while (curr != null) {
11+
stack.push(curr);
12+
curr = curr.left;
13+
}
14+
curr = stack.pop();
15+
res.add(curr.val);
16+
curr = curr.right;
17+
}
18+
return res;
19+
}
20+
}

0 commit comments

Comments
 (0)