Skip to content

Commit 38c5470

Browse files
fishercoder1534fishercoder1534
committed
add standard in .travis.yml
1 parent 9a605b5 commit 38c5470

File tree

16 files changed

+747
-1
lines changed

16 files changed

+747
-1
lines changed

‎.travis.yml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ before_script:
99
node_js: "v13.7.0"
1010
install: "npm install && npm install standard --global"
1111

12-
script: ./gradlew clean build
12+
script: ./gradlew clean build && standard
1313

1414
notifications:
1515
email:

‎src/main/java/com/fishercoder/solutions/Contest.java

Lines changed: 134 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,134 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.Collections;
6+
import java.util.HashMap;
7+
import java.util.HashSet;
8+
import java.util.LinkedList;
9+
import java.util.List;
10+
import java.util.Map;
11+
import java.util.Objects;
12+
import java.util.Queue;
13+
import java.util.Set;
14+
import java.util.Stack;
15+
16+
public class Contest {
17+
18+
public int minNumberOfSemesters(int n, int[][] dependencies, int k) {
19+
int[] indegree = new int[n + 1];
20+
for (int[] prereq : dependencies) {
21+
indegree[prereq[1]]++;
22+
}
23+
Queue<Integer> zeroDegreeQueue = new LinkedList<>();
24+
for (int i = 1; i <= n; i++) {
25+
if (indegree[i] == 0) {
26+
zeroDegreeQueue.add(i);
27+
}
28+
}
29+
Map<Integer, Set<Integer>> map = new HashMap<>();
30+
for (int[] dep : dependencies) {
31+
if (!map.containsKey(dep[1])) {
32+
map.put(dep[1], new HashSet<>());
33+
}
34+
map.get(dep[1]).add(dep[0]);
35+
}
36+
int semesterCount = 0;
37+
int coursesToTakeThisSemester = 0;
38+
while (!zeroDegreeQueue.isEmpty()) {
39+
int size = zeroDegreeQueue.size();
40+
Set<Integer> removedAtThisLevel = new HashSet<>();
41+
for (int i = 0; i < zeroDegreeQueue.size() && coursesToTakeThisSemester < k; i++) {
42+
int course = zeroDegreeQueue.poll();
43+
removedAtThisLevel.add(course);
44+
coursesToTakeThisSemester++;
45+
for (int[] dep : dependencies) {
46+
if (dep[0] == course) {
47+
indegree[dep[1]]--;
48+
if (indegree[dep[1]] == 0) {
49+
zeroDegreeQueue.add(dep[1]);
50+
}
51+
}
52+
}
53+
if (coursesToTakeThisSemester >= k) {
54+
semesterCount++;
55+
coursesToTakeThisSemester = 0;
56+
break;
57+
} else if (i + 1 == size) {
58+
if (removedAtThisLevel.retainAll(map.get(zeroDegreeQueue.peek()))) {
59+
semesterCount++;
60+
coursesToTakeThisSemester = 0;
61+
break;
62+
} else {
63+
coursesToTakeThisSemester++;
64+
break;
65+
}
66+
}
67+
}
68+
removedAtThisLevel.clear();
69+
}
70+
semesterCount += coursesToTakeThisSemester > 0 ? 1 : 0;
71+
return semesterCount;
72+
}
73+
74+
public static void main(String... args) {
75+
System.out.println("Hello!");
76+
Contest contest = new Contest();
77+
// System.out.println(contest.minNumberOfSemesters(4, new int[][]{
78+
// {2, 1},
79+
// {3, 1},
80+
// {1, 4}
81+
// }, 2));//3
82+
//
83+
// System.out.println(contest.minNumberOfSemesters(5, new int[][]{
84+
// {2, 1},
85+
// {3, 1},
86+
// {4, 1},
87+
// {1, 5}
88+
// }, 2));//4
89+
//
90+
// System.out.println(contest.minNumberOfSemesters(4, new int[][]{
91+
// {2, 1},
92+
// {4, 3},
93+
// {1, 3},
94+
// {2, 3}
95+
// }, 4));//3
96+
//
97+
// System.out.println(contest.minNumberOfSemesters(8, new int[][]{
98+
// {1, 6},
99+
// {2, 7},
100+
// {8, 7},
101+
// {2, 5},
102+
// {3, 4}
103+
// }, 3));//3
104+
105+
// System.out.println(contest.minNumberOfSemesters(9, new int[][]{
106+
// {4, 8},
107+
// {3, 6},
108+
// {6, 8},
109+
// {7, 6},
110+
// {4, 2},
111+
// {4, 1},
112+
// {4, 7},
113+
// {3, 7},
114+
// {5, 2},
115+
// {5, 9},
116+
// {3, 4},
117+
// {6, 9},
118+
// {5, 7},
119+
// }, 2));//5
120+
121+
// Set<Coord> visited = new HashSet<>();
122+
// visited.add(new Coord(0, 0));
123+
// System.out.println(visited.contains(new Coord(0, 0)));
124+
//// System.out.println(contest.isPathCrossing("NES"));
125+
// System.out.println(contest.isPathCrossing("NSSEN"));
126+
// System.out.println(contest.canArrange(new int[]{1, 2, 3, 4, 5, 10, 6, 7, 8, 9}, 5));
127+
128+
// System.out.println(contest.getLastMoment(4, new int[]{4, 3}, new int[]{0, 1}));
129+
// System.out.println(contest.getLastMoment(7, new int[]{0,1,2,3,4,5,6,7}, new int[]{}));//7, correct
130+
System.out.println("Finished!");
131+
}
132+
133+
}
134+

‎src/main/java/com/fishercoder/solutions/_1110.java

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.CommonUtils;
5+
import com.fishercoder.common.utils.TreeUtils;
6+
7+
import java.util.ArrayList;
8+
import java.util.Collection;
9+
import java.util.Collections;
10+
import java.util.HashSet;
11+
import java.util.LinkedList;
12+
import java.util.List;
13+
import java.util.Queue;
14+
import java.util.Set;
15+
16+
/**
17+
* 1110. Delete Nodes And Return Forest
18+
*
19+
* Given the root of a binary tree, each node in the tree has a distinct value.
20+
* After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).
21+
* Return the roots of the trees in the remaining forest. You may return the result in any order.
22+
*
23+
* Example 1:
24+
* Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
25+
* Output: [[1,2,null,4],[6],[7]]
26+
*
27+
* Constraints:
28+
* The number of nodes in the given tree is at most 1000.
29+
* Each node has a distinct value between 1 and 1000.
30+
* to_delete.length <= 1000
31+
* to_delete contains distinct values between 1 and 1000.
32+
* */
33+
public class _1110 {
34+
public static class Solution1 {
35+
public List<TreeNode> delNodes(TreeNode root, int[] toDelete) {
36+
List<TreeNode> result = new ArrayList<>();
37+
result.add(root);
38+
for (int i = 0; i < toDelete.length; i++) {
39+
List<TreeNode> newResult = new ArrayList<>();
40+
for (int j = 0; j < result.size(); j++) {
41+
List<TreeNode> newResultAfterDeletingThisNode = new ArrayList<>();
42+
if (dfs(result.get(j), toDelete[i], newResultAfterDeletingThisNode)) {
43+
newResult.addAll(newResultAfterDeletingThisNode);
44+
} else {
45+
newResult.add(result.get(j));
46+
}
47+
}
48+
result = newResult;
49+
}
50+
return result;
51+
}
52+
53+
private boolean dfs(TreeNode root, int delete, List<TreeNode> result) {
54+
if (root == null) {
55+
return false;
56+
}
57+
if (root.val == delete) {
58+
if (root.left != null) {
59+
result.add(root.left);
60+
}
61+
if (root.right != null) {
62+
result.add(root.right);
63+
}
64+
return true;
65+
}
66+
boolean left = dfs(root.left, delete, result);
67+
if (left) {
68+
if (root.left != null && root.left.val == delete) {
69+
root.left = null;
70+
result.add(root);
71+
}
72+
return true;
73+
}
74+
boolean right = dfs(root.right, delete, result);
75+
if (right) {
76+
if (root.right != null && root.right.val == delete) {
77+
root.right = null;
78+
result.add(root);
79+
}
80+
return true;
81+
}
82+
return false;
83+
}
84+
}
85+
}

‎src/main/java/com/fishercoder/solutions/_1143.java

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package com.fishercoder.solutions;
2+
3+
public class _1143 {
4+
public static class Solution1 {
5+
public int longestCommonSubsequence(String text1, String text2) {
6+
String shorter = text1.length() < text2.length() ? text1 : text2;
7+
String longer = shorter.equals(text1) ? text2 : text1;
8+
return -1;
9+
}
10+
}
11+
}

‎src/main/java/com/fishercoder/solutions/_1146.java

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* 1146. Snapshot Array
8+
*
9+
* Implement a SnapshotArray that supports the following interface:
10+
* SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.
11+
* void set(index, val) sets the element at the given index to be equal to val.
12+
* int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
13+
* int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id
14+
*
15+
* Example 1:
16+
* Input: ["SnapshotArray","set","snap","set","get"]
17+
* [[3],[0,5],[],[0,6],[0,0]]
18+
* Output: [null,null,0,null,5]
19+
* Explanation:
20+
* SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
21+
* snapshotArr.set(0,5); // Set array[0] = 5
22+
* snapshotArr.snap(); // Take a snapshot, return snap_id = 0
23+
* snapshotArr.set(0,6);
24+
* snapshotArr.get(0,0); // Get the value of array[0] with snap_id = 0, return 5
25+
*
26+
* Constraints:
27+
* 1 <= length <= 50000
28+
* At most 50000 calls will be made to set, snap, and get.
29+
* 0 <= index < length
30+
* 0 <= snap_id < (the total number of times we call snap())
31+
* 0 <= val <= 10^9
32+
* */
33+
public class _1146 {
34+
public static class Solution1 {
35+
public static class SnapshotArray {
36+
37+
List<List<Integer>> lists;
38+
List<Integer> list;
39+
int len;
40+
int snapId;
41+
42+
public SnapshotArray(int length) {
43+
this.len = length;
44+
this.snapId = 0;
45+
this.lists = new ArrayList<>();
46+
this.list = new ArrayList<>(length);
47+
for (int i = 0; i < length; i++) {
48+
list.add(0);
49+
}
50+
}
51+
52+
public void set(int index, int val) {
53+
list.set(index, val);
54+
}
55+
56+
public int snap() {
57+
lists.add(new ArrayList<>(list));
58+
return snapId++;
59+
}
60+
61+
public int get(int index, int snapId) {
62+
return lists.get(snapId).get(index);
63+
}
64+
}
65+
}
66+
}

‎src/main/java/com/fishercoder/solutions/_1248.java

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.fishercoder.solutions;
2+
3+
/**
4+
* 1248. Count Number of Nice Subarrays
5+
*
6+
* Given an array of integers nums and an integer k. A subarray is called nice if there are k odd numbers on it.
7+
*
8+
* Return the number of nice sub-arrays.
9+
*
10+
* Example 1:
11+
* Input: nums = [1,1,2,1,1], k = 3
12+
* Output: 2
13+
* Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].
14+
*
15+
* Example 2:
16+
* Input: nums = [2,4,6], k = 1
17+
* Output: 0
18+
* Explanation: There is no odd numbers in the array.
19+
*
20+
* Example 3:
21+
* Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
22+
* Output: 16
23+
*
24+
* Constraints:
25+
* 1 <= nums.length <= 50000
26+
* 1 <= nums[i] <= 10^5
27+
* 1 <= k <= nums.length
28+
* */
29+
public class _1248 {
30+
public static class Solution1 {
31+
public int numberOfSubarrays(int[] nums, int k) {
32+
for (int i = 0; i < nums.length; i++) {
33+
for (int j = 0; j < nums.length; j++) {
34+
35+
}
36+
}
37+
return -1;
38+
}
39+
}
40+
}

‎src/main/java/com/fishercoder/solutions/_1359.java

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.HashSet;
4+
import java.util.Set;
5+
6+
/**
7+
* 1359. Count All Valid Pickup and Delivery Options
8+
*
9+
* Given n orders, each order consist in pickup and delivery services.
10+
* Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i).
11+
* Since the answer may be too large, return it modulo 10^9 + 7.
12+
*
13+
* Example 1:
14+
* Input: n = 1
15+
* Output: 1
16+
* Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.
17+
*
18+
* Example 2:
19+
* Input: n = 2
20+
* Output: 6
21+
* Explanation: All possible orders:
22+
* (P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
23+
* This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.
24+
*
25+
* Example 3:
26+
* Input: n = 3
27+
* Output: 90
28+
*
29+
* Constraints:
30+
* 1 <= n <= 500
31+
* */
32+
public class _1359 {
33+
public static class Solution1 {
34+
public int countOrders(int n) {
35+
/**use odd number to denote pickup,
36+
* and its next even number to denote the corresponding delivery*/
37+
Set<Integer> set = new HashSet<>();
38+
for (int i = 1; i <= 2 * n; i++) {
39+
set.add(i);
40+
}
41+
for (int i = 1; i < 2*n; i++) {
42+
43+
}
44+
return -1;
45+
}
46+
}
47+
}

0 commit comments

Comments
 (0)