发表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。

阅读更多
发表LeetCode7 分钟读完 (大约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;
        }
    }
}
阅读更多
发表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中。

阅读更多

最新文章

链接

×