Skip to content

Commit ffbe814

Browse files
DreamCatsDreamCats
committed
📝 update lc
1 parent 5690373 commit ffbe814

8 files changed

Lines changed: 205 additions & 4 deletions

File tree

‎Java/alg/.DS_Store‎

0 Bytes
Binary file not shown.

‎Java/alg/README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -117,6 +117,8 @@
117117
- [43.字符串相乘](lc/43.字符串相乘.md)
118118
- [46.全排列](lc/46.全排列.md)
119119
- [47.全排列2](lc/47.全排列2.md)
120+
- [55.跳跃游戏](lc/55.跳跃游戏.md)
121+
- [56.合并区间](lc/56.合并区间.md)
120122

121123
## 笔试
122124

‎Java/alg/lc/39.组合总和.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -51,7 +51,7 @@ func combinationSum(candidates []int, target int) [][]int {
5151
var dfs func(nums []int, target int, start int, list []int)
5252
dfs = func(nums []int, target int, start int, list []int) {
5353
if target == 0 {
54-
res = append(res, list)
54+
res = append(res, append([]int{}, list...))
5555
return
5656
}
5757
for i := start; i < len(nums); i++ {

‎Java/alg/lc/40.组合总和2.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@ func combinationSum2(candidates []int, target int) [][]int {
5959
var dfs func(nums []int, target int, start int, list[] int)
6060
dfs = func(nums []int, target int, start int, list []int) {
6161
if target == 0 {
62-
res = append(res, list)
62+
res = append(res, append([]int{}, list...))
6363
return
6464
}
6565
for i := start; i < len(nums); i++ {

‎Java/alg/lc/46.全排列.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -62,7 +62,7 @@ func permute(nums []int) [][]int {
6262
marked := make([]bool, len(nums))
6363
dfs = func(nums []int, list []int) {
6464
if len(list) == len(nums) {
65-
res = append(res, list)
65+
res = append(res, append([]int{}, list...))
6666
return
6767
}
6868
for i := 0; i < len(nums); i++ {

‎Java/alg/lc/47.全排列2.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -64,7 +64,7 @@ func permuteUnique(nums []int) [][]int {
6464
marked := make([]bool, len(nums))
6565
dfs = func(nums []int, list []int) {
6666
if len(nums) == len(list) {
67-
res = append(res, list)
67+
res = append(res, append([]int{}, list...))
6868
}
6969
for i := 0; i < len(nums); i++ {
7070
if marked[i] {

‎Java/alg/lc/55.跳跃游戏.md‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
# 55. 跳跃游戏
2+
3+
[url](https://leetcode-cn.com/problems/jump-game/)
4+
5+
## 题目
6+
7+
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
8+
9+
数组中的每个元素代表你在该位置可以跳跃的最大长度。
10+
11+
判断你是否能够到达最后一个下标。
12+
13+
```
14+
输入：nums = [2,3,1,1,4]
15+
输出：true
16+
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
17+
输入：nums = [3,2,1,0,4]
18+
输出：false
19+
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
20+
```
21+
22+
## 方法
23+
24+
## code
25+
26+
### js
27+
28+
```js
29+
let canJump = nums => {
30+
if (nums === null || nums.length === 0) return false;
31+
let max = 0;
32+
for (let i = 0; i < nums.length - 1; i++) {
33+
if (i <= max)
34+
max = Math.max(max, nums[i] + 1);
35+
else
36+
break;
37+
}
38+
return max >= nums.length - 1;
39+
}
40+
```
41+
42+
### go
43+
44+
```go
45+
func canJump(nums []int) bool {
46+
if len(nums) == 0 {
47+
return false
48+
}
49+
Max := func(a int, b int) int {
50+
if a > b {
51+
return a
52+
} else {
53+
return b
54+
}
55+
}
56+
max := 0
57+
for i := 1; i < len(nums); i++ {
58+
if i <= max {
59+
max = Max(max, nums[i] + 1)
60+
} else {
61+
break
62+
}
63+
}
64+
return max >= len(nums) - 1
65+
}
66+
```
67+
68+
69+
70+
### java
71+
72+
```java
73+
class Solution {
74+
public boolean canJump(int[] nums) {
75+
if (nums == null || nums.length == 0)
76+
return false;
77+
int max = 0;
78+
for (int i = 1; i < nums.length - 1; i++){
79+
if (i <= max)
80+
max = Math.max(max, nums[i] + 1);
81+
else
82+
break;
83+
}
84+
return max >= nums.length - 1;
85+
}
86+
}
87+
```
88+

‎Java/alg/lc/56.合并区间.md‎

Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,111 @@
1+
# 56. 合并区间
2+
3+
[url](https://leetcode-cn.com/problems/merge-intervals/)
4+
5+
## 题目
6+
7+
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
8+
9+
```
10+
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
11+
输出：[[1,6],[8,10],[15,18]]
12+
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
13+
输入：intervals = [[1,4],[4,5]]
14+
输出：[[1,5]]
15+
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
16+
```
17+
18+
## 方法
19+
20+
## code
21+
22+
### js
23+
24+
```js
25+
let merge = intervals => {
26+
if (intervals === null || intervals.length <= 1) return intervals;
27+
intervals.sort((a, b) => {
28+
return a[0] - b[0]
29+
});
30+
let list = []
31+
let i = 0, n = intervals.length;
32+
while (i < n) {
33+
let l = intervals[i][0];
34+
let r = intervals[i][1];
35+
while (i < n - 1 && r >= intervals[i + 1][0]) {
36+
r = Math.max(r, intervals[i + 1][1])
37+
i++;
38+
}
39+
list.push([l, r]);
40+
i++;
41+
}
42+
return list;
43+
}
44+
```
45+
46+
### go
47+
48+
```go
49+
type numsSortable [][]int
50+
51+
func (nums numsSortable) Len() int {
52+
return len(nums)
53+
}
54+
func (nums numsSortable) Less(i, j int) bool {
55+
return nums[i][0] <= nums[j][0]
56+
}
57+
func (nums numsSortable) Swap(i, j int) {
58+
nums[i], nums[j] = nums[j], nums[i]
59+
}
60+
func merge2(intervals [][]int) [][]int {
61+
Max := func(a, b int) int {
62+
if a > b {
63+
return a
64+
}
65+
return b
66+
}
67+
if len(intervals) <= 1{
68+
return intervals
69+
}
70+
sort.Sort(numsSortable(intervals))
71+
list := make([][]int, 0)
72+
i, n := 0, len(intervals)
73+
for i < n {
74+
l, r := intervals[i][0], intervals[i][1]
75+
for i < n-1 && r >= intervals[i+1][0] {
76+
r = Max(r, intervals[i + 1][1])
77+
i++
78+
}
79+
list = append(list, []int{l, r})
80+
i++
81+
}
82+
return list
83+
}
84+
```
85+
86+
87+
### java
88+
89+
```java
90+
class Solution {
91+
public int[][] merge(int[][] intervals) {
92+
if (intervals == null || intervals.length <= 1) return intervals;
93+
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
94+
List<int[]> list = new ArrayList<>();
95+
int i = 0;
96+
int n = intervals.length;
97+
while (i < n) {
98+
int l = intervals[i][0];
99+
int r = intervals[i][1];
100+
while (i < n - 1 && r >= intervals[i + 1][0]) {
101+
r = Math.max(r, intervals[i + 1][1]);
102+
i++;
103+
}
104+
list.add(new int[] {l, r});
105+
i++;
106+
}
107+
return list.toArray(new int[list.size()][2]);
108+
}
109+
}
110+
```
111+

0 commit comments

Comments
 (0)