FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

Merge pull request #410 from yanlingli3799/master · feixiangcode/algorithm@6daf2b9 · GitHub

/ algorithm Public
forked from algorithm001/algorithm

Commit 6daf2b9

Browse files
GeekUniversity
authored
Merge pull request algorithm001#410 from yanlingli3799/master
学号118李颜翎-Week02作业
2 parents 31ffbd3 + 500acc3 commit 6daf2b9

10 files changed

Lines changed: 414 additions & 1 deletion

‎Week_02/id_118/NOTE.md‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,3 @@
1-
# 学习笔记
1+
# 学习笔记
2+
3+
这周学习比较大的感触是：把你想到的先写下来/画下来，解题思路都能从这些想法中得到启发。

‎Week_02/id_118/img/图示-263.png‎

142 KB
LoadingViewer requires iframe.

‎Week_02/id_118/img/图示-671.png‎

142 KB
LoadingViewer requires iframe.

‎Week_02/id_118/img/图示-863.png‎

271 KB
LoadingViewer requires iframe.

‎Week_02/id_118/img/思维导图-263.671.863.png‎

1.19 MB
LoadingViewer requires iframe.

‎Week_02/id_118/leetcode_236_118.java‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* public class TreeNode {
4+
* int val;
5+
* TreeNode left;
6+
* TreeNode right;
7+
* TreeNode(int x) { val = x; }
8+
* }
9+
*/
10+
// https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/submissions/
11+
// 236.二叉树的最近公共祖先
12+
class Solution {
13+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
14+
15+
// root有任何一个是根节点，则它本身就是最近公共祖先
16+
if(p==root || q==root){
17+
return root;
18+
}
19+
20+
// 判断：p和q在不在左子树上
21+
boolean pLeft = find(root.left,p);
22+
boolean qLeft = find(root.left,q);
23+
24+
if(pLeft && qLeft){
25+
// 都在左子树
26+
return lowestCommonAncestor(root.left,p,q);
27+
}else if(!pLeft && !qLeft){
28+
// 都在右子树
29+
return lowestCommonAncestor(root.right,p,q);
30+
}else{
31+
// 一个在左子树，一个在右子树，则当前节点就是最近公共祖先。
32+
return root;
33+
}
34+
35+
}
36+
37+
// 检查 root这棵树中，是否有节点x
38+
boolean find(TreeNode root, TreeNode x){
39+
if(root==null){
40+
return false;
41+
}
42+
if(root==x){
43+
return true;
44+
}
45+
if(root.left==null && root.right==null){
46+
return false;
47+
}else if(root.left==null && root.right!=null){
48+
return find(root.right,x);
49+
}else if(root.left!=null && root.right==null){
50+
return find(root.left,x);
51+
}else{
52+
return find(root.left,x) || find(root.right,x);
53+
}
54+
}
55+
}

‎Week_02/id_118/leetcode_242_118.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
// https://leetcode-cn.com/problems/valid-anagram/submissions/
2+
// 有效的字母异位词
3+
class Solution {
4+
public boolean isAnagram(String s, String t) {
5+
// 考察题型：哈希表
6+
// （1）把26个字母作为 key，出现次数作为 value，初始值为0表示没出现过或互相抵消了。
7+
// （2）遍历 s，做 value++；再遍历 t，做 value--。这过程中如果有 value 被减成负的，直接返回 false
8+
// （3）然后扫描一遍哈希表，如果有非0元素，则false。
9+
10+
// 1. 边界条件，若字符长度不一样，则直接返回
11+
if(s.length() != t.length()){
12+
return false;
13+
}
14+
15+
// 2. 定义哈希表（java语言不需要单独做初始化操作，默认值就是0）
16+
int[] hash_map = new int[27];
17+
18+
// 3. 第一遍扫描
19+
for(int i=0;i<s.length();i++){
20+
int key = s.charAt(i)-'a';
21+
hash_map[key] += 1;
22+
}
23+
24+
// 4. 第二遍扫描
25+
for(int i=0;i<t.length();i++){
26+
int key = t.charAt(i)-'a';
27+
if(hash_map[key]==0){
28+
return false;
29+
}
30+
hash_map[key] -= 1;
31+
}
32+
33+
// 5.扫描哈希表
34+
for(int i=0;i<27;i++){
35+
if(hash_map[i]!=0){
36+
return false;
37+
}
38+
}
39+
40+
return true;
41+
}
42+
}

