Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.
Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.
- Example 1:
- Input: [1,1,2,2,2]
- Output: true
- Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
- Example 2:
- Input: [3,3,3,3,4]
- Output: false
- Explanation: You cannot find a way to form a square with all the matchsticks.
卖火柴的小女孩. 需要注意的是全部的火柴都要用完. 以及不要有一种思维定式, 火柴不一定是要连着拿的. 比如 [5,5,5,5,4,4,4,4,3,3,3,3] 不连续取, 是可能形成一个 square 的. 但是如果思维定式火柴连着取, 那么得到
的结果会是错的.
错误写法
- class Solution:
- def makesquare(self, nums: List[int]) -> bool:
- if not nums or len(nums) == 0:
- return False
- if sum(nums) % 4 != 0:
- return False
- length = sum(nums) // 4
- if any (num> length for num in nums):
- return False
- nums.sort()
- return self.dfs(nums, 0, length, 0, 0)
- def dfs(self, nums, start, length, temp, count):
- if count == 4: return True
- if start> len(nums):
- return True
- if temp == length:
- return self.dfs(nums, start, length, 0, count+1)
- for i in range(start, len(nums)):
- if temp+nums[i]> length:
- break
- if self.dfs(nums, i+1, length, temp+nums[i], count): # wrong!!!
- return True
正确的思考方式是用 dfs 遍历可以得到的所有火柴的摆放顺序. 如果一味的遍历, 那么最后肯定会 TLE. 一个比较好的方式是构建一个 target = [l] * 4. l 是可以摆成的火柴的边长. 如果我们可以把这个 target 的值都变为 0,
那么意味着是可以摆成正方形的.
步骤: 1 构建 target
2 dfs 函数 def dfs(nums, target, pos). dfs 跳出条件是 pos == len(nums). 对 target 进行从 0 到 4 的遍历 (不包含 4), 每一次遍历的过程中, 对 nums 也进行一次遍历, 如果 target[i]>= num, 意味着这个 num 可能成为
这条边长的 candidate, 那么我们在这个基础上进行下一层的 dfs. 注意要把 target 变为减掉 num 的 target.self.dfs(nums, pos+1, target[:i] + [target[i]-nums[pos]]+target[i+1:]). 如果下一层的 dfs 返回值是 True, 意味着这些火柴是可以摆放成功的.
比较疑惑的是当 nums 从大到小排的时候, 不会超时. 但是从小到大排, 就会超.
- class Solution:
- def makesquare(self, nums: List[int]) -> bool:
- if not nums or len(nums) == 0:
- return False
- if sum(nums) % 4 != 0:
- return False
- length = sum(nums) // 4
- if any (num> length for num in nums):
- return False
- nums.sort(reverse = True)
- target = [length] * 4
- return self.dfs(nums, 0,target)
- def dfs(self, nums, pos, target):
- if pos == len(nums):
- return True
- for i in range(4):
- if target[i]>= nums[pos]:
- if self.dfs(nums, pos+1, target[:i] + [target[i]-nums[pos]]+target[i+1:]):
- return True
- return False
来源: http://www.bubuko.com/infodetail-3400441.html