菜鸡解题1

text

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

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

python

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的集合从集合里删除数字,为空返回。

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

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

python

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时候从后往前删,不然会越界。

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

python

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

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

python

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

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

python

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

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

python

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,从开头截取数组到queryTimeflag[:queryTime + 1]求和就是结果。

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

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

python

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。

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

python

        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

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

python

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

python

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就是答案。