[4/30]MIOJ刷题:大数相减

重阳节快乐! 独自莫凭栏, 今天没登高.

大数相减
这个题估计是leetcode改编版,更准确说是精简版,保证了这个a >= b.

思路:

字符串反转至int数组,注意需要过滤掉开始的0.如 0099999999999999这种
以较短的数字长度为上限,计算差数组,注意发生借位的条件
将较长的数字剩余部分拼接到结果数组中
反转数组至字符串中并输出,这里也需要注意0的问题.如需要反转的结果数组是 9999999999999000这种.

package playground.mioj.day4.BigNumberSubtract;

import java.util.Scanner;

/**
 * @author chuanyi@88.com
 * @date 2020/10/22
 * 大数相减 https://code.mi.com/problem/list/view?id=3
 * 这是leetcode的精简版本，a >= b
 * 不需要考虑换位和符号位的问题
 * @Description
 */
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String line;
        while (scan.hasNextLine()) {
            line = scan.nextLine().trim();
            String[] operators = line.split("-");
            String a = operators[0].trim();
            String b = operators[1].trim();
//            System.out.println(a);
//            System.out.println(b);

            String answer = subtract(a, b);
            System.out.println(answer);
//            assertResult1();
//            assertResult2();

        }
    }

    private static void assertResult2() {
        System.out.println("Assertion starts:");
        String line = "1231231237812739878951331231231237812739878951331231231237812739878951331230000000000000000000000001-331231231237812739878951331231231";
        String[] operators = line.split("-");
        String a = operators[0].trim();
        String b = operators[1].trim();
        System.out.println(a);
        System.out.println(b);

        String answer = subtract(a, b);
        System.out.println("actual result："+answer);
        String expectedResult = "1231231237812739878951331231231237812739878951331231231237812739878620099998762187260121048668768770";
        System.out.println("expected result："+expectedResult);
        System.out.println("assert success？："+expectedResult.equals(answer));

    }


    private static void assertResult1() {
        System.out.println("Assertion starts:");
        String line = "1231231237812739878951331231231237812739878951331231231237812739878951331231231237812739878951331231231237812739878951331231231237812739870-89513312312312378127398789513312312312378127398789513312312312378127398789513";
        String[] operators = line.split("-");
        String a = operators[0].trim();
        String b = operators[1].trim();
        System.out.println(a);
        System.out.println(b);

        String answer = subtract(a, b);
        System.out.println("actual result："+answer);
        String expectedResult = "1231231237812739878951331231231237812739878951331231231237812650365639018918853110413950365639018918853110413950365639018918853110413950357";
        System.out.println("expected result："+expectedResult);
        System.out.println("assert success？："+expectedResult.equals(answer));

    }

    /**
     * 2323
     * -  44
     *
     * @param a
     * @param b
     * @return
     */
    private static String subtract(String a, String b) {
        int[] reversedA = reverse(a);
        int[] reversedB = reverse(b);
        return subtract(reversedA, reversedB);
    }

    /**
     * 反转字符串
     * 找到第一个不为零的元素，从这个下标开始反转字符串至int数组中
     *
     * @param a
     * @return
     */
    private static int[] reverse(String a) {
        int length = a.length();
        int firstIndexNonZero = 0;
        for (int i = 0; i < length; i++) {
            if (a.charAt(i) != '0') {
                firstIndexNonZero = i;
                break;
            }
        }
        int[] reversed = new int[length - firstIndexNonZero];
        //逆序的时候，下面这个操作是容易出现的错误
//        for (int i = length - 1; i >= firstIndexNonZero; i--) {
//            reversed[i] = a.charAt(i) - '0';
//        }
        for (int i = 0; i < length - firstIndexNonZero; i++) {
            reversed[i] = a.charAt(length - 1 - i) - '0';
        }
        return reversed;
    }

    private static String subtract(int[] a, int[] b) {
        int[] result = new int[a.length];
        int maxLen = a.length;
        int minLen = b.length;
        for (int i = 0; i < minLen; i++) {
            //易错点，这里可以减的条件是大于或等于，不要漏掉，否则会出现非法借位，关键点不能靠记忆，要停一下想想想想想啊
            if (a[i] >= b[i]) {
                result[i] = a[i] - b[i];
            } else {
                result[i] = a[i] + 10 - b[i];
                a[i + 1]--;
                //开始有担心，这里可能越界呢，但是仔细想想？
                //预设的条件已经保证了越界不可能发生a > b说明。
                //a的位数比b多或者a的最高位大于等于b，所以当i到达了a的最高位时候，一定执行的是上一个分支
                //注意如果a的位数比b多，而且需要借位的时候，这里借位的位刚好是可以借的，也不会越界。
            }
        }
        if (maxLen > minLen) {
            //这里注意要从不能从minLen开始，因为如果a b长度相同，这里的result将会是
            for (int i = minLen; i < maxLen; i++) {
                result[i] = a[i];
            }
        }
        return recover(result);
    }

    private static String recover(int[] arr) {
        StringBuilder result = new StringBuilder();
        int firstNonZeroIndex = arr.length - 1;
        for (int i = firstNonZeroIndex; i >= 0; i--) {
            if (arr[i] != 0) {
                firstNonZeroIndex = i;
                break;
            }
        }
        int i = firstNonZeroIndex;
        while (i >= 0) {
            result.append(arr[i]);
            i--;
        }
        return result.toString();
    }
}

