最后一块石头的重量

最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例 1：

输入：[2,7,4,1,8,1]

输出：1

解释：

先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，

再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，

接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，

最后选出 1 和 1，得到 0，所以数组转换为 [1]，

所以最后剩下的石头重量为 1。

示例 2：

输入：[1]

输出：1

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        while len(stones) > 1:
            stones.sort()
            y = stones.pop()
            x = stones.pop()
            if x != y:
                stones.append(y-x)
        return stones[0] if stones else 0

目标和

目标和
给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个表达式：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。

返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3

输出：5

解释：一共有 5 种方法让最终目标和为 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

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个表达式：

示例 2：

输入：nums = [1], target = 1

输出：1

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        if (target + sum(nums)) % 2 != 0:
            return 0
        if abs(target) > sum(nums):
            return 0
        bagweight = (target + sum(nums)) // 2
        dp = [0] * (bagweight + 1)
        dp[0] = 1
        for i in range(len(nums)):
            for j in range(bagweight, nums[i] - 1, -1):
                dp[j] += dp[j - nums[i]]
        return dp[bagweight]

一和零

一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3

输出：4

解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ，因此答案是 4 。

示例 2：

输入：strs = [“10”, “0”, “1”], m = 1, n = 1

输出：2

解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for str in strs:
            zero_num = str.count('0')
            one_num = str.count('1')
            for i in range(m, zero_num - 1, -1):
                for j in range(n, one_num - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zero_num][j - one_num] + 1)
        return dp[m][n]

代码随想录-day37

最后一块石头的重量

目标和

一和零