LeetCode(18) -- 521, 551, 558

P521. Longest Uncommon Subsequence I (Easy)

两个String，找出最长的非共同的子序列。子序列可以不是连续的。

我的思路

找共同的子序列是用的动态规划。但没有具体实现过。没思路，看答案。

答案

public class Solution {
    public int findLUSlength(String a, String b) {
        if (a.equals(b))
            return -1;
        return Math.max(a.length(), b.length());
    }
}

• a=b. If both the strings are identical, it is obvious that no subsequence will be uncommon. Hence, return -1.
• length(a)=length(b) and a != b. Example: abc and abd. In this case we can consider any string i.e. abc or abd as a required subsequence, as out of these two strings one string will never be a subsequence of other string. Hence, return length(a) or length(b).
• length(a) != length(b). Example abcd and abc. In this case we can consider bigger string as a required subsequence because bigger string can’t be a subsequence of smaller string. Hence, return max(length(a),length(b)).

分析得有点蛋疼。。。

P551. Student Attendance Record I (Easy)

给一个字符串表示学生出勤记录。A表示缺勤，L表示迟到，P表示出勤。学生可以获得奖励，如果不包含多于一个缺勤或者多于两个连续的迟到。

我的思路

一开始想计数，其实用String的一些方法就可以了。

我的代码

public class E_551_StudentAttendanceRecordI {
    public boolean checkRecord(String s) {
        if (s.contains("LLL")) {
            return false;
        }
        if (s.indexOf("A") != s.lastIndexOf("A")) {
            return false;
        }
        return true;
    }
}

最优解

class Solution {
    public boolean checkRecord(String s) {
        int a = 0,l = 0;

        for(char ch : s.toCharArray()){
            if(ch=='A'){
                a++;
                if(a>1){
                    return false;
                }
                l = 0;
            }
            else if (ch =='L'){
                l++;
                if(l>2){
                    return false;
                }

            }
            else{
                l =0;
            }
        }
        return true;
    }
}

这个跟我一开始的代码差不多。

P558. Quad Tree Intersection (Easy)

四象树，求”OR”运算

A:                 B:                 C (A or B):
+-------+-------+  +-------+---+---+  +-------+-------+
|       |       |  |       | F | F |  |       |       |
|   T   |   T   |  |   T   +---+---+  |   T   |   T   |
|       |       |  |       | T | T |  |       |       |
+-------+-------+  +-------+---+---+  +-------+-------+
|       |       |  |       |       |  |       |       |
|   F   |   F   |  |   T   |   F   |  |   T   |   F   |
|       |       |  |       |       |  |       |       |
+-------+-------+  +-------+-------+  +-------+-------+

我的思路

跟一般的树一样做递归，但不知道这个如果一个是树是叶节点，另一个不是，那应该返回什么。

我的代码

class Solution {
    public Node intersect(Node quadTree1, Node quadTree2) {
        if (quadTree1.isLeaf && quadTree2.isLeaf) {
            return new Node(quadTree1.val || quadTree2.val,
                    true,null,null,null,null) ;
        }
        if (quadTree1.isLeaf) {
            return new Node(quadTree1.val,
                    true,null,null,null,null) ;
        }
        if (quadTree2.isLeaf) {
            return new Node(quadTree2.val,
                    true,null,null,null,null) ;
        }
        Node res = new Node();
        res.bottomLeft = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
        res.bottomRight = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
        res.topLeft = intersect(quadTree1.topLeft, quadTree2.topLeft);
        res.topRight = intersect(quadTree1.topRight,quadTree2.topRight);
        return res;
    }
}

结果是错误的。不知道为什么

讨论区

public class E_558_QuadTreeIntersection {
    public Node intersect(Node quadTree1, Node quadTree2) {
        if (quadTree1.isLeaf) {
            return quadTree1.val ? quadTree1 : quadTree2;
        } else if (quadTree2.isLeaf) {
            return quadTree2.val ? quadTree2 : quadTree1;
        }
        Node bl = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
        Node br = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
        Node tl = intersect(quadTree1.topLeft, quadTree2.topLeft);
        Node tr = intersect(quadTree1.topRight,quadTree2.topRight);
        if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf && tl.val == tr.val && bl.val == br.val && tl.val == bl.val) {
            return new Node(tl.val, true, null, null, null, null);
        } else {
            return new Node(false, false, tl, tr, bl, br);
        }
    }
}

100%

如果第一个树是叶节点，就看它是不是true。如果是true，就直接返回，否则返回第二个树。 然后递归出四个子节点。如果它们全是叶节点，并且值都相等，就以它们的共同的val作为值，返回一个新树。 否则的话就默认为false，返回一个新树。