Skip to content

Commit 40cbdef

Browse files
SeanforfunSeanforfun
committed
[Function add]
1. Add leetcode solutions with tag bfs.
1 parent cead194 commit 40cbdef

6 files changed

+395
-1
lines changed

‎README.md

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -243,6 +243,8 @@
243243

244244
[125. Valid Palindrome](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/125.%20Valid%20Palindrome.md)
245245

246+
[126. Word Ladder II](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/126.%20Word%20Ladder%20II.md)
247+
246248
[127. Word Ladder](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/127.%20Word%20Ladder.md)
247249

248250
[128. Longest Consecutive Sequence](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/128.%20Longest%20Consecutive%20Sequence.md)
@@ -545,7 +547,15 @@
545547
* [51. N-Queens](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/51.%20N-Queens.md)
546548
* [52. N-Queens II](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/52.%20N-Queens%20II.md)
547549
* [79. Word Search](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/79.%20Word%20Search.md)
548-
* [[212. Word Search II](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/212.%20Word%20Search%20II.md)]
550+
* [212. Word Search II](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/212.%20Word%20Search%20II.md)
551+
552+
#### BFS
553+
* [127. Word Ladder](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/127.%20Word%20Ladder.md)
554+
* [126. Word Ladder II](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/126.%20Word%20Ladder%20II.md)
555+
* [752. Open the Lock](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/752.%20Open%20the%20Lock.md)
556+
* [542. 01 Matrix](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/542.%200120Matrix.md)
557+
* [695. Max Area of Island](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/695.%20Max%20Area%20of%20Island.md)
558+
* [934. Shortest Bridge](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/934.%20Shortest%20Bridge.md)
549559

550560
## Algorithm(4th_Edition)
551561
Reading notes of book Algorithm(4th Algorithm),ISBN: 9787115293800.