‎Week_02/id_118/leetcode_671_118.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* public class TreeNode {
4+
* int val;
5+
* TreeNode left;
6+
* TreeNode right;
7+
* TreeNode(int x) { val = x; }
8+
* }
9+
*/
10+
// https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/
11+
// 671.二叉树中第二小的节点
12+
class Solution {
13+
public int findSecondMinimumValue(TreeNode root) {
14+
// 根节点一定是最小值
15+
// 若树中所有节点同值，则没有第二小
16+
// 若树中根节点和子节点值不同，则第二小要么在左子树，要么在右子树
17+
18+
if(root == null || (root.left == null && root.right == null)){
19+
return -1;
20+
}
21+
22+
int val_root = root.val;
23+
int val_left = root.left.val;
24+
int val_right = root.right.val;
25+
26+
if(val_root!=val_left && val_root!=val_right){
27+
// 左右子树根节点均与当前根节点不等值，则其一就是第二小
28+
return getMinOne(val_left,val_right);
29+
}else if(val_root==val_left && val_root!=val_right){
30+
// 左子树根节点与当前根节点同值，右子树根节点与当前根节点不同值，则左子树取第二小，与右子树根节点比。
31+
// 注意，左子树如果没有第二小，会返回负数
32+
return getMinOne(findSecondMinimumValue(root.left),val_right);
33+
}else if(val_root!=val_left && val_root==val_right){
34+
// 类似上面的
35+
return getMinOne(val_left,findSecondMinimumValue(root.right));
36+
}else{
37+
return getMinOne(findSecondMinimumValue(root.left),findSecondMinimumValue(root.right));
38+
}
39+
40+
}
41+
42+
int getMinOne(int x,int y ){
43+
if(x==-1 && y==-1){
44+
return -1;
45+
}else if(x==-1 && y!=-1){
46+
return y;
47+
}else if(x!=-1 && y==-1){
48+
return x;
49+
}else{
50+
return Math.min(x,y);
51+
}
52+
}
53+
}

‎Week_02/id_118/leetcode_692_118.java‎

