LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

题意

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

例子:

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

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

思路

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

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

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

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

阅读更多

从fastjson漏洞谈防御式编程

最近,fastjson又爆出一个漏洞,在解析特殊字符的时候,直接OOM:

首先分析一下整体流程:

在scanString时,会直接读取两个字符:

而在next方法中,每次读取都会将bp的值加一(即使没有从输入中读取字符):

1
2
3
4
5
6
public final char next() {
int index = ++bp;
return ch = (index >= this.len ? //
EOI //
: text.charAt(index));
}

在处理完x之后,继续解析剩下的字符。由于没有更多字符了,所以读到的总是EOI,然后进入如下分支:

1
2
3
4
5
6
7
if (ch == EOI) {
if (!isEOF()) {
putChar((char) EOI);
continue;
}
throw new JSONException("unclosed string : " + ch);
}

本来到这一步,isEOF应该是true了,但是isEOF是这样的:

阅读更多

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。

阅读更多

AsyncHttpClient对Cookie的控制太不灵活了

业务上遇到一个坑,java服务代理了一个接口到upstream,原样转发请求数据和头部。但是代理之后的结果总是莫名其妙的多了一个Cookie,比如是Set-Cookie: ticket=t1

业务上用一个静态的AsyncHttpClient来做代理,也没有做特殊处理,基本上就是如下的代码逻辑:

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
import org.asynchttpclient.*;

import java.io.IOException;
import java.util.concurrent.ExecutionException;

class Main {
private static AsyncHttpClient httpClient;

static {
DefaultAsyncHttpClientConfig.Builder builder = new DefaultAsyncHttpClientConfig.Builder();

httpClient = new DefaultAsyncHttpClient(builder.build());
}

public static void main(String[] args) throws ExecutionException, InterruptedException, IOException {
BoundRequestBuilder builder = httpClient.prepareGet(
"https://httpbin.org/cookies/set/ticket/val1"
);
builder.resetCookies();
builder.execute().get();

BoundRequestBuilder builder2 = httpClient.prepareGet(
"https://httpbin.org/cookies"
);
builder2.resetCookies();
Response res2 = builder2.execute().get();
System.out.println(res2.getResponseBody());
}
}

当时为了防止Cookie问题,特意加上了resetCookies。

首先是查看ticket Cookie的来源,发现upstream在客户端请求带上ticket Cookie的时候,会返回Set-Cookie: ticket=<val> 这个应该就是多余Cookie的来源了。

但是,即使客户端不带Cookie,java服务这边也会返回Set-Cookie字段。这个问题,排查之后发现问题在于resetCookies只能reset本次请求的Cookie,而客户端的Cookie,则不能清除。

即,某次请求,upstream返回了Set-Cookie: ticket=val,那么,以后的代理请求中,都会带上这个Cookie,那么最终用户也会拿到Set-Cookie字段……

从上述代码的运行结果也可以看出:

1
2
3
4
5
{
"cookies": {
"ticket": "val1"
}
}

即,async-http-client没有一个request级别的Cookie控制,只能全局控制Cookie存储。这个问题也有人反馈给了async-http-client

阅读更多

如何恢复Firefox会话中的url

昨天升级到了macOS Catalina 10.15 Beta (19A526h),发现Firefox无法打开了…

不得以,只能看下如何在不打开Firefox的情况下,将会话中打开的url拿出来。

首先,得找到Profile的问题,参考 https://support.mozilla.org/en-US/kb/profiles-where-firefox-stores-user-data 找到位置,将Profile目录下的sessionstore-backups文件夹拷出来。

其中,recovery.jsonlz4文件即为会话的恢复信息,但是这个文件不是标准的lz4压缩文件,得使用特殊的工具来解压,在 https://github.com/avih/dejsonlz4 下载dejsonlz4源码,编译。

通过命令将jsonlz4解压成json:

./dejsonlz4 /path/to/recovery.jsonlz4 /path/to/output/recovery.json

