上岸算法LeetCode Weekly Contest 286解题报告
【 NO.1 找出两数组的不同】解题思路
可以使用 sort + binary search 求差集。
代码展示
class Solution {
public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
List<Integer> res0 = Arrays.stream(nums1).
filter(i -> Arrays.binarySearch(nums2, i) < 0).
distinct().boxed().collect(Collectors.toList());
List<Integer> res1 = Arrays.stream(nums2).
filter(i -> Arrays.binarySearch(nums1, i) < 0).
distinct().boxed().collect(Collectors.toList());
return List.of(res0, res1);
}
}
【 NO.2 美化数组的最少删除数】
解题思路
从左到右遍历即可。
代码展示
class Solution {
public int minDeletion(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; ) { // i 应当和 i + 1 不同
if (i == nums.length - 1) { // i 是最后一个，应当删除
res++;
break;
}
if (nums == nums) { // i 和 i + 1 相同，应当删除，相当于 i++
i++;
res++;
} else { // i 和 i + 1 不同，可以保留，i += 2 以判断下一组
i += 2;
}
}
return res;
}
}
【 NO.3 找到指定长度的回文数】
解题思路
举个例子：长度为 6 的第 k 大的回文数的前半边其实就是 100 + k - 1，由前半边复制出后半边即可。
奇数长度的回文数在复制出后半边前去掉末尾数即可。
代码展示
class Solution {
public long[] kthPalindrome(int[] queries, int intLength) {
long[] res = new long;
for (int i = 0; i < queries.length; i++) {
res = kthPalindrome(intLength, queries);
}
return res;
}
// 返回长度为 intLength 的第 k 小的回文数
private long kthPalindrome(int intLength, int k) {
// 处理偶数
if (intLength % 2 == 0) {
long half = pow10(intLength / 2 - 1) + k - 1;
if (length(half) * 2 > intLength) {
return -1;
}
long res = half;
while (half > 0) {
res = res * 10 + (half % 10);
half /= 10;
}
return res;
}
if (intLength == 1) {
return k > 9 ? -1 : k;
}
// 处理奇数
long half = pow10(intLength / 2) + k - 1;
if (length(half) * 2 - 1 > intLength) {
return -1;
}
long res = half;
half /= 10; // 去掉末尾数
while (half > 0) {
res = res * 10 + (half % 10);
half /= 10;
}
return res;
}
private int length(long n) {
int res = 0;
while (n > 0) {
n /= 10;
res++;
}
return res;
}
private long pow10(int n) {
long res = 1;
for (int i = 0; i < n; i++) {
res *= 10;
}
return res;
}
}
【 NO.4 从栈中取出 K 个硬币的最大面值和】
解题思路
典型的动态规划问题。
定义状态：dp 表示前 i 个栈取 j 次得到的最大和。
状态转移：在第 i 个栈取几个，即 dp = max{dp + sum(i, t)}，其中 sum(i, t) 表示在第 i 个栈取 t 个硬币得到的和。
代码展示
class Solution {
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
int[][] dp = new int;
for (int j = 1; j <= k; j++) {
for (int i = 1; i <= piles.size(); i++) {
var p = piles.get(i - 1);
int sum = 0;
for (int t = 0; t <= j && t <= p.size(); t++) { // 枚举在 i 取 t 个
dp = Math.max(dp, dp + sum);
if (t < p.size()) {
sum += p.get(t);
}
}
}
}
return dp;
}
}
页:
[1]