我的思路：双指针
建立两个指针 i，j，分别指向 s 和 t
- 当
s.charAt(i) == t.charAt(j) 时，两个指针均向后移动一位
- 否则，只将 j 后移一位
循环结束后，如果 i 等于 s 的长度，说明指针遍历过整个字符串 s，均找到 t 中与之相等的字母，故返回 true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
while (i < s.length() && j < t.length()) {
if (s.charAt(i) == t.charAt(j)) {
i++;
j++;
} else {
j++;
}
}
if (i == s.length()) return true;
else return false;
}
}
|
更快的方法
遍历 s 中的字符，用 t.indexOf() 方法查询字符串 t 中是否含有该字符
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean isSubsequence(String s, String t) {
int index = -1;
for (char c : s.toCharArray()){
index = t.indexOf(c, index+1);
if (index == -1) return false;
}
return true;
}
}
|
我的思路：递归（失败）
求出 n 的下一个数 next ，带入函数 isHappy(next)
存在问题：无法确定返回 false 的条件，如果结果是 true 则可直接返回，是 false 将出现 StackOverflowError
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public boolean isHappy(int n) {
int res = 0;
while (n > 0) {
int temp = n % 10;
res += (temp * temp);
n /= 10;
}
if (res == 1) return true;
else return isHappy(res);
}
}
|
官方思路一：HashSet检测循环
直接贴代码！
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 {
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = getNext(n);
}
return n == 1;
}
}
|
官方思路二：快慢指针检测循环
直接贴代码！
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
| class Solution {
public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
int slowRunner = n;
int fastRunner = getNext(n);
while (fastRunner != 1 && slowRunner != fastRunner) {
slowRunner = getNext(slowRunner);
fastRunner = getNext(getNext(fastRunner));
}
return fastRunner == 1;
}
}
|
思路
设置一个哨兵节点，哨兵节点的 next 指向头节点
设置一个 pre 节点，记录当前节点 cur 的上一个节点
- 当
cur.val == val：pre.next = cur.next
- 否则：
pre = cur
cur 指向下一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode sentinel = new ListNode(0);
sentinel.next = head;
ListNode pre = sentinel, cur = head;
while (cur != null) {
if (cur.val == val) pre.next = cur.next;
else pre = cur;
cur = cur.next;
}
return sentinel.next;
}
}
|
思路
如求10之内的质数，首先列出2~N-1的所有数，如果当前数为质数，则其倍数就是质数，如
第一个质数为2，在2上画圈，其倍数4/6/8不是质数，划掉4/6/8，继续遍历
下一个质数为3，在3上画圈，其倍数6/9不是质数，划掉6/9，继续遍历
下一个质数为5，在5上画圈，没有倍数，继续遍历
下一个质数为7，在7上画圈，没有倍数，继续遍历。
最后再次遍历整个数组，画圈的数字就是质数，即2,3,5,7
转换为代码就是如果需要求<n的所有质数个数，则创建一个长度为n的整数数组，所有元素值变为1，1表示对应的索引值为质数，0表示对应的索引值为非质数。从2开始遍历，如果当前数字值为1，则获取其所有倍数，将元素值变为0（标记为非质数）。遍历完成后再次遍历数组，从2开始，记录元素为1的个数，即为对应的质数个数。
作者：mmmmmJCY
链接：https://leetcode-cn.com/problems/count-primes/solution/e-la-duo-sai-shai-fa-qiu-zhi-shu-java-by-zxy0917/
来源：力扣（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
| public int countPrimes(int n) {
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = 1;
}
for (int i = 2; i < n; i++) {
if (nums[i] == 1) {
for (int j = 2; i * j < n; j++) {
nums[i * j] = 0;
}
}
}
int res = 0;
for (int i = 2; i < n; i++) {
if (nums[i] == 1)
res++;
}
return res;
}
|
