一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 516|回复: 0
收起左侧

[算法题] 交流下additive number

[复制链接] |试试Instant~ |关注本帖
生活在大农村 发表于 2015-2-7 16:42:38 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
一个数字如果能拆成若干组3个数使得前两个数的和为第三个数,些数字称为additive number.
Ex: 123 true, 1234 false, 123246 true, 122436 true.
应该要考虑所有拆分情况,我是直接暴力解了…………求更好的方法

欢迎拍砖……

public static boolean isAdditive(int n){
                if (n<100)
                        return false;
                return isAdditive(String.valueOf(n).toCharArray(),0);
        }
        public static boolean isAdditive(char[] digits, int start){
                int len = digits.length;
                if (start == len)
                        return true;
                if (len - start < 3)
                        return false;
                for (int i = start; i <= start + (len-start)/2; i++){
                        int part1 = charToInt(digits,start,i);
                        int len1 = i - start + 1;
                        for (int j = i+1; j <= i+(len-start)/2; j++){                               
                                int len2 = j - i;
                                int left = len - len1 - len2;
                                if (left < Math.min(len1,len2))
                                        break;
                                int part2 = charToInt(digits,i+1,j);
                                int sum = part1 + part2;
                                int sumLen = String.valueOf(sum).length();
                                if (left >= sumLen){
                                        int part3 = charToInt(digits,j+1,j+sumLen);
                                        if (part3 == sum)
                                                return isAdditive(digits,j+sumLen+1);
                                }
                        }
                }
                return false;                       
        }
       
        public static int charToInt(char[] digits, int start, int end){
                int res = 0;
                for (int i = start; i <= end; i++){
                        res = res * 10 + (digits[i] - '0');
                }
                return res;
        }

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 07:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表