Skip to content

Commit 2c5c52d

Browse files
linwtlinwt
committed
提交代码
1 parent 864e76a commit 2c5c52d

21 files changed

+547
-396
lines changed

‎leetcode_Java/DoneTitle.txt

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,11 @@
11
1. 两数之和
22
2. 两数相加
33
3. 无重复字符的最长子串
4+
4. 寻找两个有序数组的中位数
5+
5. 最长回文子串
6+
11. 盛最多水的容器
7+
15. 三数之和
8+
17. 电话号码的字母组合
49
20. 有效的括号
510
21. 合并两个有序链表
611
53. 最大子数组和
@@ -19,13 +24,19 @@
1924
155. 最小栈
2025
160. 相交链表
2126
169. 多数元素
27+
200. 岛屿数量
2228
206. 反转链表
2329
226. 翻转二叉树
2430
234. 回文链表
31+
236. 二叉树的最近公共祖先
2532
283. 移动零
33+
300. 最长上升子序列
2634
338. 比特位计数
35+
406. 根据身高重建队列
36+
437. 路径总和
2737
448. 找到所有数组中消失的数字
2838
461. 汉明距离
39+
538. 把二叉搜索树转换为累加树
2940
543. 二叉树的直径
3041
589. N叉树的前序遍历
3142
617. 合并二叉树

‎leetcode_Java/Solution0004.java

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
// 寻找两个有序数组的中位数
2+
3+
4+
/*
5+
数组合并，排序，取中间
6+
*/
7+
public class Solution {
8+
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
9+
// Arrays.copyOf(源数组， 复制长度)
10+
int[] nums = Arrays.copyOf(nums1, nums1.length + nums2.length);
11+
// System.arraycopy(源数组， 源数组起始索引， 目标数组， 目标数组起始索引， 复制长度)
12+
System.arraycopy(nums2, 0, nums, nums1.length, nums2.length);
13+
Arrays.sort(nums);
14+
15+
if (nums.length % 2 == 0)
16+
return ((float) nums[nums.length / 2 - 1] + nums[nums.length / 2]) / 2;
17+
else
18+
return (float) nums[nums.length / 2];
19+
}
20+
}
21+
22+
23+
/*
24+
逻辑同上
25+
*/
26+
class Solution {
27+
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
28+
int n = nums1.length + nums2.length;
29+
int[] nums3 = new int[n];
30+
int k = 0;
31+
for (int i = 0; i < nums1.length; i++) {
32+
nums3[k] = nums1[i];
33+
k++;
34+
}
35+
for (int j = 0; j < nums2.length; j++) {
36+
nums3[k] = nums2[j];
37+
k++;
38+
}
39+
Arrays.sort(nums3);
40+
if (n % 2 == 0) {
41+
int num1 = nums3[n / 2];
42+
int num2 = nums3[n / 2 - 1];
43+
return (num1 + num2) / 2.0;
44+
} else {
45+
return nums3[n / 2];
46+
}
47+
}
48+
}

‎leetcode_Java/Solution0005.java

Lines changed: 124 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,124 @@
1+
// 最长回文子串
2+
3+
4+
/*
5+
暴力破解：列举所有的子串，判断是否为回文串，保存最长的回文串
6+
*/
7+
class Solution {
8+
public String longestPalindrome(String s) {
9+
int len = s.length();
10+
if (len < 2) {
11+
return s;
12+
}
13+
int maxLen = 0;
14+
String res = "";
15+
for (int i = 0; i < len; i++) {
16+
for (int j = i + maxLen; j <= len; j++) {
17+
String sub = s.substring(i, j);
18+
int subLen = sub.length();
19+
if (isPalindrome(sub) && subLen > maxLen) {
20+
res = sub;
21+
maxLen = subLen;
22+
}
23+
}
24+
}
25+
return res;
26+
}
27+
28+
private boolean isPalindrome(String s) {
29+
int l = 0, r = s.length() - 1;
30+
while (l < r) {
31+
if (s.charAt(l) != s.charAt(r)) {
32+
return false;
33+
}
34+
l++;
35+
r--;
36+
}
37+
for (int l = 0, r = s.length() - 1; l < r; )
38+
return true;
39+
}
40+
41+
// 方法同上，使用for替代while
42+
private boolean isPalindrome(String s) {
43+
for (int l = 0, r = s.length() - 1; l < r; l++, r--) {
44+
if (s.charAt(l) != s.charAt(r)) {
45+
return false;
46+
}
47+
}
48+
return true;
49+
}
50+
}
51+
52+
53+
/*
54+
中心扩散：
55+
1、遍历字符，以当前字符为中心向两边扩散，包括奇数和偶数回文串两种中心，得到当前中心的回文串长度
56+
2、比较并记录所有中心的最长回文串长度和对应起点，最后截取并返回最长回文子串
57+
*/
58+
class Solution {
59+
public String longestPalindrome(String s) {
60+
int len = s.length();
61+
if (len < 2) {
62+
return s;
63+
}
64+
int maxLen = 1;
65+
int start = 0;
66+
for (int i = 0; i < len - 1; i++) {
67+
int oddLen = expandAroudCenter(s, i, i);
68+
int evenLen = expandAroudCenter(s, i, i + 1);
69+
int curMaxLen = Math.max(oddLen, evenLen);
70+
if (curMaxLen > maxLen) {
71+
maxLen = curMaxLen;
72+
start = i - (maxLen - 1) / 2;
73+
}
74+
}
75+
return s.substring(start, start + maxLen);
76+
}
77+
78+
private int expandAroudCenter(String s, int l, int r) {
79+
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
80+
l--;
81+
r++;
82+
}
83+
return r - l - 1;
84+
}
85+
}
86+
87+
88+
/*
89+
动态规划：
90+
1、回文天然具有「状态转移」性质：一个长度大于 2 的回文去掉头尾字符以后，剩下的部分依然是回文。
91+
反之，如果一个字符串头尾两个字符都不相等，那么这个字符串一定不是回文。「动态规划」的方法根据这样的性质得到。
92+
2、动态规划是暴力破解的优化，两者同样需要遍历列举判断所有子串是否为回文串，
93+
区别是暴力破解每次都要对子串单独处理判断是否为回文串，动态规划可以利用之前记录的子串结果直接判断当前子串是否为回文串
94+
3、boolean数组创建时，默认值是false，只需要标记为true的地方即可
95+
4、dp[l][r]表示子串s[l,r]是否为回文子串，l是左区间，r是右区间
96+
5、状态转移方程：dp[l][r] = (s[l] == s[r]) and (r - l < 3 or dp[l + 1][r - 1])
97+
s[l] == s[r] 表示首尾两个字符相等
98+
r - l < 3 表示去掉首尾后剩余0或1个字符时仍是回文。作用包含了1个字符是回文，所以不用初始化dp数组的对角线为true
99+
dp[l + 1][r - 1] 表示去掉首尾后的区间是否回文
100+
6、dp[l][r]是回文时，则比较并记录最长回文串的长度和首尾位置
101+
*/
102+
class Solution {
103+
public String longestPalindrome(String s) {
104+
int len = s.length();
105+
if (len < 2) {
106+
return s;
107+
}
108+
int maxLen = 1, start = 0, end = 0;
109+
boolean[][] dp = new boolean[len][len];
110+
for (int r = 1; r < len; r++) {
111+
for (int l = 0; l < r; l++) {
112+
if (s.charAt(l) == s.charAt(r) && (r - l < 3 || dp[l + 1][r - 1])) {
113+
dp[l][r] = true;
114+
if (r - l + 1 > maxLen) {
115+
maxLen = r - l + 1;
116+
start = l;
117+
end = r;
118+
}
119+
}
120+
}
121+
}
122+
return s.substring(start, end + 1);
123+
}
124+
}

