321. 拼接最大数 # leetcode 链接： https://leetcode-cn.com/problems/create-maximum-number/ 给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。 求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。 说明：请尽可能地优化你算法的时间和空间复杂度。 示例 1: 输入： nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 输出： [9, 8, 6, 5, 3] 示例 2: 输入： nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 输出： [6, 7, 6, 0, 4] 示例 3: ...
416. 分割等和子集 # leetcode 链接： https://leetcode-cn.com/problems/partition-equal-subset-sum/ 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 注意： 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 输入：[1, 5, 11, 5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11]. 示例 2: 输入：[1, 2, 3, 5] 输出：false 解释：数组不能分割成两个元素和相等的子集。 方法一：0-1 背包问题 // 0-1 背包问题 // dp[i][target] 表示 nums[0, i] 区间内是否能找到和为 target 的组合 // 对于每个 nums[i]，如果 nums[i] <= target，可以选择 or 不选，但只要有一个为 true，dp[i][target]=true // dp[i][target] = dp[i-1][target] || dp[i][target-nums[i]] // 如果 nums[i] > target，只能不选，故： // dp[i][target] = dp[i-1][target] func canPartition(nums []int) bool { n := len(nums) if n < 2 { return false } sum := 0 maxNum := 0 for _, num := range nums { sum += num if num > maxNum { maxNum = num } } // 和为奇数 if sum%2 ! ...