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

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

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

## 10.救生艇

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.甲板上的战舰

m == board.length

n == board[i].length

1 <= m, n <= 200

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

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.取整购买后的账户余额

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.子序列最大优雅度

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

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 个项目的利润
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.访问数组中的位置使分数最大

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.数组的最大美丽值

• 选择下标 1 ，将其替换为 4（从范围 [4,8] 中选出），此时 nums = [4,4,1,2] 。
• 选择下标 3 ，将其替换为 4（从范围 [0,4] 中选出），此时 nums = [4,4,1,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.最长特殊序列 Ⅰ

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

（即不能是其他字符串的子序列） 。

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());
}
}

|
23天前
【题解】—— LeetCode一周小结25
LeetCode每日一道一周小结25
39 8
|
1月前
|

【题解】—— LeetCode一周小结23
LeetCode每日一道一周小结23
17 3
|
8天前
|

【题解】—— LeetCode一周小结27
LeetCode每日一道一周小结27
10 0
|
2月前
【题解】—— LeetCode一周小结20
LeetCode每日一道一周小结20
52 8
|
1月前
|

【题解】—— LeetCode一周小结22
LeetCode每日一道一周小结22
22 7
|
16天前
【题解】—— LeetCode一周小结26
LeetCode每日一道一周小结26
10 0
|
2月前
|

【题解】—— LeetCode一周小结21
LeetCode每日一道一周小结21
74 8
|
2月前
|

【题解】—— LeetCode一周小结14
【题解】—— LeetCode一周小结14
22 2
|
2月前
|

【题解】—— LeetCode一周小结16
【题解】—— LeetCode一周小结16
18 2
|
2月前
|

【题解】—— LeetCode一周小结9
【题解】—— LeetCode一周小结9
10 1