131 篇博文 含有标签「数组」

1、题干​

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。

花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n] 。

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i -  ranges[i], i + ranges[i]] 。

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。

示例 1：

输入：n = 5, ranges = [3,4,1,1,0,0]
输出：1
解释：
点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。

示例 2：

输入：n = 3, ranges = [0,0,0,0]
输出：-1
解释：即使打开所有水龙头，你也无法灌溉整个花园。

提示：

• 1 <= n <= 104
• ranges.length == n + 1
• 0 <= ranges[i] <= 100

写了个奇怪的动态规划思路

2、思路​

用 [i-r,i) 区间的最少水龙头数更新 dp[i]，用 dp[i] 更新 (i,i+r] 区间的最少水龙头数。

dp 数组元素有正负两种状态，正数表示自身可以达到最少水龙头数，负数表示被其他水龙头覆盖达到最少水龙头数；负数在更新 (i,i+r] 区间时需要 +1，正数则不需要。

3、代码​

function minTaps(n: number, ranges: number[]): number {
    const dp = ranges.map(() => Infinity);

    for (let i = 0, r = 0; i <= n; i++) {
        r = ranges[i];
        if (i - r < 1) dp[i] = 1;

        for (let j = Math.max(0, i - r); j <= Math.min(n, i + r); j++) {
            const di = Math.abs(dp[i]), dj = Math.abs(dp[j]);
            if (j < i && dj + 1 <= di) dp[i] = dj + 1;
            else if (j > i) {
                if (dp[i] > 0 && di <= dj) dp[j] = -di;
                else if (dp[i] <= 0 && di + 1 <= dj) dp[j] = -di - 1;
            }
        }
    }

    return dp.at(-1) < Infinity ? Math.abs(dp.at(-1)) : -1;
};

4、复杂度​

• 时间复杂度：$O(mn)$
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

给你一个整数数组 ranks 和一个字符数组 suit 。你有 5 张扑克牌，第 i 张牌大小为 ranks[i] ，花色为 suits[i] 。

下述是从好到坏你可能持有的 手牌类型 ：

1. "Flush"：同花，五张相同花色的扑克牌。
2. "Three of a Kind"：三条，有 3 张大小相同的扑克牌。
3. "Pair"：对子，两张大小一样的扑克牌。
4. "High Card"：高牌，五张大小互不相同的扑克牌。

请你返回一个字符串，表示给定的 5 张牌中，你能组成的 最好手牌类型 。

注意：返回的字符串 大小写 需与题目描述相同。

示例 1：

输入：ranks = [13,2,3,1,9], suits = ["a","a","a","a","a"]
输出："Flush"
解释：5 张扑克牌的花色相同，所以返回 "Flush" 。

示例 2：

输入：ranks = [4,4,2,4,4], suits = ["d","a","a","b","c"]
输出："Three of a Kind"
解释：第一、二和四张牌组成三张相同大小的扑克牌，所以得到 "Three of a Kind" 。
注意我们也可以得到 "Pair" ，但是 "Three of a Kind" 是更好的手牌类型。
有其他的 3 张牌也可以组成 "Three of a Kind" 手牌类型。

示例 3：

输入：ranks = [10,10,2,12,9], suits = ["a","b","c","a","d"]
输出："Pair"
解释：第一和第二张牌大小相同，所以得到 "Pair" 。
我们无法得到 "Flush" 或者 "Three of a Kind" 。

提示：

• ranks.length == suits.length == 5
• 1 <= ranks[i] <= 13
• 'a' <= suits[i] <= 'd'
• 任意两张扑克牌不会同时有相同的大小和花色。

2、思路​

结果总共4种情况，可以分类讨论：

• 首先判断花色，全部相同则为同花 Flush
• 对 ranks 排序，遍历检查 ranks 属于其他哪种情况
• 若大小全不同，则为高牌 High Card
• 若有3张相同，则为三条 Three of a Kind
• 最后只剩对子 Pair 这一种可能

