devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java算法：LeetCode算法Java版合集1111-1588题_leetcode1307口算难题java

作者：Monodyee | 2024-02-20 01:42:35

赞

踩

leetcode1307口算难题java

1111. 有效括号的嵌套深度

题目描述

有效括号字符串 仅由 "(" 和 ")" 构成，并符合下述几个条件之一：

  • 空字符串
  • 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串
  • 嵌套，可以记作 (A)，其中 A 是有效括号字符串

类似地，我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S)：

  • s 为空时，depth("") = 0
  • s 为 A 与 B 连接时，depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串
  • s 为嵌套情况，depth("(" + A + ")") = 1 + depth(A)，其中 A 是有效括号字符串

例如：""，"()()"，和 "()(()())" 都是有效括号字符串，嵌套深度分别为 0，1，2，而 ")(" 和 "(()" 都不是有效括号字符串。

 

给你一个有效括号字符串 seq，将其分成两个不相交的子序列 A 和 B，且 A 和 B 满足有效括号字符串的定义（注意：A.length + B.length = seq.length）。

现在，你需要从中选出 任意 一组有效括号字符串 A 和 B，使 max(depth(A), depth(B)) 的可能取值最小。

返回长度为 seq.length 答案数组 answer ，选择 A 还是 B 的编码规则是：如果 seq[i] 是 A 的一部分，那么 answer[i] = 0。否则，answer[i] = 1。即便有多个满足要求的答案存在，你也只需返回 一个。

 

示例 1：

输入：seq = "(()())"
输出：[0,1,1,1,1,0]

示例 2：

输入：seq = "()(())()"
输出：[0,0,0,1,1,0,1,1]

 

提示：

  • 1 <= text.size <= 10000

解法

Java

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int[] res = new int[seq.length()];
        for (int i = 0, cnt = 0; i < res.length; ++i) {
            if (seq.charAt(i) == '(') {
                res[i] = cnt++ & 1;
            } else {
                res[i] = --cnt & 1;
            }
        }
        return res;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

1114. 按序打印

题目描述

我们提供了一个类：

public class Foo {
  public void one() { print("one"); }
  public void two() { print("two"); }
  public void three() { print("three"); }
}

三个不同的线程将会共用一个 Foo 实例。

  • 线程 A 将会调用 one() 方法
  • 线程 B 将会调用 two() 方法
  • 线程 C 将会调用 three() 方法

请设计修改程序，以确保 two() 方法在 one() 方法之后被执行，three() 方法在 two() 方法之后被执行。

 

示例 1:

输入: [1,2,3]
输出: "onetwothree"
解释: 
有三个线程会被异步启动。
输入 [1,2,3] 表示线程 A 将会调用 one() 方法，线程 B 将会调用 two() 方法，线程 C 将会调用 three() 方法。
正确的输出是 "onetwothree"。

示例 2:

输入: [1,3,2]
输出: "onetwothree"
解释: 
输入 [1,3,2] 表示线程 A 将会调用 one() 方法，线程 B 将会调用 three() 方法，线程 C 将会调用 two() 方法。
正确的输出是 "onetwothree"。

 

注意:

尽管输入中的数字似乎暗示了顺序，但是我们并不保证线程在操作系统中的调度顺序。

你看到的输入格式主要是为了确保测试的全面性。

解法

Java

import java.util.concurrent.Semaphore;
class Foo {
    private Semaphore twoS = new Semaphore(0);
    private Semaphore threeS = new Semaphore(0);
    
    public Foo() {
        
    }
    public void first(Runnable printFirst) throws InterruptedException {
        printFirst.run();
        twoS.release();
    }
    public void second(Runnable printSecond) throws InterruptedException {
        twoS.acquire();
        printSecond.run();
        threeS.release();
    }
    public void third(Runnable printThird) throws InterruptedException {
        threeS.acquire();
        printThird.run();
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

1115. 交替打印 FooBar

题目描述

我们提供一个类：

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }
  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

两个不同的线程将会共用一个 FooBar 实例。其中一个线程将会调用 foo() 方法，另一个线程将会调用 bar() 方法。

请设计修改程序，以确保 "foobar" 被输出 n 次。

 

示例 1:

输入: n = 1
输出: "foobar"
解释: 这里有两个线程被异步启动。其中一个调用 foo() 方法, 另一个调用 bar() 方法，"foobar" 将被输出一次。

示例 2:

输入: n = 2
输出: "foobarfoobar"
解释: "foobar" 将被输出两次。

解法

Java

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
class FooBar {
    private int n;
    private Lock lock;
    private volatile Boolean flag;
    public FooBar(int n) {
        this.n = n;
        this.flag = true;
        this.lock = new ReentrantLock(true);
    }
    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n;) {
            lock.lock();
            if (flag) {
                printFoo.run();
                flag = false;
                i++;
            }
            lock.unlock();
        }
    }
    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n;) {
            lock.lock();
            if (!flag) {
                printBar.run();
                flag = true;
                i++;
            }
            lock.unlock();
        }
    }
}

  • 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

1116. 打印零与奇偶数

题目描述

假设有这么一个类：

class ZeroEvenOdd {
  public ZeroEvenOdd(int n) { ... }      // 构造函数
  public void zero(printNumber) { ... }  // 仅打印出 0
  public void even(printNumber) { ... }  // 仅打印出 偶数
  public void odd(printNumber) { ... }   // 仅打印出 奇数
}

相同的一个 ZeroEvenOdd 类实例将会传递给三个不同的线程：

  1. 线程 A 将调用 zero()，它只输出 0 。
  2. 线程 B 将调用 even()，它只输出偶数。
  3. 线程 C 将调用 odd()，它只输出奇数。

每个线程都有一个 printNumber 方法来输出一个整数。请修改给出的代码以输出整数序列 010203040506... ，其中序列的长度必须为 2n。

 

示例 1：

输入：n = 2
输出："0102"
说明：三条线程异步执行，其中一个调用 zero()，另一个线程调用 even()，最后一个线程调用odd()。正确的输出为 "0102"。

示例 2：

输入：n = 5
输出："0102030405"

解法

Java

