菜鸡解题1

Leetcode
关键：题目中关键信息
题解：自己或别人的解题思路
特解：这道题使用特殊方法
Get：学到的点

2869. 收集元素的最少操作次数

题解：从数组末端开始，标记数组，只有小于K的去求余标记，然后求和查一下是不是全1。全1返回结果

class Solution(object):
    def minOperations(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        flag = [0] * k
        for i in range(len(nums)-1, -1, -1):
            if nums[i]<=k:
                flag[nums[i]%k] = 1
                if sum(flag) == k:
                    return len(nums)-i

题解：创建k的集合从集合里删除数字，为空返回。

2974. 最小数字游戏

关键：bob先加入arr，Alice后加。为什么要刻意强调数组是偶数长度？

特解：排序后两两交换大的在前。

class Solution(object):
    def numberGame(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        nums.sort()
        for i in range(0, len(nums), 2):
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
        return nums

Get：pop时候从后往前删，不然会越界。

1103. 分糖果 II

题解：等差序列为1求序列和公式，对糖果数量 candies 求解并向下取整，得到的是每次增加一个可以分给几个小朋友 n（有剩余，因为使用的是取整），然后生成一个 1 到 n 的等差序列数组，数组最后加上剩余的糖果。遍历序列下标，下标对 num_people 求余加到最终答案数组里。

class Solution(object):
    def distributeCandies(self, candies, num_people):
        """
        :type candies: int
        :type num_people: int
        :rtype: List[int]
        """
        import math
        pre_check = math.floor((((-1) + (math.sqrt(1 + 8 * candies))) / 2))
        leaf_candy = int(candies - (pre_check * (pre_check + 1) / 2))
        series = [i for i in range(1,int(pre_check+1))]
        series = series + [leaf_candy] if leaf_candy > 0 else series
        res = [0] * num_people
        for i in range(0, len(series)):
            res[i % num_people] = res[i % num_people] + series[i]
        return res

944. 删列造序

题解：获取 strs 长度 l 代表一列的字符串长度，l_str 是有几列。然后相邻两个比较大小（python直接比价ASCII值）如果发生前面比后面大就说明不是严格递增。

class Solution(object):
    def minDeletionSize(self, strs):
        """
        :type strs: List[str]
        :rtype: int
        """
        l = len(strs)
        l_str = len(strs[0])

        res = 0
        for i in range(l_str):
            for j in range(l-1):
                if strs[j][i] > strs[j+1][i]:
                    res += 1
                    break
        return res

3142. 判断矩阵是否满足条件

题解：判断所有竖列相同，任选一行判断横向相邻不相同。

class Solution(object):
    def satisfiesConditions(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: bool
        """
        for i in range(len(grid[0])-1):
            k = grid[0][i]
            if grid[0][i] == grid[0][i+1]:
                return False
            for j in range(len(grid)):
                if grid[j][i] != k:
                    return False

        k = grid[0][len(grid[0])-1]
        for j in range(len(grid)):
            if grid[j][len(grid[0])-1] != k:
                return False
        return True

1450. 在既定时间做作业的学生人数

题解：要求 queryTime 处于 [startTime[i], endTime[i]] 之间。

class Solution(object):
    def busyStudent(self, startTime, endTime, queryTime):
        """
        :type startTime: List[int]
        :type endTime: List[int]
        :type queryTime: int
        :rtype: int
        """
        res = 0
        for i in range(len(startTime)):
            if endTime[i] < queryTime:
                continue
            else:
                if startTime[i] <= queryTime:
                    res += 1
        return res

其他题解：用flag标记，开始时间值为1，结束时间值为-1，从开头截取数组到queryTime 即 flag[:queryTime + 1]求和就是结果。

Get：有人在评论区问这样枚举 就可以了，其他方案都是来搞笑的，但是对于多次查询的话其他题解的方式就是一劳永逸。

3153. 所有数对中数位差之和

题解：数字长度一样，按照个十百的顺序处理每一位，对最后一位取余使用 flag 统计个数，最后对 flag 数组计算每个元素乘它右边元素值加到 res 上（比如个位4出现两次，5出现三次，那么这5个数不管其他位，个位比较且不同次数至少为2*3=6次，只能乘右边是避免重复）

class Solution(object):
    def sumDigitDifferences(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        len_num = len(str(nums[0]))
        res = 0
        for i in range(len_num):
            flag = [0]*10
            for j in nums:
                flag[(j // 10**i) % 10] += 1
            # print(flag)
            for m in range(10):
                if flag[m] > 0:
                    for n in range(m+1, 10):
                        if flag[n] > 0:
                            res += flag[m]*flag[n]
        return res

官方题解差不多，它是都乘结果除以2。

3127. 构造相同颜色的正方形

题解：遍历格子的右、右下、下。统计相同颜色超过3个就返回 True。

        for i in range(2):
            for j in range(2):
                flag = []
                flag.append(grid[i][j])
                flag.append(grid[i+1][j])
                flag.append(grid[i][j+1])
                flag.append(grid[i+1][j+1])
                from collections import Counter
                cnt = Counter(flag)
                for value in cnt.values():
                    if value >= 3:
                        return True
        return False

2024. 考试的最大困扰度

题解：就是判断最大连续的字符数，但是可以修改字符使其更长。使用滑动窗口。以 T 为例，left 和 right 记录最长的区间，sum 记录为 F 的区间长度。right 往右移，遇 T 不增加 F 增加 sum，如果 sum 大于 k，则左区间也往右移清零，ans 记录最大值答案。

class Solution(object):
    def maxConsecutiveAnswers(self, answerKey, k):
        """
        :type answerKey: str
        :type k: int
        :rtype: int
        """
        def maxCont(ch):
            left,ans,sum=0,0,0
            for right in range(len(answerKey)):
                sum += answerKey[right] != ch
                while sum > k:
                    sum -= answerKey[left] != ch
                    left += 1
                ans = max(ans,right-left+1)
            return ans
        return max(maxCont('T'),maxCont('F'))

同1004. 最大连续1的个数 III

2708. 一个小组的最大实力值

class Solution(object):
    def maxStrength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = sorted(nums)
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            ans = nums[0] * nums[1]
            if ans <= 0:
                return max(nums)
            return ans

        pos_cnt, zero_cnt, neg_cnt = 0, 0, 0
        ans = 1
        max_nav = -10
        for i in range(len(nums)):
            if nums[i] == 0:
                zero_cnt += 1
                continue
            if nums[i] > 0:
                pos_cnt += 1
            else:
                max_nav = max(max_nav, nums[i])
                neg_cnt += 1

            ans *= nums[i]
        if pos_cnt == 0:
            if neg_cnt == 1 or neg_cnt == 0:
                return 0
        if ans < 0:
            ans = ans // max_nav
        return ans

题解：分类讨论，我要气晕了。感觉代码里我考虑情况重复了。

  • 仅有一个数，直接返回。
  • 数组中小于等于1个负数，其他都是0，在 ans // max_nav 时要注意最大值是0。
  • 其他情况，非零数全乘，如果值为正返回，如果值为负，除以最大的非零负数 max_nav就是答案。