发表LeetCode3 分钟读完 (大约452个字)

LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

题意

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

例子：

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

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

思路

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

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

其实直接递归就好，或者说分治：

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

阅读更多
发表Java5 分钟读完 (大约757个字)

从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是这样的：

阅读更多
发表Java9 分钟读完 (大约1401个字)

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。

阅读更多
发表Java4 分钟读完 (大约558个字)

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。

阅读更多
发表Tips3 分钟读完 (大约388个字)

如何恢复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
阅读更多
发表Develop7 分钟读完 (大约985个字)

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

刷微博，看到一道面试题：

先说一下思路

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

总体来说，就是从可行解空间[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是正确答案了

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

阅读更多
发表LeetCode5 分钟读完 (大约780个字)

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;
    }
}
阅读更多
发表LeetCode3 分钟读完 (大约477个字)

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;
        }
    }
}
阅读更多
发表4 分钟读完 (大约601个字)

数组中第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）：

阅读更多
发表uncategorized8 分钟读完 (大约1203个字)

特工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由伊达拉·维克托扮演。

阅读更多
关注我

最新文章

分类

标签

Arthas1
Desktop5
Docker2
Firefox1
HiDPI1
Input2
JVM1
Java2
Lambda1
Laravel1
LeetCode12
Linux8
PEP1
PHP5
Python2
Redis1
Scala1
Spring Cloud2
TLS1
VSCode1
django1
ssh1
uWSGI1
源码分析1
翻译8
面试1

链接

广告

×