Divide and Conquer solution for LeetCode #494
source link: https://donghao.org/2023/02/09/divide-and-conquer-solution-for-leetcode-494/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Divide and Conquer solution for LeetCode #494
The popular solution for LeetCode #494 is dynamic programming. But my first idea is Divide and Conquer. Although it’s not very fast, it’s another idea:
from collections import Counter
class Solution:
def get_results(self, nums: List[int]) -> Counter:
layer = [nums[0], -nums[0]]
for num in nums[1:]:
new_layer = []
for item in layer:
for val in [-num, num]:
new_layer.append(item + val)
layer = new_layer
return Counter(layer)
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
if n == 1:
return [0, 1][nums[0] == target or -nums[0] == target]
half = n // 2
left = self.get_results(nums[:half])
right = self.get_results(nums[half:])
ans = 0
for lkey, lcnt in left.items():
rcnt = right[target - lkey]
ans += rcnt * lcnt
return ansfrom collections import Counter
class Solution:
def get_results(self, nums: List[int]) -> Counter:
layer = [nums[0], -nums[0]]
for num in nums[1:]:
new_layer = []
for item in layer:
for val in [-num, num]:
new_layer.append(item + val)
layer = new_layer
return Counter(layer)
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
if n == 1:
return [0, 1][nums[0] == target or -nums[0] == target]
half = n // 2
left = self.get_results(nums[:half])
right = self.get_results(nums[half:])
ans = 0
for lkey, lcnt in left.items():
rcnt = right[target - lkey]
ans += rcnt * lcnt
return ans
Related Posts
- Road to solve LeetCode #322
My first solution is using dynamic programming. Then I want to also try breath-first-search. The…
- An improvement makes the pass of LeetCode #2359
The first idea that jumped out of my mind was using Sets to track two…
- Using PyTorch on ClearLinux docker image
I am using Nvidia's official docker image of PyTorch for my model training for quite…
February 9, 2023 - 23:48
RobinDong
develop
Algorithm
Leave a comment
Leave a Reply Cancel reply
Your email address will not be published. Required fields are marked *
Comment *
Name *
Email *
Website
Save my name, email, and website in this browser for the next time I comment.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK