华为笔试 2019/5/08

第一题 简单数组操作 AC：100%

public class Main1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int N=in.nextInt();
            int[][] range=new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    range[i][j]=in.nextInt();
                }
            }
            int times=in.nextInt()%4;
            for (int i = 0; i < times; i++) {
                reverseRange(range);
                exchangeRange(range);
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    System.out.print(range[i][j]+" ");
                }
                System.out.println();
            }
        }
    }

    public static void reverseRange(int [][] range){
        for (int i = 0; i < range.length; i++) {
            for (int j = i; j < range.length; j++) {
                int temp=range[i][j];
                range[i][j]=range[j][i];
                range[j][i]=temp;
            }
        }
    }
    public static void exchangeRange(int [][]range){
        int row=0;
        int col=range.length-1;
        for (int i = 0; i < range.length/2; i++) {
            for (int j = 0; j < range.length; j++) {
                int temp=range[j][row];
                range[j][row]=range[j][col];
                range[j][col]=temp;
            }
            row++;
            col--;
        }
    }
}

第二题 字符串全排列问题 AC：100%

public class Main2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n=in.nextInt();
            int k=in.nextInt()-1;
            StringBuilder sb=new StringBuilder();
            for (int i = 0; i < k; i++) {
                sb.append("|");
            }
            for (int i = 0; i < n; i++) {
                sb.append("*");
            }
            ArrayList<String> permutation = Permutation(sb.toString());
            System.out.println(permutation.size());
            for (int i = 0; i < permutation.size(); i++) {
                System.out.println(permutation.get(i));
            }
        }
    }

    private static ArrayList<String> list=new ArrayList<>();

    public static ArrayList<String> Permutation(String str) {
        if(str.length()==0)
            return list;
        PermutationHelper(str.toCharArray(),0);
        Collections.sort(list);
        return list;
    }

    private static void PermutationHelper(char[] chars, int index){
        if(index==chars.length){
            list.add(String.valueOf(chars));
        }
        for (int i = index; i < chars.length; i++) {
            if(isSwap(chars,index,i)){
                swap(chars,index,i);
                PermutationHelper(chars,index+1);
                swap(chars,i,index);
            }
        }
    }

    //判断low到high之间是否有和low[high]元素相同的元素
    private static boolean isSwap(char[] chars, int low ,int high){
        for (int i = low; i <high; i++) {
            if (chars[i] == chars[high])
                return false;
        }
        return true;
    }

    private static void swap(char[] chars, int i, int k) {
        char temp=chars[k];
        chars[k]=chars[i];
        chars[i]=temp;
    }

}

第三题 字符串相识度问题 dp动态规划 AC：100%

public class Main3 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int N = in.nextInt();
            ArrayList<String> beforeList=new ArrayList<>();
            ArrayList<String> afterList=new ArrayList<>();
            for (int j = 0; j < N; j++) {
                beforeList.add(in.next());
            }
            for (int j = 0; j < N; j++) {
                afterList.add(in.next());
            }
            int result=0;
            for (int i = 0; i < N; i++) {
                result+=compareCharacter(beforeList.get(i),afterList.get(i));
            }
            System.out.println(result);
        }
    }

    public static int compareCharacter(String before,String after){
        int dp[][];
        int sLen=before.length();
        int tLen=after.length();
        int si,ti;
        char ch1,ch2;
        int cost;
        if(sLen==0){
            return tLen;
        }
        if(tLen==0)
            return sLen;
        dp=new int[sLen+1][tLen+1];
        for (si = 0; si <=sLen ; si++) {
            dp[si][0]=si;
        }
        for (ti= 0; ti <= tLen ; ti++) {
            dp[0][ti]=ti;
        }

        for (si=1; si<=sLen ; si++) {
            ch1= before.charAt(si-1);
            for (ti= 1; ti <=tLen ; ti++) {
                ch2=after.charAt(ti-1);
                if(ch1==ch2)
                    cost=0;
                else cost=1;
                dp[si][ti]=Math.min(Math.min(dp[si-1][ti]+1,dp[si][ti-1]+1),dp[si-1][ti-1]+cost);
            }
        }
        return dp[sLen][tLen];
    }
}