接下来就是探索这个recovery.json的内容了,很简单:

  • jq keys查看这个json文件中的顶级key,比如cat recovery.json | jq keys
  • 查看某一个节点可以通过.来引用,比如jq '.[0].entrys'就是查看第零个元素中的entrys属性

最终,可以通过如下命令输出会话中所有的url:

1
jq -r '.windows[].tabs[].entries[].url' recovery.json 
阅读更多

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

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

先说一下思路

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

总体来说,就是从可行解空间[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;
}
}
}
阅读更多

数组中第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):

阅读更多

特工355(Agent 355)

特工355(1780年后去世)是美国革命期间女性间谍的代名,是库尔珀组(Culper Ring)的一部分。 特工355是美国的第一批间谍之一,真实身份未知。355这个数字是库尔珀组中的加密系统用来表示“女士”的数字。

生平

在库尔珀组的公文中,唯一直接提及特工355的是亚伯拉罕·伍德赫尔乔治·华盛顿将军的信。伍德赫尔形容她是“对这封信有帮助的人”。

特工355的真实身份仍然未知,但有关她的一些事实似乎很清楚。作为间谍,她在美国独立战争期间与美国爱国者(或称美国辉格党,革命党)合作。她本会被伍德赫尔招募进间谍组。355这个代码表明她可能具有“某种程度的社会突出性”。她可能生活在纽约市,并且在某些时候与约翰·安德烈少校贝内迪克特·阿诺德有过接触。 一个可能是特工355的人是伍德赫尔的邻居安娜·斯特朗(Anna Strong)。另一个说法是,特工355可能是罗伯特汤森事实上的妻子。有传说表明汤森爱上了特工355。约翰·伯克和安德里亚·梅耶尔通过间接证据证明她可能与约翰·安德烈少校和本杰明·塔尔马奇关系密切,从而保护伍德赫尔不被指控为间谍,这为355参与间谍活动提出了不同的理由。特工355的其他可能候选人包括Sarah Horton Townsend和Elizabeth Burgin。

偶尔也有一些说法,说根本没有特工355,355仅仅代指一名知道有用信息的女人,并没有与特工组正式关联。代码355仅仅表示“一个女人”,而不是一个女性特工。

探员355被认为是揭露阿诺德和逮捕少校约翰·安德烈的主要角色,后者在纽约塔潘被绞死。她可能是一个著名的保皇派(或称托利党)家庭的成员,这个家庭背景使她很容易接近英国指挥官。

1780年,本尼迪克特·阿诺德(Benedict Arnold)前往保皇派那里,这时特工355被逮捕。她被囚禁在泽西号军舰上,这是一艘监狱船,在那里她可能生下了一个名叫小罗伯特·汤森的男孩。她后来死在监狱船上。然而,亚历山大·罗斯不同意这种说法,他说“女性没有被关在监狱船上”,“没有任何出生的记录”。这强化了355号特工可能是安娜·斯特朗的观点,因为她的丈夫塞拉·斯特朗被囚禁在泽西岛,她应该可以给丈夫带食物。她出现在船上使人们传言特工355被囚禁在那里。

在流行文化中

特工355已经成为通俗小说的一部分。她是《Y:世上最后一个男人》中一个主要角色。她也是现代间谍355的灵感来源,并收录在《刺客信条3》的游戏内历史事实数据库中,她的信息对于帮助主角发现要捕获的英国阴谋至关重要。

在电视剧《逆转奇兵》(Turn: Washington’s Spies)中,特工355是一位名叫阿比盖尔(Abigail)的前奴隶,安娜·斯特朗曾是她的主人。英国军队在安娜·斯特朗入狱后没收了他的财产。虽然名义上阿比盖尔是自由的,但她被迫为约翰·安德烈工作。阿比盖尔把她在安德烈家中无意中听到消息藏在给儿子的礼物中,这个儿子被迫留下交给安娜照顾。剧中,特工355由伊达拉·维克托扮演。

阅读更多