交叉队列

解法比较多,DP,递归,DFS,BFS

package lambdasinaction.playground.mioj.day4.Interleave;

import java.util.Scanner;

/**
 * @author: chuanyi@88.com
 * @description:
 * @date: 2020/10/25 23:05
 */
public class Main {
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        String line;
        while (scan.hasNextLine()) {
            line = scan.nextLine().trim();
            final String[] split = line.split(",");
            if (split.length < 3) {
                return;
            }
            String s1 = split[0];
            String s2 = split[1];
            String s3 = split[2];
            System.out.println(isInterleaveDp(s1, s2, s3));
            System.out.println(isInterleaveDpRecursive(s1, s1.length(), 0, s2, s2.length(), 0, "", s3));
            System.out.println(isInterleaveDpBfs(s1, s2, s3));
            System.out.println(isInterleaveDpDfs(s1, s2, s3));
        }
    }

    private static boolean isInterleaveDpDfs(String s1, String s2, String s3) {
        return false;
    }

    private static boolean isInterleaveDpBfs(String s1, String s2, String s3) {
        return false;
    }

    private static boolean isInterleaveDpRecursive(String s1, int s1Length, int s1Index, String s2, int s2Length, int s2Index, String result, String s3) {
        if (result.equals(s3) && s2Index == s2Length && s1Index == s1Length) {
            return true;
        }
        boolean answer = false;
        if (s1Index < s1Length) {
            answer = isInterleaveDpRecursive(s1, s1Length, s1Index + 1, s2, s2Length, s2Index, result + s1.charAt(s1Index), s3);
        }
        if (s2Index < s2Length) {
            answer |= isInterleaveDpRecursive(s1, s1Length, s1Index, s2, s2Length, s2Index + 1, result + s2.charAt(s2Index), s3);
        }
        return answer;
    }

    private static boolean isInterleaveDp(String s1, String s2, String s3) {

        if ("".equals(s1) && "".equals(s2)) {
            return false;
        }
        if ("".equals(s1)) {
            return s2.equals(s3);
        }
        if ("".equals(s2)) {
            return s1.equals(s3);
        }
        int s1Length = s1.length();
        int s2Length = s2.length();
        if (s1Length + s2Length != s3.length()) {
            return false;
        }
        boolean[][] mark = new boolean[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i <= s1Length; i++) {
            for (int j = 0; j <= s2Length; j++) {
                if (i == 0 && j == 0) {
                    mark[i][j] = true;
                } else if (j == 0) {
                    mark[i][j] = mark[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i - 1);
                } else if (i == 0) {
                    mark[i][j] = mark[i][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
                } else if (s1.charAt(i - 1) == s3.charAt(i + j - 1) && mark[i - 1][j]) {
                    mark[i][j] = true;
                } else if (s2.charAt(j - 1) == s3.charAt(i + j - 1) && mark[i][j - 1]) {
                    mark[i][j] = true;
                }
            }
        }
        return mark[s1Length][s2Length];

    }
}

参考:
dp版
 递归版
 dfs&bfs版本