‎leetcode/131. Palindrome Partitioning.md

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -92,4 +92,42 @@ class Solution {
9292
return true;
9393
}
9494
}
95+
```
96+
97+
### Third time
98+
```Java
99+
class Solution {
100+
public List<List<String>> partition(String s) {
101+
List<List<String>> result = new ArrayList<>();
102+
if(s.length() == 0){
103+
result.add(new ArrayList<>());
104+
return result;
105+
}
106+
dfs(result, s, new ArrayList<String>(), 0);
107+
return result;
108+
}
109+
private void dfs(List<List<String>> result, String s, List<String> temp, int start){
110+
if(start == s.length()) result.add(new ArrayList<String>(temp));
111+
else{
112+
for(int i = start + 1; i <= s.length(); i++){
113+
String sub = s.substring(start, i);
114+
if(isPalindrome(s.substring(start, i))){
115+
temp.add(sub);
116+
dfs(result, s, temp, i);
117+
temp.remove(temp.size() - 1);
118+
}
119+
}
120+
}
121+
}
122+
private boolean isPalindrome(String s){
123+
int len = s.length();
124+
if(len == 1) return true;
125+
char[] arr = s.toCharArray();
126+
int start = 0, end = len - 1;
127+
while(start < end){
128+
if(arr[start++] != arr[end--]) return false;
129+
}
130+
return true;
131+
}
132+
}
95133
```

‎leetcode/675. Cut Off Trees for Golf Event.md

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
## 675. Cut Off Trees for Golf Event
2+
3+
### Question
4+
You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:
5+
* 0 represents the obstacle can't be reached.
6+
* 1 represents the ground can be walked through.
7+
* The place with number bigger than 1 represents a tree can be walked through, and this positive number represents the tree's height.
8+
9+
You are asked to cut off all the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).
10+
11+
You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can't cut off all the trees, output -1 in that situation.
12+
13+
You are guaranteed that no two trees have the same height and there is at least one tree needs to be cut off.
14+
15+
```
16+
Example 1:
17+
18+
Input:
19+
[
20+
[1,2,3],
21+
[0,0,4],
22+
[7,6,5]
23+
]
24+
Output: 6
25+
26+
Example 2:
27+
28+
Input:
29+
[
30+
[1,2,3],
31+
[0,0,0],
32+
[7,6,5]
33+
]
34+
Output: -1
35+
36+
Example 3:
37+
38+
Input:
39+
[
40+
[2,3,4],
41+
[0,0,5],
42+
[8,7,6]
43+
]
44+
Output: 6
45+
Explanation: You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking.
46+
```
47+
48+
Hint: size of the given matrix will not exceed 50x50.
49+
50+
### Solution
51+
* Method 1: PriorityQueue, bfs
52+
* The idea of this method is we sort all nodes with their values.
53+
* Then we use the order to find the minimum path.
54+
```Java
55+
class Solution {
56+
private int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
57+
public int cutOffTree(List<List<Integer>> forest) {
58+
int height = forest.size(), width = forest.get(0).size();
59+
int[][] map = new int[height][width];
60+
PriorityQueue<int[]> pq = new PriorityQueue(new Comparator<int[]>(){
61+
@Override
62+
public int compare(int[] n1, int[] n2){
63+
return map[n1[0]][n1[1]] - map[n2[0]][n2[1]];
64+
}
65+
});
66+
for(int i = 0; i < height; i++){
67+
for(int j = 0; j < width; j++){
68+
map[i][j] = forest.get(i).get(j);
69+
if(map[i][j] != 0 && map[i][j] != 1) pq.offer(new int[]{i, j});
70+
}
71+
}
72+
if(map[0][0] == 0) return -1;
73+
int res = 0;
74+
Queue<int[]> queue = new LinkedList<>();
75+
int[] cur = new int[]{0, 0};
76+
while(!pq.isEmpty()){
77+
int[] dest = pq.poll();
78+
queue.clear();
79+
queue.offer(cur);
80+
boolean found = false;
81+
boolean[][] visited = new boolean[height][width];
82+
visited[cur[0]][cur[1]] = true;
83+
int step = -1;
84+
while(!queue.isEmpty() && !found){
85+
++step;
86+
int size = queue.size();
87+
for(int i = 0; i < size; i++){
88+
int[] node = queue.poll();
89+
if(map[node[0]][node[1]] == map[dest[0]][dest[1]]){
90+
found = true;
91+
res += step;
92+
break;
93+
}
94+
int tempRow = 0, tempCol = 0;
95+
for(int d = 0; d < 4; d++){
96+
tempRow = node[0] + dir[d][0];
97+
tempCol = node[1] + dir[d][1];
98+
if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && map[tempRow][tempCol] != 0 && (map[tempRow][tempCol] >= map[node[0]][node[1]] || !visited[tempRow][tempCol])){
99+
visited[tempRow][tempCol] = true;
100+
queue.add(new int[]{tempRow, tempCol});
101+
}
102+
}
103+
}
104+
if(found) break;
105+
}
106+
if(found) cur = dest;
107+
else return -1;
108+
}
109+
return res;
110+
}
111+
}
112+
```
113+
114+
### Reference
115+
1. [花花酱 LeetCode 675. Cut Off Trees for Golf Event - 刷题找工作 EP55](https://www.youtube.com/watch?v=OFkLC30OxXM)

‎leetcode/698. Partition to K Equal Sum Subsets.md

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
## 698. Partition to K Equal Sum Subsets
2+
3+
### Question
4+
Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.
5+
6+
```
7+
Example 1:
8+
9+
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
10+
Output: True
11+
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
12+
```
13+
14+
Note:
15+
* 1 <= k <= len(nums) <= 16.
16+
* 0 < nums[i] < 10000.
17+
18+
### Solution
19+
* Method 1: dfs + pruning AC slow
20+
```Java
21+
class Solution {
22+
public boolean canPartitionKSubsets(int[] nums, int k) {
23+
if(nums == null || nums.length < 4) return false;
24+
int sum = 0;
25+
for(int num : nums) sum += num;
26+
if(sum % k != 0) return false;
27+
return dfs(nums, 0, k, 0, sum / k, new boolean[nums.length]);
28+
}
29+
private boolean dfs(int[] nums, int count, int k, int cur, int sum, boolean[] visited){
30+
if(cur == sum){
31+
if(++count == k) return true;
32+
else{
33+
return dfs(nums, count, k, 0, sum, visited);
34+
}
35+
}else if(cur < sum){
36+
for(int i = 0; i < nums.length; i++){
37+
if(visited[i]) continue;
38+
visited[i] = true;
39+
if(dfs(nums, count, k, cur + nums[i], sum, visited)) return true;
40+
visited[i] = false;
41+
}
42+
}
43+
return false;
44+
}
45+
}
46+
```
47+
48+
* Method 2: dfs: pruning(A better version, beats 97%)
49+
* use a start index to record the next value to used. For a single value, in each iteration, it will be only used once.
50+
* once we reach the target, we need to set start back to 0 so dfs has a chance to check all values again.
51+
```Java
52+
class Solution {
53+
public boolean canPartitionKSubsets(int[] nums, int k) {
54+
if(nums == null || nums.length < k) return false;
55+
int sum = 0, max = Integer.MIN_VALUE;
56+
for(int num : nums){
57+
sum += num;
58+
max = Math.max(max, num);
59+
}
60+
if(sum % k != 0 || max > sum / k) return false;
61+
sum /= k;
62+
return k == 1 || dfs(nums, 0, k, 0, sum, new boolean[nums.length], 0);
63+
}
64+
private boolean dfs(int[] nums, int count, int k, int cur, int sum, boolean[] visited, int start){
65+
if(cur == sum){
66+
if(++count == k - 1) return true;
67+
else{
68+
return dfs(nums, count, k, 0, sum, visited, 0);
69+
}
70+
}else if(cur < sum){
71+
for(int i = start; i < nums.length; i++){
72+
if(visited[i]) continue;
73+
visited[i] = true;
74+
if(dfs(nums, count, k, cur + nums[i], sum, visited, i + 1)) return true;
75+
visited[i] = false;
76+
}
77+
}
78+
return false;
79+
}
80+
}
81+
```

‎leetcode/93. Restore IP Addresses.md

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
## 93. Restore IP Addresses
2+
3+
### Question
4+
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
5+
6+
```
7+
Example:
8+
9+
Input: "25525511135"
10+
Output: ["255.255.11.135", "255.255.111.35"]
11+
```
12+
13+
### Solution
14+
* Method 1: dfs partition question
15+
```Java
16+
class Solution {
17+
public List<String> restoreIpAddresses(String s) {
18+
List<String> result = new ArrayList<>();
19+
if(s == null || s.length() < 4) return result;
20+
dfs(result, new StringBuilder(), 0, s, 0);
21+
return result;
22+
}
23+
private void dfs(List<String> result, StringBuilder sb, int start, String s, int count){
24+
if(start == s.length() && count == 4){
25+
sb.deleteCharAt(sb.length() - 1);
26+
result.add(sb.toString());
27+
}else if(count < 4){
28+
for(int i = start + 1; (i <= start + 3) && (i <= s.length()); i++){
29+
String sub = s.substring(start, i);
30+
if(sub.charAt(0) == '0' && sub.length() != 1) return;
31+
int cur = Integer.parseInt(sub);
32+
if(cur >= 0 && cur <= 255){
33+
int temp = sb.length();
34+
sb.append(cur + ".");
35+
dfs(result, sb, i, s, count + 1);
36+
sb.delete(temp, sb.length());
37+
}
38+
}
39+
}
40+
}
41+
}
42+
```

0 commit comments

Comments
 (0)