Leetcode daily question 2022/2/28-2022/3/6

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

2/28 1601. The maximum number of transfer requests that can be reached

because requests Only up to 16 individual
We can enumerate all requests
Use one 16 The binary number of bits represents the case of fetching several requests 1 On behalf of the implementation request
After simulating each request If the situation is satisfied Then the maximum number of update requests

def maximumRequests(n, requests):
    """ :type n: int :type requests: List[List[int]] :rtype: int """
    ans = 0
    m = len(requests)
    def onenum(num):
        one = 0
        while num:
            num&=(num-1)
            one+=1
        return one
        
    for mask in range(1<<m):
        num = onenum(mask)
        if num<ans:
            continue
        l = [0]*n
        for i,(x,y) in enumerate(requests):
            if mask&(1<<i):
                l[x]-=1
                l[y]+=1
        tag = True
        for i in range(n):
            if l[i]!=0:
                tag = False
                break
        if tag:
            ans = num
    return ans

3/1 6. Z Font conversion

Location 0 Start calculating
The first j That's ok The first number is j There are two types of intervals step1=2*(n-j-1) step2 = 2*j

def convert(s, numRows):
    """ :type s: str :type numRows: int :rtype: str """
    if numRows==1:
        return s
    ans = ""
    num = len(s)
    for j in range(numRows):
        step1 = 2*(numRows-j-1)
        step2 = 2*j
        if step1==0 or step2==0:
            step1,step2=max(step1,step2),max(step1,step2)
        steps = [step1,step2]
        loc = j
        v = 0
        while loc<num:
            ans += s[loc]
            loc +=steps[v%2]
            v+=1
    return ans

3/2 564. Looking for the latest palindromes

If the number of digits changes The closest one is definitely 100…001 One less must be 99…99
Two cases can be specially considered
If the number of digits does not change In order to minimize the difference Definitely change the second half
The first half remains unchanged num=len(n) The first half is x=(num+1)//2 position
consider x-1,x,x+1 In three cases

def nearestPalindromic(n):
    """ :type n: str :rtype: str """
    num = len(n)
    more = 10**num+1
    less = 10**(num-1)-1
    ans = ""
    
    if len(n)==1:
        return str(int(n)-1)
    
    ori = int(n)
    diff = min(more-ori,ori-less)
    if more-ori<ori-less:
        ans = str(more)
    else:
        ans = str(less)
 
    half = int(n[:(num+1)//2])
    for x in range(half-1,half+2):
        if num%2==0:
            y = x
        else:
            y = x//10
        while y:
            x = x*10+y%10
            y//=10
        if x==ori:
            continue
        print(x,abs(x-ori),diff,ans)
        if abs(x-ori)<diff or(abs(x-ori)==diff and len(ans)>len(str(x))):
            diff = abs(x-ori)
            ans = str(x)
    
    return ans

3/3 258. Members add

simulation Take everyone and

def addDigits(num):
    """ :type num: int :rtype: int """
    while num>9:
        tmp = num
        num = 0
        while tmp>0:
            num += tmp%10
            tmp = tmp//10
    return num

3/4 2104. Subarray range and

1. violence Traverse all subarrays
2. Monotonic stack
Contribution as a maximum ：
Maintain a monotonic decreasing stack x,y (nums[x]>nums[y])
If at this time z The value of position is greater than y Need to deal with y
y Number of subarrays as the maximum (y-x)*(z-y)
Contribution: nums[y]* Number
As a minimum contribution similar Only the contribution is negative

def subArrayRanges(nums):
    """ :type nums: List[int] :rtype: int """
    n = len(nums)
    ans = 0
    for i in range(n-1):
        maxv,minv = nums[i],nums[i]
        for j in range(i+1,n):
            maxv = max(maxv,nums[j])
            minv = min(minv,nums[j])
            ans += maxv-minv
    return ans

def subArrayRanges2(nums):
    """ :type nums: List[int] :rtype: int """
    ans=0
    stack = []
    for i,num in enumerate(nums+[float('inf')]):
        while stack and nums[stack[-1]]<num:
            j = stack.pop()
            left = stack[-1] if stack else -1
            ans += nums[j]*(i-j)*(j-left)
        stack.append(i)
    stack = []
    for i,num in enumerate(nums+[float('-inf')]):
        while stack and nums[stack[-1]]>num:
            j = stack.pop()
            left = stack[-1] if stack else -1
            ans -= nums[j]*(i-j)*(j-left)
        stack.append(i)
    return ans

3/5 521. The longest special sequence Ⅰ

If two strings are equal There is no
Otherwise, the longest string subsequence takes itself It must not be a subsequence of another

def findLUSlength( a, b):
    """ :type a: str :type b: str :rtype: int """
    if a==b:
        return -1
    return max(len(a),len(b))

3/6 2100. Suitable for bank robbery

front time Day non increasing after time Days are not decreasing
Consider the two conditions separately
qian[i] Used to record the position from front to back i The longest non progressive growth
hou[i] Used to record from i The longest non decreasing length in the future

def goodDaysToRobBank(security, time):
    """ :type security: List[int] :type time: int :rtype: List[int] """
    n = len(security)
    qian,hou = [0]*n,[0]*n
    for i in range(1,n):
        if security[i]<=security[i-1]:
            qian[i] = qian[i-1]+1
        if security[n-i-1]<=security[n-i]:
            hou[n-i-1]=hou[n-i]+1
    ans = []
    for i in range(time,n-time):
        if qian[i]>=time and hou[i]>=time:
            ans.append(i)
    return ans