LeetCode冲刺：Day45

发布于 2022-12-22  133 次阅读

1. 最佳观光组合

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

动态规划。对于当前景点 i ，它的最大得分，应当是在 score_1 和 score_2 之间取最大。其中 score_1 是当前景点与上一景点的组合得分， score_2 是上一景点达到其最大得分的配对景点 j 与当前景点组合的得分，其值为上一景点的最大得分，加上当前景点value，减掉上一景点value，再减1。

代码

from typing import List

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        n = len(values)
        dp = [0 for i in range(n)]
        ans = 0
        for i in range(1, n):
            score_1 = values[i] + values[i - 1] - 1
            score_2 = dp[i - 1] + values[i] - values[i - 1] - 1
            dp[i] = score_1 if score_1 > score_2 else score_2
            ans = ans if ans > dp[i] else dp[i]
        return ans

2. [查找和最小的 K 对数字](https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/description/)

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

前几天没做出来的一题，今天忽然有灵感了。

换个思路想，不要聚焦于组合，而是“和”。针对nums1中的单个元素而言，与nums2组合的最小和，肯定是下标靠前的元素，那么将nums1中每个元素当前的最小和组合（和，下标1，下标2）放入堆中，每次取出一个，再将其下一个组合插入堆中，重复k次即可。

代码

from cmath import inf
from heapq import heappop, heappush, nsmallest
from typing import List

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        hp = []
        n1 = len(nums1)
        n2 = len(nums2)
        k = k if k <= n1 * n2 else n1 * n2
        ans = []
        for index in range(n1):
            heappush(hp, [nums1[index] + nums2[0], index, 0])
        for i in range(k):
            _, index_1, index_2 = heappop(hp)
            ans.append([nums1[index_1], nums2[index_2]])
            if index_2 < n2 - 1:
                heappush(hp, [nums1[index_1] + nums2[index_2 + 1], index_1, index_2 + 1])
        return ans

3. 矩形重叠

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

想清楚再作答。

代码

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        x1, y1, x2, y2 = 0, 1, 2, 3
        if rec2[x1] < rec1[x1]:
            temp = rec1
            rec1 = rec2
            rec2 = temp
        if rec1[x2] > rec2[x1] and rec1[y2] > rec2[y1] and rec1[y1] < rec2[y2]: return True
        return False

4. 寻找比目标字母大的最小字母

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

模拟即可。

代码

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        ans = ""
        for letter in letters:
            if letter > target:
                if ans == "": ans = letter
                else:
                    if letter < ans: ans = letter
        return ans if ans != "" else letters[0]

5. 找出两数组的不同

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

集合去重

代码

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        ans = [[], []]
        rec_1, rec_2 = set(nums1), set(nums2)
        for num in rec_1:
            if num not in rec_2: ans[0].append(num)
        for num in rec_2:
            if num not in rec_1: ans[1].append(num)
        return ans

6. 美化数组的最少删除数

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

一遍过，舒服。

为了节约时间，我们不真的删除元素，而是通过下标变化来实现。

设定 i 始终指向偶数下标（变化后数组的下标为偶数，而非当前真实下标为偶数），初始时为0。

当 i 等于 n 时跳出循环。

如果当前 i 为 n - 1 ，说明修改后数组长度为奇数，ans加一后跳出循环。

如果 i 指向元素等于下一元素，我们标记两个元素，start标记 i 的下一个元素，作为删除后 i 的下一个元素，end标记 i 的下下个元素，作为删除操作后新的 i 所在位置。然后，当start标记元素等于元素 i 时，都将ans、start、end加一，且如果start等于n了，就跳出循环。这一步是为了连续删除 i 之后的连续相同元素。然后将end赋值给 i ，且如果 start 等于 n，说明 i 之后的元素全被删了，则 i 落单，那么也要删除 i ，于是ans加一后跳出循环。

而如果 i 指向元素与下一元素不同，让 i 加二，去检查下一个数对。

代码

class Solution:
    def minDeletion(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        i = 0
        while i < n:
            if i == n - 1:
                ans += 1 
                i += 1
            else:
                if nums[i] == nums[i + 1]:
                    start = i + 1
                    end = i + 2
                    while start < n and nums[start] == nums[i]:
                        end += 1
                        start += 1
                        ans += 1
                    i = end
                    if start == n:
                        ans += 1
                else: i += 2
        return ans

7. 找到指定长度的回文数

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

要解出这题，需要想到定长回文数的构造。

以长度4为例，我们应以10作为基数，定长4的第0个（或者从1开始，一样的道理，0方便讲述）回文数，应当是10+0这个数拼接上其自身的逆序，即1001。

当长度为奇数，如3时，基数用10，第0个回文数应当是10+0拼接上其自身去掉末位的逆序，即101。

有了以上方法，我们就可以根据长度和序号快速构造出对应回文数。

那么在确定长度后，将查询数组排序，并记录下原始下标，逐个构造回文数并添加到ans数组。注意，查询数组中可能有相同的数字，所以在排序后相同数字是连续的，通过一个while循环来给连续数字快速赋值，而不用重复构造。

代码

class Solution:
    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
        n = len(queries)
        ans = [-1 for i in range(n)]
        queries = sorted(zip(queries, range(n)))
        isEven = True
        length = intLength >> 1
        if (intLength & 1) == 1:
            length += 1
            isEven = False
        length -= 1
        baseNum = 10 ** length
        # 回文数基数的上限（不包括）
        limit = baseNum * 10
        i = 0
        while i < n:
            num = baseNum + queries[i][0] - 1
            if num >= limit: break
            # 偶数长度
            if isEven:
                ans[queries[i][1]] = int(str(num) + str(num)[::-1])
            # 奇数长度
            else:
                ans[queries[i][1]] = int(str(num // 10) + str(num)[::-1])
            i += 1
            while i < n and queries[i][0] == queries[i - 1][0]:
                ans[queries[i][1]] = ans[queries[i - 1][1]]
                i += 1
        return ans

8. 从栈中取出 K 个硬币的最大面值和

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

之前学背包问题只学了01背包和完全背包，本题属于分组背包。

代码