class ZeroEvenOdd {
    private Semaphore zero_S;
    private Semaphore odd_S;
    private Semaphore even_S;
    private int n;
    public ZeroEvenOdd(int n) {
        this.n = n;
        this.zero_S = new Semaphore(1);
        this.odd_S = new Semaphore(0);
        this.even_S = new Semaphore(0);
    }
    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i ++) {
            zero_S.acquire(1);
            printNumber.accept(0);
            if ((i & 1) == 0) {
                odd_S.release(1);
            } else {
                even_S.release(1);
            }
        }
    }
    public void even(IntConsumer printNumber) throws InterruptedException {
        for (int i = 2; i <= n; i += 2) {
            even_S.acquire(1);
            printNumber.accept(i);
            zero_S.release(1);
        }
    }
    public void odd(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i += 2) {
            odd_S.acquire(1);
            printNumber.accept(i);
            zero_S.release(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

1117. H2O 生成

题目描述

现在有两种线程，氢 oxygen 和氧 hydrogen，你的目标是组织这两种线程来产生水分子。

存在一个屏障（barrier）使得每个线程必须等候直到一个完整水分子能够被产生出来。

氢和氧线程会被分别给予 releaseHydrogen 和 releaseOxygen 方法来允许它们突破屏障。

这些线程应该三三成组突破屏障并能立即组合产生一个水分子。

你必须保证产生一个水分子所需线程的结合必须发生在下一个水分子产生之前。

换句话说:

  • 如果一个氧线程到达屏障时没有氢线程到达，它必须等候直到两个氢线程到达。
  • 如果一个氢线程到达屏障时没有其它线程到达，它必须等候直到一个氧线程和另一个氢线程到达。

书写满足这些限制条件的氢、氧线程同步代码。

 

示例 1:

输入: "HOH"
输出: "HHO"
解释: "HOH" 和 "OHH" 依然都是有效解。

示例 2:

输入: "OOHHHH"
输出: "HHOHHO"
解释: "HOHHHO", "OHHHHO", "HHOHOH", "HOHHOH", "OHHHOH", "HHOOHH", "HOHOHH" 和 "OHHOHH" 依然都是有效解。

 

限制条件:

  • 输入字符串的总长将会是 3n, 1 ≤ n ≤ 50；
  • 输入字符串中的 “H” 总数将会是 2n；
  • 输入字符串中的 “O” 总数将会是 n。

解法

Java

class H2O {
    private Semaphore h = new Semaphore(2);
    private Semaphore o = new Semaphore(0);
    public H2O() {
    }
    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        // releaseHydrogen.run() outputs "H". Do not change or remove this line.
        h.acquire();
        releaseHydrogen.run();
        o.release();
    }
    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        // releaseOxygen.run() outputs "O". Do not change or remove this line.
        o.acquire(2);
        releaseOxygen.run();
        h.release(2);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

1122. 数组的相对排序

题目描述

给你两个数组，arr1 和 arr2，

  • arr2 中的元素各不相同
  • arr2 中的每个元素都出现在 arr1 中

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

 

示例：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

 

提示：

  • arr1.length, arr2.length <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000
  • arr2 中的元素 arr2[i] 各不相同
  • arr2 中的每个元素 arr2[i] 都出现在 arr1 中

解法

Java

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] map = new int[1001];
        for (int x : arr1) {
            ++map[x];
        }
        int i = 0;
        for (int x : arr2) {
            while (map[x]-- > 0) {
                arr1[i++] = x;
            }
        }
        for (int j = 0; j < map.length; ++j) {
            while (map[j]-- > 0) {
                arr1[i++] = j;
            }
        }
        return arr1;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

1123. 最深叶节点的最近公共祖先

题目描述

给你一个有根节点的二叉树，找到它最深的叶节点的最近公共祖先。

回想一下：

  • 叶节点 是二叉树中没有子节点的节点
  • 树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
  • 如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。

 

示例 1：

输入：root = [1,2,3]
输出：[1,2,3]

示例 2：

输入：root = [1,2,3,4]
输出：[4]

示例 3：

输入：root = [1,2,3,4,5]
输出：[2,4,5]

 

提示：

  • 给你的树中将有 1 到 1000 个节点。
  • 树中每个节点的值都在 1 到 1000 之间。

解法

Java

class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        Data data = dfs(root);
        return data.root;
    }
    private Data dfs(TreeNode root) {
        if (root == null) {
            return new Data(null, 0);
        }
        Data left = dfs(root.left);
        Data right = dfs(root.right);
        if (left.d > right.d) return new Data(left.root, 1 + left.d);
        if (left.d < right.d) return new Data(right.root, 1 + right.d);
        return new Data(root, 1 + left.d);
    }
    class Data {
        TreeNode root;
        int d;
        public Data(TreeNode root, int d) {
            this.root = root;
            this.d = d;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

1124. 表现良好的最长时间段

题目描述

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。

请你返回「表现良好时间段」的最大长度。

 

示例 1：

输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

 

提示：

  • 1 <= hours.length <= 10000
  • 0 <= hours[i] <= 16

解法

Java

class Solution {
    public int longestWPI(int[] hours) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int s = 0;
        for (int i = 0; i < hours.length; ++i) {
            s += hours[i] > 8 ? 1 : -1;
            if (s > 0) {
                res = i + 1;
            } else {
                int b = map.getOrDefault(s - 1, -1);
                if (b != -1) {
                    res = Math.max(res, i - b);
                }
            }
            map.putIfAbsent(s, i);
        }
        return res;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

1128. 等价多米诺骨牌对的数量

题目描述

给你一个由一些多米诺骨牌组成的列表 dominoes。

如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。

形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。

在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。

 

示例：

输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出：1

 

提示：

  • 1 <= dominoes.length <= 40000
  • 1 <= dominoes[i][j] <= 9

解法

Java

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] d : dominoes) {
            int x = d[0] < d[1] ? d[0] * 10 + d[1] : d[1] * 10 + d[0];
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        int res = 0;
        for (int v : map.values()) {
            res += v * (v - 1) / 2;
        }
        return res;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

1137. 第 N 个泰波那契数

题目描述

泰波那契序列 Tn 定义如下： 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

 

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25
输出：1389537

 

提示：

  • 0 <= n <= 37
  • 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。

解法

Java

class Solution {
    public int tribonacci(int n) {
        int[] f = new int[]{0, 1, 1, 2};
        for (int i = 4; i <= n; ++i) {
            f[i % 4] = f[(i - 1) % 4] + f[(i - 2) % 4] + f[(i - 3) % 4];
        }
        return f[n % 4];
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

1138. 字母板上的路径

题目描述

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。

在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"].

我们可以按下面的指令规则行动：

  • 如果方格存在，'U' 意味着将我们的位置上移一行；
  • 如果方格存在，'D' 意味着将我们的位置下移一行；
  • 如果方格存在，'L' 意味着将我们的位置左移一列；
  • 如果方格存在，'R' 意味着将我们的位置右移一列；
  • '!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。

返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

 

示例 1：

输入：target = "leet"
输出："DDR!UURRR!!DDD!"

示例 2：

输入：target = "code"
输出："RR!DDRR!UUL!R!"

 

提示：

  • 1 <= target.length <= 100
  • target 仅含有小写英文字母。

解法

Java

class Solution {
    public String alphabetBoardPath(String target) {
        StringBuilder sb = new StringBuilder();
        int x = 0, y = 0;
        for (char c : target.toCharArray()) {
            int dx = (c - 'a') / 5;
            int dy = (c - 'a') % 5;
            if (dy < y) {
                int n = y - dy;
                while (n-- > 0) {
                    sb.append('L');
                }
            }
            if (dx > x) {
                int n = dx - x;
                while (n-- > 0) {
                    sb.append('D');
                }
            }
            if (dx < x) {
                int n = x - dx;
                while (n-- > 0) {
                    sb.append('U');
                }
            }
            if (dy > y) {
                int n = dy - y;
                while (n-- > 0) {
                    sb.append('R');
                }
            }
            sb.append('!');
            x = dx;
            y = dy;
        }
        return sb.toString();
    }
}

  • 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

1139. 最大的以 1 为边界的正方形

题目描述

给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

 

示例 1：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9

示例 2：

输入：grid = [[1,1,0,0]]
输出：1

 

提示：

  • 1 <= grid.length <= 100
  • 1 <= grid[0].length <= 100
  • grid[i][j] 为 0 或 1

解法

Java

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] down = new int[m][n];
        int[][] right = new int[m][n];
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    down[i][j] += i + 1 < m ? down[i + 1][j] + 1 : 1;
                    right[i][j] += j + 1 < n ? right[i][j + 1] + 1 : 1;
                }
            }
        }
        for (int len = Math.min(m, n); len > 0; --len) {
            for (int i = 0; i <= m - len; ++i) {
                for (int j = 0; j <= n - len; ++j) {
                    if (down[i][j] >= len && right[i][j] >= len && right[i + len - 1][j] >= len && down[i][j + len - 1] >= len) {
                        return len * len;
                    }
                }
            }
        }
        return 0;
    }
}

  • 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

1140. 石子游戏 II

题目描述

亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。

 

示例：

输入：piles = [2,7,9,4,4]
输出：10
解释：
如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。 
如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。

 

提示：

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10 ^ 4

解法

Java

class Solution {
    public int stoneGameII(int[] piles) {
        Map<Integer, Integer> map = new HashMap<>();
        int total = Arrays.stream(piles).sum();
        return (total + dfs(0, 1, piles, map)) >> 1;
    }
    private int dfs(int s, int M, int[] piles, Map<Integer, Integer> map) {
        if (s >= piles.length) {
            return 0;
        }
        int key = s << 8 | M;
        if (map.containsKey(key)) {
            return map.get(key);
        }
        if (s + 2 * M >= piles.length) {
            int res = 0;
            for (int i = s; i < piles.length; ++i) {
                res += piles[i];
            }
            return res;
        }
        int best = Integer.MIN_VALUE;
        int cur = 0;
        for (int x = 1; x <= 2 * M && s + x - 1 < piles.length; ++x) {
            cur += piles[s + x - 1];
            best = Math.max(best, cur - dfs(s + x, Math.max(x, M), piles, map));
        }
        map.put(key, best);
        return best;
    }
}

  • 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

1144. 递减元素使数组呈锯齿状

题目描述

给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。

如果符合下列情况之一，则数组 A 就是 锯齿数组：

  • 每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] < A[2] > A[3] < A[4] > ...
  • 或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] < A[1] > A[2] < A[3] > A[4] < ...

返回将数组 nums 转换为锯齿数组所需的最小操作次数。

 

示例 1：

输入：nums = [1,2,3]
输出：2
解释：我们可以把 2 递减到 0，或把 3 递减到 1。

示例 2：

输入：nums = [9,6,1,6,2]
输出：4

 

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000

解法

Java

class Solution {
    public int movesToMakeZigzag(int[] nums) {
        int[] res = new int[2];
        for (int i = 0, n = nums.length; i < n; ++i) {
            int left = i > 0 ? nums[i - 1] : Integer.MAX_VALUE;
            int right = i + 1 < n ? nums[i + 1] : Integer.MAX_VALUE;
            res[i & 1] += Math.max(0, nums[i] - (Math.min(left, right) - 1));
        }
        return Math.min(res[0], res[1]);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

1147. 段式回文

题目描述

段式回文 其实与 一般回文 类似，只不过是最小的单位是 一段字符 而不是 单个字母。

举个例子，对于一般回文 "abcba" 是回文，而 "volvo" 不是，但如果我们把 "volvo" 分为 "vo"、"l"、"vo" 三段，则可以认为 “(vo)(l)(vo)” 是段式回文（分为 3 段）。

 

给你一个字符串 text，在确保它满足段式回文的前提下，请你返回 段 的 最大数量 k。

如果段的最大数量为 k，那么存在满足以下条件的 a_1, a_2, ..., a_k：

  • 每个 a_i 都是一个非空字符串；
  • 将这些字符串首位相连的结果 a_1 + a_2 + ... + a_k 和原始字符串 text 相同；
  • 对于所有1 <= i <= k，都有 a_i = a_{k+1 - i}。

 

示例 1：

输入：text = "ghiabcdefhelloadamhelloabcdefghi"
输出：7
解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。

示例 2：

输入：text = "merchant"
输出：1
解释：我们可以把字符串拆分成 "(merchant)"。

示例 3：

输入：text = "antaprezatepzapreanta"
输出：11
解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。

示例 4：

输入：text = "aaa"
输出：3
解释：我们可以把字符串拆分成 "(a)(a)(a)"。

 

提示：

  • text 仅由小写英文字符组成。
  • 1 <= text.length <= 1000

解法

Java

class Solution {
    public int longestDecomposition(String text) {
        char[] cs = text.toCharArray();
        int res = 0;
        for (int i = 0, j = cs.length - 1; i <= j; ) {
            boolean flag = true;
            for (int k = 1; i + k - 1 < j - k + 1; ++k) {
                if (check(cs, i, j - k + 1, k)) {
                    res += 2;
                    i += k;
                    j -= k;
                    flag = false;
                    break;
                }
            }
            if (flag) {
                ++res;
                break;
            }
        }
        return res;
    }
    private boolean check(char[] cs, int i, int j, int k) {
        while (k-- > 0) {
            if (cs[i++] != cs[j++]) {
                return false;
            }
        }
        return true;
    }
}

  • 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

1155. 掷骰子的 N 种方法

题目描述

这里有 d 个一样的骰子，每个骰子上都有 f 个面，分别标号为 1, 2, ..., f。

我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。

如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），模 10^9 + 7 后返回。

 

示例 1：

输入：d = 1, f = 6, target = 3
输出：1

示例 2：

输入：d = 2, f = 6, target = 7
输出：6

示例 3：

输入：d = 2, f = 5, target = 10
输出：1

示例 4：

输入：d = 1, f = 2, target = 3
输出：0

示例 5：

输入：d = 30, f = 30, target = 500
输出：222616187

 

提示：

  • 1 <= d, f <= 30
  • 1 <= target <= 1000

解法

Java

class Solution {
    public int numRollsToTarget(int d, int f, int target) {
        int[][] dp = new int[d + 1][target + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= d; ++i) {
            for (int j = 1; j <= target; ++j) {
                // j 大于当前所有骰子的最大和，不可能满足条件
                if (j > i * f) {
                    break;
                }
                for (int k = 1; k <= f && k <= j; ++k) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % 1000000007;
                }
            }
        }
        return dp[d][target];
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

1171. 从链表中删去总和值为零的连续节点

题目描述

给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。

 

你可以返回任何满足题目要求的答案。

（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

示例 1：

输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。

示例 2：

输入：head = [1,2,3,-3,4]
输出：[1,2,4]

示例 3：

输入：head = [1,2,3,-3,-2]
输出：[1]

 

提示：

  • 给你的链表中可能有 1 到 1000 个节点。
  • 对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.

解法

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        Map<Integer, ListNode> map = new HashMap<>();
        boolean isZeroSum = true; 
        
        while (isZeroSum) {
        	isZeroSum = false;
        	int sum = 0;
        	ListNode temp = head;
        	
        	while (temp != null) {
        		sum += temp.val;
        		
        		if (sum == 0) {
        			head = temp.next;
        			map.clear();
        			isZeroSum = true;
        			break;
        		} else if (map.containsKey(sum)) {
        			map.get(sum).next = temp.next;
        			map.clear();
        			isZeroSum = true;
        			break;
        		}
        		
        		map.put(sum, temp);
        		temp = temp.next;
        	}
        }
        
        return head;
    }
}