3、代码​

function bestHand(ranks: number[], suits: string[]): string {
    if (suits.every(s => s === suits[0])) return 'Flush';

    ranks.sort((a, b) => a - b);
    if (ranks.every((r, i) => r !== ranks[i - 1])) return 'High Card';

    if (ranks.some((r, i) => r === ranks[i - 1] && r === ranks[i + 1])) return 'Three of a Kind';

    return 'Pair';
};

4、复杂度​

• 时间复杂度：$O(C)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。

示例 1：

输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。

示例 2：

输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485

提示：

• 1 <= classes.length <= 105
• classes[i].length == 2
• 1 <= passi <= totali <= 105
• 1 <= extraStudents <= 105

2、思路​

这题思路比较容易想到，先用优先队列存储各个班级通过率 classes，优先队列排序逻辑是：假设这个班引入1个逢考必过的学霸 extraStudents 后通过率增长越多排序越靠前。

接着每次安排1个学霸进入通过率增长最多的班级，计算该班级通过率增长值并累加到最初的总通过率 rate，最后求平均就能得到最大平均通过率。

3、代码​

function maxAverageRatio(classes: number[][], c: number): number {
    const pq = new PriorityQueue({
        compare: (a: number[], b: number[]): number => {
            const da = (a[0] + 1) / (a[1] + 1) - a[0] / a[1];
            const db = (b[0] + 1) / (b[1] + 1) - b[0] / b[1];
            return db - da;
        }
    });

    let rate = 0;
    for (let i = 0; i < classes.length; i++) {
        pq.enqueue(classes[i]);
        rate += classes[i][0] / classes[i][1];
    }

    for (; c; c--) {
        const t = pq.dequeue();
        pq.enqueue([t[0] + 1, t[1] + 1]);
        rate += (t[0] + 1) / (t[1] + 1) - t[0] / t[1];
    }

    return rate / classes.length;
};

4、复杂度​

• 时间复杂度：$O(nlogn)$
• 时间复杂度：$O(n)$

5、执行结果​

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

2、思路​

纯模拟，毫无技巧，全是感情🤡

遍历网格，以当前网格单元作为正方形左上顶点，先求出左上两条边长的最大可能值，再验证右下两条边是否满足要求。

优化代码又折腾了一番，速度得到一些提升，从最快 88ms 达到最快 68ms。

主要优化在于检查边长的时候，由于是正方形可以同时检查两条边。做法是固定起始位置，然后改变边长，两条边同时满足要求时才往下遍历。

3、代码​

function largest1BorderedSquare(grid: number[][]): number {
    let maxLen = 0;
    const m = grid.length, n = grid[0].length;

    for (let i = 0; i < m - maxLen; i++) {
        for (let j = 0; j < n - maxLen; j++) {
            if (!grid[i][j]) continue;

            let len = 1;
            while (grid[i][j + len] && grid[i + len]?.at(j)) len++;

            for (; len > maxLen; len--) {
                let step = 1, ei = i + len - 1, ej = j + len - 1;
                while (step < len && grid[i + step][ej] && grid[ei][j + step]) step++;

                if (step === len) maxLen = len;
            }
        }
    }

    return maxLen ** 2;
};

下面是最开始的代码，可以对照看看

function largest1BorderedSquare(grid: number[][]): number {
    let maxLen = 0;
    const m = grid.length, n = grid[0].length;

    for (let i = 0; i < m - maxLen; i++) {
        for (let j = 0; j < n - maxLen; j++) {
            if (!grid[i][j]) continue;

            let si = i + 1, sj = j + 1;
            while (si < m && grid[si]?.at(j)) si++;
            while (sj < n && grid[i][sj]) sj++;

            let len = Math.min(si - i, sj - j);
            for (; len > maxLen; len--) {
                let ei = i + len - 1, ej = j + len - 1;
                while (ei > i && grid[ei][j + len - 1]) ei--;
                while (ej > j && grid[i + len - 1][ej]) ej--;

                if (ei === i && ej === j) maxLen = Math.max(maxLen, len);
            }
        }
    }

    return maxLen ** 2;
};

