416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

01背包问题，动态规划

01背包：416. 分割等和子集 474. 一和零 494. 目标和 879. 盈利计划 1049. 最后一块石头的重量 II 1230. 抛掷硬币

完全背包：1449. 数位成本和为目标值的最大数字 322. 零钱兑换 518. 零钱兑换 II 279. 完全平方数

方法一：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length , sum = 0 , target = 0; 
        for(int num : nums){
            sum += num;
        }
        if(len < 2 || ((sum & 1) != 0))return false;
        target = sum/2;
        boolean[][] dp = new boolean[len][target+1];
        dp[0][0] = true;
        for(int i = 0 ; i < len ; i++){
            dp[i][0] = true;
        }

        // num[i]  <  j   dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
        for(int i = 1 ; i < len ; i++){
            for(int j = 1 ; j <= target ; j++){
                if(j >= nums[i-1])dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                else dp[i][j] = dp[i-1][j];
            }
        }
        return dp[len-1][target];
    }
}

省略空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length , sum = 0 , target = 0; 
        for(int num : nums){
            sum += num;
        }
        if(len < 2 || ((sum & 1) != 0))return false;
        target = sum/2;
        boolean[] dp = new boolean[target+1];
        dp[0] = true;

        for(int i = 1 ; i < len ; i++){
            for(int j = target ; j >= nums[i-1] ; j--){
                dp[j] |= dp[j-nums[i-1]];
            }
        }
        return dp[target];
    }
}

583. 两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

示例 1：

1
2
3
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

1
2
输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

  • 1 <= word1.length, word2.length <= 500
  • word1 和 word2 只包含小写英文字母

990. 等式方程的可满足性

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

示例 1：

1
2
3
输入：["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

示例 2：

1
2
3
输入：["b==a","a==b"]
输出：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

示例 3：

1
2
输入：["a==b","b==c","a==c"]
输出：true

示例 4：

1
2
输入：["a==b","b!=c","c==a"]
输出：false

示例 5：

1
2
输入：["c==c","b==d","x!=z"]
输出：true

提示：

  1. 1 <= equations.length <= 500
  2. equations[i].length == 4
  3. equations[i][0] 和 equations[i][3] 是小写字母
  4. equations[i][1] 要么是 '='，要么是 '!'
  5. equations[i][2] 是 '='

方法一：并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public boolean equationsPossible(String[] equations) {
        int[] parten = new int[26];
        for(int i = 0 ; i < 26 ; i++){
            parten[i] = i;
        }

        for(String str : equations){
            if(str.charAt(1) == '='){
                union(parten , str.charAt(0) - 'a' , str.charAt(3) - 'a');
            }
        }

        for(String str : equations){
            if(str.charAt(1) == '!'){
                if(find(parten , str.charAt(0) - 'a') == find(parten , str.charAt(3) - 'a'))return false;
            }
        }
        return true;
    }
    //这一步联合，先去找到各位的祖宗，看看谁的祖宗是谁的儿子。
    public void union(int[] parten , int index1 , int index2){
        parten[find(parten , index1)] = find(parten , index2);
    }
    //这部是找祖宗，先找爷爷，然后循环往后找，直到找到祖宗
    public int find(int[] parten , int index){
        while(parten[index] != index){
            parten[index] = parten[parten[index]];
            index = parten[index]; 
        }
        return index;
    }
}