LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

题意

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

例子:

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

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

思路

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

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

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

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

阅读更多

LeetCode双周赛-第七场

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

第一题:

题意

一个只有一行的键盘,随机有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;
}
}

第二题:

题意

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

阅读更多

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

数组中第k大的元素

此文为 LeetCode 215. Kth Largest Element in an Array 的题解。

题意

在一个未排序的数组中,寻找第k大的元素。

分析

这个题目其实很简单,但是踩了一些坑,所以记录一下:

首先是用PriorityQueue,然后poll k次即可(5 ms,37.5 MB)。但是属于API caller,略去不表。

其次就是堆排序,很久不写了,第一次把堆排序写成了选择排序,导致时间很长:101 ms,37.2 MB。

后来复习了下堆排序,写出来了(2 ms,36.6 MB):

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
// from https://www.robberphex.com/kth-largest-element-in-an-array/
// 2 ms,36.6 MB
class Solution {
// 调整current子树,将其整理成最小堆
private void adjust(int[] nums, int current, int length) {
// 将堆顶取出来
int num = nums[current];
// 将子树中比顶大的数依次弹上来
for (int i = current * 2 + 1; i < length; i = 2 * i + 1) {
if (i + 1 < length && nums[i + 1] < nums[i]) {
i++;
}
if (nums[i] < num) {
nums[current] = nums[i];
current = i;
} else {
break;
}
}
// 不能弹,则将该数放到对应的位置
nums[current] = num;
}

public int findKthLargest(int[] nums, int k) {
for (int i = (nums.length - 1) / 2; i >= 0; i--) {
// 从第一个非叶子结点开始,构建堆
adjust(nums, i, nums.length);
}
for (int i = 1; i <= nums.length - k+1; i++) {
// 将堆顶交换到数组尾部
int tmp = nums[nums.length - i];
nums[nums.length - i] = nums[0];
nums[0] = tmp;
// 然后继续构建堆
adjust(nums, 0, nums.length - i);
}

return nums[k - 1];
}
}

当然,很容易想到,最优解就是快速选择算法:快速排序划分区间的时候,忽略所有不包含k的区间即可(1 ms,37.3 MB):

阅读更多

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中。

阅读更多

LeetCode 1103:Distribute Candies to People

本文为LeetCode 1103:Distribute Candies to People的题解。

题意

我们用下面的方法给num_people个人分发一些糖果:

我们给第一个人1块糖,给第二个人2块糖,以此类推,直到我们给最后一个人n块糖。

然后,我们回到开始,给第一个人n + 1块糖,给第二个人n + 2块糖,以此类推,直到我们给最后一个人2 * n块糖。

这个过程不断重复(当重新走到队首的时候,我们每次比上次多给n个糖果),直到糖果分配结束。最后一个人将收到我们所有剩余的糖果。

返回一个数组(长度为num_people),该数组表示最终每个人得到的糖果数量。

题解

首先我们考虑能完整的分发几轮。

由于分发数量总体上就是从1到n*num_people的等差序列,n符合如下不等式:

阅读更多

LeetCode题解:Path In Zigzag Labelled Binary Tree

本文为LeetCode 1104. Path In Zigzag Labelled Binary Tree 的题解。

题目描述

一棵无穷的二叉树,每个节点都编号(label)了:对于奇数层(第1、3、5等层),从左向右编号。对于偶数层,从右向左编号。但是每层的编号还是最小2^(level-1),最大2^level-1

如图:

给你一个编号(label),输出从顶层到该节点经过的节点编号。

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

阅读更多