Skip to content

Commit 52c8d52

Browse files
author
guangjun.ma
committed
maguangjun: add week03
1 parent 4c27c12 commit 52c8d52

4 files changed

Lines changed: 173 additions & 2 deletions

File tree

‎Week_02/id_58/NOTE.md‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,11 @@
1-
# 学习笔记
1+
# 学习笔记
2+
1.本周主要学习了哈希表的两个题解
3+
2.题242，字母异位词的题解。
4+
在解题的过程中，刚开始发现不能理解题意，后来在网上搜索了相关的题意，就理解了异位词的含义，
5+
即所谓有效的字母异位词，就是字母类型和大小都一致，但是是不同的单词，这样的两个单词互为字母异位词
6+
分别用26个字母数组来存储两个字母串，最后对比两个数组即可，发现有不一致的则返回false，
7+
若同相同则返回true。
8+
3.题692，取最大的k个值。
9+
这里是取最大的值，可以借助Java里的最大堆的数据结构 PriorityQueue
10+
主要是熟悉Java的最大堆的实现。
11+
4.本周比较忙，后续要抽出大量的时间进行练习，再接再厉。

‎Week_03/id_58/LeetCode_703_058.java‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package algorithm.Week_03.id_58;
2+
3+
import java.util.PriorityQueue;
4+
5+
/**
6+
* 703. Kth Largest Element in a Stream
7+
*
8+
* Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
9+
*
10+
* Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.
11+
*
12+
* Example:
13+
*
14+
* int k = 3;
15+
* int[] arr = [4,5,8,2];
16+
* KthLargest kthLargest = new KthLargest(3, arr);
17+
* kthLargest.add(3); // returns 4
18+
* kthLargest.add(5); // returns 5
19+
* kthLargest.add(10); // returns 5
20+
* kthLargest.add(9); // returns 8
21+
* kthLargest.add(4); // returns 8
22+
* Note:
23+
* You may assume that nums' length ≥ k-1 and k ≥ 1.
24+
*
25+
*
26+
* 分析：这里主要考的是最小堆的用法
27+
* 3
28+
* / \
29+
* 5 7
30+
*
31+
* 先维护一个k个元素的最小堆
32+
* 依次插入后续元素
33+
* 比较新加的元素和堆顶的元素，若比堆顶元素小，则丢弃；若大，则插入
34+
*
35+
* @auther: guangjun.ma
36+
* @date: 2019/5/5 20:35
37+
* @version: 1.0
38+
*/
39+
public class LeetCode_703_058 {
40+
//定义k个元素
41+
final int k ;
42+
//声明一个最小堆
43+
final PriorityQueue<Integer> q ;
44+
45+
//初始化 k q
46+
public LeetCode_703_058(int k, int[] nums) {
47+
this.k = k;
48+
q = new PriorityQueue<Integer>(k);
49+
for(int i : nums){
50+
add(i);
51+
}
52+
}
53+
54+
//新增方法
55+
// 比较新加的元素和堆顶的元素，若比堆顶元素小，则丢弃；若大，则插入
56+
public int add(int val) {
57+
if(q.size() < k){
58+
q.offer(val);
59+
}else if(q.peek() < val){
60+
q.poll();
61+
q.offer(val);
62+
}
63+
return q.peek();
64+
}
65+
66+
}

‎Week_03/id_58/LeetCode_997_058.java‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package algorithm.Week_03.id_58;
2+
3+
/**
4+
* 997. Find the Town Judge
5+
*
6+
*In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge.
7+
*
8+
* If the town judge exists, then:
9+
*
10+
* The town judge trusts nobody.
11+
* Everybody (except for the town judge) trusts the town judge.
12+
* There is exactly one person that satisfies properties 1 and 2.
13+
* You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.
14+
*
15+
* If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.
16+
*
17+
*
18+
*
19+
* Example 1:
20+
*
21+
* Input: N = 2, trust = [[1,2]]
22+
* Output: 2
23+
* Example 2:
24+
*
25+
* Input: N = 3, trust = [[1,3],[2,3]]
26+
* Output: 3
27+
* Example 3:
28+
*
29+
* Input: N = 3, trust = [[1,3],[2,3],[3,1]]
30+
* Output: -1
31+
* Example 4:
32+
*
33+
* Input: N = 3, trust = [[1,2],[2,3]]
34+
* Output: -1
35+
* Example 5:
36+
*
37+
* Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
38+
* Output: 3
39+
*
40+
*
41+
* Note:
42+
*
43+
* 1 <= N <= 1000
44+
* trust.length <= 10000
45+
* trust[i] are all different
46+
* trust[i][0] != trust[i][1]
47+
* 1 <= trust[i][0], trust[i][1] <= N
48+
*
49+
*
50+
* 分析：此题主要是理解题意，找出法官，也可以用有向图解
51+
* 评论里的解法很巧妙，值得学习！！
52+
*
53+
* 法官：入度为N-1 出度为0的结点（其他人都指向法官，法官不指向其他人）
54+
*
55+
*
56+
* @auther: guangjun.ma
57+
* @date: 2019/5/5 20:10
58+
* @version: 1.0
59+
*/
60+
public class LeetCode_997_058 {
61+
public int findJudge(int N, int[][] trust) {
62+
//定义一个二维数据,第一个放入度，第二个放出度
63+
int[][] people = new int[N][2];
64+
65+
//遍历所有的结点，计算所有结点的入度和出度
66+
for(int[] person : trust){
67+
int out = person[0];
68+
int in = person[1];
69+
people[out - 1][0]++;
70+
people[in - 1][1]++;
71+
}
72+
73+
//找出入度为N-1 出度为0的结点，即为法官
74+
for(int i = 0 ; i < N ; i++){
75+
if(people[i][0] == 0 && people[i][1] == N -1){
76+
return i+1;
77+
}
78+
}
79+
80+
//未找到，默认处理 -1
81+
return - 1;
82+
}
83+
84+
}

‎Week_03/id_58/NOTE.md‎

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,12 @@
1-
# 学习笔记
1+
# 学习笔记
2+
本周的学习笔记：
3+
1.本周主要学习了有向图、最小堆的两个题解
4+
2.题997，有向图的题解。
5+
这题的解题思路非常的巧妙，利用了一个二维数组来存储入度和出度，
6+
这里类似有向图的邻接矩阵的思想，只有拥有了类似的思想，再解类似的问题，
7+
就可以游刃有余了。
8+
3.题703，取第k大个值。
9+
这里是取第k大的值，可以借助Java里的最小堆的数据结构 PriorityQueue
10+
主要是熟悉Java的最小堆的实现。
11+
这里需要注意，PriorityQueue默认支持最小堆，如果支持最大堆需要实现Comparator接口
12+
4.本周节假日。时间过半，还得多练习。

0 commit comments

Comments
 (0)