收录问题
006. 质数因子
016. 购物单
020. 密码验证合格程序
023. 删除字符串中出现次数最少的字符
024. 合唱队
026. 字符串排序
027. 查找兄弟单词
028. 素数伴侣【待解决】
030. 字符串合并处理
031. 单词倒排
032. 字符串运用-密码截取
033. 整数与IP地址间的转换
034. 图片整理
035. 蛇形矩阵
036. 字符串加密
037. 统计每个月兔子的总数
038. 求小球落地5次后所经历的路程和第5次反弹的高度
039. 判断两个IP是否属于同一子网【待解决】
041. 称砝码
042. 计算字符串的距离


006. 质数因子
题目描述

功能:输入一个正整数，按照从小到大的顺序输出它的所有质数的因子（如180的质数因子为2 2 3 3 5 ）。最后一个数后面也要有空格

详细描述：

函数接口说明：

public String getResult(long ulDataInput)

输入参数：

long ulDataInput：输入的正整数

返回值：

String

输入描述：

输入一个long型整数

输出描述：

按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。

输入：

180

输出：

2 2 3 3 5

代码实现：
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            long N = in.nextLong();
            Solution(N);
        }
    }

    private static void Solution(long n) {
        if(n <= 1){
            System.out.println(n);
        }
        int i = 2;
        StringBuilder sb = new StringBuilder();
        while (i <= n){
        	// 当 n 能被质数所整除的时候才除以质数
            while (n % i == 0){
                sb.append(i).append(" ");
                n /= i;
            }
            i++;
        }
        System.out.println(sb);
    }
}


016. 购物单
题目描述

王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：




主件
附件




电脑
打印机，扫描仪


书柜
图书


书桌
台灯，文具


工作椅
无


        如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 5 等：用整数 1 ~ 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
        设第 j 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：
v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 为乘号）
        请你帮助王强设计一个满足要求的购物单。
输入描述：

输入的第 1 行，为两个正整数，用一个空格隔开：N m

（其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。）

从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q

（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）

输出描述：

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。

输入：

1000 5

800 2 0

400 5 1

300 5 1

400 3 0

500 2 0

输出：

2200

问题分析
这道问题比较容易可以看出是一个 0-1 背包问题，只不过它比普通的背包问题复杂一些。因为我们需要对区分出主件和附件，而附件又只有在主件购买的前提下才能购买。
由于每个主件至多有2个附件，所以我们不妨假设每个主件都有两个附件，而对于不存在的附件，直接将价格和重要度置为0即可。
我们设状态方程为 dp[m][n]，表示在钱为 n 的条件下，在 m 件商品中获利的最大值。笔者的思路是先挑选主件商品，如果主件商品能够被挑选的话，再决定是否挑选附件。而当我们处理第 m 件主件商品时，我们有以下5种选择，我们需要在比较后选择其中获利最大的方式：

放弃该主件商品，此时 dp[i][j] = dp[i-1][j]。
选择该主件商品，但不选择任何附件。
选择该主件商品，并选择附件1。
选择该主件商品，并选择附件2。
选择该主件商品，并选择附件1和附件2。

该题代码如下：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();  // 总钱数
            int m = in.nextInt();  // 商品数量
            int[][] v = new int[m+1][3];
            int[][] p = new int[m+1][3];

            for (int i = 1; i <= m; i++){
                int a = in.nextInt();   // 价格
                int b = in.nextInt() * a;  // 价格*重要度
                int c = in.nextInt();   // 主附件判断
                if(c == 0){  // 主件位于 v[i][0] 处
                    v[i][0] = a;
                    p[i][0] = b;
                } else {  // 商品为附件
                    if(v[c][1] == 0){
                        v[c ][1] = a;
                        p[c][1] = b;
                    } else {
                        v[c][2] = a;
                        p[c][2] = b;

                    }
                }
            }
            Solution(n, m, v, p);
        }
    }

    private static void Solution(int n, int m, int[][] v, int[][] p) {
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++){
            for (int j = 1; j <= n; j++){
                int max = dp[i-1][j];
                if(j >= v[i][0]){
                    max = Math.max(max, dp[i-1][j-v[i][0]] + p[i][0]);
                }
                if(j >= v[i][0] + v[i][1]){
                    max = Math.max(max, dp[i-1][j-v[i][0]-v[i][1]] + p[i][0] + p[i][1]);
                }
                if(j >= v[i][0] + v[i][2]){
                    max = Math.max(max, dp[i-1][j-v[i][0]-v[i][2]] + p[i][0] + p[i][2]);
                }
                if(j >= v[i][0] + v[i][1] + v[i][2]){
                    max = Math.max(max, dp[i-1][j-v[i][0]-v[i][1]-v[i][2]] + p[i][0] + p[i][1] + p[i][2]);
                }
                dp[i][j] = max;
            }
        }
        System.out.println(dp[m][n]);
    }

}

个人觉得这道题的思路是没啥问题的，但是在牛客网的测试中不能AC，只能通过80%，没找出是啥原因，希望有知道的人告知，非常感谢~

020. 密码验证合格程序
题目描述

密码要求:
1.长度超过8位
2.包括大小写字母.数字.其它符号,以上四种至少三种
3.不能有相同长度超2的子串重复
说明:长度超过2的子串

输入描述:

一组或多组长度超过2的子符串。每组占一行

输出描述:

如果符合要求输出：OK，否则输出NG

输入

021Abc9000

021Abc9Abc1

021ABC9000

021$bc9000

输出

OK

NG

NG

OK

问题分析
这道题靠分步验证即可比较容易地得出结果，最为棘手的验证明显就是密码要求的第三点：不能有相同长度超2的子串重复了。从这里我们应当意识到，如果有长度超过2的子串重复，那么肯定也就存在长度为2的子串重复。所以问题也就转化为了检查字符串中是否存在长度为2的子串重复，这里我们用 String#contains 方法可以轻松地解决该问题。代码如下：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String pwd = in.next();
            pwdValidate(pwd);
        }
    }

    public static void pwdValidate(String pwd){
        // 1.密码长度必须超过8
        if(pwd == null || pwd.length() < 9){
            System.out.println("NG");
            return;
        }
        int[] kind = new int[4];
        // 2. 密码需要存在3种以上的字符类型
        for (int i = 0; i < pwd.length(); i++){
            char c = pwd.charAt(i);
            if(c >= 'a' && c <= 'z'){
                kind[0] = 1;
            } else if(c >= 'A' && c <= 'Z'){
                kind[1] = 1;
            } else if(c >= '0' && c <= '9'){
                kind[2] = 1;
            } else {
                kind[3] = 1;
            }
        }
        if(kind[0] + kind[1] + kind[2] + kind[3] < 3){
            System.out.println("NG");
            return;
        }
        // 3. 密码中不能存在长度超2的重复子串
        for (int i = 0; i < pwd.length()-3; i++){
            String sub1 = pwd.substring(i, i+3);
            String sub2 = pwd.substring(i+3);
            if(sub2.contains(sub1)){
                System.out.println("NG");
                return;
            }
        }
        System.out.println("OK");
    }
}


023. 删除字符串中出现次数最少的字符
题目描述

实现删除字符串中出现次数最少的字符，若多个字符出现次数一样，则都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。

输入描述:

字符串只包含小写英文字母, 不考虑非法输入，输入的字符串长度小于等于20个字节。

输出描述:

删除字符串中出现次数最少的字符后的字符串。

输入

abcdd

输出

dd

问题分析
这道题最简单的做法就是用一个 Map 来存储字符然后找出次数最小的字符逐一删除，代码如下：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String s = in.next();
            Solution(s);
        }
    }

    public static void Solution(String s){
        if(checkValidate(s)){
            return;
        }
        // 储存字符，value为字符出现的次数
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(map.containsKey(c)){
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        // 找出出现次数最小的字符的个数
        int min = Integer.MAX_VALUE;
        for (Map.Entry entry : map.entrySet()){
            min = Math.min(min, (int) entry.getValue());
        }
        // 将出现次数最小的字符存储到 set 中
        HashSet<Character> set = new HashSet<>();
        for (Map.Entry entry : map.entrySet()){
            if((int) entry.getValue() == min){
                set.add((char) entry.getKey());
            }
        }
        // 字符串拼接，如果出现 set 中的字符直接跳过
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(set.contains(c)){
                continue;
            }
            sb.append(c);
        }
        System.out.println(sb);
    }

    private static boolean checkValidate(String s) {
        for (int i = 0; i < s.length(); i++){
            if(s.charAt(i) >= 'a' || s.charAt(i) <= 'z'){
                return false;
            }
        }
        return true;
    }
}

这种方法虽然简单，但是不够优雅（如果在面试中写这种代码必挂）。我们需要寻找更加优雅的方式来解决这个问题。
我们注意到，字符串中的字符只包含小写字母，小写字母总共也就 26 个，我们可以考虑使用一个长度为 26 的 int 数组表示小写字母的出现次数。然后找出数组中最小的非 0 值，删除字符串中该值所对应的字符即可。代码如下：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String s = in.next();
            Solution(s);
        }
    }

    public static void Solution(String s){
        if(checkValidate(s)){
            return;
        }
        int min = Integer.MAX_VALUE;
        int[] cnt = new int[26];
        char[] ch = s.toCharArray();
        for (char c : ch){
            min = Math.min(++cnt[c - 'a'], min);
        }
        StringBuilder sb = new StringBuilder();
        for (char c : ch){
            if(min == cnt[c - 'a']){
                continue;
            }
            sb.append(c);
        }
        System.out.println(sb);
    }

    private static boolean checkValidate(String s) {
        for (int i = 0; i < s.length(); i++){
            if(s.charAt(i) >= 'a' || s.charAt(i) <= 'z'){
                return false;
            }
        }
        return true;
    }
}


024. 合唱队
题目描述

计算最少出列多少位同学，使得剩下的同学排成合唱队形

说明：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，

则他们的身高满足存在i（1<=i<=K）使得T1<T2<…<Ti-1Ti+1>…>TK。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入描述:

整数N

输出描述:

最少需要几位同学出列

输入

8

186 186 150 200 160 130 197 200

输出

4

问题分析
这道题本质上属于最长子序列问题的变种，本质上也就是动态规划问题。我们只需要找到序列中的一个值，我们叫做 A[i]，以 A[i] 为结尾的递增子序列加上以 A[i] 为起点的递减子序列的序列长度最长即可。代码如下：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            int[] members = new int[n];
            for (int i = 0; i < n; i++){
                members[i] = in.nextInt();
            }
            Solution(members);
        }
    }

    private static void Solution(int[] members) {
        int[] ltr = getLongestIncrementSequence(members);
        int[] rtl = getLongestDecrementSequence(members);
        int max = 0;
        for (int i = 0; i < members.length; i++){
            max = Math.max(max, ltr[i] + rtl[i] - 1);
        }
        System.out.println(members.length - max);
    }

    private static int[] getLongestDecrementSequence(int[] members) {
        int[] rtl = new int[members.length];
        for (int i = members.length - 1; i >= 0; i--){
            rtl[i] = 1;
            for (int j = members.length - 1; j > i; j--){
                if(members[j] < members[i] && rtl[j] >= rtl[i]){
                    rtl[i] = rtl[j] + 1;
                }
            }
        }
        return rtl;
    }

    private static int[] getLongestIncrementSequence(int[] members) {
        int[] ltr = new int[members.length];
        for (int i = 0; i < members.length; i++){
            ltr[i] = 1;
            for (int j = 0; j < i; j++){
                if(members[j] < members[i] && ltr[j] >= ltr[i]){
                    ltr[i] = ltr[j] + 1;
                }
            }
        }
        return ltr;
    }
}



026. 字符串排序
题目描述
编写一个程序，将输入字符串中的字符按如下规则排序。

规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。
如，输入： Type   输出： epTy
规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。
如，输入： BabA   输出： aABb
规则 3 ：非英文字母的其它字符保持原来的位置。
如，输入： By?e   输出： Be?y

输入：

A Famous Saying: Much Ado About Nothing(2012/8).

输出：

A  aaAAbc   dFgghh :  iimM   nNn   oooos   Sttuuuy  (2012/8).

问题分析
直接通过从 a(A) ~ z(Z) 遍历的方式找出字符串中所有的大小写字符按照顺序排好即可，代码如下：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String str = in.nextLine();
            Solution(str);
        }
    }

    private static void Solution(String str) {
        if(str == null || str.length() == 0){
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++){
            for (int j = 0; j < str.length(); j++){
                if(str.charAt(j) == (char)(i + 'a') || str.charAt(j) == (char)(i + 'A')){
                    sb.append(str.charAt(j));
                }
            }
        }
        StringBuilder result = new StringBuilder();
        int k = 0;
        for (int i = 0; i < str.length(); i++){
            if(isLetter(str.charAt(i))){
                result.append(sb.charAt(k++));
            } else {
                result.append(str.charAt(i));
            }
        }
        System.out.println(result);
    }

    private static boolean isLetter(char c){
        return (c <= 'z' && c >= 'a') || (c <= 'Z' && c >= 'A');
    }

}


