【题解】—— LeetCode一周小结24

简介: LeetCode每日一道一周小结24

🌟欢迎来到 我的博客 —— 探索技术的无限可能!

🌟博客的简介(文章目录)


【题解】—— 每日一道题目栏


上接:【题解】—— LeetCode一周小结23

10.救生艇

题目链接:881. 救生艇

给定数组 people 。people[i]表示第 i 个人的体重 ,船的数量不限,每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

示例 1:

输入:people = [1,2], limit = 3

输出:1

解释:1 艘船载 (1, 2)

示例 2:

输入:people = [3,2,2,1], limit = 3

输出:3

解释:3 艘船分别载 (1, 2), (2) 和 (3)

示例 3:

输入:people = [3,5,3,4], limit = 5

输出:4

解释:4 艘船分别载 (3), (3), (4), (5)

提示:

1 <= people.length <= 5 * 104

1 <= people[i] <= limit <= 3 * 104

题解:

方法:贪心

       

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int ans = 0;
        for (int i = 0, j = people.length - 1; i <= j; --j) {
            if (people[i] + people[j] <= limit) {
                ++i;
            }
            ++ans;
        }
        return ans;
    }
}

11.甲板上的战舰

题目链接:419. 甲板上的战舰

给你一个大小为 m x n 的矩阵 board 表示甲板,其中,每个单元格可以是一艘战舰 ‘X’ 或者是一个空位 ‘.’ ,返回在甲板 board 上放置的 战舰 的数量。

战舰 只能水平或者垂直放置在 board 上。换句话说,战舰只能按 1 x k(1 行,k 列)或 k x 1(k 行,1 列)的形状建造,其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 (即没有相邻的战舰)。

示例 1:

输入:board = [[“X”,“.”,“.”,“X”],[“.”,“.”,“.”,“X”],[“.”,“.”,“.”,“X”]]

输出:2

示例 2:

输入:board = [[“.”]]

输出:0

提示:

m == board.length

n == board[i].length

1 <= m, n <= 200

board[i][j] 是 ‘.’ 或 ‘X’

进阶:你可以实现一次扫描算法,并只使用 O(1) 额外空间,并且不修改 board 的值来解决这个问题吗?

题解:

方法:遍历

       

class Solution {
    public int countBattleships(char[][] board) {
        int m = board.length, n = board[0].length;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && board[i - 1][j] == 'X') continue;
                if (j > 0 && board[i][j - 1] == 'X') continue;
                if (board[i][j] == 'X') ans++;
            }
        }
        return ans;
    }
}

12.取整购买后的账户余额

题目链接:2806. 取整购买后的账户余额

一开始,你的银行账户里有 100 块钱。

给你一个整数purchaseAmount ,它表示你在一次购买中愿意支出的金额。

在一个商店里,你进行一次购买,实际支出的金额会向 最近 的 10 的 倍数 取整。换句话说,你实际会支付一个 非负 金额 roundedAmount ,满足 roundedAmount 是 10 的倍数且 abs(roundedAmount - purchaseAmount) 的值 最小 。

如果存在多于一个最接近的 10 的倍数,较大的倍数 是你的实际支出金额。

请你返回一个整数,表示你在愿意支出金额为 purchaseAmount 块钱的前提下,购买之后剩下的余额。

注意: 0 也是 10 的倍数。

示例 1:

输入:purchaseAmount = 9

输出:90

解释:这个例子中,最接近 9 的 10 的倍数是 10 。所以你的账户余额为 100 - 10 = 90 。

示例 2:

输入:purchaseAmount = 15

输出:80

解释:这个例子中,有 2 个最接近 15 的 10 的倍数:10 和 20,较大的数 20 是你的实际开销。 所以你的账户余额为 100 -

20 = 80 。

提示:

0 <= purchaseAmount <= 100

题解:

方法:数学

       枚举 + 模拟

class Solution {
    public int accountBalanceAfterPurchase(int purchaseAmount) {
        int diff = 100, x = 0;
        for (int y = 100; y >= 0; y -= 10) {
            int t = Math.abs(y - purchaseAmount);
            if (t < diff) {
                diff = t;
                x = y;
            }
        }
        return 100 - x;
    }
}

13.子序列最大优雅度

题目链接:2813. 子序列最大优雅度

