LeetCode 周赛 311

第一题 2413. Smallest Even Multiple

给你一个正整数 n ,返回 2 和 n 的最小公倍数(正整数)。

显而易见的:

1
2
3
4
5
6
7
func smallestEvenMultiple(n int) int {
if n%2==1{
return n*2
}else{
return n
}
}

第二题 2414. Length of the Longest Alphabetical Continuous Substring

最近恰好做过dp的题目,所以立马dp:

  • 状态定义为 下标i -> 以i结尾的string中,字母序连续的字符串最大长度
  • 状态转移 s[i]和s[i-1]连续,那么在前面基础上+1,如果不连续,则置为1

最后,遍历i,拿最大长度即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func longestContinuousSubstring(s string) int {
dp := make([]int, len(s))
dp[0] = 1
for i := 1; i < len(s); i++ {
if s[i] == s[i-1]+1 {
dp[i] = dp[i-1] + 1
} else {
dp[i] = 1
}
}
res := 1
for i := 0; i < len(dp); i++ {
if res < dp[i] {
res = dp[i]
}
}
return res
}
阅读更多

LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

题意

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

例子:

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

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

思路

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

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

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

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

阅读更多

LeetCode双周赛-第七场

总是抽不出时间参加LeetCode周日上午的周赛,最近发现有周六晚上10点半的双周赛,就参加了两把。这次是第七场

第一题:Single-Row Keyboard

题意

一个只有一行的键盘,随机有26个字母,给定单词,先移动到对应的单词,然后输入第一个字母,再移动,再输入第二个字母,以此类推。问输入这个单词需要移动多长。

题解

题目难度easy,直接模拟就好:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int calculateTime(String keyboard, String word) {
int res = 0;
int index = 0;
int[] map = new int[128];
for (int i = 0; i < keyboard.length(); i++) {
map[keyboard.charAt(i)] = i;
}
for (char ch : word.toCharArray()) {
int newIndex = map[ch];
res += Math.abs(newIndex - index);
index = newIndex;
}
return res;
}
}

第二题:Design File System

题意

设计文件系统,有两种操作:create、get。

阅读更多

(据说)华为的一道面试题

刷微博,看到一道面试题:

先说一下思路

默认题意为不能取重复的数字

总体来说,就是从可行解空间[1,1]~[20,20]中,逐步过滤,找到最终答案的过程。说一下过滤步骤:

  1. 首先A不确定两个数字,所以两数之和sum满足:4<=sum<=38
  2. 其次B也不确定,所以两数之积的分解方式可能有多种(本来以为可以用质因子个数>2来判别的,但是后来发现还要考虑两数在1到20之间)
  3. A知道数字了,所以sum的所有分解方式中,只有一个是让B不能确定的,即i+j=sum,切i*j的分解方式不止一种
  4. 这一步比较难:B知道乘积prod,对于prod分解的所有可能,都能得到其和sum,如果sum的所有分解中,只有一个是让B不能确定的;而且prod的分解只有一个是满足此关系的。则当前的prod,以及对应的让B不能确定的prod分解,即为所求解。

1和2很容易理解。3的话,如果sum的诸多分解方式中,都能被B确定,即ij只能唯一分解,那B就不会说不知道数字了。如果sum的诸多分解方式中,有多个不能被B确定,那A在第三步就不能确定数字了,因为A不确定B是在哪一组ij中。

4,B知道乘积prod,假设可以分解为 I_n, J_n 。对于每一组 I_n, J_n:

和为sum=I_n+J_n,且A知道这个sum,这时B推测sum可以分解为i_n+j_n:
  由于3的结论,所以sum对应的i_n*j_n的分解不唯一的情况只有一个
  如果sum对应的i_n*j_n分解不唯一的情况为0个,那么B在第二步就可以猜出
  如果sum对应的i_n*j_n分解不唯一的情况多于1个,那么A在第三步就猜不出来了
在所有的 I_n, J_n 中,满足如上条件的只有一个
如果都满足上述条件的多于一个,那么B在最后一步就无法确定哪一组I_n,J_n是正确答案了

当然,第四步也是在第三步的结果上过滤的

阅读更多

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;
}
}
}
阅读更多

LeetCode 25. Reverse Nodes in k-Group

本文为LeetCode 25. Reverse Nodes in k-Group的题解。

题意

给定一个链表,k个一组反转链表。

