发表LeetCode5 分钟读完 (大约676个字)

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

LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

题意

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

例子：

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

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

思路

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

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

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

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

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

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。

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

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

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)的空间复杂度。
  • 不可以改变节点的值。
阅读更多
发表LeetCode2 分钟读完 (大约266个字)

LeetCode：991. Broken Calculator

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

题意

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

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

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

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

题解

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

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

代码

阅读更多
发表LeetCode3 分钟读完 (大约408个字)

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

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

阅读更多
发表LeetCode3 分钟读完 (大约435个字)

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符合如下不等式：

阅读更多

最新文章

标签

Arthas4
Desktop5
Docker1
Firefox1
Go3
Golang3
HTTP1
HiDPI1
Input2
JVM2
Java20
Java Agent2
Kubernetes1
LeetCode13
Linux8
PEP1
PHP12
Python4
Redis1
Scala1
Spring Cloud2
TLS1
VSCode1
django1
gRPC1
rust2
ssh1
uWSGI1
云原生5
垃圾回收1
容器中的Java5
源码分析1
翻译8
面试1

链接

×