LeetCode(27) -- 682, 686

P682. Baseball Game (Easy)

棒球比赛记分。“+” 代表前两个有效得分的和。“D”前一个有效得分的二倍。“C”代表上一个得分无效。

我的思路

按照规则随时修改数据。

我的代码

public class E_682_BaseballGame {
    public int calPoints(String[] ops) {
        int sum = 0;
        for (int i = 0; i < ops.length; i++) {
            if (ops[i].equals("C")) {
                int j = i - 1;
                while (j >= 0 && (ops[j] == null || ops[j].equals("C"))) {
                    j--;
                }
                if (j >= 0) {
                    sum -= Integer.parseInt(ops[j]);
                    ops[j] = null;
                }
            } else if (ops[i].equals("D")) {
                int j = i - 1;
                while (j >= 0 && (ops[j] == null || ops[j].equals("C"))) {
                    j--;
                }
                if (j >= 0) {
                    ops[i] = String.valueOf(Integer.parseInt(ops[j]) * 2);
                    sum += Integer.parseInt(ops[i]);
                }
            } else if (ops[i].equals("+")) {
                int j = i - 1;
                int twoSum = 0;
                while (j >= 0 && (ops[j] == null || ops[j].equals("C"))) {
                    j--;
                }
                if (j >= 0) {
                    twoSum = Integer.parseInt(ops[j]);
                    j--;
                }
                while (j >= 0 && (ops[j] == null || ops[j].equals("C"))) {
                    j--;
                }
                if (j >= 0) {
                    twoSum += Integer.parseInt(ops[j]);
                    ops[i] = String.valueOf(twoSum);
                }
                sum += twoSum;
            } else {
                sum += Integer.parseInt(ops[i]);
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        String[] test = {"5","2","C","D","+"};
        new E_682_BaseballGame().calPoints(test);
    }
}

94%

最优解

class Solution {
    public int calPoints(String[] o) {
        int l=0;
        int t=0;
        int a[]=new int[o.length];
        for(int i=0;i<o.length;i++)
        {
            String s=o[i];
            if(s.equals("+"))
            {
                a[l]=a[l-1]+a[l-2];
                t+=a[l];
                l++;
            }
            else if(s.equals("D"))
            {
                a[l]=a[l-1]*2;
                t+=a[l];
                l++;
            }
            else if(s.equals("C"))
            {
                t-=a[l-1];
                l--;
                a[l]=0;
                //l--;
            }
            else
            {
                int n=Integer.parseInt(s);
                a[l]=n;
                t+=a[l];
                l++;
            }
        }
        return t;
    }
}

这个代码比我的简洁很多。主要是把特殊字符去掉后，不用再往前去找了。直接用INDEX减1减2就找到了。

新开了一个数组，把所有的“C”都忽视掉，把C前面的改成0。不过我觉得这样有BUG，如果两个连续的C怎么办。可能测试中没有这种特殊情况。

P686. Repeated String Match (Easy)

两个字符串A,B。A重复几次后，B可能变成A的子字符串。问至少重复几次，B才是A的子字符串？如果无论怎么重复都不满足条件，就返回-1。

我的思路

A的长度至少要大于等于B，B才有可能是子字符串。所以我先把A拼接成一个长度大于等于B的字符串。然后如果不行，再多接一个A，再给一次机会。如果B仍然不是子字符串，那再接上几个A都没用了。

我的代码

public class E_686_RepeatedStringMatch {
    public int repeatedStringMatch(String A, String B) {
        StringBuilder sb = new StringBuilder(A);
        int count = 1;
        while (sb.length() < B.length()) {
            sb.append(A);
            count++;
        }
        if (sb.indexOf(B) >= 0) {
            return count;
        } else {
            sb.append(A);
            count++;
        }
        if (sb.indexOf(B) >= 0) {
            return count;
        }
        return -1;
    }
}

67%

最优解

class Solution {
    public int repeatedStringMatch(String search, String str) {
        int slength = search.length();
        int repeatcount = 0;
        int hlength = -1, tPos = -1;
        int scanPos = 0;
        int hplus = 0, tplus = 0;

        while (true) {
            int pos = str.indexOf(search, scanPos);
            if (pos < 0) {
                tPos = scanPos;
                break;
            }

            if (scanPos != 0) {// not the first round
                if (pos != scanPos)// extra char found in middle?
                    return -1;
            }

            repeatcount++;

            if (hlength == -1)
                hlength = pos;

            scanPos = pos + slength;

            if (scanPos >= str.length())
                break;

        }
        if (hlength == -1) {//can not search A in B like abc in bcab, abc in ab
            if (search.contains(str))
                return 1;
            if ((search + search).contains(str))
                return 2;
            return -1;
        }
        if (hlength == 0) {
            hplus = 0;
        } else {
            if (!search.endsWith(str.substring(0, hlength)))
                return -1;
            hplus = 1;
        }
        if (tPos == -1) {//exact end with tail
            tplus = 0;
        } else {
            if (!search.startsWith(str.substring(tPos)))
                return -1;
            tplus = 1;
        }
        return repeatcount + hplus + tplus;
    }
}

P687. Longest Univalue Path (Easy)

二叉树，找出最长的所有值都相同的路径。注意是边的个数，不是节点的个数。

我的思路

答案

int ans = 0;
    public int longestUnivaluePath(TreeNode root) {
        ans = 0;
        arrowLength(root);
        return ans;
    }

    public int arrowLength(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = arrowLength(node.left);
        int right = arrowLength(node.right);
        int leftArrow = 0, rightArrow = 0;
        if (node.left != null && node.left.val == node.val) {
            leftArrow += left + 1;
        }
        if (node.right != null && node.right.val == node.val) {
            rightArrow += right + 1;
        }
        ans = Math.max(ans, leftArrow + rightArrow);
        return Math.max(leftArrow, rightArrow);
    }

最优解

class Solution {
    int max = 0;
    public int longestUnivaluePath(TreeNode root) {
        if(root!=null){
            longestPathValue(root);
        }
        return max;
    }

    public int longestPathValue(TreeNode root){
        if(root.left == null && root.right == null){
            return 0;
        }
        int leftCount = 0;
        int rightCount = 0;
        if(root.left != null){
            leftCount = longestPathValue(root.left);
            if(root.val == root.left.val){
                leftCount = leftCount + 1;
            }else{
                leftCount = 0;
            }
        }

        if(root.right != null){
            rightCount = longestPathValue(root.right);
            if(root.val == root.right.val){
                rightCount = rightCount  + 1;
            }else{
                rightCount = 0;
            }
        }

        if(max<(rightCount + leftCount)){
            max = rightCount + leftCount;
        }
        if (rightCount > leftCount)
            return rightCount;
        else
            return leftCount;
    }
}