k 是一个正数,且小于链表长度。如果按照k个一组,最后剩下的不组k,则不反转剩下的元素。

例子:

对于链表: 1->2->3->4->5

k = 2, 应返回: 2->1->4->3->5

k = 3, 应返回: 3->2->1->4->5

注意:

  • 只允许O(1)的空间复杂度。
  • 不可以改变节点的值。
阅读更多

LeetCode:991. Broken Calculator

此文为LeetCode 991. Broken Calculator的题解。

题意

有一台坏掉的计算器,能够显示一个数字,我们可以对这个数字做两个操作:

  • 二: 将显示的数字乘以2, 或者;
  • 减一: 将显示的数字减1.

初始时,计算器显示数字 X.

返回要得到数字Y需要的最小操作次数。

题解

如果X>Y,则只能执行减一操作。否则,如果Y是奇数,则上一步操作一定是X减一;如果Y是偶数,则上一步操作只能是X乘二

只需要通过上述规则,由Y反推X即可。

代码

阅读更多

LeetCode:1106. Parsing A Boolean Expression

本文是LeetCode 1106. Parsing A Boolean Expression的题解。

题意

给定一个String类型的布尔表达式expression,返回一个求值的结果。

表达式可以是:

  • "t", 表示为 True;
  • "f", 表示为 False;
  • "!(expr)", 将内部的 expr 结果取反;
  • "&(expr1,expr2,...)", 将内部的expr1, expr2, ...求与;
  • "|(expr1,expr2,...)", 将内部的expr1, expr2, ...求或。

题解

直接递归解释表达式就好,每层负责解释上述的一个规则就可以。

这儿有一个优化点:实现表达式惰性求值。

代码

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
/**
* https://www.robberphex.com/parsing-a-boolean-expression/
* Runtime: 1 ms, faster than 100.00% of Java online submissions for Parsing A Boolean Expression.
* Memory Usage: 38 MB, less than 100.00% of Java online submissions for Parsing A Boolean Expression.
*/
class Solution {
class Result {
/**
* 表达式结果
*/
boolean res;
/**
* 下次解析的起始位置
*/
int end;

Result(boolean res, int end) {
this.res = res;
this.end = end;
}
}

private Result parseBoolExpr(String expression, int start) {
if (expression.charAt(start) == 'f') {
return new Result(false, start + 1);
} else if (expression.charAt(start) == 't') {
return new Result(true, start + 1);
} else if (expression.charAt(start) == '!') {
Result result = parseBoolExpr(expression, start + 2);
result.res = !result.res;
result.end++;
return result;
} else if (expression.charAt(start) == '&') {
Result finalResult = new Result(true, 0), result;
start++;
do {
result = parseBoolExpr(expression, start + 1);
if (!result.res) {
// 在这儿可以实现惰性求值
finalResult.res = false;
}
start = result.end;
// 如果是逗号,继续解析
} while (expression.charAt(result.end) == ',');
finalResult.end = result.end + 1;
return finalResult;
} else if (expression.charAt(start) == '|') {
Result finalResult = new Result(false, 0), result;
start++;
do {
result = parseBoolExpr(expression, start + 1);
if (result.res) {
// 在这儿可以实现惰性求值
finalResult.res = true;
}
start = result.end;
} while (expression.charAt(result.end) == ',');
finalResult.end = result.end + 1;
return finalResult;
} else {
throw new RuntimeException();
}
}

public boolean parseBoolExpr(String expression) {
return parseBoolExpr(expression, 0).res;
}

public static void main(String[] args) {
boolean res = new Solution().parseBoolExpr("!(&(&(!(&(f)),&(t),|(f,f,t)),&(t),&(t,t,f)))");
System.out.println(res);
// 输出 true
}
}
阅读更多

LeetCode:103. Binary Tree Zigzag Level Order Traversal

本文为LeetCode:103. Binary Tree Zigzag Level Order Traversal的题解。

题意

一颗给定的二叉树,返回节点值的之子形的便利结果。即,从左到右,然后下一级别是从右到左,如此交替。

例如:

给定二叉树:[3,9,20,null,null,15,7]

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

程序将会返回之字形遍历顺序:

1
2
3
4
5
[
[3],
[20,9],
[15,7]
]

题解

对于第一层遍历,从左到右,添加到一个stack中;对于第二层遍历,pop出来的顺序是从右到左,所以要额外考虑先添加right子节点、再添加left子节点到stack中。

阅读更多