# 跳跃游戏
55. 跳跃游戏
给定一个非负整数数组 nums
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
贪心思路：找到一个下标，这个下标刚好可以到达最后下一个下标。
- 从下标
i 出发可达区间 (i, i + nums[i] ] ， 当然， i < nums.length 。 - 前
n 个下标会有一个最大可达下标 max = max(max, i + nums[i])） 。 - 当
max >= nums.length - 1 时，这个数组的最后一个下标是可达的。 - 下标
i 不会超过最大可达下标： i <= max
1
2
3
4
5
6
7
8
9
10
11
| public boolean canJump(int[] nums) {
int len = nums.length;
int max = 0;
for(int i = 0; i < len && i<=max; i++) {
max = Math.max(nums[i] + i, max);
if(max >= len-1) {
return true;
}
}
return false;
}
|
# 最长有效括号
32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
动态规划 + 双指针
max 记录最长括号子串括号数。left 和 right 在遍历时记录左括号和右括号数。- 当
right == left 时说明括号匹配，记录 max = Math.max(right,max) 。 right > left 说明子串中有括号匹配不了， left 和 right 置 0。
这时候就有一个问题：以上操作只能判断 ) 无法匹配的情况，如何解决 ( 无法匹配的情况？
可以反转字符串重复以上步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| public int longestValidParentheses(String s) {
if (s == null || "".equals(s)) {
return 0;
}
int left = 0;
int right = 0;
int max = 0;
for(Character c : s.toCharArray()) {
if( c == '('){
left++;
} else {
right++;
}
if(left == right) {
max = Math.max(right,max);
}else if(right > left) {
right = 0;
left = 0;
}
}
left = 0;
right = 0;
for(Character c : new StringBuilder(s).reverse().toString().toCharArray()) {
if( c == '('){
left++;
} else {
right++;
}
if(left == right) {
max = Math.max(left,max);
}else if(left > right) {
right = 0;
left = 0;
}
}
return max << 1;
}
|
# 最长公共前缀
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 "" 。
输入：strs = ["flower","flow","flight"]
输出："fl"
边界条件太多，要判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| public String longestCommonPrefix(String[] strs) {
if(strs.length == 0) {
return "";
}
if(strs.length == 1 || strs[0].equals("")){
return strs[0];
}
String base = strs[0];
int res = base.length();
for(String str : strs) {
if(str.equals(base)){
continue;
}
if(str.equals("") || str.charAt(0) != str.charAt(0)){
return "";
}
int index = 0;
int count = 0;
while(index < base.length() && index < str.length()) {
if(str.charAt(index) == base.charAt(index)){
count++;
index++;
}else {
break;
}
}
res = Math.min(count,res);
}
return base.substring(0,res);
}
|
# 两数组交集
349. 两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
直接用 HashSet 解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set1 = new HashSet<>();
HashSet<Integer> set2 = new HashSet<>();
for(int i : nums1) {
set1.add(i);
}
for (int i : nums2){
if(set1.contains(i)) {
set2.add(i);
}
}
int [] res = new int[set2.size()];
int index = 0;
for(int i : set2) {
res[index++] = i;
}
return res;
}
|