给你一个长度为 n 的二维整数数组 items 和一个整数 k 。

items[i] = [profiti, categoryi],其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。

现定义 items 的 子序列 的 优雅度 可以用 total_profit + distinct_categories2 计算,其中 total_profit 是子序列中所有项目的利润总和,distinct_categories 是所选子序列所含的所有类别中不同类别的数量。

你的任务是从 items 所有长度为 k 的子序列中,找出 最大优雅度 。

用整数形式表示并返回 items 中所有长度恰好为 k 的子序列的最大优雅度。

注意:数组的子序列是经由原数组删除一些元素(可能不删除)而产生的新数组,且删除不改变其余元素相对顺序。

示例 1:

输入:items = [[3,2],[5,1],[10,1]], k = 2

输出:17

解释:

在这个例子中,我们需要选出长度为 2 的子序列。

其中一种方案是 items[0] = [3,2] 和 items[2] = [10,1] 。

子序列的总利润为 3 + 10 = 13 ,子序列包含 2 种不同类别 [2,1] 。

因此,优雅度为 13 + 22 = 17 ,可以证明 17 是可以获得的最大优雅度。

示例 2:

输入:items = [[3,1],[3,1],[2,2],[5,3]], k = 3

输出:19

解释:

在这个例子中,我们需要选出长度为 3 的子序列。

其中一种方案是 items[0] = [3,1] ,items[2] = [2,2] 和 items[3] = [5,3] 。

子序列的总利润为 3 + 2 + 5 = 10 ,子序列包含 3 种不同类别 [1, 2, 3] 。

因此,优雅度为 10 + 32 = 19 ,可以证明 19 是可以获得的最大优雅度。

示例 3:

输入:items = [[1,1],[2,1],[3,1]], k = 3

输出:7

解释:

在这个例子中,我们需要选出长度为 3 的子序列。

我们需要选中所有项目。

子序列的总利润为 1 + 2 + 3 = 6,子序列包含 1 种不同类别 [1] 。

因此,最大优雅度为 6 + 12 = 7 。

提示:

1 <= items.length == n <= 105

items[i].length == 2

items[i][0] == profiti

items[i][1] == categoryi

1 <= profiti <= 109

1 <= categoryi <= n

1 <= k <= n

题解:

方法:贪心

       

class Solution {
    public long findMaximumElegance(int[][] items, int k) {
        // 把利润从大到小排序
        Arrays.sort(items, (a, b) -> b[0] - a[0]);
        long ans = 0;
        long totalProfit = 0;
        Set<Integer> vis = new HashSet<>();
        Deque<Integer> duplicate = new ArrayDeque<>(); // 重复类别的利润
        for (int i = 0; i < items.length; i++) {
            int profit = items[i][0];
            int category = items[i][1];
            if (i < k) {
                totalProfit += profit; // 累加前 k 个项目的利润
                if (!vis.add(category)) { // 重复类别
                    duplicate.push(profit);
                }
            } else if (!duplicate.isEmpty() && vis.add(category)) { // 之前没有的类别
                totalProfit += profit - duplicate.pop(); // 选一个重复类别中的最小利润替换
            } // else:比前面的利润小,而且类别还重复了,选它只会让 totalProfit 变小,vis.size() 不变,优雅度不会变大
            ans = Math.max(ans, totalProfit + (long) vis.size() * vis.size()); // 注意 1e5*1e5 会溢出
        }
        return ans;
    }
}

14.访问数组中的位置使分数最大

题目链接:2786. 访问数组中的位置使分数最大

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。

你 一开始 在数组的位置 0 处,你可以按照下述规则访问数组中的其他位置:

如果你当前在位置 i ,那么你可以移动到满足 i < j 的 任意 位置 j 。

对于你访问的位置 i ,你可以获得分数 nums[i] 。

如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同,那么你将失去分数 x 。

请你返回你能得到的 最大 得分之和。

注意 ,你一开始的分数为 nums[0] 。

示例 1:

输入:nums = [2,3,6,1,9,2], x = 5

输出:13

解释:我们可以按顺序访问数组中的位置:0 -> 2 -> 3 -> 4 。

对应位置的值为 2 ,6 ,1 和 9 。因为 6 和 1 的奇偶性不同,所以下标从 2 -> 3 让你失去 x = 5 分。

