Leetcode daily question 2021/11/22-2021/11/28

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

11/22 384. Scramble the array

i Consider the location for the current
i The number of positions is randomly from [i,n] Choose one of loc
In exchange for i,loc The numerical Continue to consider the next position

import random
class Solution(object):

    def __init__(self, nums):
        """ :type nums: List[int] """
        self.n = len(nums)
        self.ori = nums


    def reset(self):
        """ :rtype: List[int] """
        return self.ori


    def shuffle(self):
        """ :rtype: List[int] """
        ans = []
        ans.extend(self.ori)
        for i in range(self.n):
            loc = random.randint(i,self.n-1)
            ans[i],ans[loc]=ans[loc],ans[i]
        return ans
        

11/23 859. Intimate string

Consider the situation
Different length Definitely not
If the strings are exactly the same Duplicate characters are required
Traversal string Record different numbers of characters
If there are more than two or only one, you can't
If there are two differences Determine whether to exchange the same

def buddyStrings(s, goal):
    """ :type s: str :type goal: str :rtype: bool """
    if len(s)!=len(goal):
        return False
    if s==goal:
        if len(set(s))==len(s):
            return False
        return True
    diff = 0
    diffs = []
    diffg = []
    for i in range(len(s)):
        if s[i]!=goal[i]:
            diff+=1
            diffs.append(s[i])
            diffg.append(goal[i])
            if diff>2:
                return False
    if diff==2:
        if diffs[0]==diffg[1] and diffs[1]==diffg[0]:
            return True
        return False
    if diff==1:
        return False

11/24 423. Reconstructing Chinese from English

Consider according to the special letters of each word
zero-z,two-w,four-u,six-x,eight-g
one-o,three-r,five-f,seven-s
nine-n

def originalDigits(s):
    """ :type s: str :rtype: str """
    from collections import defaultdict
    m = defaultdict(int)
    for c in s:
        m[c]+=1
    l = [0]*10
    
    l[0] = m['z']
    l[2] = m['w']
    l[4] = m['u']
    l[6] = m['x']
    l[8] = m['g']
    
    l[1] = m['o'] - l[0]-l[2]-l[4]
    l[3] = m['r'] - l[4]-l[0]
    l[5] = m['f'] - l[4]
    l[7] = m['s'] - l[6]
    l[9] = m['i'] - l[5]-l[6]-l[8]

    ans = ""
    for i in range(10):
        ans += str(i)*l[i]
    return ans

11/25 458. A Poor Pig

First of all, there is only one piglet
m = minutesToTest/minutesToDie
m It means that without drinking poison Pigs can mix with a few buckets of water at most
Then a little pig can judge at most n=m+1 Poison in the barrel of liquid If I drink m The bucket is not dead It means that the last bucket is poison
Now if there are two piglets Then consider according to two dimensions
hypothesis m=2 Every time we give a pig a drink 3 A barrel of liquid Piglets 1 Drink one line at a time Piglets 2 Drink one column at a time
x x x
x x x
x x x
If piglets 1 In the 1 OK, dead Piglets 2 In the 2 The column is dead Explain that the position of the poison is in the first row and the second column
If piglets 1 I didn't die after drinking two lines Piglets 2 I didn't die after drinking two columns It means that the poison is in the third row and the third column
Thus we can see that Two piglets can tell 33=9 Poison in the barrel of liquid And nn
A derivation Three piglets can try to think in three dimensions You can try nnn Bucket of poison
Back to topic It is known that n=minutesToTest/minutesToDie+1 bucket buckets It is known that Ask for the number of piglets
And n**x<=buckets Minimum x

def poorPigs(buckets, minutesToDie, minutesToTest):
    """ :type buckets: int :type minutesToDie: int :type minutesToTest: int :rtype: int """
    n = minutesToTest/minutesToDie+1
    num = 0
    tmp = 1
    while tmp<buckets:
        tmp *= n
        num +=1
    return num

11/26 700. Search in binary search tree

according to BTS Properties of
Find the left subtree smaller than the current node Find the right subtree larger than the current node

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def searchBST(root, val):
    """ :type root: TreeNode :type val: int :rtype: TreeNode """
    node = root
    while node:
        if node.val==val:
            return node
        elif node.val<val:
            node = node.right
        else:
            node = node.left
    return node

11/27 519. Random flip matrix

total Record the number of selectable positions currently owned
Each time from [0,total-1] Choose from idx = x*n+y (x,y)
Select a value to exchange the current position and the last position Use map Record map[idx]=total

import random
class Solution(object):

    def __init__(self, m, n):
        """ :type m: int :type n: int """
        self.m=m
        self.n=n
        self.total = m*n
        self.map = {
    }


    def flip(self):
        """ :rtype: List[int] """
        tmp = random.randint(0,self.total-1)
        self.total-=1
        idx = self.map.get(tmp,tmp)
        self.map[tmp] = self.map.get(self.total,self.total)
        return [idx//self.n,idx%self.n]


    def reset(self):
        """ :rtype: None """
        self.map={
    }
        self.total = self.n*self.m

11/28 438. Find all alphabetic words in the string

The sliding window
need Record the number of characters required
window Record the number of characters in the current window
left,right Record the left and right boundaries of the sliding window
allvalid Represents the required character type
valid Represents the type of characters that the current window meets

def findAnagrams(s, p):
    """ :type s: str :type p: str :rtype: List[int] """
    from collections import defaultdict
    need=defaultdict(int)
    window = defaultdict(int)
    for c in p:
        need[c]+=1
    left,right=0,0
    valid=0
    allvalid = len(need)
    ret = []
    while right<len(s):
        c = s[right]
        right+=1
        if need[c]>0:
            window[c]+=1
            if window[c]==need[c]:
                valid+=1
        while right-left>=len(p):
            if valid==allvalid:
                ret.append(left)
            d = s[left]
            left+=1
            if need[d]>0:
                if window[d]==need[d]:
                    valid-=1
                window[d]-=1
    return ret