思路：HashMap
将 pattern 中的字母和 str 中的单词使用 HashMap 进行一一映射
注意：需要对 pattern 和 str 进行双向映射（也可以判断 map 中是否已经包含了 value）
如果只是完成了 pattern -> str 的映射，则下例仍会判断错误
1
2
| pattern = "abba"
str = "dog dog dog dog"
|
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
| class Solution {
public boolean wordPattern(String pattern, String str) {
return wordPatternHelper1(pattern, str) && wordPatternHelper2(pattern, str);
}
public boolean wordPatternHelper1(String pattern, String str) {
HashMap<String, Character> map = new HashMap<>();
String[] strs = str.split(" ");
if (strs.length != pattern.length()) return false;
for (int i = 0; i < strs.length; i++) {
if (!map.containsKey(strs[i])) {
map.put(strs[i],pattern.charAt(i));
} else if (!map.get(strs[i]).equals(pattern.charAt(i))) {
return false;
}
}
return true;
}
public boolean wordPatternHelper2(String pattern, String str) {
HashMap<Character, String> map = new HashMap<>();
String[] strs = str.split(" ");
if (strs.length != pattern.length()) return false;
for (int i = 0; i < strs.length; i++) {
if (!map.containsKey(pattern.charAt(i))) {
map.put(pattern.charAt(i),strs[i]);
} else if (!map.get(pattern.charAt(i)).equals(strs[i])) {
return false;
}
}
return true;
}
}
|
我的思路：递归
- 当
n < 3 时，我必赢
- 当
n > 3 时，canWinNim(n - 1) 、canWinNim(n - 2) 、canWinNim(n - 3) 分别返回我拿一块、拿两块、拿三块后对方是否会获胜
1
2
3
4
5
6
| class Solution {
public boolean canWinNim(int n) {
if (n <= 3) return true;
return !(canWinNim(n - 1) && canWinNim(n - 2) && canWinNim(n - 3));
}
}
|
思路没问题，但是在执行过程中，当 n > 43 时，会出现超时的问题！
大佬思路
1
2
3
| public boolean canWinNim(int n) {
return (n % 4 != 0);
}
|
我的思路
直接暴力遍历数组的子区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class NumArray {
int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
public int sumRange(int i, int j) {
int sum = 0;
for (int k = i; k <=j; k++) {
sum += nums[k];
}
return sum;
}
}
|
这样做有可能会产生超时错误，且题目中强调了 “会多次调用 sumRange ” 方法，故我们应该考虑更高率的求和方法
更好的思路
可以改用 sum数组 来保存前 n 位的数组中元素的和，这样调用 sumRange 方法时可以直接返回 sum[j + 1] - sum[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class NumArray {
private int[] sums;
public NumArray(int[] nums) {
sums = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
sums[i + 1] = sums[i] + nums[i];
}
}
public int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
}
|
思路一：递归/迭代
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public boolean isPowerOfThree(int n) {
if (n == 0) return false;
if (n == 1 || n == 3) return true;
if (n % 3 == 0) {
return isPowerOfThree(n / 3);
} else {
return false;
}
}
}
|
思路二：取余
在整型范围内，3 的最大幂次方是 1162261467，若 n 能被它整除，则说明 n 是 3 的幂
1
2
3
4
5
| class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}
|
解题思路
本题为基础双指针法交换前后元音元素；
一般遇见字符串问题，能转成字符数组就尽量转(方便)；
转换成数组后，分别定义前后两个索引指针用 while 依次遍历数组；
定义 isVowel() 方法将非元音元素返回给判断处，然后移动指针直到符合元音的位置，然后 tmp 进行交换即可；
最后扫描完数组后，一定要在返回的时候再转成字符串 String 输出。
作者：Jasion_han
链接：https://leetcode-cn.com/problems/reverse-vowels-of-a-string/solution/20200320345easy-by-jasion_han-r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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
| class Solution {
public String reverseVowels(String s) {
if (s == null || s.length() == 0) {
return s;
}
String vowels = "aeiouAEIOU";
char[] chars = s.toCharArray();
int start = 0;
int end = s.length() - 1;
while (start < end) {
while (start < end && !vowels.contains(chars[start] + "")) {
start++;
}
while (start < end && !vowels.contains(chars[end] + "")) {
end--;
}
swap(chars, start, end);
start++;
end--;
}
return new String(chars);
}
private void swap(char[] chars, int start, int end) {
char temp = chars[start];
chars[start] = chars[end];
chars[end] = temp;
}
}
|
