Ming
0%

LeetCode-416

Posted on Edited on In

题目

结果

代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    public boolean canPartition(int[] nums) {
        // 特殊情况
        if (nums.length < 2) {
            return false;
        }

        // 如果数组和是奇数，必不可能分成相等的两份
        int sum = arraySum(nums);
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;

        // 如果最大值大于目标值，必不可能分成相等的两份
        int max = maxInArray(nums);
        if (max > target) {
            return false;
        }

        // dp[i][j]表示从0~i中选任意个数，是否存在和为j的组合
        boolean[][] dp = new boolean[nums.length][target + 1];

        // 初始情况
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;

        // 根据条件转移方程dp
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (j < nums[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[nums.length - 1][target];
    }

    private int arraySum(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }

    private int maxInArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
        }
        return max;
    }
}
  • 一个更慢的解法
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
func canPartition(nums []int) bool {
	if len(nums) < 2 {
		return false
	}
	sum := 0
	for _, v := range nums {
		sum += v
	}
	if sum%2 != 0 {
		return false
	}

	dp := make([]set, len(nums))
	for i := 0; i < len(nums); i++ {
		dp[i] = make(map[int]bool)
	}
	dp[0].add(nums[0])
	for i := 1; i < len(nums); i++ {
		for _, v := range dp[i-1].elements() {
			//dp[i] = append(dp[i], v+nums[i], abs(v-nums[i]))
			dp[i].add(v + nums[i])
			dp[i].add(abs(v - nums[i]))
		}
		// fmt.Println(dp)
	}
	for _, v := range dp[len(dp)-1].elements() {
		if v == 0 {
			return true
		}
	}
	return false
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

type set map[int]bool

func (s set) add(num int) {
	if _, ok := s[num]; !ok {
		s[num] = true
	}
}

func (s set) elements() (ans []int) {
	for i := range s {
		ans = append(ans, i)
	}
	return
}

  • DP
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
34
35
36
37
38
func canPartition(nums []int) bool {
	s := sum(nums)
	if s%2 != 0 {
		return false
	}

    // 转换成背包问题
	target := s / 2
	for _,v:=range nums{
		if v > target {
			return false
		}
	}

	// initialize
	dp := make([][]bool, len(nums))
	for i := range dp {
		dp[i] = make([]bool, target+1)
		dp[i][0] = true
	}
	dp[0][nums[0]] = true

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

func sum(nums []int) (ans int) {
	for _, v := range nums {
		ans += v
	}
	return
}

复杂度

时间复杂度：O（n²）

空间复杂度：O（n²）