发表更新算法 / LeetCode7 分钟读完 (大约1024个字)

第 356 场力扣周赛

满足目标工作时长的员工数目

方法一：遍历

1
2
3
4
5
6
7
class Solution {
    public int numberOfEmployeesWhoMetTarget(int[] hours, int target) {
        int ans = 0;
        for (int x : hours) if (x >= target) ans++;
        return ans;
    }
}

复杂度分析

  • 时间复杂度：\(O(n)\)。
  • 空间复杂度：\(O(1)\)。

统计完全子数组的数目

方法一：暴力优化

比赛时本来是想滑窗的，但是当时没想通。而枚举左右端点再遍历的暴力方法，时间复杂度为 \(O(n^{3})\) 会超时。结果想半天发现可以使用前缀和的思路，先枚举左端点，然后一边遍历一边枚举右端点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int countCompleteSubarrays(int[] nums) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int cnt = set.size(), ans = 0;
        // 至少要有 cnt 个元素
        for (int i = 0; i <= n - cnt; i++) {
            set.clear();
            for (int j = i; j < n; j++) {
                set.add(nums[j]);
                if (set.size() == cnt) {
                    ans += n - j;
                    break;
                }
            }
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度：\(O(n^{2})\)。
  • 空间复杂度：\(O(n)\)。

方法二：滑动窗口

枚举右端点，并且让窗口是完全子数组的前提下，使左端点尽可能靠右，此时所有小于等于左端点的位置，都满足条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int countCompleteSubarrays(int[] nums) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int cnt = set.size();
        int lo = 0, hi = 0, ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        while (hi < n) {
            map.merge(nums[hi++], 1, Integer::sum);
            if (map.size() == cnt) {
                while (map.get(nums[lo]) > 1) {
                    map.merge(nums[lo++], -1, Integer::sum);
                }
                ans += lo + 1;
            }
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度：\(O(n)\)。
  • 空间复杂度：\(O(n)\)。

包含三个字符串的最短字符串

方法一：枚举

枚举字符串 \(a,b,c\) 的全排列，然后从前往后合并，以消除公共字符。需要注意，如果字符串存在包含关系，则不需要进行合并操作。

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
class Solution {
    public String minimumString(String a, String b, String c) {
        List<String> list = new ArrayList<>();
        list.add(merge(merge(a, b), c));
        list.add(merge(merge(a, c), b));
        list.add(merge(merge(b, a), c));
        list.add(merge(merge(b, c), a));
        list.add(merge(merge(c, a), b));
        list.add(merge(merge(c, b), a));
        list.sort((s1, s2) -> {
            int m = s1.length(), n = s2.length();
            if (m != n) return m - n;
            return s1.compareTo(s2);
        });
        return list.get(0);
    }

    private String merge(String a, String b) {
        if (a.contains(b)) return a;
        int m = a.length(), n = b.length();
        for (int i = Math.min(m, n); ; i--) {
            if (a.substring(m - i).equals(b.substring(0, i))) {
                return a + b.substring(i);
            }
        }
    }
}

复杂度分析

  • 时间复杂度：\(O(n^{2})\)，其中 \(n\) 为字符串 \(a,b,c\) 长度的最大值。
  • 空间复杂度：\(O(n)\)。

统计范围内的步进数字数目

方法一：数位DP

感觉有点像 DFS，枚举当前位的数字，多传递一个参数 isLimit 可以省去很多判断。

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
class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countSteppingNumbers(String low, String high) {
        int m = low.length(), n = high.length();
        // dp[i][j] 表示 i 位数的最高位为 j 的步进数字的数目
        int[][] dp = new int[n][10];
        Arrays.fill(dp[0], 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 10; j++) {
                if (j - 1 >= 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
                if (j + 1 <= 9) dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD;
            }
        }
        // 字符串不方便做减法，所以先减，如果 low 是步进数字则加回来
        return (f(dp, high, 0, -1, true) - f(dp, low, 0, -1, true) + valid(low) + MOD) % MOD;
    }

    private int f(int[][] dp, String s, int i, int pre, boolean isLimit) {
        int n = s.length();
        // 如果数字不为空，则计数值加一
        if (i == n) return pre != -1 ? 1 : 0;
        if (pre != -1 && !isLimit) return dp[n - i][pre];
        int cur = s.charAt(i) - '0', res = 0;
        int hi = isLimit ? cur : 9;
        // 如果选 0 并且数字为空，则表示跳过当前位
        for (int j = 0; j <= hi; j++) {
            if (pre == -1 || Math.abs(j - pre) == 1) {
                res = (res + f(dp, s, i + 1, (pre == -1 && j == 0) ? -1 : j, isLimit && j == hi)) % MOD;
            }
        }
        return res;
    }

    private int valid(String s) {
        int n = s.length();
        for (int i = 1; i < n; i++) {
            if (Math.abs(s.charAt(i) - s.charAt(i - 1)) != 1) {
                return 0;
            }
        }
        return 1;
    }
}

复杂度分析

  • 时间复杂度：\(O(nm^{2})\)，其中 \(n\) 为 high 的长度，\(m = 10\)。
  • 空间复杂度：\(O(nm)\)。
发表更新语言 / Java1 分钟读完 (大约166个字)

Java 快速输入输出

输入

Scanner 会使用正则表达式解析输入，而 BufferedReader 直接读取输入，所以 Scanner 更慢。

输出

System.out（类型为 PrintStream）的 autoFlush 属性默认为 True，所以 System.out 更慢。

模板

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
class FastIO extends PrintWriter {
    private BufferedReader br;
    private StringTokenizer st;

    public FastIO() {
        this(System.in, System.out);
    }

    public FastIO(InputStream in, OutputStream out) {
        super(out);
        br = new BufferedReader(new InputStreamReader(in));
    }

    public FastIO(String input, String output) throws FileNotFoundException {
        super(output);
        br = new BufferedReader(new FileReader(input));
    }

    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return null;
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }
}

测试

INOUTEST - Enormous Input and Output Test

发表更新其他1 分钟读完 (大约123个字)

Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×