上岸算法LeetCode Weekly Contest 286解题报告

上岸算法 · 发表于 2022-3-27 16:58:22

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

【 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[i] == nums[i + 1]) { // 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[queries.length];
   for (int i = 0; i < queries.length; i++) {
         res[i] = kthPalindrome(intLength, queries[i]);
   }
   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 个栈取 j 次得到的最大和。

状态转移：在第 i 个栈取几个，即 dp[i][j] = max{dp[i-1][j-t] + sum(i, t)}，其中 sum(i, t) 表示在第 i 个栈取 t 个硬币得到的和。

代码展示

class Solution {
public int maxValueOfCoins(List<List<Integer>> piles, int k) {
   int[][] dp = new int[1001][2001];
   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[i][j] = Math.max(dp[i][j], dp[i - 1][j - t] + sum);
               if (t < p.size()) {
                     sum += p.get(t);
               }

            }
      }
   }
   return dp[piles.size()][k];
  }
}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 286解题报告

登录后可回复主题