abcdefgh

492. 构造矩形

Leetcode

class Solution:
    def constructRectangle(self, area: int) -> List[int]:
        '''
        w = 1
        for i in range(1, int(area**0.5)+1):
            if area % i == 0: w = i
        '''
        w = int(area ** 0.5)
        while area % w: w -= 1          
            
        return [area//w, w]

507. 完美数

Leetcode
知识点： while // % == != 条件可不断的变化，for 范围不变。

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num == 1: return False # 1 特别处理，不是完美数。
        x, i = 1, 2
		
        while i*i < num:
            if num % i == 0:
                x += i # 累计正因子和
                if i != num // i: # 相同避免加两次
                    x += num // i
            i += 1
        return x == num

575. 分糖果

Leetcode
知识点： 集合 set set.add，去重功能，无序，分类。// 整除、/ 除法。

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:        
        n = len(candyType)//2
        s = set()
        for c in candyType:
            s.add(c)
        
        return len(s) if len(s) <= n else n
        
        #return min(len(candyType)//2, len(set(candyType)))            

860. 柠檬水找零

Leetcode
知识点： 条件语句 分支的实现

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five, ten = 0, 0
        for i in bills:
            if i == 5:
                five += 1
            if i == 10:
                ten += 1
                five -= 1
            if i == 20:
                if ten > 0: # 先找 10 元的
                    ten -= 1
                    five -= 1
                else:
                    five -= 3
            if five < 0:
                return False
                
        return True

888. 公平的糖果棒交换

Leetcode
知识点： sum set 总体差的一半通过交换重新分配

class Solution:
    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
        a, b = sum(aliceSizes), sum(bobSizes)
        c, d = aliceSizes, set(bobSizes)
        for i in c:                    
            j = (b - a)//2 + i
            if j in d:
                return [i, j]                    

941. 有效的山脉数组

Leetcode

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:        
        n = len(arr)
        if n < 3: return False
        i, j = 0, n-1
        
        while i < n-2 and arr[i+1] > arr[i]: # 从左向右，至多到倒数第二个。
        	i += 1    
        while j > 1 and arr[j] < arr[j-1]:  # 从右向左，至少到第二个
        	j -= 1
        
        return i == j           

1089. 复写零

Leetcode

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        '''
        # 方法一：insert pop
        i = 0
        
        while i < len(arr):
            if not arr[i]:
                arr.insert(i, 0)
                i += 1
                arr.pop()
            i += 1
        '''
        '''
        # 方法二：添加标记
        n = len(arr)
        flag = True

        for i in range(n):
            if not arr[i] and flag:
                flag = False
                j = n - 1
                while j > i:
                    arr[j] = arr[j-1]
                    j -= 1
            else:flag = True
           
        '''   
        '''     
        # 方法三：
        n = len(arr)
        i = j = 0
        while j <= n-1:
            if arr[j]:i += 1
            j += 1
        j -= 1   
        i -= 1
        while i > 0:
            if arr[i]:
                arr[j] = arr[i]               
                
            else:
                arr[j] = 0
                j -= 1
                arr[j] = 0
            i -= 1
            j -= 1
        '''    
            
          
        n = len(arr)
        i = j = 0
        while j < n:
            if arr[i] == 0: j += 1
            i += 1
            j += 1
        
        i -= 1    # i 回到最后一次合法的位置
        j -= 1    # j 同理，但 j 仍可能等于 n（例如输入 [0]）
        while i >= 0:
            if j < n: arr[j] = arr[i]
            if arr[i] == 0:
                j -= 1
                arr[j] = arr[i]
            i -= 1
            j -= 1

1184. 公交站间的距离

Leetcode

class Solution:
    def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
       
        if destination < start: # 交换出发点和目的地距离相等
            start, destination = destination, start
            
        d = sum(distance[start:destination]) # 出发点到目的地距离

        return min(d, sum(distance) - d)

1200. 最小绝对差

Leetcode

方法一：超时

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        res, n, tmp = [], len(arr), inf
        
        for i in range(n-1):
            for j in range(i+1,n):
                a, b = arr[i], arr[j]
                if a > b:
                    a, b = b, a
                x = b - a
                
                if x == tmp: 
                    res.append([a, b])
                   
                elif x < tmp:
                    tmp = x
                    res = [[a, b]]

        res.sort()
        return res

方法二：排序

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        min_, res, n = inf, [], len(arr)
        for i in range(1, n):
            a, b = arr[i-1], arr[i]
            if (x := b - a) < min_: # 因为有序， x >= 0
                res = [[a, b]]
                min_ = x
            elif x == min_:
                res.append([a, b])
                
        return res

1281. 整数的各位积和之差

Leetcode

class Solution:
    def subtractProductAndSum(self, n: int) -> int:
        s, p = 0, 1
        while n:
            n, rem = divmod(n, 10)
            s += rem
            p *= rem
            
        return p - s

1299. 将每个元素替换为右侧最大元素

Leetcode

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        n = len(arr)
        m = max(arr)
        for i in range(n):
            if i < n-1 and arr[i] == m:
                m = max(arr[i+1:])
            
            arr[i] = m
                    
        arr[-1] = -1
        
        return arr

1346. 检查整数及其两倍数是否存在

Leetcode

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        '''
        n = len(arr)
        for i in range(n-1):
            for j in range(i+1,n):
                if arr[i] == 2 * arr[j] or 2 * arr[i] == arr[j]:
                    return True
        
        return False
        '''
        zero = False
        for i, e in enumerate(arr):   
            if not e:
                if zero:return True
                zero = True      
                
            if e%2 == 0 and e != 0:
                if e//2 in arr:
                    return True
        return False

1436. 旅行终点站

Leetcode
知识点： 列表 list，append。
教程：Python 1-14 列表

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        start, end = [], []
        for s, e in paths:
            start.append(s)
            end.append(e)

        for x in end:
            if x not in start:
                return x

**知识点：**推导式，生成器，next。
教程：Python 推导式

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        citiesA = {path[0] for path in paths}
        return next(path[1] for path in paths if path[1] not in citiesA)

1437. 是否所有 1 都至少相隔 k 个元素

Leetcode

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        tmp = k
        for i in range(len(nums)):
            if nums[i] == 1:
                if k > tmp:return False
                tmp = 0
            else:
                tmp += 1

        return True 

1700. 无法吃午餐的学生数量

Leetcode

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        # n = 0
        # while n < len(students):
        #     if students[0] == sandwiches[0]:
        #         students.pop(0)
        #         sandwiches.pop(0)
        #         n = 0
        #     else:
        #         students = students[1:] + [students[0]]
        #         n += 1
        # return n

        cnt = [0, 0]  # 统计喜欢圆形和方形三明治学生数量
        for i in students:
            cnt[i] += 1

        for i in sandwiches:    # 依次取出栈顶三明治,直到没有学生喜欢 i。
            if cnt[i] == 0:                
                break

            cnt[i] -= 1

        return sum(cnt)

1984. 学生分数的最小差值

Leetcode

方法一：排序 滑动窗口

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:

        nums.sort()
        res = inf
        for i in range(len(nums) - k + 1):
            res = min(res, nums[i + k - 1] - nums[i])
            
        return res 

1995. 统计特殊四元组

Leetcode

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        
        res = 0
        n = len(nums)
        for i in range(n-3):
            for j in range(i+1,n-2):
                for k in range(j+1,n-1):
                    for l in range(k+1,n):
                        if nums[i]+nums[j]+nums[k] == nums[l]:
                            res += 1
        return res

2006. 差的绝对值为 K 的数对数目

Leetcode

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        '''
        res, n = 0, len(nums)
        
        for i in range(n):
            for j in range(i+1, n):
                if abs(nums[i]-nums[j]) == k:
                    res += 1
        return res
        '''
        res, d = 0, defaultdict(int)

        for i in nums:
            d[k+i] += 1
        for i in nums:          
            res += d[i]

        return res

2011. 执行操作后的变量值

Leetcode

class Solution:
    def finalValueAfterOperations(self, operations: List[str]) -> int:
        x = 0
        for i in operations:
            # if i in ["++X", "X++"]:

            # if '+' in i:
            #     x += 1
            # else:
            #     x -= 1

            x += 1 if '+' in i else -1
            
        return x

        # return sum(1 if  "+" in op else -1 for op in operations)

2016. 增量元素之间的最大差值

Leetcode

class Solution:
    def maximumDifference(self, nums: List[int]) -> int:
        res, n = -1, len(nums)
        #for i in range(n-1):
            #for j in range(i+1, n):
                #if nums[i] < nums[j]:                    
                    #res = max(res, nums[j]-nums[i])

        for i in range(1,  n):
            res = max(res, nums[i] - min(nums[:i]))

        return res if res else -1