  • 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

1184. 公交站间的距离

题目描述

环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。

环线上的公交车都可以按顺时针和逆时针的方向行驶。

返回乘客从出发点 start 到目的地 destination 之间的最短距离。

 

示例 1：

在这里插入图片描述

输入：distance = [1,2,3,4], start = 0, destination = 1
输出：1
解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。

 

示例 2：

在这里插入图片描述

输入：distance = [1,2,3,4], start = 0, destination = 2
输出：3
解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。

 

示例 3：

在这里插入图片描述

输入：distance = [1,2,3,4], start = 0, destination = 3
输出：4
解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。

 

提示：

  • 1 <= n <= 10^4
  • distance.length == n
  • 0 <= start, destination < n
  • 0 <= distance[i] <= 10^4

解法

Java

class Solution {
    public static int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int length = 0;
        for (int i : distance) {
            length += i;
        }
        int min = Math.min(start, destination);
        int max = Math.max(start, destination);
        int length2 = 0;
        for (int i = min; i < max; i++) {
            length2 += distance[i];
        }
        return Math.min(length - length2, length2);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

1185. 一周中的第几天

题目描述

给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。

输入为三个整数：day、month 和 year，分别表示日、月、年。

您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。

 

示例 1：

输入：day = 31, month = 8, year = 2019
输出："Saturday"

示例 2：

输入：day = 18, month = 7, year = 1999
输出："Sunday"

示例 3：

输入：day = 15, month = 8, year = 1993
输出："Sunday"

 

提示：

  • 给出的日期一定是在 1971 到 2100 年之间的有效日期。

解法

Java

import java.util.Calendar;
class Solution {
    private static final String[] WEEK = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
    public static String dayOfTheWeek(int day, int month, int year) {
        Calendar calendar = Calendar.getInstance();
        calendar.set(year, month - 1, day);
        return WEEK[calendar.get(Calendar.DAY_OF_WEEK) - 1];
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

1195. 交替打印字符串

题目描述

编写一个可以从 1 到 n 输出代表这个数字的字符串的程序，但是：

  • 如果这个数字可以被 3 整除，输出 "fizz"。
  • 如果这个数字可以被 5 整除，输出 "buzz"。
  • 如果这个数字可以同时被 3 和 5 整除，输出 "fizzbuzz"。

例如，当 n = 15，输出： 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz。

假设有这么一个类：

class FizzBuzz {
  public FizzBuzz(int n) { ... }               // constructor
  public void fizz(printFizz) { ... }          // only output "fizz"
  public void buzz(printBuzz) { ... }          // only output "buzz"
  public void fizzbuzz(printFizzBuzz) { ... }  // only output "fizzbuzz"
  public void number(printNumber) { ... }      // only output the numbers
}

请你实现一个有四个线程的多线程版  FizzBuzz， 同一个 FizzBuzz 实例会被如下四个线程使用：

  1. 线程A将调用 fizz() 来判断是否能被 3 整除，如果可以，则输出 fizz。
  2. 线程B将调用 buzz() 来判断是否能被 5 整除，如果可以，则输出 buzz。
  3. 线程C将调用 fizzbuzz() 来判断是否同时能被 3 和 5 整除，如果可以，则输出 fizzbuzz。
  4. 线程D将调用 number() 来实现输出既不能被 3 整除也不能被 5 整除的数字。

解法

Java

class FizzBuzz {
    private int n;
    public FizzBuzz(int n) {
        this.n = n;
    }
    private Semaphore fSema = new Semaphore(0);
    private Semaphore bSema = new Semaphore(0);
    private Semaphore fbSema = new Semaphore(0);
    private Semaphore nSema = new Semaphore(1);
    // printFizz.run() outputs "fizz".
    public void fizz(Runnable printFizz) throws InterruptedException {
        for (int i = 3; i <= n; i = i + 3) {
            if (i % 5 != 0) {
                fSema.acquire();
                printFizz.run();
                nSema.release();
            }
        }
    }
    // printBuzz.run() outputs "buzz".
    public void buzz(Runnable printBuzz) throws InterruptedException {
        for (int i = 5; i <= n; i = i + 5) {
            if (i % 3 != 0) {
                bSema.acquire();
                printBuzz.run();
                nSema.release();
            }
        }
    }
    // printFizzBuzz.run() outputs "fizzbuzz".
    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        for (int i = 15; i <= n; i = i + 15) {
            fbSema.acquire();
            printFizzBuzz.run();
            nSema.release();
        }
    }
    // printNumber.accept(x) outputs "x", where x is an integer.
    public void number(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            nSema.acquire();
            if (i % 3 == 0 && i % 5 == 0) {
                fbSema.release();
            } else if (i % 3 == 0) {
                fSema.release();
            } else if (i % 5 == 0) {
                bSema.release();
            } else {
                printNumber.accept(i);
                nSema.release();
            }
        }
    }
}

  • 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

1287. 有序数组中出现次数超过 25%的元素

题目描述

给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数

 

示例：

输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6

 

提示：

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^5

解法

Java

class Solution {
    public int findSpecialInteger(int[] arr) {
        int total = arr.length;
        for (int i = 0; i < total; ++i) {
            if (arr[i] == arr[i + (total >> 2)]) {
                return arr[i];
            }
        }
        return 0;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

1290. 二进制链表转整数

题目描述

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

 

示例 1：

在这里插入图片描述

输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)

示例 2：

输入：head = [0]
输出：0

示例 3：

输入：head = [1]
输出：1

示例 4：

输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880

示例 5：

输入：head = [0,0]
输出：0

 

提示：

  • 链表不为空。
  • 链表的结点总数不超过 30。
  • 每个结点的值不是 0 就是 1。

解法

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        int sum = 0;
        StringBuilder sb = new StringBuilder("0");
        while (head != null) {
            sum += head.val;
            if (sum != 0) {
                sb.append(head.val);
            }
            head = head.next;
        }
        return Integer.valueOf(sb.toString(), 2);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

1295. 统计位数为偶数的数字

题目描述

给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。

 

示例 1：

输入：nums = [12,345,2,6,7896]
输出：2
解释：
12 是 2 位数字（位数为偶数） 
345 是 3 位数字（位数为奇数）  
2 是 1 位数字（位数为奇数） 
6 是 1 位数字 位数为奇数） 
7896 是 4 位数字（位数为偶数）  
因此只有 12 和 7896 是位数为偶数的数字

示例 2：

输入：nums = [555,901,482,1771]
输出：1 
解释： 
只有 1771 是位数为偶数的数字。

 

提示：

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 10^5

解法

首先将数组元素转换为字符串,判断字符串长度是否为偶数即可。

Java

class Solution {
    public int findNumbers(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res += (String.valueOf(num).length() & 1) == 0 ? 1 : 0;
        }
        return res;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

1346. 检查整数及其两倍数是否存在

题目描述

给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。

更正式地，检查是否存在两个下标 i 和 j 满足：

  • i != j
  • 0 <= i, j < arr.length
  • arr[i] == 2 * arr[j]

 

示例 1：

输入：arr = [10,2,5,3]
输出：true
解释：N = 10 是 M = 5 的两倍，即 10 = 2 * 5 。

        示例 2：

        输入：arr = [7,1,14,11]
输出：true
解释：N = 14 是 M = 7 的两倍，即 14 = 2 * 7 。

              示例 3：

              输入：arr = [3,1,7,11]
输出：false
解释：在该情况下不存在 N 和 M 满足 N = 2 * M 。

               

              提示：

              • 2 <= arr.length <= 500
              • -10^3 <= arr[i] <= 10^3

              解法

              Java

