Leetcode daily question 2022/1/31-2022/2/6

The preliminary problem-solving ideas are recorded And local implementation code ; Not necessarily optimal I also hope you can discuss Progress together

1/31 1342. Turn the number into 0 The number of operations

simulation

def numberOfSteps(num):
    """ :type num: int :rtype: int """
    ans = 0 
    while num>0:
        if num%2==0:
            num=num//2
        else:
            num=num-1
        ans+=1
    return ans
                

2/1 1763. The longest nice substring

low,up Record which characters appear in lowercase and uppercase respectively altogether 26 position
If low==up It indicates that the characters in upper and lower case are consistent
Enumerate all substrings

def longestNiceSubstring(s):
    """ :type s: str :rtype: str """
    n = len(s)
    loc,leng = 0,0
    for i in range(n):
        low,up = 0,0
        for j in range(i,n):
            if s[i].islower():
                low |=1<<(ord(s[j])-ord('a'))
            else:
                up |=1<<(ord(s[j])-ord('A'))
            if low==up and j-i+1>leng:
                loc = i
                leng = j-i+1
    return s[loc:loc+leng]
                

2/2 2000. Reverse word prefix

Find the place where it first appeared loc reverse [0:loc]

def reversePrefix(word, ch):
    """ :type word: str :type ch: str :rtype: str """
    ans = word
    loc = -1
    for i,c in enumerate(word):
        if c==ch:
            loc = i
            break
    if loc>-1:
        ans = word[loc::-1]+word[loc+1:]
    return ans

                

2/3 1414. And for K The minimum number of Fibonacci Numbers

Find the longest Fibonacci sequence needed l
stay l In two points, find less than k The maximum of take k Minus the maximum Keep looking for Until for 0

def findMinFibonacciNumbers(k):
    """ :type k: int :rtype: int """
    l = [1,1]
    if k==1:
        return 1
    
    while k>l[-1]:
        l.append(l[-1]+l[-2])
    ans = 0
    left,right = 0,len(l)-1
    while k>0:
        while left<=right:
            mid = (left+right)//2
            if l[mid]==k:
                ans +=1
                return ans
            elif l[mid]<k:
                left = mid+1
            else:
                right = mid-1
        k -= l[right]
        left,right = 0,left-1
        ans +=1
    return ans    
                

2/4 1725. The number of rectangles that can form the largest square

The minimum side of each rectangle is taken as the side length
Count the number of side lengths And record the maximum side length that has occurred

def countGoodRectangles(rectangles):
    """ :type rectangles: List[List[int]] :rtype: int """
    maxl = 0
    m = {
    }
    for l,w in rectangles:
        k = min(l,w)
        m[k] = m.get(k,0)+1
        maxl = max(maxl,k)
    return m[maxl]
                

2/5 1219. Golden Miner

ans Record the maximum number of gold
Every non 0 All points can be used as a starting point
Search deeply for a starting point to flash back

def getMaximumGold(grid):
    """ :type grid: List[List[int]] :rtype: int """
    m,n=len(grid),len(grid[0])
    ans = 0
    
    def dfs(i,j,gold):
        global ans
        v = grid[i][j]
        gold += v
        ans = max(ans,gold)
        
        grid[i][j] = 0
        for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
            if 0<=x<m and 0<=y<n and grid[x][y]>0:
                dfs(x,y,gold)
        grid[i][j] = v 
        
    for i in range(m):
        for j in range(n):
            if grid[i][j]>0:
                dfs(i,j,0)
    return ans
                

2/6 1748. The sum of the only elements

Count the number of occurrences of each number Accumulate the number that appears once

def sumOfUnique(nums):
    """ :type nums: List[int] :rtype: int """
    m = {
    }
    for num in nums:
        m[num] = m.get(num,0)+1
    ans = 0
    for num in m:
        if m[num]==1:
            ans+=num
    return ans