每日一题

2024年5月28日

2951. 找出峰值

给你一个下标从 $0$ 开始的数组 mountain 。你的任务是找出数组 mountain 中的所有 峰值。
以数组形式返回给定数组中 峰值 的下标，顺序不限 。

注意：
峰值 是指一个严格大于其相邻元素的元素。
数组的第一个和最后一个元素 不 是峰值。

提示：
3 <= mountain.length <= 100
1 <= mountain[i] <= 100

思路

这道题用python太简单了，，，数据约定也就100个
我的思路是这样的
新建一个空列表，用$i$把mountain从小到大遍历一遍，大于 $i-1$ 和 $i+1$ 就加入列表

（不是最优解，题解评论区说如果$i$是山峰，那么$i+1$一定不是山峰，可小优化）

代码

class Solution:
    def findPeaks(self, mountain: List[int]) -> List[int]:
        res = []
        for i in range(1,len(mountain)-1):
            if mountain[i] > mountain[i-1] and mountain[i] > mountain[i+1]:
                res.append(i)
                i += 1
        return res

2024年5月29日

2981. 找出出现至少三次的最长特殊子字符串 I

给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
子字符串 是字符串中的一个连续 非空 字符序列。

提示：
3 <= s.length <= 50
s 仅由小写英文字母组成。

思路

官方题解谜语人，完全不解释为什么只取字母列表的前三位。
题目中要求了我们需要找到出现至少三次的特殊字符串。例如样例中的abcaba，其中特殊字符串a就出现了三次，所以结果输出1。
可以先遍历一遍字符串，分离所有的特殊字符串，每个字母单独存为一个列表
如abcaba，那么a的列表就是[1, 1, 1]
如aabcabaa，那么a的列表就是[2, 1, 2]，
之后还要将a的列表排倒序
使得a[0]代表的意义为该字母最大连续出现的次数，且a[0] >= a[1] >= a[2] >= ...

以字母a为例，分类讨论怎么才能让特殊字符串 至少 出现三次：

1. 在长度为a[0]的特殊字符串中，那么只要a[0] > 2，那么必然存在3个长度为a[0] - 2的字符串，比如aaaa，则a[0] = 4就含有aaaa, aaaa, aaaa三种长度为a[0] - 2 = 2的特殊字符串
2. 在两个长度为a[0]的特殊字符串中，那么只要a[0] > 1，那么必然存在4个长度为a[0] - 1的字符串，这种情况也代表着a[0] = a[1]
     在两个长度分别为a[0]、a[1]的特殊字符串中，且满足a[0] > a[1]，只要a[0] > 1，a[1] > 0，那么必然存在2个长度为a[0] - 1的字符串以及a[1]本身，这样就能凑齐3个特殊字符串
3. 在三个长度分别为a[0]、a[1]、a[2]的特殊字符串中，每段字符串必然存在1个长度为a[2]的字符串，加起来就是3个特殊字符串。

在这3种情况中取max()最大值，如果max()没取到值则输出-1，所以官方题解中提到只要找出 每个字母 前三长的特殊字符串，是这么理解的。
对于第2种情况，用到min()是因为当a[0] = a[1]时，a[0] - 1一定比a[1]小1，在外层的max就会取到a[1]也就是a[0]的值，从而使答案大1，所以选择使用min(a[0] - 1, a[1])的方法规避这个问题
之后还要考虑只有连续一段字符串的情况，只要将a[1]、a[2]定义为0即可
然后对小写英文的26个字母全部循环一遍，这里用到enumerate(str)函数，便于我们对字母分别计数

代码

class Solution:
    def maximumLength(self, s: str) -> int:
        group = defaultdict(list)
        count = 0
        for i, chr in enumerate(s):
            count += 1
            if  i == len(s)-1 or chr != s[i+1]:
                group[chr].append(count)
                count = 0
        
        ans = 0
        for a in group.values():
            a.sort(reverse=True)
            a.extend([0,0])
            ans = max(ans, a[0] - 2, min(a[0] - 1, a[1]), a[2])
        if ans != 0:
            return ans
        else:
            return -1     

