Skip to content

Commit 5eefc42

Browse files
leosanqingleosanqing
committed
UPDATE
1 parent 5afa980 commit 5eefc42

6 files changed

Lines changed: 111 additions & 37 deletions

File tree

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/array/_53_maximum_subarray.java‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package com.leosanqing.leetcode.easy.array;
2+
3+
/**
4+
* @description: 给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
5+
* <p>
6+
* 示例 1：
7+
* <p>
8+
* 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
9+
* 输出：6
10+
* 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
11+
* 示例 2：
12+
* 输入：nums = [1]
13+
* 输出：1
14+
* <p>
15+
* 示例 3：
16+
* 输入：nums = [0]
17+
* 输出：0
18+
* <p>
19+
* 示例 4：
20+
* 输入：nums = [-1]
21+
* 输出：-1
22+
* <p>
23+
* 示例 5：
24+
* 输入：nums = [-100000]
25+
* 输出：-100000
26+
* <p>
27+
* 来源：力扣（LeetCode）
28+
* 链接：https://leetcode-cn.com/problems/maximum-subarray
29+
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
30+
* @author: rtliu
31+
* @date: 2021/4/9 10:09 上午
32+
*/
33+
public class _53_maximum_subarray {
34+
35+
public static void main(String[] args) {
36+
System.out.println(maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
37+
System.out.println(maxSubArray(new int[]{2}));
38+
System.out.println(maxSubArray(new int[]{-1, 2, -1}));
39+
System.out.println(maxSubArray(new int[]{-1, -1, -2, -2}));
40+
}
41+
42+
/**
43+
* 这个题思路很简单，从左到右遍历，如果前面的和小于当前数，则舍弃之前的数组，从当前位置重新开始找
44+
*
45+
* @param nums
46+
* @return
47+
*/
48+
public static int maxSubArray(int[] nums) {
49+
int max = nums[0];
50+
int sum = 0;
51+
for (int num : nums) {
52+
sum = Math.max(sum + num,num);
53+
max = Math.max(sum, max);
54+
}
55+
return max;
56+
}
57+
}

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

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -44,26 +44,29 @@ public static void main(String[] args) {
4444
* @return
4545
*/
4646
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
47-
4847
List<List<Integer>> answer = new ArrayList<>();
48+
49+
// 先排序
4950
Arrays.sort(candidates);
50-
backTrace(answer, new ArrayList<>(), candidates, 0, target);
51+
52+
backtrace(answer, candidates, target, new ArrayList<>(), 0);
5153

5254
return answer;
5355
}
5456

55-
56-
private static void backTrace(List<List<Integer>> answer, List<Integer> list, int[] candidates, int position, int remain) {
57-
if (remain < 0) {
57+
private static void backtrace(List<List<Integer>> answer, int[] candidates, int target, List<Integer> list, int position) {
58+
if (target < 0) {
5859
return;
59-
} else if (remain == 0) {
60+
}
61+
62+
if (target == 0) {
6063
answer.add(new ArrayList<>(list));
6164
return;
6265
}
6366

6467
for (int i = position; i < candidates.length; i++) {
6568
list.add(candidates[i]);
66-
backTrace(answer, list, candidates, i, remain - candidates[i]);
69+
backtrace(answer, candidates, target - candidates[i], list, i);
6770
list.remove(list.size() - 1);
6871
}
6972
}

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

Lines changed: 10 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -8,10 +8,10 @@
88
* @Date: 2020/7/14 上午9:36
99
* @Package: com.leosanqing.leetcode.medium.array
1010
* @Description: 1
11-
*` Given a collection of distinct integers, return all possible permutations.
12-
*` Example:
13-
*` Input: [1,2,3]
14-
*` Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
11+
* ` Given a collection of distinct integers, return all possible permutations.
12+
* ` Example:
13+
* ` Input: [1,2,3]
14+
* ` Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
1515
* @Version: 1.0
1616
*/
1717
public class _46_permutations {
@@ -20,37 +20,29 @@ public static void main(String[] args) {
2020
System.out.println(permute(new int[]{1, 2, 3}));
2121
}
2222

23-
2423
public static List<List<Integer>> permute(int[] nums) {
2524
List<List<Integer>> answer = new ArrayList<>();
2625

27-
backTrace(answer, new ArrayList<>(), nums);
26+
backtrace(answer, nums, new ArrayList<>());
2827
return answer;
29-
3028
}
3129

32-
/**
33-
* 递归遍历
34-
* @param answer
35-
* @param list
36-
* @param nums
37-
*/
38-
private static void backTrace(List<List<Integer>> answer, List<Integer> list, int[] nums) {
30+
31+
private static void backtrace(List<List<Integer>> answer, int[] nums, List<Integer> list) {
3932
if (list.size() == nums.length) {
4033
answer.add(new ArrayList<>(list));
4134
return;
4235
}
36+
4337
for (int num : nums) {
44-
// 如果有这个数字，就跳过
4538
if (list.contains(num)) {
4639
continue;
4740
}
41+
4842
list.add(num);
49-
backTrace(answer, list, nums);
43+
backtrace(answer, nums, list);
5044
list.remove(list.size() - 1);
5145
}
52-
53-
5446
}
5547

5648
}

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

Lines changed: 27 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -49,24 +49,24 @@ public static void main(String[] args) {
4949

5050
/**
5151
* 分成两步进行旋转
52-
*
52+
* <p>
5353
* 1 2 3
5454
* 4 5 6
5555
* 7 8 9
56-
*
56+
* <p>
5757
* 1 4 7
5858
* 2 5 8
5959
* 3 6 9
60-
*
60+
* <p>
6161
* 7 4 1
6262
* 8 5 2
6363
* 9 6 3
6464
*
65-
*
6665
* @param matrix
6766
*/
6867
public static void rotate(int[][] matrix) {
6968
int temp;
69+
7070
for (int i = 0; i < matrix.length; i++) {
7171
for (int j = i; j < matrix[0].length; j++) {
7272
temp = matrix[i][j];
@@ -83,4 +83,27 @@ public static void rotate(int[][] matrix) {
8383
}
8484
}
8585
}
86+
87+
88+
public static void rotate1(int[][] matrix) {
89+
int temp;
90+
for (int i = 0; i < matrix.length; i++) {
91+
for (int j = i; j < matrix[0].length; j++) {
92+
if (i == j) {
93+
continue;
94+
}
95+
temp = matrix[i][j];
96+
matrix[i][j] = matrix[j][i];
97+
matrix[j][i] = temp;
98+
}
99+
}
100+
101+
for (int i = 0; i < matrix.length; i++) {
102+
for (int j = 0; j < matrix[0].length / 2; j++) {
103+
temp = matrix[i][j];
104+
matrix[i][j] = matrix[i][matrix[0].length - j - 1];
105+
matrix[i][matrix[0].length - j - 1] = temp;
106+
}
107+
}
108+
}
86109
}

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

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@ public static void main(String[] args) {
2525
String[] strings = {"eat", "tea", "tan", "ate", "nat", "bat"};
2626
System.out.println(groupAnagrams(strings));
2727
}
28+
2829
public static List<List<String>> groupAnagrams(String[] strs) {
2930
List<List<String>> answer = new ArrayList<>();
3031

@@ -43,7 +44,7 @@ public static List<List<String>> groupAnagrams(String[] strs) {
4344

4445
List<String> list = map.getOrDefault(s, new ArrayList<>());
4546
list.add(str);
46-
map.put(s,list);
47+
map.put(s, list);
4748

4849
}
4950
return new ArrayList<>(map.values());

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

Lines changed: 5 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -53,16 +53,14 @@ public static void main(String[] args) {
5353
* @return
5454
*/
5555
public static boolean canJump(int[] nums) {
56-
int reachable = 0;
57-
for (int i = 0; i < nums.length; ++i) {
58-
// 当 i 大于 reachable 说明这个地方不可达，那肯定有问题
59-
if (i > reachable) {
56+
int max = 0;
57+
for (int i = 0; i < nums.length; i++) {
58+
if (i > max) {
6059
return false;
6160
}
62-
reachable = Math.max(reachable, i + nums[i]);
61+
// 算出能到达的最远距离
62+
max = Math.max(max, i + nums[i]);
6363
}
6464
return true;
6565
}
66-
67-
6866
}

0 commit comments

Comments
 (0)