LeetCode冲刺：Day28

发布于 2022-12-05  113 次阅读

1. 判断一个数的数字计数是否等于数位的值

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

题目本身不难，但是被Python的字典和条件判断、循环、逻辑运算符折磨了一会儿。想念cpp的第一天。

代码

class Solution:
    def digitCount(self, num: str) -> bool:
        dic = {}
        n = len(num)
        for i in range(n):
            if (int(num[i], 10) in dic): dic[int(num[i], 10)] += 1
            else: dic[int(num[i], 10)] = 1
        for i in range(n):
            if ((int(num[i], 10) == 0 and i in dic) or (int(num[i], 10) != 0 and (i not in dic or dic[i] != int(num[i], 10)))): return False
        return True

2. 最多单词数的发件人

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

句子内单词数等于空格数+1，因为已经保证是正常句子，也不需要考虑特例了。

代码

class Solution:
    def largestWordCount(self, messages: List[str], senders: List[str]) -> str:
        dic = {}
        n = len(messages)
        maxCnt = 0
        maxSender = senders[0]
        for i in range(n):
            if senders[i] not in dic: dic[senders[i]] = 0
            dic[senders[i]] += messages[i].count(" ") + 1
            if dic[senders[i]] > maxCnt: 
                maxCnt = dic[senders[i]]
                maxSender = senders[i]
            elif dic[senders[i]] == maxCnt:
                if (senders[i] > maxSender): maxSender = senders[i]
        return maxSender

3. 道路的最大总重要性

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

要总和最大，显然连接道路更多的城市应当分到更大的权重，所以统计每个城市连接的道路数即可。

自己写的版本只能优化到超过25%，进一步优化参考了这篇

初始化数组尽量用乘号，而不是for循环。巧用 enumerate 来遍历得到下标和数据。

代码

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        cities = [0] * n
        for road in roads:
            cities[road[0]] += 1
            cities[road[1]] += 1
        cities.sort()
        return sum(city * i for city, i in enumerate(cities, 1))

4. 以组为单位订音乐会的门票

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

按自己的思路，实现是没问题，但有用例超时。

正确解法用到线段树，参考这篇。按作者的说法，这题有点超纲hh

代码

# 暴力解，超时
class BookMyShow:
    seat = []
    colUpBound = 0
    rowUpBound = 0
    start = 0

    def __init__(self, n: int, m: int):
        self.seat = [0] * n
        self.colUpBound = m
        self.rowUpBound = n
        self.start = 0

    def gather(self, k: int, maxRow: int) -> List[int]:
        for i in range(self.start, self.rowUpBound):
            if i <= maxRow:
                if self.colUpBound - self.seat[i] >= k:
                    ans = [i, self.seat[i]]
                    self.seat[i] += k
                    while self.start < self.rowUpBound and self.seat[self.start] == self.colUpBound: self.start += 1
                    return ans
        return []

    def scatter(self, k: int, maxRow: int) -> bool:
        seatBackup = list(self.seat)
        startBackup = self.start
        for i in range(self.start, self.rowUpBound):
            if i <= maxRow:
                if self.seat[i] < self.colUpBound:
                    if (k <= self.colUpBound - self.seat[i]):
                        self.seat[i] += k
                        while self.start < self.rowUpBound and self.seat[self.start] == self.colUpBound: self.start += 1
                        return True
                    else:
                        k -= self.colUpBound - self.seat[i]
                        self.seat[i] = self.colUpBound
                        while self.start < self.rowUpBound and self.seat[self.start] == self.colUpBound: self.start += 1
            else: break
        self.seat = seatBackup
        self.start = startBackup
        return False

5. 字母在字符串中的百分比

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

内置的计数居然比直接写要快这么多。

代码

class Solution:
    def percentageLetter(self, s: str, letter: str) -> int:
        return  int(100 * s.count(letter) / len(s))

6. 装满石头的背包的最大数量

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

乍一看还以为是背包问题。

写的时候时刻注意节约空间，能原地改就原地改。

代码

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        n = len(capacity)
        for i in range(n): capacity[i] -= rocks[i]
        capacity.sort()
        for i in range(n):
            additionalRocks -= capacity[i]
            if additionalRocks < 0: return i
        return n

7. 表示一个折线图的最少线段数

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

本来是想用斜率来做，但存在精度问题。Python只有float一种小数类型，两字节，在特定用例下会由于精度问题判断错误。所以把斜率公式变换一下，改为乘法对比。

如果是在竞赛中看不到错误用例，那我估计又会卡在这里。

以后要注意，用除法要考虑精度问题，用乘法要考虑溢出问题。一般来讲能用乘法做尽量用乘法做。

代码

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        n = len(stockPrices)
        if n == 1: return 0
        if n == 2: return 1
        stockPrices.sort(key = lambda x: x[0])
        # pre = (stockPrices[1][1] - stockPrices[0][1]) / (stockPrices[1][0] - stockPrices[0][0])
        # ans = 1
        # for i in range(1, len(stockPrices)):
        #     cur = (stockPrices[i][1] - stockPrices[i - 1][1]) / (stockPrices[i][0] - stockPrices[i - 1][0])
        #     if  cur != pre:
        #         ans += 1
        #         pre = cur
        # return ans
        ans = 1
        for i in range(2, n):
            if (stockPrices[i - 1][1] - stockPrices[i - 2][1]) * (stockPrices[i][0] - stockPrices[i - 1][0]) != (stockPrices[i][1] - stockPrices[i - 1][1]) * (stockPrices[i - 1][0] - stockPrices[i - 2][0]):
                ans += 1
        return ans

8. 巫师的总力量和

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

只能想到暴力解法。参考这篇

代码