华为笔试题（4）

一、
计算n x m的棋盘格子（n为横向的格子数，m为竖向的格子数）
沿着各自边缘线从左上角走到右下角，总共有多少种走法，
要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
输入描述:
输入两个正整数
输出描述:
返回结果
示例1
输入
2 2
输出
6

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        /* nXm格，则有(n+1)X(m+1)个点
         * 用递归，由于只能往下和往右，情况就比较少了
         */
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            System.out.println(recur(n, m));
        }
        sc.close();
    }

    private static int recur(int posX, int posY) {
        //X等于0或Y等于0只能是朝一个方向走的，只有1种情况
        if(posX == 0 || posY == 0) {
            return 1;
        }
        return recur(posX - 1, posY) + recur(posX, posY - 1);
    }
}

二、
现在IPV4下用一个32位无符号整数来表示，一般用点分方式来显示，
点将IP地址分成4个部分，每个部分为8位，表示成一个无符号整数（因此不需要用正号出现）
如10.137.17.1，是我们非常熟悉的IP地址，一个IP地址串中没有空格出现（因为要表示成一个32数字）。
现在需要你用程序来判断IP是否合法。
输入描述:
输入一个ip地址
输出描述:
返回判断的结果YES or NO
输入
10.138.15.1
输出
YES

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        /* nXm格，则有(n+1)X(m+1)个点
         * 用递归，由于只能往下和往右，情况就比较少了
         */
        while(sc.hasNext()) {
            String str = sc.next();
            String[] strs = str.split("\\.");
            System.out.println(process(strs));

        }
        sc.close();
    }

    private static String process(String[] strs) {
        //位数不合法
        if(strs == null || strs.length != 4) {
            return "NO";
        }
        //超界不合法
        for(int i = 0; i < strs.length; i++) {
            int tmp = Integer.parseInt(strs[i]);
            if(tmp > 255 || tmp < 0) {
                return "NO";
            }
        }
        return "YES";
    }
}

三、
功能: 求一个byte数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1
输入描述:
输入一个byte数字
输出描述:
输出转成二进制之后连续1的个数
输入
3
输出
2

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        /* byte型8位
         * 最大连续相同字符串问题
         */
        while(sc.hasNext()) {
            int n = sc.nextInt();
            System.out.println(process(n));

        }
        sc.close();
    }

    private static int process(int n) {
        //化成数组
        int tmp = n;
        int[] bit = new int[8];
        int index = 7;
        while(tmp != 0) {
            bit[index--] = tmp & 1;
            tmp >>>= 1;
        }
        int max = 0;
        int cnt = 0;
        //统计最大连续1串
        for(int i = 0; i < 8; i++) {
            if(bit[i] == 1) {
                cnt++;
                max = Math.max(max, cnt);
            }else {
                cnt = 0;
            }
        }
        return max;
    }
}

四、
找出一个随机字符串中最长回文串，输出它的长度
输入描述:
输入一个字符串
输出描述:
返回最长回文串的长度
输入
ABBA
输出
4

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        //最长回文子串问题
        while(sc.hasNext()) {
            String str = sc.next();
            System.out.println(process(str));

        }
        sc.close();
    }

    private static int process(String str) {
        int n=str.length();
        int max=0;
        char[]ch=str.toCharArray();
        for(int i=0;i<n;i++){//以i为中心的回文串
            //奇数长度的子串
            int j=1;
            int cur=1;
            while(i-j>=0&&i+j<n&&ch[i-j]==ch[i+j]){//不越界且左右相等
                cur+=2;
                j++;
            }
            max=Math.max(cur,max);         
            //偶数长度的子串
            j=0;
            cur=0;
            while(i-j>=0&&i+j+1<n&&ch[i-j]==ch[i+1+j]){
                cur+=2;
                j++;
            }
            max=Math.max(cur,max);     
        }
        return max;
    }
}

五、
找出给定字符串中大写字符(即’A’-‘Z’)的个数
输入描述:
输入一个String数据
输出描述:
输出string中大写字母的个数
示例1
输入
add123#$%#%#O
输出
1

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            String str = sc.next();
            System.out.println(process(str));

        }
        sc.close();
    }

    private static int process(String str) {
        int n=str.length();
        int num = 0;
        for(int i = 0; i < n; i++) {
            char tmp = str.charAt(i);
            if(tmp >= 'A' && tmp <= 'Z') {
                num++;
            }
        }
        return num;
    }
}

六、
判断短字符串中的所有字符是否在长字符串中全部出现
输入描述:
输入两个字符串。第一个为短字符，第二个为长字符。
输出描述:
返回值
示例1
输入
bc
abc
输出
true

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        //不是字符串匹配问题，只要求出现即可
        while(sc.hasNext()) {
            String strShort = sc.next();
            String strLong = sc.next();
            System.out.println(process(strShort, strLong));
        }
        sc.close();
    }

    private static boolean process(String strShort, String strLong) {
        int n = strShort.length();
        int m = strLong.length();
        int[] ch = new int[128];
        for(int i = 0; i < n; i++) {
            ch[strShort.charAt(i)] = 1;
        }
        for(int i = 0; i < m; i++) {
            ch[strLong.charAt(i)]++;
        }
        for(int i = 0; i < n; i++) {
            if(ch[strShort.charAt(i)] == 1) {
                return false;
            }
        }
        return true;
    }
}

