Skip to content

Commit 04b331f

Browse files
awangdevawangdev
committed
cp
1 parent 2c3043a commit 04b331f

19 files changed

+892
-309
lines changed

‎Java/Evaluate Division.java

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,16 @@
11
M
2-
tags: Graph, DFS, Union Find
2+
tags: Graph, DFS, Union Find, BFS
33

44
#### DFS
55
- build map of `x#y -> val` to store values[i] and 1/values[i]
66
- build map of `x -> list children`
77
- dfs to traverse the graph
88

9+
#### BFS
10+
- BFS should also work: build graph and valueMap
11+
- for each starting item, add all next candidate to queue
12+
- mark visited, loop until end item is found
13+
914
```
1015
/*
1116
Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

‎Java/Insert Interval.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -117,6 +117,44 @@ private PriorityQueue<Point> buildQueue(List<Interval> intervals, Interval newIn
117117

118118
}
119119

120+
// intervals is sorted
121+
class Solution {
122+
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
123+
if (intervals == null || intervals.size() == 0 || newInterval == null) {
124+
if (newInterval != null) {
125+
intervals.add(newInterval);
126+
}
127+
return intervals;
128+
}
129+
//Insert
130+
int start = newInterval.start;
131+
int front = -1;
132+
for (int i = 0; i < intervals.size(); i++) {
133+
if (intervals.get(i).start <= start) {
134+
front = i;
135+
}
136+
}
137+
138+
// if front==-1, add to front + 1 = 0
139+
intervals.add(front + 1, newInterval);
140+
141+
//Merge
142+
Interval pre = intervals.get(0);
143+
Interval curr = null;
144+
for (int i = 1; i < intervals.size(); i++) {
145+
curr = intervals.get(i);
146+
if (pre.end >= curr.start) {
147+
pre.end = pre.end > curr.end ? pre.end : curr.end;
148+
intervals.remove(i);
149+
i--;
150+
} else {
151+
pre = curr;
152+
}
153+
}
154+
155+
return intervals;
156+
}
157+
}
120158

121159

122160

‎Java/Max Sum of Rectangle No Larger Than K.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -88,4 +88,35 @@ public int maxSumSubmatrix(int[][] matrix, int k) {
8888
}
8989

9090

91+
// Simpler, without considering iterating m^2 on the smaller side
92+
class Solution {
93+
public int maxSumSubmatrix(int[][] matrix, int k) {
94+
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
95+
return -1;
96+
}
97+
int m = matrix.length, n = matrix[0].length;
98+
int max = Integer.MIN_VALUE;
99+
// 3 loop layers:
100+
// 1. int[] preSum; 2. TreeSet, store all area for curr iteration, 3. newSum in new row
101+
for (int row = 0; row < m; row++) {
102+
int[] preSum = new int[n];
103+
for (int i = row; i < m; i++) { // iteration
104+
TreeSet<Integer> areaSet = new TreeSet<>();
105+
int newSum = 0; // adding up with preSum[j]
106+
for (int j = 0; j < n; j++) {
107+
preSum[j] += matrix[i][j];
108+
newSum += preSum[j];
109+
if (newSum <= k) max = Math.max(max, newSum);
110+
Integer extraArea = areaSet.ceiling(newSum - k);
111+
if (extraArea != null) {
112+
max = Math.max(max, newSum - extraArea);
113+
}
114+
areaSet.add(newSum);
115+
}
116+
}
117+
}
118+
return max == Integer.MIN_VALUE ? -1 : max;
119+
}
120+
}
121+
91122
```

