2018-08-26 LeetCode分割等和子集

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

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums.length == 0) return false;
        int sum = 0;
        for(int i:nums){
            sum += i;
        }
        if(sum % 2 == 1)return false;//集合总和为奇数
        boolean[] dp = new boolean[sum+1];
        dp[0] = true;   
        for (int j = 0; j < nums.length; j++) {
                for (int k = sum; k >= 0 && k >= nums[j]; k--) {
                        dp[k] =  dp[k] || dp[k-nums[j]];
                }
                if(dp[sum / 2]) {//存在某个子集的和sum / 2
                    return true;
                }
            }
        return false;
    }
}

京东2018校招求神奇数
东东在一本古籍上看到有一种神奇数，如果能够将一个数的数字分成两组，其中一组数字的和等于另一组数字的和，我们就将这个数称为神奇数。例如242就是一个神奇数，我们能够将这个数的数字分成两组,分别是{2,2}以及{4},而且这两组数的和都是4。东东现在需要统计给定区间中有多少个神奇数，即给定区间[l, r]，统计这个区间中有多少个神奇数，请你来帮助他

public class jd {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int start = sc.nextInt();
        int end =sc.nextInt();
        System.out.println(findMagicNumber(start, end));
        sc.close();
        
    }
    static public int findMagicNumber(int start, int end) {
        int ans = 0;
        int[] digitals = new int[10];
        boolean[] dp = new boolean[9 * 9];
        Arrays.fill(digitals, -1);
        Arrays.fill(dp, false);
        dp[0] = true;
        for (int i = start; i <= end; i++) {
            int num = i;
            int sum = 0;
            int index = 0;
            while (num > 0) {
                int temp = num % 10;
                digitals[index++] = temp;
                sum += temp;
                num = num / 10;
            }
            // 当各位数字和为偶数时，才存在神奇数
            if ((sum & 1) == 0){
                for (int j = 0; j < digitals.length && digitals[j] != -1; j++) {
                    for (int k = sum; k >= 0; k--) {
                        // 用一维数组进行更新
                        if(k >= digitals[j]) {
                            dp[k] = dp[k] || dp[k-digitals[j]];
                            System.out.println(k+" "+digitals[j]+" "+dp[k]);
                        }
                            
                    }
                    if(dp[sum / 2]) {
                        ans++;
                        System.out.println(i);
                        break;
                    }
                }
            }
            Arrays.fill(digitals, -1);
            Arrays.fill(dp, false);
            dp[0] = true;
        }
        return ans;
    }
}