Random guess will work...... Python


  • 0
    B

    We just shuffle the accounts for N times, and pick the smallest transaction result for the N experiments, it can almost guarantee an accept....

    class Solution(object):
        def minTransfers(self, transactions):
            """
            :type transactions: List[List[int]]
            :rtype: int
            """
            Dic={}
            for T in transactions:
                if T[0] not in Dic:
                    Dic[T[0]]=-T[2]
                else:
                    Dic[T[0]]-=T[2]
                    
                
                if T[1] not in Dic:
                    Dic[T[1]]=T[2]
                else:
                    Dic[T[1]]+=T[2]
                    
            Minus,Plus=[],[]
            
            for key in Dic:
                if Dic[key]>0:
                    Plus.append( Dic[key])
                elif(Dic[key]<0):
                    Minus.append(Dic[key])
                    
            Trans=len(transactions)
            
            import copy
            import random
            for i in range(0,100):
                TM=copy.deepcopy(Minus)
                TP=copy.deepcopy(Plus)
                
                random.shuffle(TM)
                random.shuffle(TP)
                
                NTrans=0
                while(TM and TP):
                    if(TM[-1]+TP[-1]==0):
                        TM.pop()
                        TP.pop()
                        
                    elif(TP[-1]+TM[-1]>0):
                        TP[-1]+=TM[-1]
                        TM.pop()
                        
                    elif(TP[-1]+TM[-1]<0):
                        TM[-1]+=TP[-1]
                        TP.pop()
                    
                    NTrans+=1
                    if(NTrans>=Trans):
                        break
    
                Trans=min(NTrans,Trans)
                
            return Trans
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.