【算法题】字符串分割

  • A+
所属分类:编程茶楼


共计 1569 个字符,预计需要花费 4 分钟才能阅读完成。

给定非空字符串在s,将该字符串分割成一些子串,使每个子串的ASCII码值的和均为水仙花数。
1、若分割不成功则返回 0
2、若分割成功且分割结果不唯一则返回-1
3、若分割成功且分割结果唯一,则返回分割后的子串数目

备注:“水仙花数”是指一个三位数,每位上数字的立方和等于该数字本身,如 371是“水仙花数”,因为:371=3^3+7^3+1^3。

输入:输入字符串的最大长度为 200
输出:返回相应的结果

输入 abc
输出 0
说明 分割不成功

输入 f3@d5a8
输出 -1
说明 分割成功但分割结果不唯一,可以分割为两组,
一组:””f3″” 和 “”@d5a8″”
另一组: “”f3@d5″” 和 “”a8″”

输入 AXdddF
输出 2
说明 分割成功且结果唯一,可以分割为AX””(153) 和””dddF””(370)

public class SubString {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        // 超过长度200,返回分割不成功
        if (line.length() > 200) {
            System.out.println(0);
        }

       StringBuilder sb = new StringBuilder();
        ArrayList<String> strings = new ArrayList<>();
        char[] chars = line.toCharArray();
        digui(chars, sb, strings, 0);

        // 分割结果不唯一打印-1
        if (strings.size() > 1) {
            System.out.println(strings);
            System.out.println(-1);
        }
        // 分割结果唯一打印分割的子串个数
        if (strings.size() == 1) {
            System.out.println(strings);
            System.out.println(strings.get(0).split(" ").length);
        }
        // 分割没有结果打印0
        if (strings.size() == 0) {
            System.out.println(0);
        }
    }

    public static void digui(char[] chars, StringBuilder sb, ArrayList<String> strings, int startIndex) {
        int num = 0;
        StringBuilder sb_temp = new StringBuilder();
        for (int i = startIndex; i < chars.length; i++) {
            char aChar = chars[i];
            num += aChar;
            sb_temp.append(aChar);

            if (!isNar(num)) {
                continue;
            }

            StringBuilder sb_copy = new StringBuilder(sb);
            sb_copy.append(sb_temp).append(" ");

            if (i == chars.length - 1) {
                strings.add(sb_copy.toString().trim());
                return;
            }

            digui(chars, sb_copy, strings, i + 1);
        }
    }

    public static boolean isNar(int num) {
        if (num < 100 || num > 999) return false;
        int bai = num / 100;
        int shi = (num % 100) / 10;
        int ge = (num % 100) % 10;
        int v = (int) (Math.pow(bai, 3) + Math.pow(shi, 3) + Math.pow(ge, 3));
        return v == num;
    }
}
  • 我的微信
  • 这是我的微信扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: