Skip to content

Commit 2c8180f

Browse files
leosanqingleosanqing
committed
1. 新增209题，208题
2. 调整项目目录
1 parent 8a80365 commit 2c8180f

8 files changed

Lines changed: 272 additions & 38 deletions

File tree

‎java-note-algorithm/java-note-algorithm.iml‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<module type="JAVA_MODULE" version="4" />

‎java-note-algorithm/pom.xml‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -13,8 +13,8 @@
1313
<groupId>org.apache.maven.plugins</groupId>
1414
<artifactId>maven-compiler-plugin</artifactId>
1515
<configuration>
16-
<source>7</source>
17-
<target>7</target>
16+
<source>8</source>
17+
<target>8</target>
1818
</configuration>
1919
</plugin>
2020
</plugins>

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/_73_setMatrixZeroes.java‎

Lines changed: 32 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -2,58 +2,57 @@
22

33
/**
44
* 题目： 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
5-
*
5+
* <p>
66
* 示例：输入:
7-
* [
8-
* [1,1,1],
9-
* [1,0,1],
10-
* [1,1,1]
11-
* ]
12-
* 输出:
13-
* [
14-
* [1,0,1],
15-
* [0,0,0],
16-
* [1,0,1]
17-
* ]
18-
*
7+
* [
8+
* [1,1,1],
9+
* [1,0,1],
10+
* [1,1,1]
11+
* ]
12+
* 输出:
13+
* [
14+
* [1,0,1],
15+
* [0,0,0],
16+
* [1,0,1]
17+
* ]
18+
* <p>
1919
* 思路： 把矩阵的第一行和第一列作为标志位，如果该行或者该列有0，那么他就置为0
20-
* 然后再遍历，替换
20+
* 然后再遍历，替换
2121
*/
2222
class _73_setMatrixZeroes {
2323
public void setZeroes(int[][] matrix) {
24-
if(matrix == null || matrix.length ==0||matrix[0].length==0) {
24+
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
2525
return;
2626
}
27-
28-
int col0 = 1,rows = matrix.length,cols = matrix[0].length;
29-
30-
31-
for(int i = 0;i<rows;i++){
32-
if(matrix[i][0] == 0) {
27+
28+
int col0 = 1, rows = matrix.length, cols = matrix[0].length;
29+
30+
31+
for (int i = 0; i < rows; i++) {
32+
if (matrix[i][0] == 0) {
3333
col0 = 0;
3434
}
35-
for(int j = 0;j<cols;j++){
36-
if(matrix[i][j] == 0){
35+
for (int j = 0; j < cols; j++) {
36+
if (matrix[i][j] == 0) {
3737
matrix[i][0] = 0;
3838
matrix[0][j] = 0;
3939
}
40-
40+
4141
}
4242
}
43-
43+
4444
// 遍历集合，把他们变成0
45-
for(int i=rows-1;i>=0;i--){
46-
for(int j=cols-1;j>=1;j--){
47-
if(matrix[0][j]==0||matrix[i][0]==0)
48-
matrix[i][j] =0;
49-
}
50-
51-
if(col0 == 0) {
45+
for (int i = rows - 1; i >= 0; i--) {
46+
for (int j = cols - 1; j >= 1; j--) {
47+
if (matrix[0][j] == 0 || matrix[i][0] == 0)
48+
matrix[i][j] = 0;
49+
}
50+
51+
if (col0 == 0) {
5252
matrix[i][0] = 0;
5353
}
5454
}
5555
}
5656

5757

58-
5958
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/_92_reverseLinkedList2.java‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,5 @@
11
package com.leosanqing.leetcode.medium;
22

3-
import java.util.List;
4-
53
/**
64
* @Author: rtliu
75
* @Date: 2020/6/1 下午7:01
@@ -46,6 +44,7 @@ public ListNode reverseBetween(ListNode head, int m, int n) {
4644
cur2 = next;
4745
}
4846

47+
// 反转完之后，链接 m 之前的节点 和 n 后的节点
4948
pre1.next = pre2;
5049
cur1.next = cur2;
5150

java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/_15_3nums.java renamed to java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/array/_15_3nums.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.leosanqing.leetcode.medium;
1+
package com.leosanqing.leetcode.medium.array;
22

33
import java.util.Arrays;
44
import java.util.LinkedList;

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/array/_207_courseSchedule.java‎

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
package com.leosanqing.leetcode.medium.array;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
/**
7+
* @Author: rtliu
8+
* @Date: 2020/6/17 下午3:57
9+
* @Package: com.leosanqing.leetcode.medium.array
10+
* @Description:
11+
* There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
12+
* Some courses may have prerequisites, for example to take course 0 you have to first take course 1,
13+
* which is expressed as a pair: [0,1]
14+
* Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
15+
*
16+
* 您必须参加总共numCourses课程，从0到numCourses-1标记。
17+
* 有些课程可能有先决条件，例如，要参加课程0，您必须先参加课程1，表示为一对：[0,1]
18+
* 鉴于课程总数和先决条件对列表，您是否可以完成所有课程？
19+
*
20+
*
21+
* Input: numCourses = 2, prerequisites = [[1,0]]
22+
* Output: true
23+
* Explanation: There are a total of 2 courses to take.
24+
* To take course 1 you should have finished course 0. So it is possible.
25+
*
26+
* @Version: 1.0
27+
*/
28+
public class _207_courseSchedule {
29+
30+
public static void main(String[] args) {
31+
int[][] courses = {
32+
{0,1},
33+
{1,0}
34+
};
35+
36+
System.out.println(canFinish(2,courses));
37+
}
38+
39+
public static boolean canFinish(int numCourses, int[][] prerequisites) {
40+
if (numCourses <= 0) {
41+
return false;
42+
}
43+
Queue<Integer> queue = new LinkedList<>();
44+
int[] inDegree = new int[numCourses];
45+
for (int[] prerequisite : prerequisites) {
46+
inDegree[prerequisite[1]]++;
47+
}
48+
for (int i = 0; i < inDegree.length; i++) {
49+
if (inDegree[i] == 0) {
50+
queue.offer(i);
51+
}
52+
}
53+
while (!queue.isEmpty()) {
54+
int x = queue.poll();
55+
for (int[] prerequisite : prerequisites) {
56+
if (x == prerequisite[0]) {
57+
inDegree[prerequisite[1]] --;
58+
if (inDegree[prerequisite[1]] == 0) {
59+
queue.offer(prerequisite[1]);
60+
}
61+
}
62+
}
63+
}
64+
for (int value : inDegree) {
65+
if (value != 0) {
66+
return false;
67+
}
68+
}
69+
return true;
70+
}
71+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/array/_209_minimumSizeSubarraySum.java‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package com.leosanqing.leetcode.medium.array;
2+
3+
/**
4+
* @Author: rtliu
5+
* @Date: 2020/6/17 下午2:38
6+
* @Package: com.leosanqing.leetcode.medium.array
7+
* @Description:
8+
* Given an array of n positive integers and a positive integer s,
9+
* find the minimal length of a contiguous subarray of which the sum ≥ s.
10+
* If there isn't one, return 0 instead.
11+
*
12+
* 给定一个只有正整数的数组和一个正整数 s
13+
* 返回 子数组之和大于 s 的长度
14+
* 如果没有，则返回 0
15+
*
16+
*
17+
* Example:
18+
*
19+
* Input: s = 7, nums = [2,3,1,2,4,3]
20+
* Output: 2
21+
* Explanation: the subarray [4,3] has the minimal length under the problem constraint.
22+
*
23+
*
24+
*
25+
* @Version: 1.0
26+
*/
27+
public class _209_minimumSizeSubarraySum {
28+
29+
public static void main(String[] args) {
30+
int a[] = {2,3,1,2,4,3};
31+
System.out.println(minSubArrayLen(7,a));
32+
}
33+
34+
/**
35+
* 使用滑动窗口，设置两个指针 i 和 j 充当窗口的界限
36+
* @param s
37+
* @param a
38+
* @return
39+
*/
40+
public static int minSubArrayLen(int s, int[] a) {
41+
if (a == null || a.length == 0) {
42+
return 0;
43+
}
44+
int i = 0, j = 0, sum = 0;
45+
int min = Integer.MAX_VALUE;
46+
47+
// 在数组范围内
48+
while (j < a.length) {
49+
50+
sum += a[j++];
51+
// 如果和大于 s，就从前开始挨个减去
52+
while (sum >= s) {
53+
min = Math.min(min, j - i);
54+
sum -= a[i++];
55+
}
56+
}
57+
58+
return min == Integer.MAX_VALUE ? 0 : min;
59+
}
60+
61+
62+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/tree/_208_implementTrie.java‎

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,101 @@
1+
package com.leosanqing.leetcode.medium.tree;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* @Author: rtliu
8+
* @Date: 2020/6/17 上午10:33
9+
* @Package: com.leosanqing.leetcode.medium.tree
10+
* @Description: 实现 一个 Trie
11+
* Implement a trie with insert, search, and startsWith methods.
12+
*
13+
* Example:
14+
*
15+
* Trie trie = new Trie();
16+
*
17+
* trie.insert("apple");
18+
* trie.search("apple"); // returns true
19+
* trie.search("app"); // returns false
20+
* trie.startsWith("app"); // returns true
21+
* trie.insert("app");
22+
* trie.search("app"); // returns true
23+
*
24+
*
25+
* 很多人可能不了解 Trie
26+
* 在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。
27+
* 与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。
28+
* 一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。
29+
* 一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
30+
* @Version: 1.0
31+
*/
32+
public class _208_implementTrie {
33+
34+
public static void main(String[] args) {
35+
Trie trie = new Trie();
36+
trie.insert("apple");
37+
boolean apple = trie.search("apple");
38+
System.out.println(apple);
39+
}
40+
}
41+
42+
class TrieNode{
43+
private final Map<Character,TrieNode> children = new HashMap<>();
44+
45+
public boolean isEnd = false;
46+
47+
public void putChildIfAbsent(char c){
48+
// 直接调用 HashMap 的代码，创建 子节点
49+
children.putIfAbsent(c,new TrieNode());
50+
}
51+
52+
public TrieNode getChildren(char c){
53+
return children.get(c);
54+
}
55+
}
56+
57+
class Trie {
58+
59+
60+
TrieNode root = new TrieNode();
61+
62+
/** Initialize your data structure here. */
63+
public Trie() {
64+
65+
}
66+
67+
/** Inserts a word into the trie. */
68+
public void insert(String word) {
69+
TrieNode curr = root;
70+
for (char ch : word.toCharArray()) {
71+
curr.putChildIfAbsent(ch);
72+
curr = curr.getChildren(ch);
73+
}
74+
curr.isEnd = true;
75+
}
76+
77+
/** Returns if the word is in the trie. */
78+
public boolean search(String word) {
79+
TrieNode curr = root;
80+
for (char ch : word.toCharArray()) {
81+
curr = curr.getChildren(ch);
82+
if (curr == null) {
83+
return false;
84+
}
85+
}
86+
return curr.isEnd;
87+
}
88+
89+
/** Returns if there is any word in the trie that starts with the given prefix. */
90+
public boolean startsWith(String prefix) {
91+
TrieNode curr = root;
92+
for (char c : prefix.toCharArray()) {
93+
curr = curr.getChildren(c);
94+
if (curr == null) {
95+
return false;
96+
}
97+
}
98+
99+
return true;
100+
}
101+
}

0 commit comments

Comments
 (0)