027. 查找兄弟单词
题目描述
实现一个可存储若干个单词的字典。用户可以：

在字典中加入单词。
查找指定单词在字典中的兄弟单词个数。
查找指定单词的指定序号的兄弟单词，指定序号指兄弟单词按字典顺序排序后的序号（从1开始）。
清空字典中的所有单词。

定义，格式说明
单词

由小写英文字母组成，不含其它字符。

兄弟单词


给定一个单词X，如果通过任意交换单词中字母的位置得到不同的单词Y，那么定义Y是X的兄弟单词。

字典顺序


两个单词（字母按照从左向右顺序），先以第一个字母作为排序的基准，如果第一个字母相同，就用第二个字母为基准，如果第二个字母相同就以第三个字母为基准。依此类推，如果到某个字母不相同，字母顺序在前的那个单词顺序在前。如果短单词是长单词从首字母开始连续的一部分，短单词顺序在前。


举例：bca 是 abc 的兄弟单词；abc 与 abc 是相同单词，不是兄弟单词。


规格

0 ≤ 字典中所含单词个数 ≤ 1000
1 ≤ 单词所含字母数 ≤ 50

问题分析
这道题不难，但是题目有些长，读起来有些费劲。这道题我们需要解决的点为：兄弟单词识别。可以注意到单词是只含小写字母的，所以这道题的做法和前面字符串排序的做法类似，可以通过维护2个字母数组来判断两个单词是否为兄弟单词，代码实现如下：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            String[] words = new String[n];
            for (int i = 0; i < n; i++){
                words[i] = in.next();
            }
            String target = in.next();
            int k = in.nextInt();
            Solution(words, target, k);
        }
    }

    private static void Solution(String[] words, String target, int k) {
        if(words == null || target == null || target.length() == 0){
            return;
        }
        int count = 0;
        String[] broWords = new String[words.length];
        for (int i = 0; i < words.length; i++){
            if(isBroWord(words[i], target)){
                broWords[count++] = words[i];
            }
        }
        Arrays.sort(broWords, 0, count);
        System.out.println(count);
        if(k <= count){
            System.out.println(broWords[k-1]);
        }

    }

	/**
	 * 兄弟单词识别方法
	 */
    private static boolean isBroWord(String word, String target) {
        if(word.equals(target) || word.length() != target.length()){
            return false;
        }
        int[] s1 = new int[26];
        int[] s2 = new int[26];
        for (int i = 0; i < word.length(); i++){
            s1[word.charAt(i)-'a']++;
            s2[target.charAt(i)-'a']++;
        }
        for (int i = 0; i < 26; i++){
            if(s1[i] != s2[i]){
                return false;
            }
        }
        return true;
    }
}


028. 素数伴侣【待解决】
题目描述

若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。

输入:

有一个正偶数N（N≤100），表示待挑选的自然数的个数。后面给出具体的数字，范围为[2,30000]。

输出:

输出一个整数K，表示你求得的“最佳方案”组成“素数伴侣”的对数。

输入描述:

1 输入一个正偶数n

2 输入n个整数

输出描述:

求得的“最佳方案”组成“素数伴侣”的对数。

输入

4

2 5 6 13

输出

2

问题分析
这道题使用匈牙利算法可以比较快速地得出结果。素数除了 2 之外，其它的数均为奇数，而一个偶数和一个奇数相加才能得到一个奇数，所以我们可以把输入的数分为奇数和偶数两部分，将奇偶相加得到素数的两个数用一条线相连接，此时我们的问题就转化成了求二分图的最大连接数。代码如下：

030. 字符串合并处理
题目描述

按照指定规则对输入的字符串进行处理。

详细描述：

将输入的两个字符串合并。

对合并后的字符串进行排序，要求为：下标为奇数的字符和下标为偶数的字符分别从小到大排序。这里的下标意思是字符在字符串中的位置。

对排序后的字符串进行操作，如果字符为‘0’——‘9’或者‘A’——‘F’或者‘a’——‘f’，则对他们所代表的16进制的数进行BIT倒序的操作，并转换为相应的大写字符。如字符为‘4’，为0100b，则翻转后为0010b，也就是2。转换后的字符为‘2’； 如字符为‘7’，为0111b，则翻转后为1110b，也就是e。转换后的字符为大写‘E’。

 

举例：输入str1为"dec"，str2为"fab"，合并为“decfab”，分别对“dca”和“efb”进行排序，排序后为“abcedf”，转换后为“5D37BF”

输入:

dec fab

输出:

5D37BF

问题分析
本题的难点体现在对字符的转化上，笔者一直想通过二进制数字的特性之间的联系来解答，但都没想出所以然来。最终采用的方法是直接保存一个数组来对应转换的字符。代码如下所示：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String str1 = in.next();
            String str2 = in.next();
            System.out.println(processString(str1.toCharArray(), str2.toCharArray()));
        }
    }

    public static char[] processString(char[] str1, char[] str2){
        if (str1 == null || str2 == null || str1.length == 0 || str2.length == 0){
            return null;
        }

        char[] newString = new char[str1.length + str2.length];
        // 复制数组，进行合并
        for (int i = 0; i < str1.length; i++){
            newString[i] = str1[i];
        }
        for (int i = 0; i < str2.length; i++){
            newString[i+str1.length] = str2[i];
        }
        // 排序
        sort(newString, 0);
        sort(newString, 1);
        for (int i = 0; i < newString.length; i++){
            newString[i] = convert(newString[i]);
        }
        return newString;
    }

    private static void sort(char[] ch, int begin){
        // 因为是小数组，所以采用插入排序即可
        for (int i = begin; i < ch.length; i += 2){
            int index = i;
            char temp;
            for (int j = i+2; j <ch.length; j += 2){
                if (ch[index] > ch[j]){
                    index = j;
                }
            }
            temp = ch[i];
            ch[i] = ch[index];
            ch[index] = temp;
        }
    }

    private static char convert(char c){
        // 采用保存数组的形式来转化
        char[] ch = { '0', '8', '4', 'C', '2', 'A', '6', 'E',
                '1', '9', '5', 'D', '3', 'B', '7', 'F' };
        if (c >= '0' && c <= '9'){
            return ch[c - '0'];
        } else if (c >= 'a' && c <= 'f'){
            return ch[c - 'a' + 10];
        } else if (c >= 'A' && c <= 'F') {
            return ch[c - 'A' + 10];
        }
        return c;
    }
}


031. 单词倒排
题目描述

对字符串中的所有单词进行倒排。

说明：

1、每个单词是以26个大写或小写英文字母构成；

