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

阅读更多

最新文章

链接

×