4、复杂度​

• 时间复杂度：最差$O(n^4)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以执行以下步骤：

• 从 nums 选出 两个 相等的 整数
• 从 nums 中移除这两个整数，形成一个 数对

请你在 nums 上多次执行此操作直到无法继续执行。

返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案，其中 answer[0] 是形成的数对数目，answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。

示例 1：

输入：nums = [1,3,2,1,3,2,2]
输出：[3,1]
解释：
nums[0] 和 nums[3] 形成一个数对，并从 nums 中移除，nums = [3,2,3,2,2] 。
nums[0] 和 nums[2] 形成一个数对，并从 nums 中移除，nums = [2,2,2] 。
nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [2] 。
无法形成更多数对。总共形成 3 个数对，nums 中剩下 1 个数字。

示例 2：

输入：nums = [1,1]
输出：[1,0]
解释：nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [] 。
无法形成更多数对。总共形成 1 个数对，nums 中剩下 0 个数字。

示例 3：

输入：nums = [0]
输出：[0,1]
解释：无法形成数对，nums 中剩下 1 个数字。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

2、思路​

假设所求结果为数组 ans，ans[0] 表示数对数目，ans[1] 表示剩下的整数数目。

遍历 nums 数组并对每个整数计数，当某个整数个数为奇数时 ans[1]+=1，反之 ans[1]-=1 且 ans[0]+=1。

3、代码​

function numberOfPairs(nums: number[]): number[] {
    const ans = [0, 0], bucket = new Array(101).fill(0);

    for (let i = 0; i < nums.length; i++) {
        bucket[nums[i]] += 1;
        ans[0] += bucket[nums[i]] % 2 ? 0 : 1;
        ans[1] += bucket[nums[i]] % 2 ? 1 : -1;
    }

    return ans;
};

4、复杂度​

• 时间复杂：$O(n)$
• 空间复杂：$O(C)$

5、执行结果​

1、题干​

给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。

假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。

示例 1：

输入：nums = [12,5,7,23]
输出：true
解释：挑选数字 5 和 7。
5*3 + 7*(-2) = 1

示例 2：

输入：nums = [29,6,10]
输出：true
解释：挑选数字 29, 6 和 10。
29*1 + 6*(-3) + 10*(-1) = 1

示例 3：

输入：nums = [3,6]
输出：false

提示：

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

2、思路​

这不是我能写出来的题，看了提示才AC

根据提示，要求所有数字的最大公约数是否等于1。想到的思路是：先升序排序 nums 数组，如果存在相邻数字的最大公约数 gi 等于1，或者 gi 与 gcd(nums[0],nums[1]) 的最大公约数等于1，那么 nums 是一个好数组。虽然过了，但无法证明算法正确性

3、代码​

function isGoodArray(nums: number[]): boolean {
    nums.sort((a, b) => a - b);
    const gcd = (a: number, b: number) => a ? gcd(b % a, a) : b;

    const g1 = gcd(nums[0], nums[1] || 0);

    for (let i = 1; i < nums.length; i++) {
        const gi = gcd(nums[i], nums[i + 1]);
        if (gi === 1 || gcd(g1, gi) === 1) return true;
    }

    return g1 === 1;
};

官解根据裴蜀定理推论和证明，严谨很多，代码也不难。整体思路也是求所有数字的最大公约数是否等于1

function isGoodArray(nums: number[]): boolean {
    let d = nums[0];
    const gcd = (a: number, b: number) => a ? gcd(b % a, a) : b;

    for (let i = 0; i < nums.length && d !== 1; i++) {
        d = gcd(d, nums[i]);
    }

    return d === 1;
};

4、复杂度​

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(logn)$

5、执行结果​