2、非构成单词的字符均视为单词间隔符；

3、要求倒排后的单词间隔符以一个空格表示；如果原字符串中相邻单词间有多个间隔符时，倒排转换后也只允许出现一个空格间隔符；

4、每个单词最长20个字母；

输入描述:

输入一行以空格来分隔的句子

输出描述:

输出句子的逆序

输入：

I am a student

输出：

student a am I

问题分析
这道题刚开始一直无法验证通过，很纳闷，仔细看了要求之后才发现非构成单词的字符均视为单词间隔符，所以审题很重要，下面是这道题的代码：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String str = in.nextLine();
            System.out.println(Solution(str));
        }
    }

    private static String Solution(String str) {
        // 非空检测
        if (str == null || str.length() == 0){
            return null;
        }
        int i = 0;
        StringBuilder sb = new StringBuilder();
        // 将所有非字母的字符用空格替换，方便后续的处理
        while (i < str.length()){
            char c = str.charAt(i);
            if (isAlphabet(c)){
                sb.append(c);
            } else {
                sb.append(" ");
            }
            i++;
        }
        String[] words = sb.toString().split(" ");
        sb = new StringBuilder();
        for (i = words.length-1; i >= 0; i--){
            if ("".equals(words[i])){
                continue;
            }
            sb.append(words[i]).append(" ");
        }
        // 注意把最后一个空格删去
        return sb.toString().substring(0, sb.length()-1);
    }

    private static boolean isAlphabet(char c) {
        return (c <= 'z' && c >= 'a') || (c <= 'Z' && c >= 'A');
    }

}


032. 字符串运用-密码截取
题目描述

Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？

输入：

ABBA

输出：

4

问题分析
这道题说的这么复杂，本质上无非就是一道求一个字符串中最长回文的长度，这里采用马拉车算法求解，代码如下所示：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String s = in.next();
            System.out.println(findLongestPalindrome(s));
        }
    }

    private static String preHandleString(String s){
        StringBuilder sb = new StringBuilder("#");
        for (int i = 0; i < s.length(); i++){
            sb.append(s.charAt(i)).append('#');
        }
        return sb.toString();
    }

    public static int findLongestPalindrome(String s) {
        if (s == null || s.length() == 0){
            return 0;
        }
        String str = preHandleString(s);
        int rightSide = 0;
        int rightCenter = 0;
        int[] lens = new int[str.length()];
        int max = 1;

        for (int i = 0; i < str.length(); i++){
            boolean needExpand = true;
            // 如果i点位于rightSide内
            if (i < rightSide){
                // 找出以rightCenter为中心，和i对称的左对称点
                int leftPoint = 2 * rightCenter - i;
                // 直接利用回文的特性得出回文个数
                lens[i] = lens[leftPoint];
                if (i + lens[i] > rightSide){
                    lens[i] = rightSide - i;
                }
                if (i + lens[leftPoint] < rightSide){
                    needExpand = false;
                }
            }
            // 需要进行中心扩展
            if (needExpand){
                while (i - 1 - lens[i] >= 0 && i + 1 + lens[i] < str.length()){
                    if (str.charAt(i - 1 - lens[i]) != str.charAt(i + 1 + lens[i])){
                        break;
                    }
                    ++lens[i];
                }
                rightCenter = i;
                rightSide = i + lens[i];
                if (max < lens[i]){
                    max = lens[i];
                }
            }
        }

        return max;
    }
}

关于马拉车算法，这里推荐一篇文章，对该算法的讲解非常详细生动：【面试现场】如何找到字符串中的最长回文子串？

033. 整数与IP地址间的转换
题目描述

原理：ip地址的每段可以看成是一个0-255的整数，把每段拆分成一个二进制形式组合起来，然后把这个二进制数转变成 一个长整数。

举例：一个ip地址为10.0.3.193

每段数字                     相对应的二进制数

 10                                      00001010

   0                                         00000000

   3                                         00000011

193                                      11000001

组合起来即为：00001010 00000000 00000011 11000001,转换为10进制数就是：167773121，即该IP地址转换后的数字就是它了。

 

IP地址的每段可以看成是一个0-255的整数，需要对IP地址进行校验

输入描述:

1 输入IP地址

2 输入10进制型的IP地址

输出描述:

1 输出转换成10进制的IP地址

2 输出转换后的IP地址

输入：

10.0.3.193

167969729

输出：

167773121

10.3.3.193

问题分析
这道题不难，拿出来的原因是在调用String#split方法的时候一度傻了眼，所以特地记录一下。代码如下所示：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String s1 = in.next();
            long num = in.nextLong();
            System.out.println(ip2num(s1));
            System.out.println(num2ip(num));
        }
        in.close();
    }

    private static String num2ip(long num) {
        long[] numbers = new long[4];
        for (int i = 3; i >= 0; i--){
            numbers[i] = num & 0xFF;
            num >>>= 8;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 4; i++){
            sb.append(numbers[i]).append('.');
        }
        return sb.toString().substring(0, sb.length()-1);
    }

    private static long ip2num(String s) {
        if (s == null || s.length() == 0){
            return 0;
        }
        String[] numbers = s.split("\\.");
        if (numbers.length != 4){
            throw new IllegalArgumentException("Illegal IP.");
        }
        long result = 0;
        for (int i = 0; i < 4; i++){
            result <<= 8;
            int num = Integer.parseInt(numbers[i]);
            if (num < 0 || num > 255){
                throw new IllegalArgumentException("Illegal IP.");
            }
            result += num;
        }
        return result;
    }

}

题目其实很简单，当牵扯到其中的关于各个数据类型的字节长度以及转义字符等的知识却是值得我们去注意的，笔者就是在这里卡了很久。

034. 图片整理
题目描述

Lily上课时使用字母数字图片教小朋友们学习英语单词，每次都需要把这些图片按照大小（ASCII码值从小到大）排列收好。请大家给Lily帮忙，通过C语言解决。

输入描述:

Lily使用的图片包括"A"到"Z"、“a"到"z”、“0"到"9”。输入字母或数字个数不超过1024。

输出描述:

Lily的所有图片按照从小到大的顺序输出

输入：

Ihave1nose2hands10fingers

输出：

0112Iaadeeefghhinnnorsssv

问题分析
没太懂这道题想要表达什么，就当作是熟悉一下插入排序了，代码如下所示：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String s = in.next();
            System.out.println(solution(s));
        }
        in.close();
    }

    private static String solution(String s) {
        if (s == null || s.length() == 0){
            return null;
        }
        char[] ch = s.toCharArray();
        sort(ch);
        return new String(ch);
    }


    // 插入排序
    private static void sort(char[] ch){
        for (int i = 1; i < ch.length; i++){
            for (int j = i; j > 0 && ch[j] < ch[j-1]; j--){
                char temp = ch[j];
                ch[j] = ch[j-1];
                ch[j-1] = temp;
            }
        }
    }

}