总得分为:2 + 6 + 1 + 9 - 5 = 13 。

示例 2:

输入:nums = [2,4,6,8], x = 3

输出:20

解释:数组中的所有元素奇偶性都一样,所以我们可以将每个元素都访问一次,而且不会失去任何分数。

总得分为:2 + 4 + 6 + 8 = 20 。

提示:

2 <= nums.length <= 105

1 <= nums[i], x <= 106

题解:

方法:动态规划

       

class Solution {
    public long maxScore(int[] nums, int x) {
        long[] f = new long[2];
        Arrays.fill(f, -(1L << 60));
        f[nums[0] & 1] = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            int v = nums[i];
            f[v & 1] = Math.max(f[v & 1], f[v & 1 ^ 1] - x) + v;
        }
        return Math.max(f[0], f[1]);
    }
}

15.数组的最大美丽值

题目链接:2779. 数组的最大美丽值

给你一个下标从 0 开始的整数数组 nums 和一个 非负 整数 k 。

在一步操作中,你可以执行下述指令:

在范围 [0, nums.length - 1] 中选择一个 此前没有选过 的下标 i 。

将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数。

数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。

对数组 nums 执行上述操作任意次后,返回数组可能取得的 最大 美丽值。

注意:你 只 能对每个下标执行 一次 此操作。

数组的 子序列 定义是:经由原数组删除一些元素(也可能不删除)得到的一个新数组,且在此过程中剩余元素的顺序不发生改变。

示例 1:

输入:nums = [4,6,1,2], k = 2

输出:3

解释:在这个示例中,我们执行下述操作:

  • 选择下标 1 ,将其替换为 4(从范围 [4,8] 中选出),此时 nums = [4,4,1,2] 。
  • 选择下标 3 ,将其替换为 4(从范围 [0,4] 中选出),此时 nums = [4,4,1,4] 。

执行上述操作后,数组的美丽值是 3(子序列由下标 0 、1 、3 对应的元素组成)。

可以证明 3 是我们可以得到的由相等元素组成的最长子序列长度。

示例 2:

输入:nums = [1,1,1,1], k = 10

输出:4

解释:在这个示例中,我们无需执行任何操作。

数组 nums 的美丽值是 4(整个数组)。

提示:

1 <= nums.length <= 105

0 <= nums[i], k <= 105

题解:

方法:排序

       

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = 0;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            while (nums[right] - nums[left] > k * 2) {
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

16.最长特殊序列 Ⅰ

题目链接:521. 最长特殊序列 Ⅰ

给你两个字符串 a 和 b,请返回 这两个字符串中 最长的特殊序列 的长度。如果不存在,则返回 -1 。

「最长特殊序列」 定义如下:该序列为 某字符串独有的最长

子序列

(即不能是其他字符串的子序列) 。

字符串 s 的子序列是在从 s 中删除任意数量的字符后可以获得的字符串。

例如,“abc” 是 “aebdc” 的子序列,因为删除 “aebdc” 中斜体加粗的字符可以得到 “abc” 。 “aebdc” 的子序列还包括 “aebdc” 、 “aeb” 和 “” (空字符串)。

示例 1:

输入: a = “aba”, b = “cdc”

输出: 3

解释: 最长特殊序列可为 “aba” (或 “cdc”),两者均为自身的子序列且不是对方的子序列。

示例 2:

输入:a = “aaa”, b = “bbb”

输出:3

解释: 最长特殊序列是 “aaa” 和 “bbb” 。

示例 3:

输入:a = “aaa”, b = “aaa”

输出:-1

解释: 字符串 a 的每个子序列也是字符串 b 的每个子序列。同样,字符串 b 的每个子序列也是字符串 a 的子序列。

提示:

1 <= a.length, b.length <= 100

a 和 b 由小写英文字母组成

题解:

方法:脑筋急转弯

       

class Solution {
    public int findLUSlength(String a, String b) {
        return a.equals(b) ? -1 : Math.max(a.length(), b.length());
    }
}

下接:【题解】—— LeetCode一周小结25


相关文章
|
2月前
|
机器人
|
2月前
|
人工智能 BI
|
3月前
|
人工智能 BI
|
4月前
|
算法
|
4月前
|
测试技术 索引
|
5月前
|
机器学习/深度学习