215. 数组中的第K个最大元素

215. 数组中的第K个最大元素

import heapq


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums = [-i for i in nums]
        heapq.heapify(nums)
        ans = 0
        for i in range(k):
            ans = heapq.heappop(nums)
        return -ans

2410. 运动员和训练师的最大匹配数

2410. 运动员和训练师的最大匹配数

class Solution:
    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
        players.sort()
        trainers.sort()
        players_index = 0
        trainers_index = 0
        cnt = 0
        while players_index < len(players) and trainers_index < len(trainers):
            if players[players_index] <= trainers[trainers_index]:
                cnt += 1
                players_index += 1
                trainers_index += 1
            else:
                trainers_index += 1
        return cnt

1742. 盒子中小球的最大数量

1742. 盒子中小球的最大数量

from collections import defaultdict


class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        max_box = 0
        box_index = 0
        count = defaultdict(int)
        for i in range(lowLimit, highLimit + 1):
            box = sum(list(map(int, list(str(i)))))
            count[box] += 1
            if count[box] > max_box:
                box_index = box
                max_box = count[box]
        return count[box_index]

面试题 01.02. 判定是否互为字符重排

面试题 01.02. 判定是否互为字符重排

class Solution:
    def CheckPermutation(self, s1: str, s2: str) -> bool:
        return sorted(list(s1)) == sorted(list(s2))

2014. 重复 K 次的最长子序列

2014. 重复 K 次的最长子序列

最简洁易懂的方法：利用字母频率

from collections import Counter
from itertools import permutations


class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        num = Counter(s)
        # 字母频率为freq，那么其可能参与组成的子串最多为freq//k个
        hot = "".join([c * (num[c] // k) for c in sorted(num, reverse=True)])
        print(hot)
        for i in range(len(hot), 0, -1):
            for item in permutations(hot, i):
                word = ''.join(item)
                ss = iter(s)
                # in的判断contains也会消耗迭代器，迭代器只能前进。
                if all(c in ss for c in word * k):
                    return word
        return ''

3. 无重复字符的最长子串

3. 无重复字符的最长子串

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if s == '':
            return 0
        p0 = 0
        p1 = 0
        max_length = 0
        sets = set()
        for p1 in range(len(s)):
            if s[p1] in sets:
                max_length = p1 - p0 if p1 - p0 > max_length else max_length
                for i in range(p0, len(s)):
                    sets.discard(s[i])
                    if s[i] == s[p1]:
                        p0 = i + 1
                        sets.add(s[p1])
                        break
            else:
                sets.add(s[p1])
        p1 += 1
        max_length = p1 - p0 if p1 - p0 > max_length else max_length
        return max_length