Skip to content

Commit 1c0f156

Browse files
DingyaningDingyaning
committed
week6:DP
1 parent 622c31c commit 1c0f156

16 files changed

Lines changed: 809 additions & 5 deletions

‎.gitignore‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
/.idea/
2+
/output/

‎Week_01/G20200343040206/ListNode.java‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
public class ListNode {
2+
int val;
3+
ListNode next;
4+
5+
ListNode(int x) {
6+
val = x;
7+
}
8+
}

‎Week_01/G20200343040206/Test_189.java‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
public class Test_189 {
2+
3+
public static void main(String[] args) {
4+
LeetCode_189_0206 source = new LeetCode_189_0206();
5+
6+
int[] nums_3 = new int[]{1,2,3,4,5,6,7};
7+
source.rotate(nums_3,3);
8+
System.out.println(nums_3);
9+
10+
}
11+
12+
13+
}

‎Week_01/G20200343040206/Test_26.java‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
public class Test_26 {
2+
3+
public static void main(String[] args) {
4+
LeetCode_26_0206 source = new LeetCode_26_0206();
5+
6+
int[] nums_0 = new int[]{};
7+
int[] nums_1 = new int[]{1};
8+
int[] nums_2 = new int[]{1,1,2};
9+
int[] nums_n = new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
10+
11+
12+
System.out.println(source.removeDuplicates(nums_0));
13+
System.out.println(source.removeDuplicates(nums_1));
14+
System.out.println(source.removeDuplicates(nums_2));
15+
System.out.println(source.removeDuplicates(nums_n));
16+
17+
}
18+
19+
20+
}

‎Week_02/G20200343040206/LeetCode_409_0206.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
2+
//给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
3+
//
4+
// 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
5+
//
6+
// 注意:
7+
//假设字符串的长度不会超过 1010。
8+
//
9+
// 示例 1:
10+
//
11+
//
12+
//输入:
13+
//"abccccdd"
14+
//
15+
//输出:
16+
//7
17+
//
18+
//解释:
19+
//我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
20+
//
21+
// Related Topics 哈希表
22+
23+
24+
//leetcode submit region begin(Prohibit modification and deletion)
25+
class LeetCode_409_0206 {
26+
//1. 取所有字符串的最大偶数次数
27+
//2. 如果有奇数个字符串，则可以+1
28+
public int longestPalindrome(String s) {
29+
if (s==null) return 0;
30+
if (s.length()==1)return 1;
31+
int result = 0;
32+
//26+26+不连续的中间6个
33+
int[] num = new int[58];
34+
for (char c : s.toCharArray()) {
35+
num[c - 'A']++;
36+
}
37+
for (int i : num) {
38+
result += i - (i & 1);
39+
if ((i & 1) ==1 && (result & 1) == 0){
40+
result++;
41+
}
42+
}
43+
return result;
44+
}
45+
46+
public static void main(String[] args) {
47+
LeetCode_409_0206 source = new LeetCode_409_0206();
48+
System.out.println(source.longestPalindrome("abccccdd"));
49+
}
50+
}
51+
//leetcode submit region end(Prohibit modification and deletion)

‎Week_02/G20200343040206/LeetCode_49_0206.java‎

Lines changed: 0 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -82,10 +82,5 @@ private String transformStr(String s) {
8282
return result;
8383
}
8484

85-
public static void main(String[] args) {
86-
String[] str = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
87-
LeetCode_49_0206 source = new LeetCode_49_0206();
88-
source.groupAnagrams_2(str);
89-
}
9085
}
9186
//leetcode submit region end(Prohibit modification and deletion)

‎Week_04/G20200343040206/DFS.java‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
public class DFS {
2+
// if node in visited:
3+
// # already visited
4+
// return
5+
//
6+
// visited.add(node)
7+
//
8+
// # process current node
9+
// # ...# logic here
10+
// dfs(node.left)
11+
// dfs(node.right)
12+
}
13+
//
14+
//visited = set()
15+
//def dfs(node, visited):
16+
// visited.add(node)
17+
// # process current node here.
18+
// ...
19+
// for next_node in node.children():
20+
// if not next_node in visited:
21+
// dfs(next_node, visited)
22+
//
23+
//
24+
//def BFS(graph, start, end):
25+
//
26+
// queue = []
27+
// queue.append([start])
28+
// visited.add(start)
29+
//
30+
// while queue:
31+
// node = queue.pop()
32+
// visited.add(node)
33+
//
34+
// process(node)
35+
// nodes = generate_related_nodes(node)
36+
// queue.push(nodes)
37+
//
38+
// # other processing work
39+
// ...
40+
//
41+
//visited = set()
42+
//
43+
//def dfs(node, visited):
44+
// visited.add(node)
45+
//
46+
// # process current node here.
47+
// ...
48+
//
49+
// for next_node in node.children():
50+
// if not next_node in visited:
51+
// def(next_node, visited)
52+
//
53+
//left,right=0,len(array)-1
54+
//while left<=right
55+
// mid = (left+right)/2
56+
// if array[mid] == target:
57+
// #find the target!!
58+
// break or return result
59+
// else array[mid] < target:
60+
// left = mid + 1
61+
// else:
62+
// right = mid - 1