2024年5月30号

Leetcode登不上去缓一天

2024年5月31号

2965. 找出缺失和重复的数字

给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n^2] 范围内。除了 a 出现 两次，b 缺失 之外，每个整数都 恰好出现一次 。
任务是找出重复的数字a 和缺失的数字 b 。
返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 ans[0] 等于 a ，ans[1] 等于 b 。

思路

我的方法与题解比较不一样，不是最优解
这道题数据约定也不是很大，不会存在超时的风险。
假设不存在重复的数字，那么每个数字其实都是确定 1-n^2 的，用一个求和公式可以非常快的把所有数字之和找出来
然后 将这个和与实际的数组和相减，就可以得到 a 与 b 的 差

最后一步就是找出哪个是重复的，python直接sort数组就行了

代码

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        num = []
        ans = 0
        ans_sum = (1 + len(grid)*len(grid))*len(grid)*len(grid) / 2
        for i in range(0,len(grid)):
            for j in range(0,len(grid)):
                ans += grid[i][j]
                num.append(grid[i][j])

        num.sort()
        for i in range(0,len(num)-1):
            if num[i] == num[i+1]:
                return [num[i], num[i] + int(ans_sum) - ans]

2024年6月1号

2928. 给小朋友们分糖果 I

给你两个正整数 n 和 limit 。
请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

思路

我这里写我觉得的最笨的办法，也是最简单的，但是数据约定上去了肯定是不对的
首先输入limit， 每个小孩能拿到的糖一定在[0, 1, 2, ..., limit]数组内
然后暴力枚举，只要3个小孩拿到的糖果最后等于n，则认为这是一个可行的方案

代码

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        possible_choice = []
        for i in range(0, limit+1):
            possible_choice.append(i)
        
        ans = 0
        for i in possible_choice:
            for j in possible_choice:
                for k in possible_choice:
                    if i+j+k == n:
                        ans += 1
        return ans

2024年6月2号

575. 分糖果

Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。

医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。

给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的 最多 种类数。

思路

看完题解以后，真的好简单，是我想复杂了，没想到还能用set功能。
先说我的思路，这道题肯定用贪心。
先把所有种类的糖全吃一遍，如果没到一半，则输出糖果种类的值，如果超过则输出糖果总量的一半

糖果是无序且有重复的，我就把那个数组排序后又遍历一遍，如果当前的和数组后一位不一样则 糖果种类+1
结果，题解用一个len(set)就解决了我的想法。。。以后我会记住的

代码

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        n = len(candyType)
        candyType.sort()
        cur = candyType[0]
        num_candyType = 1
        for i in range(0, n-1):
            if cur != candyType[i+1]:
                num_candyType += 1
                cur = candyType[i+1]
        if num_candyType < n/2:
            return num_candyType
        else:
            return int(n/2)

2024年6月3号

1103. 分糖果 II

我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。
给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。
然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。
重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。
返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

思路

首先创建一个长度为 num_people 的数组
设置一个计数器为 candy
模拟发糖，让Group[i]加上当前candy的值，再让candy+1，同时让candies，也就是剩余的糖果数 -1
如果剩余的candies不足以发完当前的candy，则让当前的Group[i]加上candies剩余的值，并将candies的值设为0，达成跳出循环的条件

代码

class Solution:
    def distributeCandies(self, candies: int, num_people: int) -> List[int]:
        Group = []
        for i in range(num_people):
            Group.append(0)

        candy = 1
        while candies != 0:
            for i in range(num_people):
                if candies >= candy:
                    Group[i] += candy
                    candies -= candy
                    candy += 1
                else:
                    Group[i] += candies
                    candies = 0
                    break
        
        return Group

2024年6月4号

3067. Count Pairs of Connectable Servers in a Weighted Tree Network

思路

代码

