473.-matchsticks-to-square.md

473. Matchsticks to Square

class Solution:
    def makesquare(self, nums: List[int]) -> bool:
        
        sumv = sum(nums)
        if sumv % 4 :return False
        line = sumv//4
        import random 
        import numpy as np
        
        self.ans = False
        def check():
            cur = 0
            cnt = 0
            for i in range(len(nums)):
                cur += nums[i]
                if cur == line:
                    cnt += 1
                    cur = 0
                elif cur > line:
                    return 0
            if cnt == 4 and not cur :
                self.ans = True
            return 1 if self.ans else 0

        
        
        def simmulate_anneal():
            random.shuffle(nums)
            t = 1e6
            while t > 1e-5 :
                a = random.randint(0, len(nums) - 1)
                b = random.randint(0, len(nums) - 1)
                if a == b:continue
                x = check()
                nums[a], nums[b] = nums[b],nums[a]
                y = check()
                delta = y - x  ## 变小了。。假设
                if delta < 0 and  np.exp(delta/t) > random.random():
                    nums[a], nums[b] = nums[b],nums[a]
                t *=0.97
                
        for i in range(40):
            simmulate_anneal()
        return self.ans