十-二进制数的最少数目

如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个 十-二进制数 。例如，101 和 1100 都是 十-二进制数，而 112 和 3001 不是。

给你一个表示十进制整数的字符串 n ，返回和为 n 的 十-二进制数 的最少数目。

 

示例 1：

输入：n = "32"
输出：3
解释：10 + 11 + 11 = 32
示例 2：

输入：n = "82734"
输出：8
示例 3：

输入：n = "27346209830709182346"
输出：9
 

提示：

1 <= n.length <= 105
n 仅由数字组成
n 不含任何前导零并总是表示正整数
通过次数3,013提交次数3,417

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

贪心算法

因为数字的每个位都是由0和1组成的，所以要想组成该数字的数字数量最小，那么对于每一位的数字，它不应该有进位，如果有低位的进位，那么可以在高位直接用一个数字代替，因此组成该数字的最小的数字的数量应该取决于该数字中最大的那一位的数值

class Solution{
    public static int minPartitions(String n) {
        int max = 0;
        for (int i = 0; i < n.length(); i++) {
            max = Math.max(n.charAt(i)-'0', max);
        }

        return max;
    }
}

暴力解法（超时，不能保证正确性）

class Solution{
    public static int minPartitions(String n) {
        backtrack(n, "", 1, 1);
        return minDeep;
    }

    static char[] val = new char[]{'0', '1'};
    static int minDeep = Integer.MAX_VALUE;

    public static void backtrack(String n, String sum, int deep, int index) {
        if (sum.equals(n)) {
            minDeep = Math.min(minDeep, deep);
        } else {
            if (isGt(sum, n)) {
                return;
            }
            StringBuilder bd = new StringBuilder();
            bd.append(1);
            for (int i = index; i <= n.length(); i++) {
                for (int j = 1; j < i; j++) {
                    bd.append('1');
                }
                for (int j = i; j < n.length(); j++) {
                    bd.append('0');
                }
                String cur = bd.toString();
                sum = calSum(sum, cur);
                backtrack(n, sum, deep + 1, index);
                index++;
                bd.delete(1, bd.length());
            }

        }
    }

    public static boolean isGt(String s1, String s2) {
        if (s1.length() > s2.length() || (s1.length() == s2.length() && s1.charAt(0) > s2.charAt(0))) {
            return true;
        }
        return false;
    }

    public static String calSum(String last, String cur) {
        if (last.equals("")) {
            return cur;
        }
        int length1 = last.length() - 1;
        int length2 = cur.length() - 1;

        int flag = 0;
        StringBuilder bd = new StringBuilder();
        int minLen = Math.min(length1, length2);
        while (minLen >= 0) {
            int val1 = last.charAt(length1) - '0';
            int val2 = cur.charAt(length2) - '0';
            int sum = val1 + val2 + flag;
            if (sum > 9) {
                sum = sum - 10;
                flag = 1;
            } else {
                flag = 0;
            }
            bd.append(sum);
            minLen--;
            length1--;
            length2--;
        }

        while (length1 >= 0) {
            if (flag > 0) {
                int val1 = last.charAt(length1) - '0';
                int sum = val1 + flag;
                if (sum > 9) {
                    sum = sum - 10;
                    flag = 1;
                } else {
                    flag = 0;
                }
                bd.append(sum);
            } else {
                bd.append(last.charAt(length1));
            }
            length1--;
        }
        while (length2 >= 0) {
            if (flag > 0) {
                int val2 = cur.charAt(length2) - '0';
                int sum = val2 + flag;
                if (sum > 9) {
                    sum = sum - 10;
                    flag = 1;
                } else {
                    flag = 0;
                }
                bd.append(sum);
            } else {
                bd.append(last.charAt(length2));
            }
            length2--;
        }
        return bd.reverse().toString();
    }
}

赏

谢谢你请我吃糖果

微信