7.3号刷题

发表于 | 分类于 | 0 comments

第一题 551. Student Attendance Record I

题目描述

给定一个字符串s，若其中的’A’大于1个，或者出现连续的3个或3个以上’L’，返回False，否则返回True

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public boolean checkRecord(String s) {
        int Ab = 0;
        if (s.length() < 2) return true;
        for (int i = 0; i < 2; i++) {
            if (s.charAt(i) == 'A') Ab++;
            if (Ab > 1) return false;
        }
        
        for (int i = 2; i < s.length(); i++) {
            if (s.charAt(i) == 'A') {
                Ab++;
                if (Ab > 1) return false;
            } else if (s.charAt(i) == 'L') {
                if (s.charAt(i - 1) == 'L' && s.charAt(i - 2) == 'L') return false;
            }
        }
        return true;       
    }
}

第二题 552. Student Attendance Record II

题目描述

字符串由’A’, ‘L’, ‘P’三种字符构成，若其中包含的’A’不超过1个，并且不包含连续的3个或3个以上’L’，则称该字符串有效。

给定正整数n，返回长度为n的“有效字符串”的个数。

由于结果可能会很大，对1e9 + 7取模。

注意：n的值不超过100,000

算法

详情见链接

非常好的一道题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class checkRecord552 {
    static final int m = 1000000007;
    public int checkRecord(int n) {
        if (n == 0) return 0;
        int k = 0;
        if (n > 3) k = n;
        else k = 3;
        long[] P = new long[k];  //end with P
        long[] A = new long[k];  //end with A
        long[] L = new long[k];  //end with L
        //initial
        P[0] = 1; L[0] = 1; A[0] = 1;
        P[1] = 3; L[1] = 3; A[1] = 2; A[2] = 4;
        for (int i = 2; i < n; i++) {
            P[i] = A[i - 1] + L[i - 1] + P[i - 1];
            P[i] %= m;
            L[i] = A[i - 1] + P[i - 1] + A[i - 2] + P[i - 2];
            L[i] %= m;
            if (i > 2) {
                A[i] = A[i - 1] + A[i - 2] + A[i - 3];
                A[i] %= m;
            }
        }
        return (int) ((P[n - 1] + A[n - 1] + L[n - 1]) % m);
    }
}

第三题 583. Delete Operation for Two Strings

题目描述

给定单词word1和word2，从word1和/或word2中删去一些字符，使得word1和word2相同，求最少删除的字符数。

注意：

单词长度不超过500
单词只包含小写字母

算法

利用动态规划的原理求最长的公共序列

求最长的公共SubSequence
对于word1，我们现在处于i位置。
对于word2，我们处于j位置。
dp[i][j]表示word1长度为0~i，word2长度为0~j的String，他们的最大公共长度。
如果 char(i) == char(j)，那么他们的最大公共长度为dp[i-1][j-1]，即他们上一个的最大公共长度加1。
如果char(i) != char(j), 那么长度为Max(dp[i-1][j], dp[i][j-1])即之前的对于0~i-1,0~j或0~i,0~j-1的最大的子集
由此可以写出循环，解决此问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class minDistance583 {
    public int minDistance(String word1, String word2) {
        if (word1.isEmpty() || word2.isEmpty()) return word1.length() + word2.length();
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < word1.length() + 1; i++) {
            for (int j = 0; j < word2.length() + 1; j++) {
                if (i == 0 || j == 0) dp[i][j] = 0;
                else {
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
        }
        return word1.length() + word2.length() - 2 * dp[word1.length()][word2.length()];
    }
}
求最短的能使两个Array相同的路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int minDistance(String word1, String word2) {
        if (word1.isEmpty() || word2.isEmpty()) return word1.length() + word2.length();
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;
        for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;
        for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 2);
                }
            }
        }
        return dp[word1.length()][word2.length()];       
    }
}

第四题 72. Edit Distance

题目描述

有两个String, 现在我们有replace, insert, delete 三种方法。求让两个String相同的最短操作数

算法

与上一题相似，都是求让两个String一步步相同，然后再查看最小的情况

