发表Java7 分钟读完 (大约1049个字)

lambda表达式导致arthas无法redefine的问题

作为一个从PHP转Java的人，发现alibaba的arthas很好用。通过arthas的redefine命令，可以像PHP一样，不用重新发布，就可以改变程序行为（前提是不改变类结构，不改变方法签名）。

但是用多了，发现很多时候，我们就改了几行代码，甚至有的时候就添加了一行日志，就无法redefine了。提示

redefine error! java.lang.UnsupportedOperationException: class redefinition failed: attempted to add a method

它提示我们新增加方法，那我们就看看是不是新增加了方法。通过javap来查看定义的方法：

老的类：

新的类：

对比之后发现，新的类，即本地编译的类，其中的lambda对应的方法名都是lambda$getAllCity$0这样的。

阅读更多
发表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）：

阅读更多
关注我

最新文章

分类

标签

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

链接

广告

×