Leetcode daily question 202110

282 Add operators to expressions

The difficulty lies in ：

We consider if only + and - Words , It's easy to combine search with expression . But when there is * when , Due to the problem of operation priority , We need to record things like a + b * c The multiplication part of .

  My thoughts ：

Typical backtracking .

Backtracking termination conditions yes ：

if len(path)==len(num)+len(num)-1 and cal_value(path)==target:
    res.append(path)

My termination condition only considers, for example

123,6.   1+2+3 This situation .

  such as 105,5.10-5 This situation does not take into account .

There is a problem with this termination condition , Not fully considered .

class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        def cal_value(s):
            # Calculate the value of the string 
            fuhao = 1
            left = 0
            right = 2
            if s[fuhao] == '+':
                cur = int(s[left]) + int(s[right])
            elif s[fuhao] == '-':
                cur = int(s[left]) - int(s[right])
            elif s[fuhao] == '*':
                cur = int(s[left]) * int(s[right])
            while right < 2 * len(num) - 2:
                fuhao = fuhao + 2
                right = right + 2
                if s[fuhao] == '+':
                    cur = cur + int(s[right])
                elif s[fuhao] == '-':
                    cur = cur - int(s[right])
                elif s[fuhao] == '*':
                    cur = cur * int(s[right])
            return cur
        def backtracing(num,target,path,start):
            if len(path)==len(num)+len(num)-1 and cal_value(path)==target:
                res.append(path)
            for i in range(start,len(num)):
                if i!=len(num)-1:
                    for f in ['+','-','*']:
                        cur=num[i]+f
                        path=path+cur
                        backtracing(num,target,path,i+1)
                        path=path[:len(path)-2]
                else:
                    cur=num[i]
                    path = path + cur
                    backtracing(num,target,path,i+1)
                    path=path[:len(path)-2]
        res=[]
        path=""
        start=0
        backtracing(num,target,path,start)
        return res

This code can pass part of , Not all of them can pass .

Power button

class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        def backtracing(num,target,path,pre,sum,start,res):
            # Recursive termination condition 
            if start==len(num) and sum==target:
                res.append(''.join(path[:]))
            for i in range(start,len(num)):
                # Handle case, If the beginning is 0, Do not continue 
                if num[start]=='0' and i!=start:
                    break
                s=num[start:i+1]
                val=int(s)
                if start==0:
                    path.append(s)
                    backtracing(num,target,path,val,sum+val,i+1,res)
                    path.pop()
                else:
                    path.append('+')
                    path.append(s)
                    backtracing(num,target,path,val,sum+val,i+1,res)
                    path.pop()
                    path.pop()

                    path.append('-')
                    path.append(s)
                    backtracing(num,target,path,-val,sum-val,i+1,res)
                    path.pop()
                    path.pop()

                    path.append('*')
                    path.append(s)
                    backtracing(num,target,path,val*pre,sum-pre+val*pre,i+1,res)
                    path.pop()
                    path.pop()
        path=[]
        pre=0
        sum=0
        start=0
        res=[]
        backtracing(num,target,path,pre,sum,start,res)
        return res

227 Basic calculator

166 Fractions to decimals

class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        # Analog vertical multiplication 
        a = numerator
        b = denominator
        # If it can divide itself , Directly return the calculation result 
        if a%b ==0:
            return str(a/b)
        res=[]
        # If one of them is negative , Add a minus sign first 
        if a * b < 0:
            res.append('-')
        a=abs(a)
        b=abs(b)
        # Calculate the part before the decimal point , And assign the remainder to  a
        a1=a/b
        res.append(str(a1))
        res.append(".")
        a=a%b
        maps={}
        # Determine whether it is a circular decimal 
        circle=0
        while a>0:
            # Cycle from the decimal place , from res Which bit of the starts the cycle 
            maps[a]=len(res)
            a=a*10
            res.append(a/b)
            a=a%b
            # If the current remainder has occurred before , Will  [ Location of occurrence   To   The current position ]  Pull out the part of （ Cycle the decimal part ）
            if a in maps:
                circle=maps[a]
                break
        print(res)
        print(res[0:2])
        ans=""
        for i in res[0:2]:
            ans=ans+i
        for i in range(2,len(res)):
            if i==circle:
                ans=ans+"("
            ans=ans+str(res[i])
        if circle>0:
            ans=ans+")"
        return ans

230 Binary search tree k Minor elements

 leetcode—hot100- Trees 1_MaYingColdPlay The blog of -CSDN Blog

638 package

python Mutable objects versus immutable objects - You know

python Mutable objects versus immutable objects .

problem ： Is an element a mutable object or an immutable object , For example, word splitting , Recursion , Use one. self.res To judge in each layer of recursion . Guess is a variable object , Check it out

class Solution(object):
    def dfs(self,needs, price, special, maps):
        ans = 0
        needs_str = ''
        for c in needs:
            needs_str = needs_str+str(c) + '_'
        if needs_str in maps.keys():
            return maps[needs_str]
        else:
            #  The weakest way ; Don't buy big gift bags 
            for h in range(len(price)):
                ans = ans + needs[h] * price[h]
            #  Go through each big gift bag , Buy it , See if you can get a cheaper price 
            for i in range(len(special)):
                valid = True
                anext = []
                #  The number of purchases cannot exceed needs
                for j in range(len(price)):
                    if special[i][j] > needs[j]:
                        valid = False
                        break
                if not valid:
                    continue
                if valid:
                    #  use anext Array update after buying the current big gift bag , How much more to buy 
                    for j in range(len(price)):
                        anext.append(needs[j] - special[i][j])
                #  Update minimum 
                ans = min(ans, self.dfs(tuple(anext),price,special, maps) + special[i][-1])
            needs_str=''
            for c in needs:
                needs_str=needs_str+str(c)+'_'
            maps[needs_str] = ans
            return ans
    def shoppingOffers(self, price, special, needs):
        """
        :type price: List[int]
        :type special: List[List[int]]
        :type needs: List[int]
        :rtype: int
        """
        maps={}
        return self.dfs(tuple(needs),price,special,maps)

Note that in recursion , The list should be transformed into Yuanzu . Because the value of the list will change during recursion , Then I can't go back . Variable and immutable parameters .