二维矩阵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class minDistance72 {
    public int minDistance(String word1, String word2) {
        if (word1.isEmpty() || word2.isEmpty()) return word1.length() + word2.length();
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;
        for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;
        for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}
一维矩阵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int minDistance(String word1, String word2) {
        if (word1.isEmpty() || word2.isEmpty()) return word1.length() + word2.length();
        int[] dp = new int[word1.length() + 1];
        for (int i = 0; i < word1.length() + 1; i++) dp[i] = i;
        for (int j = 1; j < word2.length() + 1; j++) {
            int pre = dp[0];
            dp[0] = j;
            for (int i = 1; i < word1.length() + 1; i++) {
                int temp = dp[i];
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i] = pre;
                } else {
                    dp[i] = Math.min(Math.min(pre + 1, dp[i] + 1), dp[i - 1] + 1);
                }
                pre = temp;
            }
        }
        return dp[word1.length()];       
    }
}

第五题 161. One Edit Distance

题目描述

检查两个String是否可以通过一次修改就可以得到

算法

只有三种情况

* 1) Replace 1 char:
s: a B c
t: a D c
* 2) Delete 1 char from s: 
s: a D  b c
t: a    b c
* 3) Delete 1 char from t
s: a   b c
t: a D b c

Insert可以看做delete的一种形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class isOneEditDistance161 {
    public boolean isOneEditDistance(String s, String t) {
        if (Math.abs(s.length() - t.length()) > 1) return false;
        for (int i = 0; i < Math.min(s.length(), t.length()); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (s.length() == t.length()) {
                    return s.substring(i + 1).equals(t.substring(i + 1));
                }
                else if (s.length() > t.length()) {
                    return s.substring(i + 1).equals(t.substring(i));
                }
                else return s.substring(i).equals(t.substring(i + 1));
            }
        }
        return Math.abs(s.length() - t.length()) == 1;
    }
}

第六题 28. Implement strStr()

题目描述

找寻在String1 里，是否存在String2，并返回第一个String2的标号

算法

1
2
3
4
5
6
7
8
9
10
11
public class strStr28 {
    public int strStr(String haystack, String needle) {
        for (int i = 0; ; i++) {
            for (int j = 0; ;j++) {
                if (j == needle.length()) return i;
                if (i + j >= haystack.length()) return -1;
                if (needle.charAt(j) != haystack.charAt(i + j)) break;
            }
        }
    }
}

第七题 459. Repeated Substring Pattern

题目描述

给定一个非空字符串，判断它是否可以通过自身的子串重复若干次构成。你可以假设字符串只包含小写英文字母，并且长度不会超过10000

算法

如果能够复制，首先必须满足重复的要求，必须有重复的字母出现，找到首次出现的重复字母。对整个String进行查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class repeatedSubstringPattern459 {
    public boolean repeatedSubstringPattern(String s) {
        int[] store = new int[26];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (sb.length() > s.length() - sb.length()) break;
            char c = s.charAt(i);
            int index = 'z' - c;
            store[index]++;
            if (store[index] >= 2) {
                if (s.length() % sb.length() == 0) {
                    int k = i;
                    while (k < s.length()) {
                        if (s.substring(k, k + sb.length()).equals(sb.toString())) {
                            k += sb.length();
                        } else break;
                    }
                    if (k == s.length()) return true;
                }
            }
            sb.append(c);
        }
        return false;
    }
}

第八题 536. Construct Binary Tree from String

题目描述

根据字符串重构二叉树。

输入包含数字和括号，数字代表根节点，括号内的子串代表左、右孩子。

注意：

输入字符串只包含’(‘, ‘)，’-‘和数字’0’-‘9’

算法

利用回溯，将String进行切割，并返回答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode str2tree(String s) {
        if (s == null || s.length() == 0) return null;
        int firstLeft = s.indexOf("(");
        int val = firstLeft == -1 ? Integer.valueOf(s) : Integer.valueOf(s.substring(0, firstLeft));
        TreeNode cur = new TreeNode(val);
        if (firstLeft == -1) return cur; //no Left and no Right
        
        int start = firstLeft, count = 0;
        for (int i = firstLeft; i < s.length(); i++) {
            if (s.charAt(i) == '(') count++;
            else if (s.charAt(i) == ')') count--;
            
            //Left
            if (count == 0 && start == firstLeft) {
                cur.left = str2tree(s.substring(start + 1, i));
                start = i + 1;
            }//Right
            else if (count == 0) {
                cur.right = str2tree(s.substring(start + 1, i));
            }
        }
        return cur;        
    }
}