面试算法题

    /**
     * 编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节截取的字符串。
     * 但是要保证汉字不被截半个，如输入（“我ABC”，4），应该输出“我AB”；
     * 输入（“我ABC汉DEF”，6），应该输出“我ABC”而不是“我ABC”+“汉”的半个
     *
     * 考点：汉字截半时对应字节的ASCII码小于0
     */

    public static void main(String[] args) throws Exception {
        String src = "我ABC汉DEF";
        System.out.println(spiltString(src, 4));
        System.out.println(spiltString(src, 6));
    }

    private static String spiltString(String src, int len) throws Exception {
        if (src == null || src.equals("")) {
            System.out.println("The source String is null!");
            return null;
        }
        byte[] srcBytes = src.getBytes("GBK");
        if (len > srcBytes.length) {
            len = srcBytes.length;
        }
        if (srcBytes[len] < 0) {
            return new String(srcBytes, 0, --len);
        } else {
            return new String(srcBytes, 0, len);
        }
    }

  /**
     * 在实际开发工作中，对字符串的处理是最常见的编程任务。
     * 本题目即是要求程序对用户输入的字符串进行处理。具体规则如下：
     * a）把每个单词的首字母变为大写
     * b）把数字与字母之间用下划线字符（_）分开，使得更清晰
     * c）把单词中间有多个空格的调整为1个空格
     * 例如：
     * 用户输入：
     * you and me what      cpp2005program
     * 则程序输出：
     * You And Me What Cpp_2005_program
     * 
     * 相关文章：http://blog.csdn.net/u013091087/article/details/43793149
     */

    public static void main(String[] args) {
        System.out.println("please input:");
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        scanner.close();
        String[] ss = s.split("\\\\s+"); // \\s表示空格、\\t、\\n等空白字符
        for (int i = 0; i < ss.length; i++) {
            String up = (ss[i].charAt(0) + "").toUpperCase(); // 大写
            StringBuffer sb = new StringBuffer(ss[i]);
            ss[i] = sb.replace(0, 1, up).toString(); // 首字母替换为大写
            Matcher m = Pattern.compile("\\\\d+").matcher(ss[i]);
            int fromIndex = 0;
            while (m.find()) {
                String num = m.group();
                int index = ss[i].indexOf(num, fromIndex);
                StringBuffer sbNum = new StringBuffer(ss[i]);
                ss[i] = sbNum.replace(index, index + num.length(),
                        "_" + num + "_").toString();
                fromIndex = index + num.length() + 2;
                if (ss[i].startsWith("_")) { // 去头"_"
                    ss[i] = ss[i].substring(1);
                }
                if (ss[i].endsWith("_")) { // 去尾"_"
                    ss[i] = ss[i].substring(0, ss[i].length() - 1);
                }
            }
        }
        for (int i = 0; i < ss.length - 1; i++) {
            System.out.print(ss[i] + " ");
        }
        System.out.print(ss[ss.length - 1]);
    }

    /**
     * 两个有序数组的合并函数
     * @param a
     * @param b
     * @return
     */
    public static int[] MergeList(int a[], int b[]) {
        int result[];
        result = new int[a.length + b.length];
        //i:用于标示a数组    j：用来标示b数组  k：用来标示传入的数组
        int i = 0, j = 0, k = 0;

        while (i < a.length && j < b.length) {
            if (a[i] <= b[j]) {
                result[k++] = a[i++];
            } else {
                result[k++] = b[j++];
            }
        }
            /* 后面连个while循环是用来保证两个数组比较完之后剩下的一个数组里的元素能顺利传入 */
        while (i < a.length)
            result[k++] = a[i++];
        while (j < b.length)
            result[k++] = b[j++];

        return result;
    }

    public static int rank(int key, int a[]) {
        return rank(key, a, 0, a.length - 1);
    }

    public static int rank(int key, int a[], int lo, int hi) {
        if (lo > hi)
            return -1;//error
        int mid = lo + (hi - lo) / 2;
        if (key < a[mid])
            return rank(key, a, lo, mid - 1);
        else if (key > a[mid])
            return rank(key, a, mid + 1, hi);
        else
            return mid;
    }