1、题干​

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

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

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

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

示例 1：

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

示例 2：

输入：hours = [6,6,6]
输出：0

提示：

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

2、思路-前缀和+哈希表​

• 计算 hours 的前缀和数组 sums，当 hours[i] 大于 8 时前缀和 +1 否则 -1
• 将 sums[i] 与 i 分别作为键值存入哈希表 map；为保证结果时段最大，仅当哈希表中不存在 sums[i] 时才存入该键值对
• 如果 sums[i] 大于 0，则区间 [0,i] 可能是最长时段
• 如果 sums[i] 小于等于 0，则区间 [map.get(sums[i] - 1),i) 也可能是最长时段
• 所有备选时段长度的最大值即所求的最长时段

这题的前缀和在整数范围上具有连续性，所以能用哈希表

3、代码​

function longestWPI(hours: number[]): number {
    const sums = hours.map(() => 0);
    const map = new Map();

    let ans = 0;
    for (let i = 0; i < hours.length; i++) {
        sums[i] = (sums[i - 1] || 0) + (hours[i] > 8 ? 1 : -1);
        if (sums[i] > 0) ans = Math.max(ans, i + 1);
        else {
            if (map.has(sums[i] - 1)) ans = Math.max(ans, i - map.get(sums[i] - 1));
        }

        if (!map.has(sums[i])) map.set(sums[i], i);
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

6、前缀和+栈​

这个思路是我能写出来的吗

function longestWPI(hours: number[]): number {
    const sums = hours.map(() => 0);
    const minStack = [0];

    let ans = 0;
    for (let i = 0; i < hours.length; i++) {
        sums[i] = (sums[i - 1] || 0) + (hours[i] > 8 ? 1 : -1);
        if (sums[i] > 0) ans = Math.max(ans, i + 1);
        if (sums[i] < sums[minStack.at(-1)]) minStack.push(i);
    }

    for (let i = hours.length - 1; i > -1; i--) {
        while (sums[minStack.at(-1)] < sums[i]) {
            const l = minStack.pop();
            ans = Math.max(ans, i - l);
        }
    }

    return ans;
};

1、题干​

存在一种仅支持 4 种操作和 1 个变量 X 的编程语言：

• ++X 和 X++ 使变量 X 的值 加 1
• --X 和 X-- 使变量 X 的值 减 1

最初，X 的值是 0

给你一个字符串数组 operations ，这是由操作组成的一个列表，返回执行所有操作后， X 的 最终值 。

示例 1：

输入：operations = ["--X","X++","X++"]
输出：1
解释：操作按下述步骤执行：
最初，X = 0
--X：X 减 1 ，X =  0 - 1 = -1
X++：X 加 1 ，X = -1 + 1 =  0
X++：X 加 1 ，X =  0 + 1 =  1

示例 2：

输入：operations = ["++X","++X","X++"]
输出：3
解释：操作按下述步骤执行： 
最初，X = 0
++X：X 加 1 ，X = 0 + 1 = 1
++X：X 加 1 ，X = 1 + 1 = 2
X++：X 加 1 ，X = 2 + 1 = 3

示例 3：

输入：operations = ["X++","++X","--X","X--"]
输出：0
解释：操作按下述步骤执行：
最初，X = 0
X++：X 加 1 ，X = 0 + 1 = 1
++X：X 加 1 ，X = 1 + 1 = 2
--X：X 减 1 ，X = 2 - 1 = 1
X--：X 减 1 ，X = 1 - 1 = 0

提示：

• 1 <= operations.length <= 100
• operations[i] 将会是 "++X"、"X++"、"--X" 或 "X--"

2、思路​

模拟

3、代码​

function finalValueAfterOperations(operations: string[]): number {
    let ans = 0;
    for (const o of operations) {
        ans += o.includes('+') ? 1 : -1;
    }
    return ans;
};

4、复杂度​

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

5、执行结果​

1、题干​

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。

给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。

示例 1：

输入：amount = [1,4,2]
输出：4
解释：下面给出一种方案：
第 1 秒：装满一杯冷水和一杯温水。
第 2 秒：装满一杯温水和一杯热水。
第 3 秒：装满一杯温水和一杯热水。
第 4 秒：装满一杯温水。
可以证明最少需要 4 秒才能装满所有杯子。

示例 2：

输入：amount = [5,4,4]
输出：7
解释：下面给出一种方案：
第 1 秒：装满一杯冷水和一杯热水。
第 2 秒：装满一杯冷水和一杯温水。
第 3 秒：装满一杯冷水和一杯温水。
第 4 秒：装满一杯温水和一杯热水。
第 5 秒：装满一杯冷水和一杯热水。
第 6 秒：装满一杯冷水和一杯温水。
第 7 秒：装满一杯热水。

示例 3：

输入：amount = [5,0,0]
输出：5
解释：每秒装满一杯冷水。

提示：

• amount.length == 3
• 0 <= amount[i] <= 100

2、思路​

假设杯子数量从少到多分别为 min、mid、max，首先得装满最多的杯子，因此存在两种情况：

• min + mid <= max，这种情况只需要 max 秒钟就能装满所有杯子
• min + mid > max，先装满最多的杯子，需要 max 秒钟
  • 另外两种杯子会剩余 min + mid - max 个，剩余杯子可能为奇数也可能为偶数，但两种杯子差值最多为 1，所以还需要 Math.ceil((mid + min - max) / 2) 秒钟

3、代码​

function fillCups(amount: number[]): number {
    const [min, mid, max] = amount.sort((a, b) => a - b);
    if (min + mid <= max) return max;
    return max + Math.ceil((mid + min - max) / 2);
};

4、复杂度​

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。

• 例如，"/leetcode" 和 "/leetcode/problems" 都是有效的路径，而空字符串和 "/" 不是。

示例 1：

输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释："/a/b" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。

示例 2：

输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d" 都会被删除，因为它们都是 "/a" 的子文件夹。

示例 3：

输入: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
输出: ["/a/b/c","/a/b/ca","/a/b/d"]

提示：

• 1 <= folder.length <= 4 * 104
• 2 <= folder[i].length <= 100
• folder[i] 只包含小写字母和 '/'
• folder[i] 总是以字符 '/' 起始
• folder 每个元素都是 唯一 的

2、思路1-排序​

• 对文件夹数组 folder 升序排序，初始化父文件夹 pf = folder[0] + '/'
• 遍历检查所有文件夹 folder[i] 与当前父文件夹 pf 是否父子关系，是则说明 folder[i] 是子文件夹，不是则将 folder[i] 置为父文件夹继续检查

3、代码​

function removeSubfolders(folder: string[]): string[] {
    folder.sort();

    const ans = [folder[0]];
    let pf = folder[0] + '/';

    for (let i = 1; i < folder.length; i++) {
        if (!folder[i].startsWith(pf)) {
            ans.push(folder[i]);
            pf = folder[i] + '/';
        }
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(nm*logn)$
• 空间复杂度：$O(logn)$

5、执行结果​

6、思路2-哈希​

将 folder 数组中所有文件夹存入哈希集合 set，遍历检查文件夹 folder[i] 所有前缀路径，若前缀路径存在于 set 中，则说明 folder[i] 是子文件夹

7、代码​

function removeSubfolders(folder: string[]): string[] {
    const ans = [], set = new Set(folder);

    for (const f of folder) {
        let found = false;

        for (let i = 0; i < f.length;) {
            i = f.indexOf('/', i + 1);
            if (i < 0) break;

            const dir = f.slice(0, i);

            if (set.has(dir)) {
                found = true;
                break;
            }
        }

        if (!found) ans.push(f);
    }

    return ans;
};

8、复杂度​

• 时间复杂度：$O(nm)$
• 空间复杂度：$O(nm)$

9、执行结果​