LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

题意

每层括号里面的东西需要反转一次。即在在偶数层括号里面的字符是正序的,在奇数层括号里面的字符是逆序的。然后拼成结果。

例子:

“(abcd)”
反转之后就是:
cdba

“(u(love)i)”
love不反转,u,love,i三个反转,答案为:
iloveu

思路

网上有人直接用栈存储,每一个元素代表当前层级括号中的字符串,如果遇到括号关闭,将当前层级字符串反转再append到上一级的字符串中。

但是,括号层级一多,字符串反转的次数就非常多了。而且很多反转都是没有必要的。

其实直接递归就好,或者说分治:

每个括号内部都算作独立的子问题,如果正序,直接逐个append,逆序则反向append;如果遇到括号,则继续分治。

阅读更多

LeetCode 23. Merge k Sorted Lists

LeetCode 23. Merge k Sorted Lists

题意

合并k个链表,每个链表内部都是排好序的(从小到大),但是k个链表之间是无序的。

思路

首先,最简单的办法就是链表之间选择排序,取第一个链表的第一个节点插到结果中。然后如果链表还有节点,放回到数组中。如此往复,直到没有节点剩余。

时间复杂度O(k*n),空间复杂度O(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
33
34
35
36
37
38
39
40
41
42
43
// from https://www.robberphex.com/merge-k-sorted-lists/
// Runtime: 420 ms Memory Usage: 38.6 MB
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
ListNode head = null;
int hi = -1;
// 选出一个head
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null && (head == null || lists[i].val < head.val)) {
head = lists[i];
hi = i;
}
}

if (head == null)
return head;
lists[hi] = lists[hi].next;
ListNode prev = head;

while (true) {
ListNode cur = null;
int ci = 0;
// 选出最小的node
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null && (cur == null || lists[i].val < cur.val)) {
cur = lists[i];
ci = i;
}
}
if (cur == null)
break;
// 插入到链表中
lists[ci] = lists[ci].next;
prev.next = cur;
cur.next = null;
prev = cur;
}

return head;
}
}

显然,多次对k个链表排序是很浪费的,这时候就想到了堆,只需要将k个链表构成一个堆即可。时间复杂度O(N*log(k)),空间复杂度O(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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// from https://www.robberphex.com/merge-k-sorted-lists/
// Runtime: 2 ms Memory Usage: 43.2 MB
class Solution {
private int len;

public void adjust(ListNode[] lists, int startIndex) {
ListNode start = lists[startIndex];
int currIndex = startIndex;
while (currIndex < len) {
int nextIndex = currIndex * 2 + 1;
if (nextIndex + 1 < len && lists[nextIndex + 1].val < lists[nextIndex].val) {
nextIndex += 1;
}
if (nextIndex < len && start.val > lists[nextIndex].val) {
lists[currIndex] = lists[nextIndex];
currIndex = nextIndex;
} else {
break;
}
}
lists[currIndex] = start;
}

public ListNode mergeKLists(ListNode[] lists) {
len = lists.length;
// 剔除null
for (int i = 0; i < len; ) {
if (lists[i] == null) {
lists[i] = lists[--len];
} else {
i++;
}
}
ListNode head = null;
ListNode tail = null;
// i==0时的调整交给下面的while循环
for (int i = len / 2; i > 0; i--) {
adjust(lists, i);
}
while (len > 0) {
adjust(lists, 0);
if (tail == null) {
head = tail = lists[0];
} else {
tail.next = lists[0];
tail = tail.next;
}
if (tail.next != null) {
lists[0] = tail.next;
} else {
lists[0] = lists[len - 1];
len--;
}
tail.next = null;
}
return head;
}
}
阅读更多

Codeforces Round #575 B. Odd Sum Segments

题目:https://codeforces.com/contest/1196/problem/B

将长度为n的数组a划分成k个非空组,确保所有的组内之和都为奇数。

本来以为是要输出所有的可行解,所以想了一个O(n^k)的解法,结果超时。后来发现只需要输出一组解即可。

首先计算数组中奇数个数,如果奇数个数等于k,则每组一个奇数,满足需求。

如果奇数个数比k大奇数个,则这些奇数一定会导致一个组的和变成偶数,不满足。如果奇数个数比k大偶数个,则满足要求。

然后就是如何构造序列的问题了。

首先,对于前k-1个序列,每个序列仅包含一个奇数,最后剩下的一个组包含剩下的数字,很容易可以想到,最后一个组一定包含了奇数个奇数。

另外,java.util.Scanner有性能问题,还是使用自己实现的FastReader

代码如下:

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
private static void process(int[] arr, int segs) {
int[] indexes = new int[arr.length];
int index = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] % 2 == 1) {
indexes[index++] = i;
}
}
if (index < segs || (index - segs) % 2 == 1) {
System.out.println("NO");
return;
}
System.out.println("YES");
for (int i = 0; i < segs - 1; i++) {
System.out.print(indexes[i] + 1);
System.out.print(" ");
}
System.out.println(arr.length);
}

public static void main(String[] args) {
FastReader scn=new FastReader();
int tn = scn.nextInt();
while (tn-- > 0) {
int n = scn.nextInt();
int seg = scn.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scn.nextInt();
}
process(arr, seg);
}
}

static class FastReader {
BufferedReader br;
StringTokenizer st;

public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}

String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}
阅读更多