035. 蛇形矩阵
题目描述

蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。

样例输入
5
样例输出
1 3 6 10 15
2 5 9 14
4 8 13
7 12
11

输入描述:

输入正整数N（N不大于100）

输出描述:

输出一个N行的蛇形矩阵。

输入：

4

输出：

1 3 6 10

2 5 9

4 8

7

问题分析
这道题就纯粹属于一个找规律的问题了。蛇形矩阵的规律如下，设输入数字为n：

第$\ i$ 行的开始值为$\frac {(i-1)*i}{2}+1$
第$\ i$ 行的元素个数为$\ n-i$
第$\ i$ 行的初始间隔为$\ i+1$，依次递增

代码如下所示：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            solution(n);
        }
        in.close();
    }

    private static void solution(int n) {
        if (n <= 0){
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++){
            int lo = i*(i-1)/2 + 1;
            int diff = i+1;
            for (int j = 0; j <= n-i; j++){
                sb.append(lo).append(' ');
                lo += diff++;
            }
            sb.setCharAt(sb.length()-1, '\n');
        }
        System.out.print(sb);
    }

}

这道题用递归的方式也是可以做出来的，但是不如找规律来的实在，有兴趣的同学可以试试递归的形式。

036. 字符串加密
题目描述

有一种技巧可以对数据进行加密，它使用一个单词作为它的密匙。下面是它的工作原理：首先，选择一个单词作为密匙，如TRAILBLAZERS。如果单词中包含有重复的字母，只保留第1个，其余几个丢弃。现在，修改过的那个单词属于字母表的下面，如下所示：
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
T R A I L B Z E S C D F G H J K M N O P Q U V W X Y
上面其他用字母表中剩余的字母填充完整。在对信息进行加密时，信息中的每个字母被固定于顶上那行，并用下面那行的对应字母一一取代原文的字母(字母字符的大小写状态应该保留)。因此，使用这个密匙，Attack AT DAWN(黎明时攻击)就会被加密为Tpptad TP ITVH。

输入描述:

先输入key和要加密的字符串

输出描述:

返回加密后的字符串

输入：

nihao

ni

输出：

le

问题分析

037. 统计每个月兔子的总数
题目描述

有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，假如兔子都不死，问每个月的兔子总数为多少？

输入描述:

输入int型表示month

输出描述:

输出兔子总数int型

输入：

9

输出：

34

问题分析
这道题很明显是在用递归的思路求解的，代码比较简单，如下所示：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            System.out.println(solution(n));
        }
    }

    private static int solution(int n) {
        return solution(n, 0, 0, 1);
    }

    /**
     * 计算兔子数量的递归方法
     * @param n 
     * @param parent 能够生育的兔子数量
     * @param child2 年龄为2个月的兔子数量
     * @param child1 年龄为1个月的兔子数量，刚出生的兔子年龄均为1个月
     * @return 兔子的总数
     */
    private static int solution(int n, int parent, int child2, int child1){
        // 递归终止的条件
        if (n <= 1){
            return parent+child2+child1;
        }
        return solution(n-1, parent+child2, child1, parent+child2);
    }
}


038. 求小球落地5次后所经历的路程和第5次反弹的高度
题目描述

假设一个球从任意高度自由落下，每次落地后反跳回原高度的一半; 再落下, 求它在第5次落地时，共经历多少米?第5次反弹多高？

输入描述:

输入起始高度，int型

输出描述:

分别输出第5次落地时，共经过多少米第5次反弹多高

输入：

1

输出：

2.875

0.03125

问题分析
这道题不难，这里直接上代码：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            solution(n);
        }
    }

    private static void solution(int height) {
        // 非法检测
        if (height < 0){
            return;
        }
        double totalHeight = 0;
        double currentHeight = height;
        for (int i = 1; i <= 5; i++){
            currentHeight /= 2.0;
            totalHeight += currentHeight * 3.0;
        }
        // 减去第5次反弹的高度
        totalHeight -= currentHeight;
        System.out.println(totalHeight);
        System.out.println(currentHeight);
    }

}


039. 判断两个IP是否属于同一子网【待解决】
题目描述

子网掩码是用来判断任意两台计算机的IP地址是否属于同一子网络的根据。

子网掩码与IP地址结构相同，是32位二进制数，其中网络号部分全为“1”和主机号部分全为“0”。利用子网掩码可以判断两台主机是否中同一子网中。若两台主机的IP地址分别与它们的子网掩码相“与”后的结果相同，则说明这两台主机在同一子网中。
示例： I P 地址　 192.168.0.1 子网掩码　 255.255.255.0
转化为二进制进行运算：
I P 地址　11010000.10101000.00000000.00000001

子网掩码　11111111.11111111.11111111.00000000
AND运算

　　　　11000000.10101000.00000000.00000000
转化为十进制后为：

　　　　192.168.0.0
I P 地址　 192.168.0.254 子网掩码　 255.255.255.0
转化为二进制进行运算：
I P 地址　11010000.10101000.00000000.11111110

子网掩码　11111111.11111111.11111111.00000000
AND运算

　　　　　11000000.10101000.00000000.00000000
转化为十进制后为：

　　　　　192.168.0.0
通过以上对两台计算机IP地址与子网掩码的AND运算后，我们可以看到它运算结果是一样的。均为192.168.0.0，所以这二台计算机可视为是同一子网络。

输入描述:

输入子网掩码、两个ip地址

输出描述:

得到计算结果

输入：

255.255.255.0 192.168.224.256 192.168.10.4

输出：

1

问题分析



041. 称砝码
题目描述

现有一组砝码，重量互不相等，分别为m1,m2,m3…mn；

每种砝码对应的数量为x1,x2,x3…xn。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。
注：
称重重量包括0
方法原型：public static int fama(int n, int[] weight, int[] nums)

输入描述:

输入包含多组测试数据。
对于每组测试数据：
第一行：n — 砝码数(范围[1,10])
第二行：m1 m2 m3 … mn — 每个砝码的重量(范围[1,2000])
第三行：x1 x2 x3 … xn — 每个砝码的数量(范围[1,6])

输出描述:

利用给定的砝码可以称出的不同的重量数

输入：

2

1 2

2 1

输出：

5

