🌟欢迎来到 我的博客 —— 探索技术的无限可能!
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()); } }