class Solution:
    def countPairsOfConnectableServers(self, edges: List[List[int]], signalSpeed: int) -> List[int]:
        graph = [[] for _ in range(len(edges) + 1)]
        # 变成邻接链表存储
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        def dfs(p: int, root: int, curr: int) -> int:
            res = 0
            if curr == 0:
                res += 1
            for v, cost in graph[p]:
                if v != root:
                    res += dfs(v, p, (curr + cost) % signalSpeed)
            return res
        
        res = [0] * (len(edges) + 1)
        for i in range(len(edges) + 1):
            pre = 0
            for v, cost in graph[i]:
                count = dfs(v, i, cost % signalSpeed)
                res[i] += pre * count
                pre += count
        return res

2024年6月5号

3072. Distribute Elements Into Two Arrays II

思路

代码

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        arr1 = [nums[0]]
        arr2 = [nums[1]]

        def binary_search(arr: List[int], left, right, x) -> int:
            closest = 0
            while left <= right:
                mid = (left + right) // 2
                if arr[mid] == x:
                    while mid != 0 and arr[mid - 1] == x:
                        mid -= 1
                    return mid

                elif arr[mid] > x:
                    closest = mid + 1
                    left = mid + 1
                else:
                    right = mid - 1
            return closest

        def greaterCount(arr: List[int], ans) -> int:
            test_arr = sorted(arr, reverse=True)
            res = binary_search(test_arr, 0, len(arr)-1, ans)
            return res
            
        for i in range(2, len(nums)):
            if greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]):
                arr1.append(nums[i])
            elif greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]):
                arr2.append(nums[i])
            elif greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]):
                if len(arr1) < len(arr2):
                    arr1.append(nums[i])
                elif len(arr1) > len(arr2):
                    arr2.append(nums[i])
                else:
                    arr1.append(nums[i])

        return arr1 + arr2

2024年6月6号

2938. Separate Black and White Balls

思路

代码

class Solution:
    def minimumSteps(self, s: str) -> int:
        n = len(s)
        ans = 0
        first_1 = 0

        if '1' not in s:
            return 0

        while s[first_1] != '1':
            first_1 += 1
        
        cnt_0 = 0
        for i in range(first_1, n):
            if s[i] == '0':
                cnt_0 += 1
        
        pre = first_1
        ans += cnt_0
        if pre != n - 1:
            for i in range(first_1 + 1, n):
                if s[i] == '1':
                    cnt_0 -= i - pre - 1
                    ans += cnt_0
                    pre = i        
        return ans

2024年6月7号

3038. Maximum Number of Operations With the Same Score I

思路

代码

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        n = nums[0]+nums[1]
        res = 0
        while len(nums) >= 2 and nums[0]+nums[1] == n:
            del nums[0:2]
            res += 1
        return res

2024年6月8号

3040. Maximum Number of Operations With the Same Score II

思路

代码

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        res = []
        n_1 = nums[0] + nums[1]
        n_2 = nums[len(nums)-2] + nums[len(nums)-1]
        n_3 = nums[0] + nums[len(nums)-1]
        n = [n_1, n_2, n_3]

        @cache
        def opt(head, tail, target):
            if head >= tail:
                return 0
            ans = 0
            if nums[head] + nums[head+1] == target:
                ans = max(ans, 1 + opt(head + 2, tail, target))
            if nums[tail - 1] + nums[tail] == target:
                ans = max(ans, 1 + opt(head, tail - 2, target))
            if nums[head] + nums[tail] == target:
                ans = max(ans, 1 + opt(head + 1, tail - 1, target))
            return ans
            
        for i in n:
            res.append(opt(0, len(nums) - 1, i))
        return max(res)

2024年6月9号

312. Burst Balloons

思路

代码

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        dp_list = [[0] * (len(nums)+2) for _ in range(len(nums)+2)]
        temp_extend = [1] + nums + [1]

        for i in range(len(nums)-1, -1, -1):
            for j in range(i+2, len(nums)+2):
                for k in range(i+1, j):
                    ans = temp_extend[i] * temp_extend[k] * temp_extend[j]
                    ans += dp_list[i][k] + dp_list[k][j]
                    dp_list[i][j] = max(dp_list[i][j], ans)
        
        return dp_list[0][len(nums) + 1]

2024年6月10号

881. Boats to Save People

思路