‎leetcode_Java/Solution0011.java

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
// 盛最多水的容器
2+
3+
4+
/*
5+
双指针：初始化左右指针，面积 = 柱子距离 * 矮柱子高度，然后矮柱子指针向中间移动一步，争取更高的高度，继续计算面积，记录最大面积
6+
*/
7+
class Solution {
8+
public int maxArea(int[] height) {
9+
int l = 0, r = height.length - 1, maxArea = 0;
10+
while (l < r) {
11+
maxArea = Math.max(maxArea, (r - l) * Math.min(height[l], height[r]));
12+
if (height[l] < height[r]) {
13+
l++;
14+
} else {
15+
r--;
16+
}
17+
}
18+
return maxArea;
19+
}
20+
}

‎leetcode_Java/Solution0015.java

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
// 三数之和
2+
3+
4+
/*
5+
数组排序后，先固定一个数，再用双指针从头尾向内移动确定另外两个数，使用HashSet对结果去重
6+
*/
7+
class Solution {
8+
public List<List<Integer>> threeSum(int[] nums) {
9+
int n = nums.length;
10+
Set<List<Integer>> set = new HashSet<>();
11+
Arrays.sort(nums);
12+
for (int i = 0; i < n - 2; i++) {
13+
int l = i + 1, r = n - 1;
14+
while (l < r) {
15+
if (nums[i] + nums[l] + nums[r] == 0) {
16+
List<Integer> list = new ArrayList<>();
17+
list.add(nums[i]);
18+
list.add(nums[l]);
19+
list.add(nums[r]);
20+
set.add(list);
21+
l++;
22+
r--;
23+
} else if (nums[i] + nums[l] + nums[r] < 0) {
24+
l++;
25+
} else {
26+
r--;
27+
}
28+
}
29+
}
30+
List<List<Integer>> res = new ArrayList<>(set);
31+
return res;
32+
}
33+
}
34+
35+
36+
/*
37+
逻辑同上，有优化：
38+
1、遍历时第一个数跟前一个相同，则跳过重复处理
39+
2、使用ArrayList存放结果，当有一组满足条件的三元组时，通过while循环移动指针进行去重，避免出现重复的三元组
40+
*/
41+
class Solution {
42+
public List<List<Integer>> threeSum(int[] nums) {
43+
int n = nums.length;
44+
List<List<Integer>> res = new ArrayList<>();
45+
Arrays.sort(nums);
46+
for (int i = 0; i < n - 2; i++) {
47+
if (i > 0 && nums[i] == nums[i - 1]) {
48+
continue;
49+
}
50+
int l = i + 1, r = n - 1;
51+
while (l < r) {
52+
if (nums[i] + nums[l] + nums[r] == 0) {
53+
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
54+
l++;
55+
r--;
56+
while (l < r && nums[l] == nums[l - 1]) {
57+
l++;
58+
}
59+
while (l < r && nums[r] == nums[r + 1]) {
60+
r--;
61+
}
62+
} else if (nums[i] + nums[l] + nums[r] < 0) {
63+
l++;
64+
} else {
65+
r--;
66+
}
67+
}
68+
}
69+
return res;
70+
}
71+
}

0 commit comments

Comments
 (0)