Algorithm
本周选择的算法题是：Target Sum。
规则
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
- For example, if
nums = [2, 1], you can add a'+'before2and a'-'before1and concatenate them to build the expression"+2-1".
Return the number of different expressions that you can build, which evaluates to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
Example 2:
Input: nums = [1], target = 1
Output: 1
Constraints:
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
Solution
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
def _findTargetSumWays(i: int, target: int) -> int:
if i == len(nums):
return int(target == 0)
else:
return _findTargetSumWays(i + 1, target + nums[i]) + _findTargetSumWays(i + 1, target - nums[i])
ans = _findTargetSumWays(0, target)
return ans
优化为迭代：
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
dp = { 0 : 1 }
for num in nums:
dp2 = {}
for old_key in dp.keys():
new_key_1 = old_key + num
dp2[new_key_1] = dp2.get(new_key_1, 0) + dp[old_key]
new_key_2 = old_key - num
dp2[new_key_2] = dp2.get(new_key_2, 0) + dp[old_key]
dp = dp2
return dp.get(target, 0)
Review
一篇旧文，因为最近在考虑 PR 的规范所以重新认真看了遍。
企业项目与开源项目有些不同，最明显的区别就是体现在修改粒度上，PR 虽然只做一件事，但这件事可能是一个需求或重构（开源项目很少有外部开发者做需求或重构），这个过程会包含多条 Commits，比如一个需求变更同时会去修改文档、调整代码等，以保持一致性。要保证一个 PR 只有一个 Commit 的话，免不了要用 git rebase or squash。
Tip
了解了如何用 venv.EnvBuilder 管理 python 的虚拟环境。