              import java.util.*;
class Solution {
    public boolean checkIfExist(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], i);
        }
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i] * 2) && i != map.get(arr[i] * 2))
                return true;
        }
        return false;
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12
              • 13
              • 14

              1347. 制造字母异位词的最小步骤数

              题目描述

              给你两个长度相等的字符串 s 和 t。每一个步骤中，你可以选择将 t 中的 任一字符 替换为 另一个字符。

              返回使 t 成为 s 的字母异位词的最小步骤数。

              字母异位词 指字母相同，但排列不同的字符串。

               

              示例 1：

              输出：s = "bab", t = "aba"
输出：1
提示：用 'b' 替换 t 中的第一个 'a'，t = "bba" 是 s 的一个字母异位词。

              示例 2：

              输出：s = "leetcode", t = "practice"
输出：5
提示：用合适的字符替换 t 中的 'p', 'r', 'a', 'i' 和 'c'，使 t 变成 s 的字母异位词。

              示例 3：

              输出：s = "anagram", t = "mangaar"
输出：0
提示："anagram" 和 "mangaar" 本身就是一组字母异位词。

              示例 4：

              输出：s = "xxyyzz", t = "xxyyzz"
输出：0

              示例 5：

              输出：s = "friend", t = "family"
输出：4

               

              提示：

              • 1 <= s.length <= 50000
              • s.length == t.length
              • s 和 t 只包含小写英文字母

              解法

              Java

              import java.util.*;
class Solution {
    public int minSteps(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else map.put(c, 1);
        }
        int res = 0;
        for (char c : s.toCharArray()) {
            if (map.containsKey(c) && map.get(c) > 0) {
                map.put(c, map.get(c) - 1);
            } else res ++;
        }
        return res;
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12
              • 13
              • 14
              • 15
              • 16
              • 17
              • 18

              1380. 矩阵中的幸运数

              题目描述

              给你一个 m * n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。

              幸运数是指矩阵中满足同时下列两个条件的元素：

              • 在同一行的所有元素中最小
              • 在同一列的所有元素中最大

               

              示例 1：

              输入：matrix = [[3,7,8],[9,11,13],[15,16,17]]
输出：[15]
解释：15 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。

              示例 2：

              输入：matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
输出：[12]
解释：12 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。

              示例 3：

              输入：matrix = [[7,8],[1,2]]
输出：[7]

               

              提示：

              • m == mat.length
              • n == mat[i].length
              • 1 <= n, m <= 50
              • 1 <= matrix[i][j] <= 10^5
              • 矩阵中的所有元素都是不同的

              解法

              取行最小值与列最大值的交集即可。

              Java

              class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        Set<Integer> rowMin = new HashSet<>();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < n; ++j) {
                min = Math.min(min, matrix[i][j]);
            }
            rowMin.add(min);
        }
        for (int j = 0; j < n; ++j) {
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < m; ++i) {
                max = Math.max(max, matrix[i][j]);
            }
            if (rowMin.contains(max)) {
                res.add(max);
            }
        }
        return res;
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12
              • 13
              • 14
              • 15
              • 16
              • 17
              • 18
              • 19
              • 20
              • 21
              • 22
              • 23
              • 24

              1476. 子矩形查询

              题目描述

              请你实现一个类 SubrectangleQueries ，它的构造函数的参数是一个 rows x cols 的矩形（这里用整数矩阵表示），并支持以下两种操作：

              1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)

              • 用 newValue 更新以 (row1,col1) 为左上角且以 (row2,col2) 为右下角的子矩形。

              2. getValue(int row, int col)

              • 返回矩形中坐标 (row,col) 的当前值。

               

              示例 1：

              输入：
["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue","getValue"]
[[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]]
输出：
[null,1,null,5,5,null,10,5]
解释：
SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]);  
// 初始的 (4x3) 矩形如下：
// 1 2 1
// 4 3 4
// 3 2 1
// 1 1 1
subrectangleQueries.getValue(0, 2); // 返回 1
subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5);
// 此次更新后矩形变为：
// 5 5 5
// 5 5 5
// 5 5 5
// 5 5 5 
subrectangleQueries.getValue(0, 2); // 返回 5
subrectangleQueries.getValue(3, 1); // 返回 5
subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10);
// 此次更新后矩形变为：
// 5   5   5
// 5   5   5
// 5   5   5
// 10  10  10 
subrectangleQueries.getValue(3, 1); // 返回 10
subrectangleQueries.getValue(0, 2); // 返回 5

              示例 2：

              输入：
["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue"]
[[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]]
输出：
[null,1,null,100,100,null,20]
解释：
SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]);
subrectangleQueries.getValue(0, 0); // 返回 1
subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100);
subrectangleQueries.getValue(0, 0); // 返回 100
subrectangleQueries.getValue(2, 2); // 返回 100
subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20);
subrectangleQueries.getValue(2, 2); // 返回 20

               

              提示：

              • 最多有 500 次updateSubrectangle 和 getValue 操作。
              • 1 <= rows, cols <= 100
              • rows == rectangle.length
              • cols == rectangle[i].length
              • 0 <= row1 <= row2 < rows
              • 0 <= col1 <= col2 < cols
              • 1 <= newValue, rectangle[i][j] <= 10^9
              • 0 <= row < rows
              • 0 <= col < cols

              解法

              Java

              class SubrectangleQueries {
    int[][] matrix;
    public SubrectangleQueries(int[][] rectangle) {
        matrix = new int[rectangle.length][rectangle[0].length];
        for (int i = 0; i < rectangle.length; i++) {
            for (int j = 0; j < rectangle[0].length; j++) {
                matrix[i][j] = rectangle[i][j];
            }
        }
    }
    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        if (row1 > row2 || col1 > col2) {
            return;
        }
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                matrix[i][j] = newValue;
            }
        }
    }
    public int getValue(int row, int col) {
        return matrix[row][col];
    }
}
/**
 * Your SubrectangleQueries object will be instantiated and called as such:
 * SubrectangleQueries obj = new SubrectangleQueries(rectangle);
 * obj.updateSubrectangle(row1,col1,row2,col2,newValue);
 * int param_2 = obj.getValue(row,col);
 */

              • 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

              1535. 找出数组游戏的赢家

              题目描述

              给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。

              每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。

              返回赢得比赛的整数。

              题目数据 保证 游戏存在赢家。

               

              示例 1：

              输入：arr = [2,1,3,5,4,6,7], k = 2
输出：5
解释：
一起看一下本场游戏每回合的情况：
![这里插入图片描述](https://img-blog.csdnimg.cn/20210225001641409.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjY1Njcz,size_16,color_FFFFFF,t_70)
因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。

              示例 2：

              输入：arr = [3,2,1], k = 10
输出：3
解释：3 将会在前 10 个回合中连续获胜。

              示例 3：

              输入：arr = [1,9,8,2,3,7,6,4,5], k = 7
输出：9

              示例 4：

              输入：arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
输出：99

               

              提示：

              • 2 <= arr.length <= 10^5
              • 1 <= arr[i] <= 10^6
              • arr 所含的整数 各不相同 。
              • 1 <= k <= 10^9

              解法

              Java

              class Solution {
    public int getWinner(int[] arr, int k) {
        int time = 0, max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max > arr[i]) {
                time++;
            } else {
                time = 1;
                max = arr[i];
            }
            if (time >= k) {
                return max;
            }
        }
        return max;
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12
              • 13
              • 14
              • 15
              • 16
              • 17

              1537. 最大得分

              题目描述

              你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。

              一条 合法路径 定义如下：

              • 选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
              • 从左到右遍历当前数组。
              • 如果你遇到了 nums1 和 nums2 中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。

              得分定义为合法路径中不同数字的和。

              请你返回所有可能合法路径中的最大得分。

              由于答案可能很大，请你将它对 10^9 + 7 取余后返回。

               

              示例 1：

              在这里插入图片描述

              输入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
输出：30
解释：合法路径包括：
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（从 nums1 开始遍历）
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]  （从 nums2 开始遍历）
最大得分为上图中的绿色路径 [2,4,6,8,10] 。

              示例 2：

              输入：nums1 = [1,3,5,7,9], nums2 = [3,5,100]
输出：109
解释：最大得分由路径 [1,3,5,100] 得到。

              示例 3：

              输入：nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
输出：40
解释：nums1 和 nums2 之间无相同数字。
最大得分由路径 [6,7,8,9,10] 得到。

              示例 4：

              输入：nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
输出：61

               

              提示：

              • 1 <= nums1.length <= 10^5
              • 1 <= nums2.length <= 10^5
              • 1 <= nums1[i], nums2[i] <= 10^7
              • nums1 和 nums2 都是严格递增的数组。

              解法

              Java

              class Solution {
    final int MOD = (int) (1e9 + 7);
    public int maxSum(int[] nums1, int[] nums2) {
        Set<Integer> set1 = Arrays.stream(nums1).boxed().collect(Collectors.toSet());
        Set<Integer> set2 = Arrays.stream(nums2).boxed().collect(Collectors.toSet());
        set1.retainAll(set2);
        if (set1.isEmpty()) {
            return (int) (Math.max(sum(nums1, 0, nums1.length - 1), sum(nums2, 0, nums2.length - 1))
                    % MOD);
        }
        long res = 0;
        List<Integer> list = set1.stream().sorted(Comparator.naturalOrder())
                .collect(Collectors.toList());
        int start1 = 0, start2 = 0, end1 = 0, end2 = 0;
        for (int common : list) {
            // 2 个数组同时到达 set
            while (nums1[end1] != common) {
                end1++;
            }
            while (nums2[end2] != common) {
                end2++;
            }
            // max
            res += Math.max(sum(nums1, start1, end1), sum(nums2, start2, end2));
            start1 = end1 + 1;
            start2 = end2 + 1;
        }
        res += Math.max(sum(nums1, end1 + 1, nums1.length - 1),
                sum(nums2, end2 + 1, nums2.length - 1));
        res %= MOD;
        return (int) res;
    }
    private long sum(int[] n, int l, int r) {
        long res = 0;
        while (l <= r) {
            res += n[l++];
        }
        return res;
    }
}

              • 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

              1541. 平衡括号字符串的最少插入次数

              题目描述

              给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：

              • 任何左括号 '(' 必须对应两个连续的右括号 '))' 。
              • 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

              比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。

              你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。

              请你返回让 s 平衡的最少插入次数。

               

              示例 1：

              输入：s = "(()))"
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。

              示例 2：

              输入：s = "())"
输出：0
解释：字符串已经平衡了。

              示例 3：

              输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。

              示例 4：

              输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。

              示例 5：

              输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。

               

              提示：

              • 1 <= s.length <= 10^5
              • s 只包含 '(' 和 ')' 。

              解法

              Java

              class Solution {
     public int minInsertions(String s) {
        int left = 0;
        int res = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length;) {
            if (chars[i] == '(') {
                left++;
                i++;
            } else {
                // 连续2个 )
                if (i < chars.length - 1 && chars[i + 1] == ')') {
                    if (left > 0) {
                        left--;
                    } else {
                        res++;
                    }
                    i += 2;
                } else {
                    if (left > 0) {
                        left--;
                        res++;
                    } else {
                        res += 2;
                    }
                    i++;
                }
            }
        }
        if (left > 0) {
            res += 2 * left;
        }
        return res;
    }
}

              • 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

              1544. 整理字符串

              题目描述

              给你一个由大小写英文字母组成的字符串 s 。

              一个整理好的字符串中，两个相邻字符 s[i] 和 s[i + 1] 不会同时满足下述条件：

              • 0 <= i <= s.length - 2
              • s[i] 是小写字符，但 s[i + 1] 是相同的大写字符；反之亦然 。

              请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。

              请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。

              注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。

               

              示例 1：

              输入：s = "leEeetcode"
输出："leetcode"
解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 "leEeetcode" 缩减为 "leetcode" 。

              示例 2：

              输入：s = "abBAcC"
输出：""
解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

              示例 3：

              输入：s = "s"
输出："s"

               

              提示：

              • 1 <= s.length <= 100
              • s 只包含小写和大写英文字母

              解法

              Java

              class Solution {
    public String makeGood(String s) {
        return help(s);
    }
    private String help(String s) {
        if (s == null || s.length() == 0 || s.length() == 1) {
            return s;
        }
        char[] chars = s.toCharArray();
        for (int i = 1; i < chars.length; i++) {
            if (Math.abs(chars[i] - chars[i - 1]) == Math.abs('A' - 'a')) {
                return help(newString(chars, i));
            }
        }
        return s;
    }
    private String newString(char[] chars, int i) {
        StringBuilder tmp = new StringBuilder();
        for (int j = 0; j < chars.length; j++) {
            if (j != i && j != i - 1) {
                tmp.append(chars[j]);
            }
        }
        return tmp.toString();
    }
}

              • 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

              1545. 找出第 N 个二进制字符串中的第 K 位

              题目描述

              给你两个正整数 n 和 k，二进制字符串  Sn 的形成规则如下：

              • S1 = "0"
              • 当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))

              其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）

              例如，符合上述描述的序列的前 4 个字符串依次是：

              • S1 = "0"
              • S2 = "011"
              • S3 = "0111001"
              • S4 = "011100110110001"

              请你返回  Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。

               

              示例 1：

              输入：n = 3, k = 1
输出："0"
解释：S3 为 "0111001"，其第 1 位为 "0" 。

              示例 2：

              输入：n = 4, k = 11
输出："1"
解释：S4 为 "011100110110001"，其第 11 位为 "1" 。

              示例 3：

              输入：n = 1, k = 1
输出："0"

              示例 4：

              输入：n = 2, k = 3
输出："1"

               

              提示：

              • 1 <= n <= 20
              • 1 <= k <= 2n - 1

              解法

              Java

              class Solution {
      public char findKthBit(int n, int k) {
        if (k == 1 || n == 1) {
            return '0';
        }
        Set<Integer> set = new HashSet<>();
        int len = calcLength(n, set);
        if (set.contains(k)) {
            return '1';
        }
        // 中间，返回1
        if (k < len / 2) {
            return findKthBit(n - 1, k);
        } else {
            if (set.contains(len - k)) {
                return '1';
            }
            return r(findKthBit(n - 1, len - k + 1));
        }
    }
    private char r(char b) {
        if (b == '0') {
            return '1';
        }
        return '0';
    }
    private int calcLength(int n, Set<Integer> set) {
        if (n == 1) {
            return 1;
        }
        int ans = 2 * calcLength(n - 1, set) + 1;
        set.add(ans + 1);
        return ans;
    }
}

              • 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

              1546. 和为目标值的最大数目不重叠非空子数组数目

              题目描述

              给你一个数组 nums 和一个整数 target 。

              请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。

               

              示例 1：

              输入：nums = [1,1,1,1,1], target = 2
输出：2
解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。

              示例 2：

              输入：nums = [-1,3,5,1,4,2,-9], target = 6