问题分析
这道题的解题思路参考了牛客网的通过代码，是通过动态规划的思路来做的，不过总的来说效率着实不高，需要嵌套3层for循环，也是很醉，代码如下所示：
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            int[] weight = new int[n];
            int[] nums = new int[n];
            for (int i = 0; i < n; i++){
                weight[i] = in.nextInt();
            }
            for (int i = 0; i < n; i++){
                nums[i] = in.nextInt();
            }
            System.out.println(fama(n, weight, nums));
        }
    }

    public static int fama(int n, int[] weight, int[] nums){
        // 出现n为0的情况时我们也可以称出重量为0，所以返回1
        if (n == 0 || weight == null || nums == null){
            return 1;
        }

        int sum = 0;
        for (int i = 0; i < n; i++){
            sum += weight[i] * nums[i];
        }
        // 下标表示重量，true表示该重量可以用砝码称出
        boolean[] dp = new boolean[sum+1];
        dp[0] = dp[sum] = true;
        // 外面两层for循环是对砝码的逐个遍历
        for (int i = 0; i < n; i++){ 
            for (int j = 0; j < nums[i]; j++){
                // 第三层for循环是从后往前遍历，利用动态规划的思路
                // 如果还未加上weight[i]时的重量是可以被测出来的，
                // 那么加上weight[i]之后的砝码同样也是可以被测出来的
                for (int k = sum; k >= weight[i]; k--){
                    if (dp[k - weight[i]]){
                        dp[k] = true;
                    }
                }
            }
        }
        int result = 0;
        for (int i = 0; i <= sum; i++){
            if (dp[i]){
                ++result;
            }
        }
        return result;
    }

}

如果各位有比较高效的做法，欢迎告知！

042. 计算字符串的距离
题目描述

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。
Ex：
字符串A:abcdefg
字符串B: abcdef
通过增加或是删掉字符”g”的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
要求：

给定任意两个字符串，写出一个算法计算它们的编辑距离。

输入描述:

输入两个字符串

输出描述:

得到计算结果

输入

abcdefg

abcdef

输出

1

问题分析
这道题很容易看出是一道动态规划问题，同样定义动态函数 $d[i][j]$，表示字符串 str1 的前 $i$ 个字符变换为字符串 str2 的前 $j$ 个字符的最小编辑距离。很容易可得，$d[i][0] = i, d[0][j] = j$，因为当某一字符串的其中一个为 0 时，编辑距离很明显就是另一字符串的长度了。
而当 str1 的第 $i$ 个字符和 str2 的第 $j$ 个字符相同时，不需要变换，所以$d[i][j] = d[i-1][j-1]$；不相等时，我们可以选择添加、删除、替换，因此我们需要在 $dp[i-1][j-1]、dp[i][j-1]和dp[i-1][j]$中选择一个最小值+1赋值给 $dp[i][j]$，代码如下所示：
public class Main {
    
    private static int calStringDistance(String str1, String str2){
        if (str1 == null || str2 == null){
            return -1;
        }
        int n = str1.length();
        int m = str2.length();
        int[][] dp = new int[n+1][m+1];
        // 初始化
        for (int i = 1; i <= m; i++){
            dp[0][i] = i;
        }
        for (int i = 1; i <= n; i++){
            dp[i][0] = i;
        }
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                if (str1.charAt(i-1) == str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                }
            }
        }
        return dp[n][m];
    }
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String str1 = in.next();
            String str2 = in.next();
            System.out.println(calStringDistance(str1, str2));
        }
    }
    
}

题目描述：
新入职华为的小伙伴们都有在oj上面刷题的任务，共需要刷100道初级题，45道中级题，5道高级题,其中，做出来的高级题如果超标可以当初级或者中级题，做出来的中级题如果超标可以当初级题。每天，出题的大哥会给大家出Xi道题，这Xi道题属于同一个难度级别，小伙伴们要么用一天时间把这些题全做出来，要么就不做。现在，给你每天出题大哥出的题数以及难度，请问，小伙伴们最少要挑选其中几天去做题，才能把这150道题的任务完成呢？
输入示例：
5
100 70 5 5 55
1 2 2 2 3
输出：
2
表示两天就可以完成。
自己的解决思路：
这个题目的难点在于高难度的题目可以当做低难度的题目。
现将所有的题目按难度进行分类，并对每一类进行从大到小的排序。
首先，先做难度3的题目，如果难度三的题目搞定了 ，再将剩下的难度二和难度三的题目进行排序。在此基础上，再做难度二的。做完难度二以后，再将剩下的所有题目进行排序。在此基础上再做难度一的题目。
实现代码：
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LOWLEVEL 100
#define MIDLEVEL 45
#define UPLEVEL  5
bool MoreThan(int a,int b)
{
return a > b;
}
int theMax(int a,int b,int c)
{
return (a>b?(a>c?a:c):(b>c?b:c));
}
void display(char* str,vector &src)
{
int i,n;
n = src.size();
cout<
for (i = 0; i < n; i++)
{
cout<
}
cout<
}
void OJDoWorks(int days,vector &numbers,vector &nandu)
{
int i,n;
int dayOver,flagu,flagm,flagl;
int lowsum,midsum,upsum;
vector lowv, midv, upv,sortv,sortlv;
n = numbers.size();
flagl = flagm = flagu = -1;
lowsum = midsum = upsum = dayOver = 0;
//将题目进行分类
for (i = 0; i < n; i++)
{
if (nandu[i] == 1)
{
lowv.push_back(numbers[i]);
}
else if (nandu[i] == 2)
{
midv.push_back(numbers[i]);
}
else
{
upv.push_back(numbers[i]);
}
}
//按大小进行排序
sort(upv.begin(),upv.end(),MoreThan);
sort(midv.begin(),midv.end(),MoreThan);
sort(lowv.begin(),lowv.end(),MoreThan);
display("up",upv);
display("mid",midv);
display("low",lowv);
n = theMax(upv.size(),midv.size(),lowv.size());
//先把高级的做满
for(i = 0; i < upv.size();i++)
{
dayOver++;
upsum += upv[i];
if (upsum >= UPLEVEL)
{
flagu = i;
break;
}
}
//高级题目不够
if (flagu < 0)
{
return;
}
midsum = upsum - UPLEVEL;
//将剩下的高级和中级的题目进行排序
for (i = flagu+1; i< upv.size(); i++)
{
sortv.push_back(upv[i]);
}
for (i = 0; i < midv.size(); i++)
{
sortv.push_back(midv[i]);
}
sort(sortv.begin(),sortv.end(),MoreThan);
display("sort mid:",sortv);
//再把中级的做满
n = sortv.size();
for (i = 0; i < n; i++)
{
if (midsum >= MIDLEVEL)
{
flagm = i;
break;
}
dayOver++;
midsum += sortv[i];
}
//中级题目数量不够
if (flagm < 0)
{
return;
}
lowsum = midsum - MIDLEVEL;
//再做低级的题目
for ( i = flagm; i < n; i++)
{
sortlv.push_back(sortv[i]);
}
for (i = 0; i < lowv.size(); i++)
{
sortlv.push_back(lowv[i]);
}
sort(sortlv.begin(),sortlv.end(),MoreThan);
display("sort low",sortlv);
n = sortlv.size();
for (i = 0; i < n; i++)
{
if (lowsum >= LOWLEVEL)
{
flagl = i;
break;
}
dayOver++;
lowsum += sortlv[i];
}
if ((upsum >= UPLEVEL) && (midsum >= MIDLEVEL) && (lowsum >= LOWLEVEL))
{
cout<
}
else
{
return;
}
}
int main()
{
//fstream in("data.txt");
int n,i,value;
vector numbers,nandu;
cin>>n;
for (i = 0; i < n; i++)
{
cin>>value;
numbers.push_back(value);
}
for (i = 0; i < n; i++)
{
cin>>value;
nandu.push_back(value);
}
OJDoWorks(n,numbers,nandu);
cout<
return 0;
}