‎Java/Maximum Vacation Days.java

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
H
2+
1534400155
3+
tags: DP
4+
5+
```
6+
/*
7+
LeetCode wants to give one of its best employees the option to travel among N cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in some particular cities and weeks. Your job is to schedule the traveling to maximize the number of vacation days you could take, but there are certain rules and restrictions you need to follow.
8+
9+
Rules and restrictions:
10+
You can only travel among N cities, represented by indexes from 0 to N-1. Initially, you are in the city indexed 0 on Monday.
11+
The cities are connected by flights. The flights are represented as a N*N matrix (not necessary symmetrical), called flights representing the airline status from the city i to the city j. If there is no flight from the city i to the city j, flights[i][j] = 0; Otherwise, flights[i][j] = 1. Also, flights[i][i] = 0 for all i.
12+
You totally have K weeks (each week has 7 days) to travel. You can only take flights at most once per day and can only take flights on each week's Monday morning. Since flight time is so short, we don't consider the impact of flight time.
13+
For each city, you can only have restricted vacation days in different weeks, given an N*K matrix called days representing this relationship. For the value of days[i][j], it represents the maximum days you could take vacation in the city i in the week j.
14+
You're given the flights matrix and days matrix, and you need to output the maximum vacation days you could take during K weeks.
15+
16+
Example 1:
17+
Input:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
18+
Output: 12
19+
Explanation:
20+
Ans = 6 + 3 + 3 = 12.
21+
22+
One of the best strategies is:
23+
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
24+
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
25+
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
26+
3rd week : stay at city 2, and play 3 days and work 4 days.
27+
Example 2:
28+
Input:flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]]
29+
Output: 3
30+
Explanation:
31+
Ans = 1 + 1 + 1 = 3.
32+
33+
Since there is no flights enable you to move to another city, you have to stay at city 0 for the whole 3 weeks.
34+
For each week, you only have one day to play and six days to work.
35+
So the maximum number of vacation days is 3.
36+
Example 3:
37+
Input:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[7,0,0],[0,7,0],[0,0,7]]
38+
Output: 21
39+
Explanation:
40+
Ans = 7 + 7 + 7 = 21
41+
42+
One of the best strategies is:
43+
1st week : stay at city 0, and play 7 days.
44+
2nd week : fly from city 0 to city 1 on Monday, and play 7 days.
45+
3rd week : fly from city 1 to city 2 on Monday, and play 7 days.
46+
Note:
47+
N and K are positive integers, which are in the range of [1, 100].
48+
In the matrix flights, all the values are integers in the range of [0, 1].
49+
In the matrix days, all the values are integers in the range [0, 7].
50+
You could stay at a city beyond the number of vacation days, but you should work on the extra days, which won't be counted as vacation days.
51+
If you fly from the city A to the city B and take the vacation on that day, the deduction towards vacation days will count towards the vacation days of city B in that week.
52+
We don't consider the impact of flight hours towards the calculation of vacation days.
53+
54+
*/
55+
56+
class Solution {
57+
public int maxVacationDays(int[][] flights, int[][] days) {
58+
int m = days[0].length; // week count
59+
int n = days.length; // city count
60+
int[][] dp = new int[m][n];
61+
62+
for (int i = 0; i < m; i++) {
63+
for (int j = 0; j < n; j++) {
64+
if (i == 0) {
65+
dp[i][j] = j == 0 || flights[0][j] != 0 ? days[j][i]: Integer.MIN_VALUE;
66+
continue;
67+
}
68+
dp[i][j] = Integer.MIN_VALUE;
69+
for (int k = 0; k < m; k++) { // last city
70+
if ((k == j || flights[k][j] == 1) && dp[i - 1][k] != Integer.MIN_VALUE) {
71+
dp[i][j] = Math.max(dp[i - 1][k] + days[j][i], dp[i][j]);
72+
}
73+
}
74+
}
75+
}
76+
77+
int max = 0;
78+
for (int i = 0; i < n; i++) {
79+
max = Math.max(max, dp[m - 1][i]);
80+
}
81+
return max;
82+
}
83+
}
84+
```

‎Java/Robot Room Cleaner.java

