1.3 81. 分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
思路
和除以2，判断数组中元素和是否可以组成。
最优解
状态定义：dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。
状态转移方程：
public class Solution {
public boolean canPartition(int[] nums) {
int len = nums.length;
// 题目已经说非空数组，可以不做非空判断
int sum = 0;
for (int num : nums) {
sum += num;
}
// 特判：如果是奇数，就不符合要求
if ((sum & 1) == 1) {
return false;
}
int target = sum / 2;
// 创建二维状态数组，行：物品索引，列：容量（包括 0）
boolean[][] dp = new boolean[len][target + 1];
// 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满
if (nums[0] <= target) {
dp[0][nums[0]] = true;
}
// 再填表格后面几行
for (int i = 1; i < len; i++) {
for (int j = 0; j <= target; j++) {
// 直接从上一行先把结果抄下来，然后再修正
dp[i][j] = dp[i - 1][j];
if (nums[i] == j) {
dp[i][j] = true;
continue;
}
if (nums[i] < j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
}
}
}
return dp[len - 1][target];
}
}
在「填表格」的时候，当前行只参考了上一行的值，因此状态数组可以只设置 22 行，使用「滚动数组」的技巧「填表格」即可；
实际上，在「滚动数组」的基础上还可以优化，在「填表格」的时候，当前行总是参考了它上面一行 「头顶上」 那个位置和「左上角」某个位置的值。因此，我们可以只开一个一维数组，从后向前依次填表即可。
public class Solution {
public boolean canPartition(int[] nums) {
int len = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
if ((sum & 1) == 1) {
return false;
}
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
if (nums[0] <= target) {
dp[nums[0]] = true;
}
// 从第一行
for (int i = 1; i < len; i++) {
// 倒着画表
for (int j = target; nums[i] <= j; j--) {
if (dp[target]) {
return true;
}
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[target];
}
}
最优解总结
二维数组转为一维数组，利用了剪枝，相同的判断可以优化。此类背包问题要先画表，0-1背包问题（非对即错）
包的数量是元素和/2
1.4 82. 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
最优解思路
0-1背包，dp[i][j]表示i个0，j个1所能拼成的最大子集的容量。画表可以推导出来。
画表方法，判断是否可以容纳，选定哪些背包有容量可以放。可以放的包可以调用状态转移方程。
最优解
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
if len(strs) == 0:
return 0
dp = [[0]*(n+1) for _ in range(m+1)] #准备很多个背包
for strs_item in strs:
item_count0 = strs_item.count('0')
item_count1 = strs_item.count('1')
#遍历可容纳的背包
for i in range(m, item_count0 - 1, -1): #采取倒序
for j in range(n, item_count1 - 1, -1):
dp[i][j] = max(dp[i][j], 1 + dp[i-item_count0][j-item_count1])
return dp[m][n]
总结
背包问题的特征有了新的认识，即每个背包都是一种可能，每个背包都有状态转移方程。
1.5 83. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
输入：coins = [2], amount = 3
输出：-1
最优解思路
动态规划
输入: coins = [1, 2, 5], amount = 11
凑成面值为 11 的最少硬币个数可以由以下三者的最小值得到：
凑成面值为 10 的最少硬币个数 + 面值为 1 的这一枚硬币；
凑成面值为 9 的最少硬币个数 + 面值为 2 的这一枚硬币；
凑成面值为 6 的最少硬币个数 + 面值为 5 的这一枚硬币。
即 dp[11] = min (dp[10] + 1, dp[9] + 1, dp[6] + 1)。
dp[amount] = min(dp[amount], 1 + dp[amount - coins[i]]) for i in [0, len - 1] if coins[i] <= amount
最优解
public int coinChange(int[] coins, int amount) {
// 给 0 占位
int[] dp = new int[amount + 1];
// 注意：因为要比较的是最小值，这个不可能的值就得赋值成为一个最大值
Arrays.fill(dp, amount + 1);
// 理解 dp[0] = 0 的合理性，单独一枚硬币如果能够凑出面值，符合最优子结构
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i - coin >= 0 && dp[i - coin] != amount + 1) {
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
}
if (dp[amount] == amount + 1) {
dp[amount] = -1;
}
return dp[amount];
}
1.9 84. 两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
最优解
利用位运算求解
位移操作可以模拟乘法：
如：7 * 13 = 7 * (8 + 4 + 1) = 7 * 8 + 7 * 4 + 7 * 1
其中8,4,1分别是2的3,2,0次幂，因此
7 * 13 = 7 << 3 + 7 << 2 + 7 << 0 , 对于本题来说，即是：
a * x = b (暂不考虑余数)时，求x。根据上面位移运算模拟乘法的逻辑，可以把x看做一个由2的整数次幂的指数部分组成的一个数组。
如7 * 13，则13大约可以看成是[3,2,0]。因此本题可以转化为求此数组，之后累加2的数组元素次幂即可。
例子： 3 * x = 10
3 << 1 = 6 且 3 << 2 = 12
因12已经超过10的范围了，故y1 = 1。
然后，求 3 * x = (10 - (3 << 1)) 即3 * x = 4
可得y2 = 0，因为3 << 1 = 6,已经超过4了。
之后4 - (3 << 0) = 4 - 3 = 1。由于1已经小于3，不需要再继续找y3了。
故最终得出的y相关的数组为[1,0],则 x = 2^1 + 2^0 = 2 + 1 = 3（注：2^1 = 1<<1, 而在不溢出的情况下2 ^ n = 1 << n，后面不再赘述）。
最优解
var divide = function (dividend, divisor) {
var INT_MAX = 0x7FFFFFFF;
var INT_MIN = 1 << 31;
//先判断符号
var symbol = (dividend ^ divisor) >> 31;
//由于Math.abs(INT_MIN)存在溢出问题
//因此被除数与除数全部转为负数处理
var _dividend = dividend > 0 ? -dividend : dividend;
var _divisor = divisor > 0 ? -divisor : divisor;
var times = divided_negtive(_dividend, _divisor);
var output = 0;
for (var i = 0; i < times.length; i++) {
if (times[i] === 31) {
//i=31表示INT_MIN，times无第二个元素，直接短路处理
if (symbol === 0) {
//符号为正，此时存在INT_MIN转为正数溢出,返回INT_MAX
return INT_MAX;
}
return INT_MIN;
}
output += (1 << times[i]);
}
return symbol ? -output : output;
};
function divided_negtive(dividend, divisor) {
//两负数相除
//如-10/-20当除数小于被除数时，商为0
if (divisor < dividend) {
return [];
}
var timesMax = 32;
var timesMin = 0;
while (timesMax !== timesMin + 1) {
//二分查找
var mid = (timesMax + timesMin) >> 1;
//divisor<<mid后有可能超过-1<<31的范围
//因此要判断divisor是否大于等于-1<<(31-mid)，一旦小于这个值，则必定溢出
if (divisor < (-1 << (31 - mid))) {
//符合溢出条件，说明mid过大，将mid赋给timesMax，供下次折半查找使用
timesMax = mid;
continue;
}
var testVal = divisor << mid;
if (testVal < dividend) {
timesMax = mid;
} else {
timesMin = mid;
}
}
return [timesMin].concat(divided_negtive(dividend - (divisor << timesMin), divisor));
}
总结
- 用二分法最快确定位移的位数
- 异或右移31位取符号
1.12 85. 存在重复元素
在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。
如果存在则返回 true，不存在返回 false。
输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
我的解
滑动窗口的大小知道，从前到后遍历。
最优解
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < nums.length; ++i) {
// Find the successor of current element
Integer s = set.ceiling(nums[i]);
if (s != null && s <= nums[i] + t) return true;
// Find the predecessor of current element
Integer g = set.floor(nums[i]);
if (g != null && nums[i] <= g + t) return true;
set.add(nums[i]);
if (set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}
最优解总结
用set的大小保证了滑动窗口的大小，set.ceiling cet.floor可以获取前继节点和后继节点。java中的treeSet 二叉排序树（BST）