代码

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        cnt = 0
        head = 0
        tail = len(people) - 1
        while head <= tail:
            if people[head] + people[tail] > limit:
                tail -= 1
            else:
                head += 1
                tail -= 1
            cnt += 1
        return cnt

2024年6月11号

419. Battleships in a Board

思路

代码

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        m = len(board)
        n = len(board[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'X':
                    if (i == 0 or board[i-1][j] != 'X') and (j == 0 or board[i][j-1] != 'X'):
                        ans += 1
        return ans

2024年6月12号

2806. Account Balance After Rounded Purchase

思路

代码

class Solution:
    def accountBalanceAfterPurchase(self, purchaseAmount: int) -> int:
        if purchaseAmount % 10 != 0:
            if purchaseAmount % 10 < 5:
                purchaseAmount -= purchaseAmount % 10
            else:
                purchaseAmount += 10 - purchaseAmount % 10
        return 100 - purchaseAmount

2024年6月13号

2813. Maximum Elegance of a K-Length Subsequence

不会做，看题解，以后再来研究

思路

代码

class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        items.sort(key = lambda item: -item[0])
        categorySet = set()
        res, profit = 0, 0
        st = []
        for i, item in enumerate(items):
            if i < k:
                profit += item[0]
                if item[1] in categorySet:
                    st.append(item[0])
                else:
                    categorySet.add(item[1])
            elif item[1] not in categorySet and len(st) > 0:
                profit += item[0] - st.pop()
                categorySet.add(item[1])
            res = max(res, profit + len(categorySet) * len(categorySet))
        return res

2024年6月14号

2786. Visit Array Positions to Maximize Score

思路

代码

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        res = nums[0]
        opt = [-inf, -inf]
        opt[nums[0] % 2] = nums[0]
        for i in range(1, len(nums)):
            parity = nums[i] % 2
            cur = max(opt[parity] + nums[i], opt[1 - parity] - x + nums[i])
            res = max(res, cur)
            opt[parity] = max(opt[parity], cur)
        return res

2024年6月15号

2779. Maximum Beauty of an Array After Applying Operation

思路

代码

class Solution:
    def maximumBeauty(self, nums: List[int], k: int) -> int:
        res = 0
        j = 0
        n = len(nums)
        nums.sort()
        for i in range(n):
            while nums[i] - 2*k > nums[j]:
                j += 1
            res = max(res, i-j+1)
        return res

2024年6月16号

521. Longest Uncommon Subsequence I

思路

代码

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        if a == b:
            return -1
        else:
            return max(len(a),len(b))

2024年6月17号

522. Longest Uncommon Subsequence II

思路

代码

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def compare(s,t):
            pt_s = pt_t = 0
            while pt_s < len(s) and pt_t < len(t):
                if s[pt_s] == t[pt_t]:
                    pt_s += 1
                pt_t += 1
            return pt_s == len(s)

        ans = -1    
        for i, s in enumerate(strs):
            check = True
            for j, t in enumerate(strs):
                if i != j and compare(s, t):
                    check = False
                    break
            if check:
                ans = max(ans, len(s))
        
        return ans

2024年6月18号

2288. Apply Discount to Prices

思路

代码

class Solution:
    def discountPrices(self, sentence: str, discount: int) -> str:
        words = sentence.split()
        for i, word in enumerate(words):
            if word[0] == "$" and word[1:].isnumeric():
                price = int(word[1:]) * (1 - discount / 100)
                words[i] = f"${price:.2f}"
        return " ".join(words)

2024年6月19号

2713. Maximum Strictly Increasing Cells in a Matrix

思路

代码

class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        g = defaultdict(list)
        for i, row in enumerate(mat):
            for j, x in enumerate(row):
                g[x].append((i, j))  

        row_max = [0] * len(mat)
        col_max = [0] * len(mat[0])
        for _, pos in sorted(g.items(), key=lambda p: p[0]):
            fs = [max(row_max[i], col_max[j]) + 1 for i, j in pos]
            for (i, j), f in zip(pos, fs):
                row_max[i] = max(row_max[i], f)  
                col_max[j] = max(col_max[j], f)  
        return max(row_max)

2024年6月20号

2748. Number of Beautiful Pairs

思路

代码

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                ans_f = int(str(nums[i])[0])
                ans_l = nums[j] % 10
                if gcd(ans_f, ans_l) == 1:
                    ans += 1
        return ans   

2024年6月21号

LCP 61. 气温变化趋势

思路

代码

class Solution:
    def temperatureTrend(self, temperatureA: List[int], temperatureB: List[int]) -> int:
        ans_A = []
        ans_B = []
        a_n = len(temperatureA)
        for i in range(1,a_n):
            if temperatureA[i] > temperatureA[i-1]:
                ans_A.append(1)
            elif temperatureA[i] == temperatureA[i-1]:
                ans_A.append(2)
            elif temperatureA[i] < temperatureA[i-1]:
                ans_A.append(3)

        for i in range(1,a_n):
            if temperatureB[i] > temperatureB[i-1]:
                ans_B.append(1)
            elif temperatureB[i] == temperatureB[i-1]:
                ans_B.append(2)
            elif temperatureB[i] < temperatureB[i-1]:
                ans_B.append(3)     
        
        max_ans = 0
        ans = 0
        for i in range(a_n - 1):
            if ans_A[i] != ans_B[i]:
                ans = 0
            else:
                ans += 1
            max_ans = max(max_ans, ans)
        
        print(ans_A, ans_B)
        return max_ans

2024年6月22号

2663. Lexicographically Smallest Beautiful String

思路

代码

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        for i in range(len(s) - 1, -1, -1):
            blockedCharacters = set()
            for j in range(1, 3):
                if i - j >= 0:
                    blockedCharacters.add(s[i - j])
            for j in range(1, 4):
                if ord(s[i]) - ord('a') + j + 1 <= k and chr(ord(s[i]) + j) not in blockedCharacters:
                    return self.generate(s, i, j)
        return ""

    def generate(self, s: str, idx: str, offset: str) -> str:
        res = list(s)
        res[idx] = chr(ord(res[idx]) + offset)
        for i in range(idx + 1, len(s)):
            blockedCharacters = set()
            for j in range(1, 3):
                if i - j >= 0:
                    blockedCharacters.add(res[i - j])
            for j in range(3):
                if chr(ord('a') + j) not in blockedCharacters:
                    res[i] = chr(ord('a') + j)
                    break
        return ''.join(res)

2024年6月23号

520. Detect Capital

思路

代码

class Solution:
    def detectCapitalUse(self, word: str) -> bool:
        return word.isupper() or word.islower() or word == word.capitalize()

2024年6月24号

503. Next Greater Element II

思路

代码

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ret = [-1] * n
        stk = list()

        for i in range(n * 2 - 1):
            while stk and nums[stk[-1]] < nums[i % n]:
                ret[stk.pop()] = nums[i % n]
            stk.append(i % n)
        
        return ret

2024年6月25号

2732. Find a Good Subset of the Matrix

思路

代码

class Solution:
    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:
        mask_to_idx = {}
        for i, row in enumerate(grid):
            mask = 0
            for j, x in enumerate(row):
                mask |= x << j
            if mask == 0:
                return [i]
            mask_to_idx[mask] = i

        for x, i in mask_to_idx.items():
            for y, j in mask_to_idx.items():
                if (x & y) == 0:
                    return sorted((i, j))
        return []

2024年6月26号

2741. Special Permutations

思路

代码

class Solution:
    def specialPerm(self, nums: List[int]) -> int:
        n = len(nums)
        u = (1 << n) - 1
        @cache
        def dp(s, i):
            if s == u:
                return 1
            else:
                pre = nums[i]
                res = 0
                for j in range(n):
                    if (s >> j) & 1 == 0 and (nums[j] % pre == 0 or pre % nums[j] == 0):
                        res += dp(s | 1 << j, j)
                return res
        final_res = 0
        for i in range(n):
            final_res += dp(0 | 1 << i, i)
        final_res %= (10 ** 9+ 7)
        return final_res

2024年6月27号

忘记做了= =
暂停一礼拜，由于最近学校在期中，任务繁重，需要调整，预计7月8日更新