Lines changed: 154 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,154 @@
1+
// https://leetcode-cn.com/problems/top-k-frequent-words/submissions/
2+
// 692.前k个高频单词
3+
// 这是拿到题目后的最快想出来的思路。晚点再想想有没有别的做法。
4+
class Solution {
5+
class LinkNode{
6+
String val;
7+
LinkNode next;
8+
LinkNode(String s){
9+
val = s;
10+
}
11+
}
12+
13+
public List<String> topKFrequent(String[] words, int k) {
14+
List<String> result_list = new LinkedList();
15+
16+
// 1. 统计词频表和最大词频出现次数
17+
Map<String,Integer> frequency_map = new HashMap();// 词频表：key：单词，value：单词出现次数。
18+
int most_frequent = 0;
19+
20+
for(int i=0;i<words.length;i++){
21+
String word = words[i];
22+
if(frequency_map.containsKey(word)){
23+
frequency_map.put(word,frequency_map.get(word)+1);
24+
}else{
25+
frequency_map.put(word,1);
26+
}
27+
most_frequent = Math.max(frequency_map.get(word),most_frequent);
28+
}
29+
30+
// 2. 生成哈希表：下标 i 表示出现次数，值是出现 i 次的单词列表（这里是用链表表示的，字典序有序，初始为null）
31+
LinkNode[] frequency_list = new LinkNode[most_frequent+1];
32+
for (String key : frequency_map.keySet()) {
33+
int frequent = frequency_map.get(key);
34+
frequency_list[frequent] = build(frequency_list[frequent],key);
35+
}
36+
37+
// 3. 逆序扫描哈希表，总共输出k个单词
38+
for(int i=most_frequent;i>=0;i--){
39+
LinkNode link = frequency_list[i];
40+
if(link==null){
41+
continue;
42+
}
43+
while(k!=0 && link!=null){
44+
result_list.add(link.val);
45+
k--;
46+
link = link.next;
47+
}
48+
}
49+
50+
// 4. 这就是k个单词了
51+
return result_list;
52+
}
53+
54+
//-------------------------------------------
55+
56+
// 新节点插入链表，字典序有序。
57+
LinkNode build(LinkNode head,String s){
58+
// 如果原始链表为空，则直接 new 一个节点回去
59+
if(head==null){
60+
return new LinkNode(s);
61+
}
62+
63+
// 否则的话，要找到合适的位置插入
64+
LinkNode tmp = new LinkNode(s);
65+
66+
// 若s应该在头结点前面，即 s > head.val
67+
// System.out.println("---单词比较，s="+s+" head="+head.val+" 左侧比较小？"+leftIsSmaller(s,head.val));
68+
if(leftIsSmaller(s,head.val)){
69+
tmp.next = head;
70+
head = tmp;
71+
return head;
72+
}
73+
74+
// 否则，s应该再头结点后面。then：
75+
LinkNode pre = head;
76+
LinkNode current = head.next;
77+
while(current!=null){
78+
// System.out.println("---单词比较，s="+s+" head="+current.val+" 左侧比较小？"+leftIsSmaller(s,current.val));
79+
if(leftIsSmaller(s,current.val)){
80+
// s应该在 current 前面
81+
pre.next = tmp;
82+
tmp.next = current;
83+
return head;
84+
}
85+
pre = pre.next;
86+
current = current.next;
87+
}
88+
89+
// 如果在中间没找到，那就是直接插到结尾
90+
pre.next = tmp;
91+
return head;
92+
93+
}
94+
95+
96+
//-------------------------------------------
97+
98+
99+
// 手动撸了一个字典序排序。。。心累。。。
100+
boolean leftIsSmaller(String x,String y){
101+
int i=0;
102+
while(i<x.length() && i<y.length()){
103+
int xc = x.charAt(i);
104+
int yc = y.charAt(i);
105+
if(xc==yc){
106+
i++;
107+
continue;// 注意啊，这里不能退出，得去比较下一个
108+
}else if(xc<yc){
109+
return true;
110+
}else{
111+
return false;
112+
}
113+
}
114+
// 注意，这里是 <=，不是 <
115+
if(x.length()<=i){
116+
return true;
117+
}else{
118+
return false;
119+
}
120+
}
121+
122+
123+
//-------------------------------------------
124+
// 请不要管我，我是 debug 用的
125+
//-------------------------------------------
126+
127+
void print(Map<String,Integer> map){
128+
for (String key : map.keySet()) {
129+
System.out.println("单词-出现次数："+key+" - "+map.get(key));
130+
}
131+
}
132+
133+
134+
void print(LinkNode[] list){
135+
for(int i=0;i<list.length;i++){
136+
System.out.print("- "+i+"：");
137+
LinkNode tmp = list[i];
138+
while(tmp!=null){
139+
System.out.print("->"+tmp.val);
140+
tmp = tmp.next;
141+
}
142+
System.out.println();
143+
}
144+
}
145+
146+
void print(LinkNode head){
147+
LinkNode tmp = head;
148+
while(tmp!=null){
149+
System.out.print("->"+tmp.val);
150+
tmp = tmp.next;
151+
}
152+
System.out.println();
153+
}
154+
}

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL