LeetCode 每日一题 2024/4/8-2024/4/14

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

4/8 2009. 使数组连续的最少操作数

将nums数组去重从小到大排序
假设x为排好序后的最大值
对于n=len(nums) 范围为x-n+1~x
将[x-n+1,x]看做一个区间
尽可能将更多地数能够出现在这个区间内

def minOperations(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    n = len(nums)
    nums = list(set(nums))
    nums.sort()
    left = 0
    ans = 0
    for i,x in enumerate(nums):
        while nums[left]<x-n+1:
            left+=1
        ans = max(ans,i-left+1)
    return n-ans

4/9 2529. 正整数和负整数的最大计数

从头遍历 记录正负数的个数

def maximumCount(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    neg,pos=0,0
    for num in nums:
        if num<0:
            neg+=1
        if num>0:
            pos+=1
    return max(neg,pos)

4/10 1702. 修改后的最大二进制字符串

最终结果最多有1个0
如果字符串没有0 直接返回结果
如果有0 结果中0的位置取决于字符串第一个0的位置
之后每多一个0 可以向后移动一位

def maximumBinaryString(binary):
    """
    :type binary: str
    :rtype: str
    """
    n = len(binary)
    i = binary.find("0")
    if i<0:
        return binary
    cnt = binary.count('0')
    s = ['1']*n
    s[i+cnt-1] = '0'
    return ''.join(s)

4/11 1766. 互质树

数值范围在1~50之间
gcd[i]表示与i互质的数

def getCoprimes(nums, edges):
    """
    :type nums: List[int]
    :type edges: List[List[int]]
    :rtype: List[int]
    """
    import math
    n=len(nums)
    gcd = [[] for _ in range(51)]
    tmp = [[] for _ in range(51)]
    ans = [-1]*n
    dep = [-1]*n
    g = [[] for _ in range(n)]
    
    def dfs(x,dp):
        dep[x] = dp
        for v in gcd[nums[x]]:
            if not tmp[v]:
                continue
            las = tmp[v][-1]
            if ans[x]==-1 or dep[las]>dep[ans[x]]:
                ans[x]=las
        tmp[nums[x]].append(x)
        for v in g[x]:
            if dep[v]==-1:
                dfs(v,dp+1)
        tmp[nums[x]].pop()
    for i in range(1,51):
        for j in range(1,51):
            if math.gcd(i,j)==1:
                gcd[i].append(j)
    for x,y in edges:
        g[x].append(y)
        g[y].append(x)
    dfs(0,1)
    return ans

4/12 2923. 找到冠军 I

遍历
1.如果是冠军 那么那一行的总和为n-1
2.依次比较n次 假设当前为冠军ans 如果遇到了grid[i][ans]==1
说明i比ans要厉害 那么假设i为冠军 最后剩下的ans就是冠军

def findChampion(grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    n = len(grid)
    for i in range(n):
        if sum(grid[i])==n-1:
            return i

def findChampion2(grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    n = len(grid)
    ans = 0
    for i in range(1,n):
        if grid[i][ans]==1:
            ans = i
    return ans

4/13 2924. 找到冠军 II

依次遍历[a,b] 去除所有b
如果剩下只有一个 那么这个就是冠军

def findChampion(n, edges):
    """
    :type n: int
    :type edges: List[List[int]]
    :rtype: int
    """
    s = set(list(range(n)))
    for _,b in edges:
        if b in s:
            s.remove(b)
    return s.pop() if len(s)==1 else -1

4/14 705. 设计哈希集合

使用一个10**6+1长度的数组l 记录l[key]是否在集合中

class MyHashSet(object):

    def __init__(self):
        self.l = [0]*(10**6)


    def add(self, key):
        """
        :type key: int
        :rtype: None
        """
        self.l[key]=1


    def remove(self, key):
        """
        :type key: int
        :rtype: None
        """
        self.l[key]=0


    def contains(self, key):
        """
        :type key: int
        :rtype: bool
        """
        return self.l[key]==1