七、
将两个整型数组按照升序合并，并且过滤掉重复数组元素
输入描述:
输入说明，按下列顺序输入：
1 输入第一个数组的个数
2 输入第一个数组的数值
3 输入第二个数组的个数
4 输入第二个数组的数值
输出描述:
输出合并之后的数组
示例1
输入
3
1 2 5
4
-1 0 3 2
输出
-101235

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

            TreeSet<Integer> set = new TreeSet<>();
            StringBuffer sb = new StringBuffer();
            for(int i = 0; i < n; i++) {
                set.add(sc.nextInt());
            }
            int m = sc.nextInt();
            for(int i = 0; i < m; i++) {
                set.add(sc.nextInt());
            }
            for(int i : set) {
                sb.append(i);
            }
            System.out.println(sb.toString());
        }
        sc.close();
    }
}

八、
对于不同的字符串，我们希望能有办法判断相似程度，
我们定义了一套操作方法来把两个不相同的字符串变得相同，具体的操作方法如下：
1 修改一个字符，如把“a”替换为“b”。
2 增加一个字符，如把“abdd”变为“aebdd”。
3 删除一个字符，如把“travelling”变为“traveling”。
比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加和减少一个“g”的方式来达到目的。
上面的两种方案，都只需要一次操作。把这个操作所需要的次数定义为两个字符串的距离，
而相似度等于“距离＋1”的倒数。
也就是说，“abcdefg”和“abcdef”的距离为1，相似度为1/2=0.5.
给定任意两个字符串，你是否能写出一个算法来计算出它们的相似度呢？
输入描述:
输入两个字符串
输出描述:
输出相似度，string类型
示例1
输入
abcdef
abcdefg
输出
1/2

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        //编辑距离问题，用动态规划
        while(sc.hasNext()) {
            String a = sc.next();
            String b = sc.next();
            System.out.println(process(a, b));
        }
        sc.close();
    }

    private static String process(String a, String b) {
        int n = a.length();
        int m = b.length();
        int [][]dp = new int[n + 1][2];
        for(int i = 0; i <= n; i++){
            dp[i][0] = i;
        }
        for(int j = 1; j <= m; j++) {
            dp[0][1] = j;
            for(int i = 1; i <= n; i++) {
                if(a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][1] = dp[i - 1][0];
                }else {
                    dp[i][1]=Math.min(dp[i-1][1]+1, dp[i][0]+1);
                    dp[i][1]=Math.min(dp[i][1], dp[i-1][0]+1);
                }
            }
            for(int i = 0; i <= n; i++) {
                dp[i][0] = dp[i][1];
            }
        }
        return String.valueOf("1/"+(dp[n][1]+1));
    }
}

九、
请设计一个算法完成两个超长正整数的加法。
输入描述:
输入两个字符串数字
输出描述:
输出相加后的结果，string型
示例1
输入
99999999999999999999999999999999999999999999999999
1
输出
100000000000000000000000000000000000000000000000000

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        //按位相加后处理进位问题即可
        while(sc.hasNext()) {
            String a = sc.next();
            String b = sc.next();
            System.out.println(process(a, b));
        }
        sc.close();
    }

    private static String process(String a, String b) {
        int[] bit = new int[Math.max(a.length(), b.length())];
        int i = a.length() - 1, j = b.length() - 1, k = 0;
        for(;i >= 0 && j >= 0; i--,j--,k++) {
            bit[k] = a.charAt(i) - '0' + b.charAt(j) - '0';
        }
        if(i >= 0) {
            while(i >= 0) {
                bit[k++] = a.charAt(i--) - '0';
            }
        }
        if(j >= 0) {
            while(j >= 0) {
                bit[k++] = b.charAt(j--) - '0';
            }
        }
        StringBuffer sb = new StringBuffer();
        for(i = 0; i < bit.length - 1; i++) {
            if(bit[i] > 9) {
                bit[i + 1]++;
                bit[i] -= 10;
            }
            sb.append(bit[i]);
        }
        if(bit[bit.length - 1] > 9) {
            sb.append(bit[bit.length - 1] - 10);
            sb.append(1);
        }else {
            sb.append(bit[bit.length - 1]);
        }
        return sb.reverse().toString();
    }
}

十、
给定一个正整数N代表火车数量，0

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        //出栈全排序问题，可用递归
        //利用两个栈来模拟出栈入栈
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int a[] = new int[n];
            for(int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            Stack<Integer> stk1 = new Stack<>();
            Stack<Integer> stk2 = new Stack<>();
            for(int i = n - 1; i >= 0; i--) {
                stk1.push(a[i]);
            }
            List<String> res = new ArrayList<>();
            process("", stk1, stk2, res);
            Collections.sort(res);
            for(String s : res) {
                System.out.println(s);
            }
        }
        sc.close();
    }

    private static void process(String str, Stack<Integer>stk1, Stack<Integer>stk2, List<String> res) {
        if(stk1.isEmpty() && stk2.isEmpty()) {
            res.add(str.trim()) ;//过滤首位空白
            return;
        }
        if(!stk2.isEmpty()) {
            int tmp = stk2.pop();
            process(str+" "+tmp, stk1, stk2, res);
            stk2.push(tmp);
        }
        if(!stk1.isEmpty()) {
            int tmp = stk1.pop();
            stk2.push(tmp);
            process(str, stk1, stk2, res);
            stk2.pop();
            stk1.push(tmp);
        }
    } 
}