题目1 ——
通过输入英文句子。将每一个单词反过来，标点符号顺序不变。非26个字母且非标点符号的情况就可以标识单词结束。
标点符号包含,.!?
比如输入：Hello, I need an apple.
输出：
/**
* 华为机试训练1： 通过输入英文句子，将每一个单词反过来。标点符号顺序不变。非26个字母且非标点符号的情况就可以标识单词结束。 标点符号包含,.!?
* Hello, I need an apple.
*
* @author snail
*
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String string = scanner.nextLine();
scanner.close();
String[] ssString = string.split("\\W+");
String[] s2 = string.split("\\w+");
int wordsNum = ssString.length;
for (int i = 0; i < wordsNum; i++) {
if (s2.length >= wordsNum) {
int j = ssString[i].length() - 1;
for (; j > -1; j--) {
System.out.print(ssString[i].charAt(j));
}
System.out.print(s2[i + s2.length - wordsNum]);
} else {
System.out.print(s2[i - s2.length + wordsNum]);
int j = ssString[i].length() - 1;
for (; j > -1; j--) {
System.out.print(ssString[i].charAt(j));
}
}
}
System.out.println();
}
}
题目2——
实现“十七进制”转“十进制”算法：输入一个十七进制数字的字符串(字母一律大写)，输出这个数值相应的十进制结果。达到进制转换目的，范围：0-0xFFFFFFFF。
我的程序——
/**
* 实现“十七进制”转“十进制”算法：
* 输入一个十七进制数字的字符串(字母一律大写)，
* 输出这个数值相应的十进制结果，达到进制转换目的，
* 范围：0-0xFFFFFFFF。
* @author snail
*
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String string = scanner.nextLine();
scanner.close();
double result = 0;
int length = string.length();
double temp = 0;
char tempChar = '0';
int bitvalue = 0;
for (int i = 0; i < length; i++) {
tempChar = string.charAt(length -i-1);
if (!Character.isDigit(tempChar)) {
if (tempChar>=0x40 && tempChar <=0x46) {
bitvalue = tempChar - 0x41 +10;
}else {
bitvalue = tempChar - 0x61 +10;
}
}else {
bitvalue = tempChar - 0x30;
}
temp = bitvalue * Math.pow(17, i);
result += temp;
}
System.out.println(result);
}
}
题目3——
状态机——
背景：状态机在计算机各个领域中使用很广泛。最简单的状态机包括一组状态集(states)、一个起始状态(start state)、状态间转换条件(transition condition)。
要求：依据定义的脚本构造出状态机，并依据脚本进行状态迁移，或输出状态。
脚本包括例如以下keyword：
Insert  插入状态或迁移条件
语法是Insert 状态1,状态2,条件1
第一条Insert语句的第一个状态默觉得状态机的起始态。
假设状态1或状态2不存在，则新增状态1或状态2，假设状态1在条件1下已经存在其它迁移状态，则Insert失败。并输出Error字符串。
Delete 删除状态或迁移条件，
语法是Delete 状态1/条件1
当删除状态1时。状态1所关联的全部条件全被删除，Delete起始态将删除整个状态机，删除当前活动状态时，无效并输出Error字符串，删除的条件或状态不存在，输出Error字符串。
Input 状态机接收新条件
语法是 Input 条件1
当前状态在条件1下有正确的迁移状态时。状态机迁移到下一个状态，假设在条件1下没有正确的迁移状态时。保持在当前状态，并输出Error字符串；假设当前状态机没有状态。相同输出Error字符串。
Output 输出当前状态
语法是Output。假设当前状态机不存在。输出Error字符串，否则输出当前状态名.
End结束命令
语法是End。收到该命令，脚本执行结束，忽略后面的脚本
说明：输入脚本命令正确，不用考虑异常情况
例子输入：
Insert Sa,Sb,C1
Insert Sb,Sc,C2
Insert Sb,Sd,C3
Insert Sc,Se,C4
Insert Sd,Se,C5
Insert Se,Sa,C6
Input C1
Delete Sc
Input C2
Output
Input C3
Output
End
输出是 ：
Error
Sb
Sd
我的程序——感觉写得非常垃圾，没有找到合适的方法来表示这个状态。懂的朋友请指点下。
package tree.test;
import java.util.ArrayList;
import java.util.Scanner;
/**
* 状态机
* 20:03
* @author snail
*
*/
public class Main {
private static ArrayList statusList = new ArrayList();
private static String currentStatus ;
private static Status firstStatus ;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String string = "";
ArrayList inputList = new ArrayList();
while(!(string=scanner.nextLine()).equals("End")){
inputList.add(string);
}
int length = inputList.size();
String temp = "";
for (int i = 0; i < length; i++) {
temp = inputList.get(i);
if (temp.contains("Insert")) {
insert(temp);
}else if (temp.contains("Delete")) {
delete(temp);
System.out.println("debug-Delete --剩下"+statusList.size());
}else if (temp.contains("Input")) {
input(temp);
System.out.println("当前状态："+currentStatus.toString());
}else if (temp.contains("Output")) {
output();
//System.out.println("Output"+statusList.toString());
}
}
System.out.println();
}
private static void insert(String string){
String[] ss = string.split(" ");
String dataString = ss[1];
String[] insertStrings = dataString.split(",");
String currentString = insertStrings[0];
String nextString = insertStrings[1];
String requireString = insertStrings[2];
int size = statusList.size();
boolean existFlag = false;
for (int i = 0; i < size; i++) {
if (statusList.get(i).getCurrentStatus().equals(currentString)&&
statusList.get(i).getRequireString().equals(requireString)&&
!statusList.get(i).getNextStatus().equals(nextString)
) {
existFlag = true;
break;
}
}
if (existFlag) {
System.out.println("Error");
return ;
}else {
Status status = new Status();
status.setCurrentStatus(currentString);
status.setRequireString(requireString);
status.setNextStatus(nextString);
if(statusList.size() == 0){
firstStatus = status;
currentStatus = currentString;
}
statusList.add(status);
}
}
/**
* 删除
* @author snail
*
*/
private static void delete(String string){
String[] ss = string.split(" ");
String deleteString = ss[1];
if (deleteString == currentStatus) {
System.out.println("Error");
return ;
}else if(deleteString == firstStatus.getCurrentStatus()){
statusList.clear();
return ;
}
for (int i = 0; i < statusList.size(); i++) {
Status status = statusList.get(i);
//删除状态
if (status.getCurrentStatus().equals(deleteString)) {
for (int j = 0; j < statusList.size(); j++) {
if (statusList.get(j).getNextStatus().equals(deleteString)) {
statusList.get(j).setRequireString("");//删除有关的条件
//statusList.remove(j);
}
}
statusList.remove(i);
return ;
}
//删除条件
if (status.getRequireString().equals(deleteString)) {
statusList.remove(i);
return ;
}
}
//不存在
System.out.println("Error");
return ;
}
private static void input(String string){
String[] ss = string.split(" ");
String inputString = ss[1];
if (currentStatus == null) {
System.out.println("debug-input -- null");
System.out.println("Error");
return ;
}
ArrayList currentList = new ArrayList();
for (int i = 0; i < statusList.size(); i++) {
if (statusList.get(i).currentStatus.equals(currentStatus)) {
currentList.add(statusList.get(i));
}
}
boolean exist = false;
for (int i = 0; i < currentList.size(); i++) {
//System.out.println("debug-input --require:"+currentStatus.requireString+",input :"+inputString);
if (currentList.get(i).requireString.equals(inputString) ) {
String nextString = currentList.get(i).getNextStatus();
//System.out.println("debug-input -- 当前状态中有该条件");
//System.out.println("debug-input -- 下一个状态是"+nextString);
int size = statusList.size();
//寻找下一个状态
for (int j = 0; j < size; j++) {
if (statusList.get(i).getCurrentStatus().equals(nextString)) {
currentStatus = statusList.get(j).getCurrentStatus();
exist = true;
break;
}
}
}
if (exist) {
return ;
}else {
//System.out.println("debug-input -- 没有该迁移状态");
System.out.println("Error");
return ;
}}
{
//System.out.println("debug-input -- 没有该迁移条件");
System.out.println("Error");
return ;
}
}
private static void output(){
if (currentStatus == null) {
System.out.println("Error");
return ;
}else {
System.out.println(currentStatus);
return ;
}
}
public static class Status{
private String currentStatus;
private String requireString;
private String nextStatus;
public String getCurrentStatus() {
return currentStatus;
}
public void setCurrentStatus(String currentStatus) {
this.currentStatus = currentStatus;
}
public String getRequireString() {
return requireString;
}
public void setRequireString(String requireString) {
this.requireString = requireString;
}
public String getNextStatus() {
return nextStatus;
}
public void setNextStatus(String nextStatus) {
this.nextStatus = nextStatus;
}
@Override
public String toString() {
return "Status [currentStatus=" + currentStatus
+ ", requireString=" + requireString + ", nextStatus="
+ nextStatus + "]";
}
}
}

