面试题5: 替换空格和归并数组

5-1 替换空格

package cn.zxy.interview;

/**
 * 分析:
 * 首先不要使用StringBuffer+append; 使用重新设置str长度的方式
 * 1. 先遍历一遍字符串, 确定空格的个数; 根据空格个数和原字符串长度确定新长度newLength
 * 2. 用p1指向旧字符串尾部, 用p2指向新(长度)字符串的尾部
 * 3. 从后向前
 */
public class A05_ReplaceSpacing {
    public static String replaceSpacing(StringBuilder str){
        int countSpace = 0;
        for (int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == ' '){
                countSpace++;
            }
        }
        // 确定新长度, 设置指针
        int oldLength = str.length();
        int newLength = str.length() + 2 * countSpace;
        str.setLength(newLength);

        int p1 = oldLength - 1;
        int p2 = newLength - 1;

        // p1指示原始字符串末尾
        // 当两个指针碰面, 转移完毕
        while(p1 != p2){
            char ch = str.charAt(p1);
            if(ch != ' '){
                str.setCharAt(p2, ch);
                p1--;
                p2--;
            }else if(ch == ' '){
                str.setCharAt(p2--, '0');
                str.setCharAt(p2--, '2');
                str.setCharAt(p2--, '%');
                p1--;
            }
        }
        return str.toString();

    }

    public static void main(String[] args) {
        String str = "We are happy.";
        String strNew = replaceSpacing(new StringBuilder(str));
        System.out.println(strNew);
    }
}

5-2 归并数组

package cn.zxy.interview;

import java.util.Arrays;

/**
 * 问题: 数组A1和A2都有序, A1空余空间足够, 有序归并两数组
 * 分析:
 * 1. 根据A1和A2的长度, 确定合并后数组的长度, 利用一个指针指向该位置
 * 2. 利用两个指针分别指示元素在A1和A2中的位置
 * 3. 比较 较大者放入新数组
 * 4. 注意分四种情况
 */

public class A05_MergeArray {
    public static void mergeArray(int[] a1, int[] a2, int m, int n){
        if (a1 == null || a2 == null || a1.length == 0 || a2.length == 0) return;
        int newLength = m + n;
        int p1 = m - 1;
        int p2 = n - 1;
        int p3 = newLength - 1;

        // 可能有1组先归并完
        while(p3> 0){
            if(p1 == 0)              a1[p3--] = a2[p2--];  // a1先归并完
            else if(p2 == 0)         a1[p3--] = a1[p1--];  // a2先归并完
            else if(a1[p1] > a2[p2]) a1[p3--] = a1[p1--];  // 大的放后面
            else                     a1[p3--] = a2[p2--];
        }

    }

    public static void main(String[] args) {
        int[] a1 = {1, 3, 4, 7, 12, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        int[] a2 = {2, 3, 5, 8};
        int m = 6;
        int n = 4;
        mergeArray(a1, a2, m, n);
        for (int i = 0; i < a1.length; i++) {
            System.out.print(a1[i]+ " ");
        }

    }

}