‎Week_04/G20200343040206/Test_01.java‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
import java.util.ArrayList;
2+
import java.util.Arrays;
3+
import java.util.List;
4+
5+
//给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
6+
//
7+
//注意：
8+
//
9+
//答案中不可以包含重复的四元组。
10+
//
11+
//示例：
12+
//
13+
//给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
14+
//
15+
//满足要求的四元组集合为：
16+
//[
17+
// [-1, 0, 0, 1],
18+
// [-2, -1, 1, 2],
19+
// [-2, 0, 0, 2]
20+
//]
21+
public class Test_01 {
22+
public List<List<Integer>> fourSum(int[] nums, int target) {
23+
List<List<Integer>> result = new ArrayList<>();
24+
Arrays.sort(nums);
25+
int n = nums.length;
26+
27+
int start = 0;
28+
int end = n-1;
29+
30+
for (int i = start; i< n-3; ++i) {
31+
if (i > start && nums[i] == nums[i-1]) {
32+
continue;
33+
}
34+
35+
for (int j = i+1; j<n-2;++j) {
36+
if (j > (i+1) && nums[j] == nums[j-1]) {
37+
continue;
38+
}
39+
40+
int k = j+1;
41+
int l = n-1;
42+
43+
while (k < l) {
44+
if (k > (j+1) && nums[k] == nums[k-1]) {
45+
k++;
46+
continue;
47+
}
48+
49+
if (l < (n-1) && nums[l] == nums[l+1]) {
50+
l--;
51+
continue;
52+
}
53+
54+
int s = nums[i] +nums[j] + nums[k] + nums[l];
55+
if (s == target) {
56+
result.add(Arrays.asList(nums[i],nums[j],nums[k],nums[l]));
57+
k++;
58+
l--;
59+
} else if (s < target) {
60+
k++;
61+
} else {
62+
l--;
63+
}
64+
65+
}
66+
67+
}
68+
69+
70+
}
71+
return result;
72+
}
73+
}

‎Week_04/G20200343040206/Test_02.java‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
public class Test_02 {
2+
// 给定一个非负整数数组，你最初位于数组的第一个位置。
3+
//
4+
//数组中的每个元素代表你在该位置可以跳跃的最大长度。
5+
//
6+
//你的目标是使用最少的跳跃次数到达数组的最后一个位置。
7+
//
8+
//示例:
9+
//
10+
//输入: [2,3,1,1,4]
11+
//输出: 2
12+
//解释: 跳到最后一个位置的最小跳跃数是 2。
13+
// 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
14+
//说明:
15+
//
16+
//假设你总是可以到达数组的最后一个位置。
17+
18+
19+
public int jump(int[] nums) {
20+
if (nums==null || nums.length == 0){
21+
return 0;
22+
}
23+
24+
int step = 0;
25+
int maxPos = 0;
26+
int end = 0;
27+
for (int i = 0; i < nums.length - 1; i++) {
28+
maxPos = Math.max(maxPos,nums[i] + i);
29+
if (i == end) {
30+
end = maxPos;
31+
step++;
32+
}
33+
}
34+
return step;
35+
}
36+
}

‎Week_06/G20200343040206/LeetCode_221_0206.java‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
//在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
2+
//
3+
// 示例:
4+
//
5+
// 输入:
6+
//
7+
//1 0 1 0 0
8+
//1 0 1 1 1
9+
//1 1 1 1 1
10+
//1 0 0 1 0
11+
//
12+
//输出: 4
13+
// Related Topics 动态规划
14+
15+
16+
//leetcode submit region begin(Prohibit modification and deletion)
17+
class LeetCode_221_0206 {
18+
//暴力求解,感觉都很难
19+
//遍历矩阵，找到1，就从1开始往下找矩形，0就跳过
20+
//怎么从1开始找矩形？找边长，然后遍历最长边长组成的长方形，看是否都是1
21+
22+
//直接上动态规划
23+
//dp[i,j]表示以a[i,j]为右下角的正方形的最大边长
24+
//那就可以得出dp方程:dp[i,j] = min(dp[i-1,j], dp[i,j-1], dp[i-1,j-1]) + 1
25+
public int maximalSquare(char[][] matrix) {
26+
if(matrix == null || matrix.length == 0) {
27+
return 0;
28+
}
29+
int[][] dp = new int[matrix.length][matrix[0].length];
30+
int maxSide = 0;
31+
for (int i = 0; i < matrix[0].length; i++) {
32+
if (matrix[0][i] == '1') {
33+
dp[0][i] = 1;
34+
maxSide = 1;
35+
}
36+
}
37+
for (int i = 1; i < matrix.length; i++) {
38+
if (matrix[i][0] == '1') {
39+
dp[i][0] = 1;
40+
maxSide = 1;
41+
}
42+
}
43+
44+
for (int i = 1; i < matrix.length; i++) {
45+
for (int j = 1; j < matrix[0].length; j++) {
46+
if (matrix[i][j] == '1') {
47+
dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
48+
}
49+
maxSide = Math.max(maxSide, dp[i][j]);
50+
}
51+
}
52+
53+
return maxSide * maxSide;
54+
}
55+
56+
//优化存储空间，使用一维dp方程
57+
public int maximalSquare_1(char[][] matrix) {
58+
if(matrix == null || matrix.length == 0) {
59+
return 0;
60+
}
61+
int[] dp = new int[matrix[0].length + 1];
62+
int maxSide = 0;
63+
int pre = 0;
64+
for (int i = 1; i <= matrix.length; i++) {
65+
for (int j = 1; j <= matrix[0].length; j++) {
66+
int temp = dp[j];
67+
if (matrix[i-1][j-1] == '1') {
68+
dp[j] = Math.min(dp[j-1],Math.min(dp[j], pre)) + 1;
69+
maxSide = Math.max(dp[j],maxSide);
70+
} else {
71+
dp[j] = 0;
72+
}
73+
pre = temp;
74+
}
75+
}
76+
return maxSide * maxSide;
77+
}
78+
}
79+
//leetcode submit region end(Prohibit modification and deletion)

0 commit comments

Comments
 (0)