/*
编写一个函数，传入一个int型数组，返回该数组能否分成两组，
使得两组中各元素加起来的和相等，并且，所有5的倍数必须在其中一个组中，
所有3的倍数在另一个组中(不包括5的倍数)，能满足以上条件，返回true；
不满足时返回false。
*/
#include 
#include 
#include 
using namespace std;
string myplus(string str)//用于将字符串加1，转换为下一个字符串
{
int length=str.length();
string str1(length,'0');
str1[length-1]='1';
int flag=0;
for(int i=length-1;i>=0;i--)
{
if(str[i]-'0'+str1[i]-'0'+flag>1)
{
str[i]='0';
flag=1;
}
else
{
char temp;
temp=str[i]-'0'+str1[i]-'0'+flag+'0';
str[i]=temp;
break;
}
}
return str;
}
bool canFind(vector& ivec,int sum)//判断一个数组中，是否存在一个或几个数的和为一个已知的特定值。用排列组合的方式，如果有n个数，则存在2^n种选择
{
sort(ivec.begin(),ivec.end());
vector::iterator itr=ivec.begin();
while(itr!=ivec.end())
if (*itr==sum) return true;
int count=ivec.size();
string str(ivec.size(),'0');
int count1=pow(2.0,count);
for(int i=1;i<=count1;i++)
{
int a1=0,b1=0;
for(int j=0;j
{
if(str[j]=='0')
a1=a1+ivec[j];
else if(str[j]=='1')
b1=b1+ivec[j];
}
if(abs(a1-b1)==sum)
{
return true;
}
str=myplus(str);
}
return false;
}
void FindNum(int *arr,int n, int sum)
{
int begin = 0;
int end = n-1;
while(begin < end)
{
if(sum == arr[begin]+arr[end])
{
cout<
return;
}
else if (sum > arr[begin]+arr[end])
begin++;
else
end--;
}
cout<
}
bool getArray(vector& ivec)
{
int len=ivec.size();
int i,sum=0,difference;
int sumofFive=0,sumofThree=0,sumofOthers=0;
int sum1,sum2;
vector others;
for(i=0;i
{
sum=sum+ivec[i];
if(ivec[i]%5==0) sumofFive+=ivec[i];
else if(ivec[i]%3==0) sumofThree+=ivec[i];
else
{
others.push_back(ivec[i]);
sumofOthers+=ivec[i];
}
}
if (sum%2!=0) return false;
else
{
difference=abs(sumofFive-sumofThree);
if(difference==sumofOthers)
return true;
else if(sumofOthers
return false;
else
{
sum1=(difference+sumofOthers)/2;
sum2=(sumofOthers-difference)/2;
if(canFind(others,sum2))
return true;
}
}
return false;
}
int main()
{
vector ivec;
int num;
cin>>num;
int data;
for(int i=0;i
{
cin>>data;
ivec.push_back(data);
}
if(getArray(ivec)) cout<
else cout<
return 0;
}