Lines changed: 185 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,185 @@
1+
H
2+
1534395770
3+
tags: DFS, Backtracking
4+
5+
#### DFS
6+
- Different from regular dfs to visit all, the robot move() function need to be called, backtrack needs to move() manually and backtracking path shold not be blocked by visited positions
7+
- IMPORTANT: Mark on the way in using set, but `backtrack directly without re-check against set`
8+
- Mark coordinate 'x@y'
9+
- Backtrack: turn 2 times to revert, move 1 step, and turn 2 times to revert back.
10+
- Direction has to be up, right, down, left.
11+
- `int [] dx = {-1, 0, 1, 0};`, `int[] dy = {0, 1, 0, -1};`
12+
13+
```
14+
/*
15+
Given a robot cleaner in a room modeled as a grid.
16+
17+
Each cell in the grid can be empty or blocked.
18+
19+
The robot cleaner with 4 given APIs can move forward, turn left or turn right. Each turn it made is 90 degrees.
20+
21+
When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.
22+
23+
Design an algorithm to clean the entire room using only the 4 given APIs shown below.
24+
25+
interface Robot {
26+
// returns true if next cell is open and robot moves into the cell.
27+
// returns false if next cell is obstacle and robot stays on the current cell.
28+
boolean move();
29+
30+
// Robot will stay on the same cell after calling turnLeft/turnRight.
31+
// Each turn will be 90 degrees.
32+
void turnLeft();
33+
void turnRight();
34+
35+
// Clean the current cell.
36+
void clean();
37+
}
38+
Example:
39+
40+
Input:
41+
room = [
42+
[1,1,1,1,1,0,1,1],
43+
[1,1,1,1,1,0,1,1],
44+
[1,0,1,1,1,1,1,1],
45+
[0,0,0,1,0,0,0,0],
46+
[1,1,1,1,1,1,1,1]
47+
],
48+
row = 1,
49+
col = 3
50+
51+
Explanation:
52+
All grids in the room are marked by either 0 or 1.
53+
0 means the cell is blocked, while 1 means the cell is accessible.
54+
The robot initially starts at the position of row=1, col=3.
55+
From the top left corner, its position is one row below and three columns right.
56+
Notes:
57+
58+
The input is only given to initialize the room and the robot's position internally. You must solve this problem "blindfolded". In other words, you must control the robot using only the mentioned 4 APIs, without knowing the room layout and the initial robot's position.
59+
The robot's initial position will always be in an accessible cell.
60+
The initial direction of the robot will be facing up.
61+
All accessible cells are connected, which means the all cells marked as 1 will be accessible by the robot.
62+
Assume all four edges of the grid are all surrounded by wall.
63+
*/
64+
65+
/**
66+
* // This is the robot's control interface.
67+
* // You should not implement it, or speculate about its implementation
68+
* interface Robot {
69+
* // Returns true if the cell in front is open and robot moves into the cell.
70+
* // Returns false if the cell in front is blocked and robot stays in the current cell.
71+
* public boolean move();
72+
*
73+
* // Robot will stay in the same cell after calling turnLeft/turnRight.
74+
* // Each turn will be 90 degrees.
75+
* public void turnLeft();
76+
* public void turnRight();
77+
*
78+
* // Clean the current cell.
79+
* public void clean();
80+
* }
81+
*/
82+
/*
83+
- Different from regular dfs to visit all, the robot move() function need to be called, backtrack needs to move() manually and backtracking path shold not be blocked by visited positions
84+
- Mark on the way in using set, but backtrack directly without re-check against set
85+
- Mark coordinate 'x@y'
86+
- Use degree to mark direction, rather than {0,0,1,-1}
87+
- Backtrack: turn 2 times to revert, move 1 step, and turn 2 times to revert back.
88+
*/
89+
90+
class Solution {
91+
int[] dx = {-1, 0, 1, 0};
92+
int[] dy = {0, 1, 0, -1};
93+
public void cleanRoom(Robot robot) {
94+
// use 'x@y' mark visited nodes, where x,y are integers tracking the coordinates
95+
dfs(robot, new HashSet<>(), 0, 0, 0); // 0: up, 90: right, 180: down, 270: left
96+
}
97+
98+
public void dfs(Robot robot, Set<String> visited, int x, int y, int curDir) {
99+
String key = x + "@" + y;
100+
if (visited.contains(key)) return;
101+
visited.add(key);
102+
robot.clean();
103+
104+
for (int i = 0; i < 4; i++) { // 4 directions
105+
if(robot.move()) { // can go directly. Find the (x, y) for the next cell based on current direction
106+
dfs(robot, visited, x + dx[curDir], y + dy[curDir], curDir);
107+
backtrack(robot);
108+
}
109+
110+
// turn to next direction
111+
robot.turnRight();
112+
curDir += 1;
113+
curDir %= 4;
114+
}
115+
}
116+
117+
// go back to the starting position
118+
private void backtrack(Robot robot) {
119+
robot.turnLeft();
120+
robot.turnLeft();
121+
robot.move();
122+
robot.turnRight();
123+
robot.turnRight();
124+
}
125+
}
126+
127+
128+
129+
130+
131+
class Solution {
132+
public void cleanRoom(Robot robot) {
133+
// use 'x@y' mark visited nodes, where x,y are integers tracking the coordinates
134+
dfs(robot, new HashSet<>(), 0, 0, 0); // 0: up, 90: right, 180: down, 270: left
135+
}
136+
137+
public void dfs(Robot robot, Set<String> visited, int i, int j, int curDir) {
138+
String key = i + "@" + j;
139+
if (visited.contains(key)) return;
140+
visited.add(key);
141+
robot.clean();
142+
143+
for (int n = 0; n < 4; n++) { // 4 directions
144+
if(robot.move()) { // can go directly. Find the (x, y) for the next cell based on current direction
145+
int x = i, y = j;
146+
switch(curDir) {
147+
case 0: // go up, reduce i
148+
x = i-1;
149+
break;
150+
case 90: // go right
151+
y = j+1;
152+
break;
153+
case 180: // go down
154+
x = i+1;
155+
break;
156+
case 270: // go left
157+
y = j-1;
158+
break;
159+
default:
160+
break;
161+
}
162+
163+
dfs(robot, visited, x, y, curDir);
164+
backtrack(robot);
165+
}
166+
167+
// turn to next direction
168+
robot.turnRight();
169+
curDir += 90;
170+
curDir %= 360;
171+
}
172+
}
173+
174+
// go back to the starting position
175+
private void backtrack(Robot robot) {
176+
robot.turnLeft();
177+
robot.turnLeft();
178+
robot.move();
179+
robot.turnRight();
180+
robot.turnRight();
181+
}
182+
}
183+
184+
185+
```

‎Java/Sliding Puzzle.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
H
22
1534211551
3-
tags: BFS
3+
tags: BFS, Graph
44

55
```
66
/*

0 commit comments

Comments
 (0)