双指针
1.字符串删减
3768. 字符串删减 - AcWing题库
给定一个由 n 个小写字母构成的字符串。
现在，需要删掉其中的一些字母，使得字符串中不存在连续三个或三个以上的 x。
请问，最少需要删掉多少个字母？
如果字符串本来就不存在连续的三个或三个以上 x，则无需删掉任何字母。
输入格式
第一行包含整数 n。
第二行包含一个长度为 n 的由小写字母构成的字符串。
输出格式
输出最少需要删掉的字母个数。
数据范围
3≤n≤100
输入样例：
输出样例：
代码
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
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
String s = in.readLine();
int res = 0;
int temp = 0;
for (char c : s.toCharArray()) {
if (c != 'x') {
temp = 0;
} else {
temp++;
if (temp > 2) {
res++;
}
}
}
System.out.println(res);
}
}
|
2.日志统计
1238. 日志统计 - AcWing题库
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。
其中每一行的格式是：
ts id  
表示在 ts时刻编号 id的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。
具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。
给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式
第一行包含三个整数 N,D,K。
以下 N 行每行一条日志，包含两个整数 ts 和 id。
输出格式
按从小到大的顺序输出热帖 id。
每个 id 占一行。
数据范围
1≤K≤N≤10e5
0≤ts,id≤10e5
1≤D≤10000
输入样例：
1
2
3
4
5
6
7
8
| 7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
|
输出样例：
代码
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] s = in.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int d = Integer.parseInt(s[1]);
int k = Integer.parseInt(s[2]);
int[] nums = new int[100010];
int[][] read = new int[n][2];
for (int i = 0; i < n; i++) {
s = in.readLine().split(" ");
int time = Integer.parseInt(s[0]);
int id = Integer.parseInt(s[1]);
read[i][0] = time;
read[i][1] = id;
}
Arrays.sort(read,(o1, o2) -> o1[0]-o2[0]);
HashSet<Integer> set = new HashSet<>();
int l = 0;
int r = 0;
while(r < read.length) {
while (r < read.length&&read[r][0] - read[l][0] < d) {
nums[read[r][1]]++;
if (nums[read[r][1]] >= k) {
set.add(read[r][1]);
}
r++;
}
nums[read[l][1]]--;
l++;
}
Integer[] integers = new Integer[0];
Integer[] ints = set.toArray(integers);
Arrays.sort(ints);
for (int t : ints) {
System.out.println(t);
}
}
}
|
3.完全二叉树的权值
1240. 完全二叉树的权值 - AcWing题库
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1,A2,⋅⋅⋅AN
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？
如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 11。
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋅⋅⋅AN
输出格式
输出一个整数代表答案。
数据范围
1≤N≤10e5
−10e5≤Ai≤10e5
输入样例：
输出样例：
代码
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
40
41
42
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
String[] s = in.readLine().split(" ");
int[] nums = new int[n + 1];
for (int i = 0; i < n; i++) {
nums[i + 1] = Integer.parseInt(s[i]);
}
long res = 1;
long max = nums[1];
long lay = 1;
int l = 1;
int r = 0;
while (r <= n) {
long temp = 0;
while (r <= n && r - l < (1 << (lay - 1))) {
temp += nums[r];
r++;
}
if (temp > max) {
max = temp;
res = lay;
}
lay++;
l=r;
}
System.out.println(res);
}
}
|
