[toc]
第一题双指针
剑指 Offer II 018. 有效的回文 - 力扣（LeetCode）
双指针，处理字符串比较麻烦
反正都是O(n)，不追求空间的话，用收集字符后反转再比较更块
双指针做法：
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
| class Solution {
public boolean isPalindrome(String s) {
int left = 0, right = s.length()-1;
s = s.toUpperCase();
while(left <= right && left <s.length() && !Character.isDigit(s.charAt(left)) && !Character.isAlphabetic(s.charAt(left))) {
left++;
}
while(left <= right && right >=0 && !Character.isDigit(s.charAt(right)) && !Character.isAlphabetic(s.charAt(right))) {
right--;
}
while(left <right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
while(left <= right && left <s.length() && !Character.isDigit(s.charAt(left)) && !Character.isAlphabetic(s.charAt(left))) {
left++;
}
while(left <= right && right >=0 && !Character.isDigit(s.charAt(right)) && !Character.isAlphabetic(s.charAt(right))) {
right--;
}
}
return true;
}
}
|
字符串翻转做法：
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean isPalindrome(String s) {
int left = 0, right = s.length()-1;
s = s.toUpperCase();
StringBuilder sb =new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
sb.append(c);
}
}
return sb.toString().equals(sb.reverse().toString());
}
}
|
注意Character.isLetterOrDigit©就是判断是否是字母或者数字的意思
注意sb.reverse()会改变自身
第二题博弈论，记忆化搜索
1140. 石子游戏 II - 力扣（LeetCode）
这种博弈论问题，请直接dfs+记忆化搜索好吧，别纠结动态规划了
而且直接考虑根据当前人的不同，选取最大或者最小值，不要考虑那个简化正负的那种策略。
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
| class Solution {
Integer[][][] dp;
public int stoneGameII(int[] piles) {
dp = new Integer[2][piles.length][101];
return dfs(0, 1, piles, true);
}
int dfs(int index, int m, int[] piles, boolean isAlice) {
if (index == piles.length) {
return 0;
}
if (dp[isAlice ? 0 : 1][index][m] != null) {
return dp[isAlice ? 0 : 1][index][m];
}
int needDfsRes = (isAlice ? Integer.MIN_VALUE :
Integer.MAX_VALUE);
int sum = 0;
for (int i = index;i<index + 2*m && i < piles.length;i++) {
int dfsRes = dfs(i+1, Math.max(i - index + 1, m),
piles, !isAlice);
if (isAlice) {
sum += piles[i];
needDfsRes = Math.max(needDfsRes, sum + dfsRes);
} else {
needDfsRes = Math.min(needDfsRes, dfsRes);
}
}
dp[isAlice ? 0 : 1][index][m] = needDfsRes;
return needDfsRes;
}
}
|
第三题二分查找
540. 有序数组中的单一元素 - 力扣（LeetCode）
要求O(logn)，显然不能用异或的那个方法了
既然是有序的，说明相同的2个数字一定是连在一起的
那么在目标左边的连体数字，一定是偶数索引开头
目标右边的连体数字，一定是奇数索引开头
搞定
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
| class Solution {
public int singleNonDuplicate(int[] nums) {
int left = 0, right = nums.length;
while(left < right) {
int mid = left + (right - left)/2;
int num1 = nums[mid];
int index1 = -1;
if (mid-1 >=0 && nums[mid-1] == num1) {
index1 = mid-1;
} else if (mid+1<nums.length && nums[mid+1] == num1) {
index1 = mid;
}
if (index1 == -1) {
return num1;
}
if (index1 %2 == 0) {
left = mid+1;
} else {
right = mid;
}
}
return -1;
}
}
|