Leetcode daily question 2021/12/13-2021/12/19

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

12/13 807. Keep the city skyline

Find each line Maximum height of each column
For location i,j The maximum height is min( The first i Yes max, The first j Column max)

def maxIncreaseKeepingSkyline(grid):
    """ :type grid: List[List[int]] :rtype: int """
    n,m = len(grid),len(grid[0])
    col,row = [0]*m,[0]*n
    for i in range(n):
        for j in range(m):
            row[i] = max(row[i],grid[i][j])
            col[j] = max(col[j],grid[i][j])
    ans = 0
    for i in range(n):
        for j in range(m):
            new =  min(row[i],col[j])
            ans += new-grid[i][j]
    return ans

12/14 630. The curriculum III

Sort the deadline dates from small to large
Put the time into the big top pile If the current time consumption cannot be met But smaller than the maximum in the heap Replace

def scheduleCourse(courses):
    """ :type courses: List[List[int]] :rtype: int """
    import heapq
    l=[]
    heapq.heapify(l)
    courses.sort(key = lambda x:x[1])
    now = 0
    for d,last in courses:
        if now+d<=last:
            now +=d
            heapq.heappush(l,-d)
        elif len(l)>0 and -l[0]>d:
            now = now-l[0]-d
            heapq.heapreplace(l,-d)
    return len(l)

12/15 851. Noise and wealth

According to the regulation I must meet the requirements
m[i] Record all ratios i Rich number
Deep search
about i Initialize to itself
Search all than i A rich man j( Ensure that all j Have found the quietest person )
Find the quietest person
dfs Used to determine the number num Result

def loudAndRich(richer, quiet):
    """ :type richer: List[List[int]] :type quiet: List[int] :rtype: List[int] """
    from collections import defaultdict
    m = defaultdict(list)
    for x,y in richer:
        m[y].append(x)
    n = len(quiet)
    ans = [-1]*n
    def dfs(num):
        if ans[num]!=-1:
            return
        ans[num]=num
        for i in m[num]:
            dfs(i)
            if quiet[ans[i]]<quiet[ans[num]]:
                ans[num] = ans[i]
    for i in range(n):
        dfs(i)
    return ans

12/16 1610. The maximum number of visible points

Use tangent atan Representative points and loc The angle of [-π,π] Put all the points +2π Can be connected -π And π The area between
Sort the angles There are at most several points to judge by sliding the window
Special considerations and loc Coincidence point

import math
def visiblePoints(points, angle, location):
    """ :type points: List[List[int]] :type angle: int :type location: List[int] :rtype: int """
    same = 0
    deg = []
    for p in points:
        if p==location:
            same+=1
        else:
            deg.append(math.atan2(p[1]-location[1],p[0]-location[0]))
    deg.sort()
    n = len(deg)
    deg += [v+2*math.pi for v in deg]
    maxc = 0
    angdeg = angle*math.pi/180
    r = 0
    for l in range(n):
        while r<2*n and deg[r]<=deg[l]+angdeg:
            r+=1
        maxc = max(maxc,r-l)
    return maxc+same

12/17 1518. Wine exchange

simulation
empty Represents the number of empty bottles
new Represents the current number of empty bottles that can be exchanged
Empty bottles are updated every time

def numWaterBottles(numBottles, numExchange):
    """ :type numBottles: int :type numExchange: int :rtype: int """
    ans = numBottles
    empty = numBottles
    while empty>=numExchange:
        new = empty//numExchange
        ans += new
        empty = empty%numExchange + new
    return new

12/18 419. Warships on deck

Find the upper left starting point of each warship Each starting point is marked with one

def countBattleships(board):
    """ :type board: List[List[str]] :rtype: int """
    n,m = len(board),len(board[0])
    ans =0
    for i in range(n):
        for j in range(m):
            if board[i][j]=='X' and (board[i-1][j]=='.' or i==0) and (board[i][j-1]=='.' or j==0):
                ans +=1
    return ans

12/19 997. Find the judge in town

m[i] Record i How many people believe
ub Record people who don't trust others

def findJudge(n, trust):
    """ :type n: int :type trust: List[List[int]] :rtype: int """
    from collections import defaultdict
    m = defaultdict(int)
    ub = set(list(range(1,n+1)))
    for a,b in trust:
        m[b]+=1
        if a in ub:
            ub.remove(a)
    if len(ub)==1:
        num = ub.pop()
        if m[num]==n-1:
            return num
    
    return -1