输出：2
解释：总共有 3 个子数组和为 6 。
([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。

              示例 3：

              输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10
输出：3

              示例 4：

              输入：nums = [0,0,0], target = 0
输出：3

               

              提示：

              • 1 <= nums.length <= 10^5
              • -10^4 <= nums[i] <= 10^4
              • 0 <= target <= 10^6

              解法

              Java

              class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        set.add(0);
        int sum = 0, ans = 0;
        for (int num : nums) {
            sum += num;
            if (set.contains(sum - target)) {
                ans++;
                set.clear();
                sum = 0;
            }
            set.add(sum);
        }
        return ans;
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12
              • 13
              • 14
              • 15
              • 16
              • 17

              1550. 存在连续三个奇数的数组

              题目描述

              给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false 。

               

              示例 1：

              输入：arr = [2,6,4,1]
输出：false
解释：不存在连续三个元素都是奇数的情况。

              示例 2：

              输入：arr = [1,2,34,3,4,5,7,23,12]
输出：true
解释：存在连续三个元素都是奇数的情况，即 [5,7,23] 。

               

              提示：

              • 1 <= arr.length <= 1000
              • 1 <= arr[i] <= 1000

              解法

              Java

              class Solution {
    public boolean threeConsecutiveOdds(int[] arr) {
        int count = 0;
        for (int n : arr) {
            if (n % 2 == 0) {
                count = 0;
            } else {
                count++;
                if (count >= 3) {
                    return true;
                }
            }
        }
        return false;
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12
              • 13
              • 14
              • 15
              • 16

              1551. 使数组中所有元素相等的最小操作数

              题目描述

              存在一个长度为 n 的数组 arr ，其中 arr[i] = (2 * i) + 1 （ 0 <= i < n ）。

              一次操作中，你可以选出两个下标，记作 x 和 y （ 0 <= x, y < n ）并使 arr[x] 减去 1 、arr[y] 加上 1 （即 arr[x] -=1 且 arr[y] += 1 ）。最终的目标是使数组中的所有元素都 相等 。题目测试用例将会 保证 ：在执行若干步操作后，数组中的所有元素最终可以全部相等。

              给你一个整数 n，即数组的长度。请你返回使数组 arr 中所有元素相等所需的 最小操作数 。

               

              示例 1：

              输入：n = 3
输出：2
解释：arr = [1, 3, 5]
第一次操作选出 x = 2 和 y = 0，使数组变为 [2, 3, 4]
第二次操作继续选出 x = 2 和 y = 0，数组将会变成 [3, 3, 3]

              示例 2：

              输入：n = 6
输出：9

               

              提示：

              • 1 <= n <= 10^4

              解法

              Java

              class Solution {
    public int minOperations(int n) {
        int ans = 0;
        for (int i = 0; i < n / 2; i++) {
            int curr = 2 * i + 1;
            ans += Math.abs(n - curr);
        }
        return ans;
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10

              1552. 两球之间的磁力

              题目描述

              在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。

              已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。

              给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。

               

              示例 1：

              在这里插入图片描述

              输入：position = [1,2,3,4,7], m = 3
输出：3
解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。

              示例 2：

              输入：position = [5,4,3,2,1,1000000000], m = 2
输出：999999999
解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。

               

              提示：

              • n == position.length
              • 2 <= n <= 10^5
              • 1 <= position[i] <= 10^9
              • 所有 position 中的整数 互不相同 。
              • 2 <= m <= position.length

              解法

              Java

              class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        // 最小磁力的可能最小值
        int min = 1;
        // 最小磁力的可能最大值
        int max = (position[position.length - 1] - position[0]) / (m - 1);
        int ans = -1;
        while (min <= max) {
            int mid = (min + max) / 2;
            if (checkDistance(mid, position, m)) {
                ans = mid;
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        return ans;
    }
    private boolean checkDistance(int mid, int[] position, int m) {
        int count = 1;
        int pre = position[0];
        for (int i = 1; i < position.length; i++) {
            if (position[i] - pre >= mid) {
                count++;
                if (count >= m) {
                    return true;
                }
                pre = position[i];
            }
        }
        return false;
    }
}

              • 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

              1553. 吃掉 N 个橘子的最少天数

              题目描述

              厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：

              • 吃掉一个橘子。
              • 如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
              • 如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。

              每天你只能从以上 3 种方案中选择一种方案。

              请你返回吃掉所有 n 个橘子的最少天数。

               

              示例 1：

              输入：n = 10
输出：4
解释：你总共有 10 个橘子。
第 1 天：吃 1 个橘子，剩余橘子数 10 - 1 = 9。
第 2 天：吃 6 个橘子，剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。（9 可以被 3 整除）
第 3 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。
第 4 天：吃掉最后 1 个橘子，剩余橘子数 1 - 1 = 0。
你需要至少 4 天吃掉 10 个橘子。

              示例 2：

              输入：n = 6
输出：3
解释：你总共有 6 个橘子。
第 1 天：吃 3 个橘子，剩余橘子数 6 - 6/2 = 6 - 3 = 3。（6 可以被 2 整除）
第 2 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。（3 可以被 3 整除）
第 3 天：吃掉剩余 1 个橘子，剩余橘子数 1 - 1 = 0。
你至少需要 3 天吃掉 6 个橘子。

              示例 3：

              输入：n = 1
输出：1

              示例 4：

              输入：n = 56
输出：6

               

              提示：

              • 1 <= n <= 2*10^9

              解法

              Java

              class Solution {
    private Map<Integer, Integer> map = new HashMap<>();
    public int minDays(int n) {
        if (n < 2) {
            return n;
        }
        if (!map.containsKey(n)) {
            map.put(n, Math.min(minDays(n / 2) + 1 + n % 2, minDays(n / 3) + 1 + n % 3));
        }
        return map.get(n);
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12

              1560. 圆形赛道上经过次数最多的扇区

              题目描述

              给你一个整数 n 和一个整数数组 rounds 。有一条圆形赛道由 n 个扇区组成，扇区编号从 1 到 n 。现将在这条赛道上举办一场马拉松比赛，该马拉松全程由 m 个阶段组成。其中，第 i 个阶段将会从扇区 rounds[i - 1] 开始，到扇区 rounds[i] 结束。举例来说，第 1 阶段从 rounds[0] 开始，到 rounds[1] 结束。

              请你以数组形式返回经过次数最多的那几个扇区，按扇区编号 升序 排列。

              注意，赛道按扇区编号升序逆时针形成一个圆（请参见第一个示例）。

               

              示例 1：

              在这里插入图片描述

              输入：n = 4, rounds = [1,3,1,2]
输出：[1,2]
解释：本场马拉松比赛从扇区 1 开始。经过各个扇区的次序如下所示：
1 --> 2 --> 3（阶段 1 结束）--> 4 --> 1（阶段 2 结束）--> 2（阶段 3 结束，即本场马拉松结束）
其中，扇区 1 和 2 都经过了两次，它们是经过次数最多的两个扇区。扇区 3 和 4 都只经过了一次。

              示例 2：

              输入：n = 2, rounds = [2,1,2,1,2,1,2,1,2]
输出：[2]

              示例 3：

              输入：n = 7, rounds = [1,3,5,7]
输出：[1,2,3,4,5,6,7]

               

              提示：

              • 2 <= n <= 100
              • 1 <= m <= 100
              • rounds.length == m + 1
              • 1 <= rounds[i] <= n
              • rounds[i] != rounds[i + 1] ，其中 0 <= i < m

              解法

              Java

              class Solution {
    public List<Integer> mostVisited(int n, int[] rounds) {
        int[] ans = new int[n];
        for (int i = 0; i < rounds.length; i++) {
            rounds[i]--;
        }
        ans[rounds[0]]++;
        for (int i = 0; i < rounds.length - 1; i++) {
            int start = rounds[i];
            int end = rounds[i + 1];
            if (end <= start) {
                end += n;
            }
            for (int j = start + 1; j <= end; j++) {
                ans[j % n]++;
            }
        }
        int max = Arrays.stream(ans).max().orElse(-1);
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < ans.length; i++) {
            if (ans[i] == max) {
                list.add(i + 1);
            }
        }
        return list;
    }
}

              • 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

              1561. 你可以获得的最大硬币数目

              题目描述

              有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：

              • 每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
              • Alice 将会取走硬币数量最多的那一堆。
              • 你将会取走硬币数量第二多的那一堆。
              • Bob 将会取走最后一堆。
              • 重复这个过程，直到没有更多硬币。

              给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。

              返回你可以获得的最大硬币数目。

               

              示例 1：

              输入：piles = [2,4,1,2,7,8]
输出：9
解释：选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 7 枚硬币的那堆，Bob 取走最后一堆。
选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 2 枚硬币的那堆，Bob 取走最后一堆。
你可以获得的最大硬币数目：7 + 2 = 9.
考虑另外一种情况，如果选出的是 (1, 2, 8) 和 (2, 4, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。

              示例 2：

              输入：piles = [2,4,5]
输出：4

              示例 3：

              输入：piles = [9,8,7,6,5,1,2,3,4]
输出：18

               

              提示：

              • 3 <= piles.length <= 10^5
              • piles.length % 3 == 0
              • 1 <= piles[i] <= 10^4

              解法

              Java

              class Solution {
    public int maxCoins(int[] piles) {
        Arrays.sort(piles);
        int start = 0, end = piles.length - 1, ans = 0;
        while (start < end) {
            ans += piles[end - 1];
            start++;
            end -= 2;
        }
        return ans;
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12

              1562. 查找大小为 M 的最新分组

              题目描述

              给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。

              在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位于位置 arr[i] 的位将会设为 1 。

              给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。

              返回存在长度 恰好 为 m 的 一组 1  的最后步骤。如果不存在这样的步骤，请返回 -1 。

               

              示例 1：

              输入：arr = [3,5,1,2,4], m = 1
输出：4
解释：
步骤 1："00100"，由 1 构成的组：["1"]
步骤 2："00101"，由 1 构成的组：["1", "1"]
步骤 3："10101"，由 1 构成的组：["1", "1", "1"]
步骤 4："11101"，由 1 构成的组：["111", "1"]
步骤 5："11111"，由 1 构成的组：["11111"]
存在长度为 1 的一组 1 的最后步骤是步骤 4 。

              示例 2：

              输入：arr = [3,1,5,4,2], m = 2
输出：-1
解释：
步骤 1："00100"，由 1 构成的组：["1"]
步骤 2："10100"，由 1 构成的组：["1", "1"]
步骤 3："10101"，由 1 构成的组：["1", "1", "1"]
步骤 4："10111"，由 1 构成的组：["1", "111"]
步骤 5："11111"，由 1 构成的组：["11111"]
不管是哪一步骤都无法形成长度为 2 的一组 1 。

              示例 3：

              输入：arr = [1], m = 1
输出：1

              示例 4：

              输入：arr = [2,1], m = 2
输出：2

               

              提示：

              • n == arr.length
              • 1 <= n <= 10^5
              • 1 <= arr[i] <= n
              • arr 中的所有整数 互不相同
              • 1 <= m <= arr.length

              解法

              Java

              class Solution {
    public int findLatestStep(int[] arr, int m) {
        // 倒序遍历 arr，转换为第一次出现 m 个的步骤
        if (arr.length == m) {
            return m;
        }
        TreeSet<Integer> set = new TreeSet<>();
        set.add(0);
        set.add(arr.length + 1);
        for (int i = arr.length - 1; i >= 0; i--) {
            int index = arr[i];
            int l = set.lower(index);
            int h = set.higher(index);
            if (index - l - 1 == m || h - index - 1 == m) {
                return i;
            }
            set.add(index);
        }
        return -1;
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12
              • 13
              • 14
              • 15
              • 16
              • 17
              • 18
              • 19
              • 20
              • 21

              1566. 重复至少 K 次且长度为 M 的模式

              题目描述

              给你一个正整数数组 arr，请你找出一个长度为 m 且在数组中至少重复 k 次的模式。

              模式 是由一个或多个值组成的子数组（连续的子序列），连续 重复多次但 不重叠 。 模式由其长度和重复次数定义。

              如果数组中存在至少重复 k 次且长度为 m 的模式，则返回 true ，否则返回  false 。

               

              示例 1：

              输入：arr = [1,2,4,4,4,4], m = 1, k = 3
输出：true
解释：模式 (4) 的长度为 1 ，且连续重复 4 次。注意，模式可以重复 k 次或更多次，但不能少于 k 次。

              示例 2：

              输入：arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
输出：true
解释：模式 (1,2) 长度为 2 ，且连续重复 2 次。另一个符合题意的模式是 (2,1) ，同样重复 2 次。

              示例 3：

              输入：arr = [1,2,1,2,1,3], m = 2, k = 3
输出：false
解释：模式 (1,2) 长度为 2 ，但是只连续重复 2 次。不存在长度为 2 且至少重复 3 次的模式。

              示例 4：

              输入：arr = [1,2,3,1,2], m = 2, k = 2
输出：false
解释：模式 (1,2) 出现 2 次但并不连续，所以不能算作连续重复 2 次。

              示例 5：

              输入：arr = [2,2,2,2], m = 2, k = 3
输出：false
解释：长度为 2 的模式只有 (2,2) ，但是只连续重复 2 次。注意，不能计算重叠的重复次数。

               

              提示：

              • 2 <= arr.length <= 100
              • 1 <= arr[i] <= 100
              • 1 <= m <= 100
              • 2 <= k <= 100

              解法

              Java

              class Solution {
    public boolean containsPattern(int[] arr, int m, int k) {
        if (arr.length < m * k) {
            return false;
        }
        for (int i = 0; i <= arr.length - m * k; i++) {
            boolean match = true;
            for (int j = i + m; j < i + m * k; j++) {
                if (arr[j] != arr[j - m]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return true;
            }
        }
        return false;
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12
              • 13
              • 14
              • 15
              • 16
              • 17
              • 18
              • 19
              • 20

              1567. 乘积为正数的最长子数组长度

              题目描述

              给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。

              一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。

              请你返回乘积为正数的最长子数组长度。

               

              示例  1：

              输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。

              示例 2：

              输入：nums = [0,1,-2,-3,-4]
输出：3
解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。

              示例 3：

              输入：nums = [-1,-2,-3,0,1]
输出：2
解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。

              示例 4：

              输入：nums = [-1,2]
输出：1

              示例 5：

              输入：nums = [1,2,3,5,-6,4,0,10]
输出：4

               

              提示：

              • 1 <= nums.length <= 10^5
              • -10^9 <= nums[i] <= 10^9

              解法

              Java

              class Solution {
     public int getMaxLen(int[] nums) {
        // p[i] = n[i-1] + 1, nums[i] < 0
        // p[i] = p[i-1] + 1, nums[i] > 0
        // p[i] = 0, nums[i] = 0
        // n[i] = p[i-1] + 1, nums[i] < 0
        // n[i] = n[i-1] + 1, nums[i] > 0
        // n[i] = 0, nums[i] = 0
        int[] p = new int[nums.length];
        int[] n = new int[nums.length];
        p[0] = nums[0] > 0 ? 1 : 0;
        n[0] = nums[0] < 0 ? 1 : 0;
        int res = Math.max(p[0], 0);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > 0) {
                p[i] = p[i - 1] + 1;
                n[i] = n[i - 1] == 0 ? 0 : n[i - 1] + 1;
            } else if (nums[i] == 0) {
                p[i] = 0;
                n[i] = 0;
            } else {
                p[i] = n[i - 1] == 0 ? 0 : n[i - 1] + 1;
                n[i] = p[i - 1] + 1;
            }
            res = Math.max(res, p[i]);
        }
        return res;
    }
}

              • 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

              1569. 将子数组重新排序得到同一个二叉查找树的方案数

              题目描述

              给你一个数组 nums 表示 1 到 n 的一个排列。我们按照元素在 nums 中的顺序依次插入一个初始为空的二叉查找树（BST）。请你统计将 nums 重新排序后，统计满足如下条件的方案数：重排后得到的二叉查找树与 nums 原本数字顺序得到的二叉查找树相同。

              比方说，给你 nums = [2,1,3]，我们得到一棵 2 为根，1 为左孩子，3 为右孩子的树。数组 [2,3,1] 也能得到相同的 BST，但 [3,2,1] 会得到一棵不同的 BST 。

              请你返回重排 nums 后，与原数组 nums 得到相同二叉查找树的方案数。

              由于答案可能会很大，请将结果对 10^9 + 7 取余数。

               

              示例 1：

              在这里插入图片描述

              输入：nums = [2,1,3]
输出：1
解释：我们将 nums 重排， [2,3,1] 能得到相同的 BST 。没有其他得到相同 BST 的方案了。

              示例 2：

              在这里插入图片描述

              输入：nums = [3,4,5,1,2]
输出：5
解释：下面 5 个数组会得到相同的 BST：
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]

              示例 3：

              在这里插入图片描述

              输入：nums = [1,2,3]
输出：0
解释：没有别的排列顺序能得到相同的 BST 。

              示例 4：

              在这里插入图片描述

              输入：nums = [3,1,2,5,4,6]
输出：19

              示例  5：

              输入：nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]
输出：216212978
解释：得到相同 BST 的方案数是 3216212999。将它对 10^9 + 7 取余后得到 216212978。

               

              提示：

              • 1 <= nums.length <= 1000
              • 1 <= nums[i] <= nums.length
              • nums 中所有数 互不相同 。

              解法

              Java

              class Solution {
     int mod = (int) 1e9 + 7;
    public int numOfWays(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        return dfs(Arrays.stream(nums).boxed().collect(Collectors.toList()), calc(nums.length)) - 1;
    }
    private int dfs(List<Integer> list, int[][] c) {
        if (list.isEmpty()) {
            return 1;
        }
        List<Integer> left = list.stream().filter(n -> n < list.get(0))
                .collect(Collectors.toList());
        List<Integer> right = list.stream().filter(n -> n > list.get(0))
                .collect(Collectors.toList());
        return (int) ((long) c[list.size() - 1][left.size()] * dfs(left, c) % mod * dfs(right, c)
                % mod);
    }
    private int[][] calc(int n) {
        int[][] c = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    c[i][j] = 1;
                } else {
                    c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
                }
            }
        }
        return 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
              • 28
              • 29
              • 30
              • 31
              • 32
              • 33

              1572. 矩阵对角线元素的和

              题目描述

              给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。

              请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。

               

              示例  1：

              在这里插入图片描述

              输入：mat = [[1,2,3],
            [4,5,6],
            [7,8,9]]
输出：25
解释：对角线的和为：1 + 5 + 9 + 3 + 7 = 25
请注意，元素 mat[1][1] = 5 只会被计算一次。

              示例  2：

              输入：mat = [[1,1,1,1],
            [1,1,1,1],
            [1,1,1,1],
            [1,1,1,1]]
输出：8

              示例 3：

              输入：mat = [[5]]
输出：5

               

              提示：

              • n == mat.length == mat[i].length
              • 1 <= n <= 100
              • 1 <= mat[i][j] <= 100

              解法

              Java

              class Solution {
    public int diagonalSum(int[][] mat) {
        int sum = 0, n = mat.length, mid = n >> 1;
        for (int i = 0, j = n - 1; i < n; i++, j--) {
            sum += (mat[i][i] + mat[i][j]);
        }
        return n % 2 == 0 ? sum : sum - mat[mid][mid];
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9

              1573. 分割字符串的方案数

              题目描述

              给你一个二进制串 s  （一个只包含 0 和 1 的字符串），我们可以将 s 分割成 3 个 非空 字符串 s1, s2, s3 （s1 + s2 + s3 = s）。

              请你返回分割 s 的方案数，满足 s1，s2 和 s3 中字符 '1' 的数目相同。

              由于答案可能很大，请将它对 10^9 + 7 取余后返回。

               

              示例 1：

              输入：s = "10101"
输出：4
解释：总共有 4 种方法将 s 分割成含有 '1' 数目相同的三个子字符串。
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"

              示例 2：

              输入：s = "1001"
输出：0

              示例 3：

              输入：s = "0000"
输出：3
解释：总共有 3 种分割 s 的方法。
"0|0|00"
"0|00|0"
"00|0|0"

              示例 4：

              输入：s = "100100010100110"
输出：12

               

              提示：

              • s[i] == '0' 或者 s[i] == '1'
              • 3 <= s.length <= 10^5

              解法

              Java

              class Solution {
    public int numWays(String s) {
        char[] chars = s.toCharArray();
        List<Long> p = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '1') {
                p.add((long) i);
            }
        }
        int l = p.size();
        if (l % 3 != 0) {
            return 0;
        }
        int MOD = (int) (1e9 + 7);
        if (l == 0) {
            return (int) (((long) (s.length() - 1) * (s.length() - 2) / 2) % MOD);
        }
        // 每 n/3 的地方为分界线
        return (int) ((p.get(l / 3) - p.get(l / 3 - 1)) * (p.get(2 * l / 3) - p.get(2 * l / 3 - 1))
                % MOD);
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12
              • 13
              • 14
              • 15
              • 16
              • 17
              • 18
              • 19
              • 20
              • 21
              • 22

              1578. 避免重复字母的最小删除成本

              题目描述

              给你一个字符串 s 和一个整数数组 cost ，其中 cost[i] 是从 s 中删除字符 i 的代价。

              返回使字符串任意相邻两个字母不相同的最小删除成本。

              请注意，删除一个字符后，删除其他字符的成本不会改变。

               

              示例 1：

              输入：s = "abaac", cost = [1,2,3,4,5]
输出：3
解释：删除字母 "a" 的成本为 3，然后得到 "abac"（字符串中相邻两个字母不相同）。

              示例 2：

              输入：s = "abc", cost = [1,2,3]
输出：0
解释：无需删除任何字母，因为字符串中不存在相邻两个字母相同的情况。

              示例 3：

              输入：s = "aabaa", cost = [1,2,3,4,1]
输出：2
解释：删除第一个和最后一个字母，得到字符串 ("aba") 。

               

              提示：

              • s.length == cost.length
              • 1 <= s.length, cost.length <= 10^5
              • 1 <= cost[i] <= 10^4
              • s 中只含有小写英文字母

              解法

              Java

              class Solution {
    public int minCost(String s, int[] cost) {
        int res = 0;
        char[] word = s.toCharArray();
        for(int i = 0;i < word.length;i++){
            char c = word[i];
            int max = cost[i];
            int sum = max;
            while(i + 1 < word.length && word[i + 1] == c){
                sum += cost[++i];
                max = Math.max(max,cost[i]);
            }
            if(sum != max){
                res += sum - max;
            }
        }
        return res;
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12
              • 13
              • 14
              • 15
              • 16
              • 17
              • 18
              • 19

              1579. 保证图可完全遍历

              题目描述

              Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3  种类型的边：

              • 类型 1：只能由 Alice 遍历。
              • 类型 2：只能由 Bob 遍历。
              • 类型 3：Alice 和 Bob 都可以遍历。

              给你一个数组 edges ，其中 edges[i] = [typei, ui, vi] 表示节点 ui 和 vi 之间存在类型为 typei 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。

              返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。

               

              示例 1：

              在这里插入图片描述

              输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
输出：2
解释：如果删除 [1,1,2] 和 [1,1,3] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。再删除任何其他的边都无法保证图可以完全遍历。所以可以删除的最大边数是 2 。

              示例 2：

              在这里插入图片描述

              输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
输出：0
解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。

              示例 3：

              在这里插入图片描述

              输入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
输出：-1
解释：在当前图中，Alice 无法从其他节点到达节点 4 。类似地，Bob 也不能达到节点 1 。因此，图无法完全遍历。

               

              提示：

              • 1 <= n <= 10^5
              • 1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)
              • edges[i].length == 3
              • 1 <= edges[i][0] <= 3
              • 1 <= edges[i][1] < edges[i][2] <= n
              • 所有元组 (typei, ui, vi) 互不相同

              解法

              Java

              class Solution {
    // https://oi-wiki.org/ds/dsu/#_3
    private boolean[] used;
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        used = new boolean[edges.length];
        // type 为倒序，3, 2, 1
        Arrays.sort(edges, (a, b) -> Integer.compare(b[0], a[0]));
        if (!unionFind(n, edges, 1)) return -1;
        if (!unionFind(n, edges, 2)) return -1;
        int result = 0;
        for (boolean u : used) {
            result += u ? 0 : 1;
        }
        return result;
    }
    private boolean unionFind(int n, int[][] edges, int excludedType) {
        int[] union = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            union[i] = i;
        }
        int cnt = 0;
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            if (edge[0] == excludedType) continue;
            int rootA = findRoot(union, edge[1]);
            int rootB = findRoot(union, edge[2]);
            if (rootA != rootB) {
                cnt += 1;
                union[rootA] = rootB;
                used[i] = true;
            }
            if (cnt == n - 1) return true;
        }
        return false;
    }
    private int findRoot(int[] union, int idx) {
        if (union[idx] != idx) {
            int root = findRoot(union, union[idx]);
            union[idx] = root;
            return root;
        }
        return idx;
    }
}

              • 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

              1582. 二进制矩阵中的特殊位置

              题目描述

              给你一个大小为 rows x cols 的矩阵 mat，其中 mat[i][j] 是 0 或 1，请返回 矩阵 mat 中特殊位置的数目 。

              特殊位置 定义：如果 mat[i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均为 0（行和列的下标均 从 0 开始 ），则位置 (i, j) 被称为特殊位置。

               

              示例 1：

              输入：mat = [[1,0,0],
            [0,0,1],
            [1,0,0]]
输出：1
解释：(1,2) 是一个特殊位置，因为 mat[1][2] == 1 且所处的行和列上所有其他元素都是 0

              示例 2：

              输入：mat = [[1,0,0],
            [0,1,0],
            [0,0,1]]
输出：3
解释：(0,0), (1,1) 和 (2,2) 都是特殊位置

              示例 3：

              输入：mat = [[0,0,0,1],
            [1,0,0,0],
            [0,1,1,0],
            [0,0,0,0]]
输出：2

              示例 4：

              输入：mat = [[0,0,0,0,0],
            [1,0,0,0,0],
            [0,1,0,0,0],
            [0,0,1,0,0],
            [0,0,0,1,1]]
输出：3

               

              提示：

              • rows == mat.length
              • cols == mat[i].length
              • 1 <= rows, cols <= 100
              • mat[i][j] 是 0 或 1

              解法

              Java

              class Solution {
    public int numSpecial(int[][] mat) {
        int rows = mat.length;
        int cols = mat[0].length;
        
        int[] rows1 = new int[rows];
        int[] cols1 = new int[cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (mat[i][j] == 1) {
                    rows1[i]++;
                    cols1[j]++;
                }
            }
        }
        
        int ans = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (mat[i][j] == 1 && rows1[i] == 1 && cols1[j] == 1) {
                    ans ++;
                } 
            }
        }
        
        return ans;
    }
}

              • 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

              1583. 统计不开心的朋友

              题目描述

              给你一份 n 位朋友的亲近程度列表，其中 n 总是 偶数 。

              对每位朋友 i，preferences[i] 包含一份 按亲近程度从高到低排列 的朋友列表。换句话说，排在列表前面的朋友与 i 的亲近程度比排在列表后面的朋友更高。每个列表中的朋友均以 0 到 n-1 之间的整数表示。

              所有的朋友被分成几对，配对情况以列表 pairs 给出，其中 pairs[i] = [xi, yi] 表示 xi 与 yi 配对，且 yi 与 xi 配对。

              但是，这样的配对情况可能会是其中部分朋友感到不开心。在 x 与 y 配对且 u 与 v 配对的情况下，如果同时满足下述两个条件，x 就会不开心：

              • x 与 u 的亲近程度胜过 x 与 y，且
              • u 与 x 的亲近程度胜过 u 与 v

              返回 不开心的朋友的数目 。

               

              示例 1：

              输入：n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]]
输出：2
解释：
朋友 1 不开心，因为：
- 1 与 0 配对，但 1 与 3 的亲近程度比 1 与 0 高，且
- 3 与 1 的亲近程度比 3 与 2 高。
朋友 3 不开心，因为：
- 3 与 2 配对，但 3 与 1 的亲近程度比 3 与 2 高，且
- 1 与 3 的亲近程度比 1 与 0 高。
朋友 0 和 2 都是开心的。

              示例 2：

              输入：n = 2, preferences = [[1], [0]], pairs = [[1, 0]]
输出：0
解释：朋友 0 和 1 都开心。

              示例 3：

              输入：n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]]
输出：4

               

              提示：

              • 2 <= n <= 500
              • n 是偶数
              • preferences.length == n
              • preferences[i].length == n - 1
              • 0 <= preferences[i][j] <= n - 1
              • preferences[i] 不包含 i
              • preferences[i] 中的所有值都是独一无二的
              • pairs.length == n/2
              • pairs[i].length == 2
              • xi != yi
              • 0 <= xi, yi <= n - 1
              • 每位朋友都 恰好 被包含在一对中

              解法

              Java

              class Solution {
    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] pair : pairs) {
            calcBetter(preferences[pair[0]], map, pair[0], pair[1]);
            calcBetter(preferences[pair[1]], map, pair[1], pair[0]);
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < pairs.length; i++) {
            for (int j = i + 1; j < pairs.length; j++) {
                if (unhappy(pairs[i][0], pairs[j][0], map)) {
                    set.add(pairs[i][0]);
                    set.add(pairs[j][0]);
                }
                if (unhappy(pairs[i][1], pairs[j][0], map)) {
                    set.add(pairs[i][1]);
                    set.add(pairs[j][0]);
                }
                if (unhappy(pairs[i][0], pairs[j][1], map)) {
                    set.add(pairs[i][0]);
                    set.add(pairs[j][1]);
                }
                if (unhappy(pairs[i][1], pairs[j][1], map)) {
                    set.add(pairs[i][1]);
                    set.add(pairs[j][1]);
                }
            }
        }
        return set.size();
    }
    private void calcBetter(int[] preference, Map<Integer, Set<Integer>> map, int from, int to) {
        Set<Integer> betterSet = new HashSet<>();
        for (int i : preference) {
            if (i == to) {
                break;
            }
            betterSet.add(i);
        }
        map.put(from, betterSet);
    }
    private boolean unhappy(int x, int y, Map<Integer, Set<Integer>> map) {
        return map.get(x).contains(y) && map.get(y).contains(x);
    }
}

              • 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

              1584. 连接所有点的最小费用

              题目描述

              给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。

              连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。

              请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

               

              示例 1：

              在这里插入图片描述

              输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：

我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。

              在这里插入图片描述

              示例 2：

              输入：points = [[3,12],[-2,5],[-4,1]]
输出：18

              示例 3：

              输入：points = [[0,0],[1,1],[1,0],[-1,1]]
输出：4

              示例 4：

              输入：points = [[-1000000,-1000000],[1000000,1000000]]
输出：4000000

              示例 5：

              输入：points = [[0,0]]
输出：0

               

              提示：

              • 1 <= points.length <= 1000
              • -106 <= xi, yi <= 106
              • 所有点 (xi, yi) 两两不同。

              解法

              Java

              class Solution {
    static class Edge {
        int x;
        int y;
        int len;
        Edge(int x, int y, int len) {
            this.x = x;
            this.y = y;
            this.len = len;
        }
    }
    public int minCostConnectPoints(int[][] points) {
        Queue<Edge> heap = new PriorityQueue<>(Comparator.comparingInt((Edge e) -> e.len));
        boolean[] marked = new boolean[points.length];
        marked[0] = true;
        addVertex(points, marked, 0, heap);
        int count = 1;
        int res = 0;
        while (!heap.isEmpty()) {
            Edge edge = heap.poll();
            if (!marked[edge.y]) {
                res += edge.len;
                marked[edge.y] = true;
                addVertex(points, marked, edge.y, heap);
                count++;
                if (count == points.length) {
                    break;
                }
            }
        }
        return res;
    }
    public void addVertex(int[][] points, boolean[] marked, int x, Queue<Edge> heap) {
        for (int i = 0; i < marked.length; i++) {
            if (marked[i]) {
                continue;
            }
            heap.add(new Edge(x, i,
                    Math.abs(points[x][0] - points[i][0]) + Math.abs(points[x][1] - points[i][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

              1588. 所有奇数长度子数组的和

              题目描述

              给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

              子数组 定义为原数组中的一个连续子序列。

              请你返回 arr 中 所有奇数长度子数组的和 。

               

              示例 1：

              输入：arr = [1,4,2,5,3]
输出：58
解释：所有奇数长度子数组和它们的和为：
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

              示例 2：

              输入：arr = [1,2]
输出：3
解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。

              示例 3：

              输入：arr = [10,11,12]
输出：66

               

              提示：

              • 1 <= arr.length <= 100
              • 1 <= arr[i] <= 1000

              解法

              Java

              class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int[] sum = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            sum[i] = (i != 0 ? sum[i - 1] : 0) + arr[i];
        }
        int ans = 0;
        // sum[b] - sum[a] 为 (a,b] 的和
        for (int i = 0; i < arr.length; i++) {
            ans += arr[i];
            for (int j = i + 2; j < arr.length; j += 2) {
                // [i, j]
                ans += sum[j] - sum[i] + arr[i];
            }
        }
        return ans;
    }
}

              • 1
              • 2
              • 3
              • 4
              • 5
              • 6
              • 7
              • 8
              • 9
              • 10
              • 11
              • 12
              • 13
              • 14
              • 15
              • 16
              • 17
              • 18
              声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/117812
              推荐阅读
              相关标签

              Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

                

              闽ICP备14008679号