leetcode题解-71. Simplify Path && 43. Multiply Strings

好久没刷题了，感觉有些荒废，今天突然想到明年就要找工作了，吓得我赶紧刷两道压压惊==

题目：43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

在不将字符串转化为整型数字的情况下实现字符串乘法，一开始看到这个题目没有什么思路，一直局限在怎么表示字符串整数的问题上，后来看了别人的解法，恍然大悟，原来要从乘法规则上进行考虑，思考两个整数相乘时里面每个数字是如何计算的，然后如何拼接成最后的结果。我们来看下面这张图片，很好地解释了乘法的工作原理，就是两个数的第i，j个数字相乘的结果会是一个两位数，将期分别放在最终结果的第i+j和i+j+1处，需要注意的是需要先将该乘积加上第i+j位置出的数字，以保证进位正确。而且应该从右到左也就是从小到大进行计算，代码如下所示：

    //59%
    public static String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] pos = new int[m + n];

        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                //计算乘积
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j, p2 = i + j + 1;
                //将乘积与p2位置处的数字相加在进行后续的赋值操作
                int sum = mul + pos[p2];

                //十位数放在p1，个位数放在p2
                pos[p1] += sum / 10;
                pos[p2] = (sum) % 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
        return sb.length() == 0 ? "0" : sb.toString();
    }

此外还有一种效果更好的算法，可以击败97.5%的用户，代码如下所示：

    //97.5%
    public String multiply1(String num1, String num2) {
        int m=num1.length(), n=num2.length(), zero=0;
        int[] a = new int[m], c = new int[m+n];
        for(int i=0,k=m; i<m; i++) a[--k]=num1.charAt(i)-'0';  // reverse the first number
        for(int i=n-1; i>=0; i--)
            //将两个字符串每个字符两两相乘放在c数组中，zero表示c的下表，i表示num1的下表
            add(c,a,num2.charAt(i)-'0',zero++);    // multiply each digits of num2 to num1
        //将乘出来的结果进行处理
        carry(c);            // handle all carry operation together
        int i=m+n;
        while(i>0 && c[--i]==0);  // find the highest digit
        i++;
        StringBuilder ret = new StringBuilder(i);
        while(i>0) ret.append((char)(c[--i]+'0'));
        return ret.toString();
    }
    void carry(int[] a){
        //对相邻的数字进行进位处理
        int i;
        for(int k=0,d=0; k<a.length; k++){
            i=a[k]+d;
            a[k]=i%10;
            d=i/10;
        }
    }
    void add(int[] c, int[] a, int b, int zero){
        for(int i=zero,j=0; j<a.length; j++,i++)
            c[i]+=a[j]*b;
    }

题目：71. Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
click to show corner cases.

Corner Cases:
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".

本题就是一个简化linux路径表示的问题。首先要了解路径表示的规则，主要有下面几个符号：

• .
• ..
• /
• //
• 文件名

这几种符号，..表示上一级目录，.可以不用管，所以我们直接对字符串按照/进行分割即可，然后分割后的结果中如果是.或者空，则不管，如果是文件名则保存到结果中，如果是..则删除结果中最后一个文件名。代码如下所示：

    //95%
    public String simplifyPath(String path) {
        //使用两个数组，第一个数组用于保存切分之后的内容，然后遍历
        //遇到.或者空的时候直接跳过，遇到文件夹名的时候向第二个数组添加，遇到..的时候将第二个数组的最后一个内容删除，其实
        //就是游标向前移动一个值
        String[] dir = path.split("/");
        String[] stack = new String[dir.length];
        int ptr = 0;
        for(int i = 0; i < dir.length; i++){
            if(dir[i].equals(".") || dir[i].equals(""))
                continue;
            else if(dir[i].equals("..")){
                if(ptr > 0) ptr--;
            }else{
                stack[ptr] = dir[i];
                ptr++;
            }
        }
        StringBuilder result = new StringBuilder();
        for(int i = 0; i < ptr; i++){
            result.append("/");
            result.append(stack[i]);
        }
        return result.length() == 0 ? "/" : result.toString();
    }

我们还可以使用栈来实现上述代码，栈的好处是可以方便的将最后一个元素进行删除和添加操作，代码如下：

    //34%
    public String simplifyPath2(String path) {
        Stack<String> stack = new Stack<>();
        String[] p = path.split("/");
        for (int i = 0; i < p.length; i++) {
            if (!stack.empty() && p[i].equals(".."))
                stack.pop();
            else if (!p[i].equals(".") && !p[i].equals("") && !p[i].equals(".."))
                stack.push(p[i]);
        }
        List<String> list = new ArrayList(stack);
        return "/"+String.join("/", list);
    }

可以看到效率低了很多，这是因为栈相对于数组来讲效率会较差。不过还可以使用下面这种方法进行改进，就可已达到更好的效果，不适用split的方法，而是直接遍历字符串进行操作：

    //96.5%
    public String simplifyPath1(String path) {
        int len = path.length();
        Deque<String> stack = new ArrayDeque<>();
        for (int i = 0; i < len; ) {
            char c = path.charAt(i);
            if (c == '/') { ++i; }  // skip the separator '/'
            else if (c == '.') {
                int j = i + 1;
                while (j < len && path.charAt(j) != '/') { ++j; }
                if (j - i == 2 && path.charAt(i + 1) == '.' && !stack.isEmpty()) {  // go up to parent directory
                    stack.removeLast();
                } else if (j - i > 2) {
                    stack.addLast(path.substring(i, j));  // go down to child directory
                }
                i = j;
            } else {
                int j = i + 1;
                while (j < len && path.charAt(j) != '/') { ++j; }
                stack.addLast(path.substring(i, j));  // go down to child directory
                i = j;
            }
        }
        StringBuilder ans = new StringBuilder();
        for (String dir: stack) { ans.append('/').append(dir); }
        if (ans.length() == 0) { return "/"; }
        return ans.toString();
    }