发表于 | 分类于

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1
2
3
4
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

解法1：

诀窍在于dp[i][j] 表示以(i,j)为底的正方形的边长。
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1, if matrix[i][j] == 1,
画一下图就比较清楚。
C++

1

Java

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
37
38
39
40
41
42
public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = matrix[0][0] - '0' == 1 ? 1 : 0;
        int res = dp[0][0];    // record the final result
        for (int j = 1; j < col; j++) {
            if (matrix[0][j] - '0' == 1) {
                dp[0][j] = 1;
                res = 1;
            }
        }
        for (int i = 1; i < row; i++) {
            if (matrix[i][0] - '0' == 1) {
                dp[i][0] = 1;
                res = 1;
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] - '0' == 0) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]),dp[i - 1][j - 1]) + 1;
                }
                res = Math.max(res, dp[i][j] * dp[i][j]);
            }
        }
        return res;        
    }
}

发表于 | 分类于

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

解法1：

C++

1

Java

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
public class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int i = 0, j = 0, k = 0;
        int d1 = 2, d2 = 3, d3 = 5;
        int count = 1;
        for (int p = 1; p < n; p++) {
            int res = Math.min(Math.min(d1, d2), d3);
            dp[p] = res;
            if (d1 == res) {
                d1 = 2 * dp[++i];
            }
            if (d2 == res) {
                d2 = 3 * dp[++j];
            }
            if (d3 == res) {
                d3 = 5 * dp[++k];
            }
        }
        return dp[n - 1];
    }
}

发表于 | 分类于

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

解法1：O(N*K) Time

N是房子的数量，K是房子的颜色数。
经典dp, dp[i][j] 表示前i个房子的最小cost,当第i个房子涂得颜色是j。
C++

1

Java

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
public class Solution {
    public int minCost(int[][] costs) {
        if (costs.length == 0 || costs[0].length == 0) {
            return 0;
        }
        int n = costs.length;
        int col = costs[0].length;
        int[][] dp = new int[n][col];   // first i houses painted and ith house painted with jth color
        for (int j = 0; j < col;j++) {
            dp[0][j] = costs[0][j];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < col; j++) {
                int temp = Integer.MAX_VALUE;
                for (int k = 0; k < col; k++) {
                    if (k != j) {
                        temp = Math.min(temp, dp[i - 1][k]);    
                    }
                }
                dp[i][j] = costs[i][j] + temp;
            }
        }
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < col; j++) {
            res = Math.min(res, dp[n - 1][j]);
        }
        return res;
    }
}

发表于 | 分类于

Given a string representing a code snippet, you need to implement a tag validator to parse the code and return whether it is valid. A code snippet is valid if all the following rules hold:

The code must be wrapped in a valid closed tag. Otherwise, the code is invalid.
A closed tag (not necessarily valid) has exactly the following format : <TAG_NAME>TAG_CONTENT</TAG_NAME>. Among them, <TAG_NAME> is the start tag, and </TAG_NAME> is the end tag. The TAG_NAME in start and end tags should be the same. A closed tag is valid if and only if the TAG_NAME and TAG_CONTENT are valid.
A valid TAG_NAME only contain upper-case letters, and has length in range [1,9]. Otherwise, the TAG_NAME is invalid.
A valid TAG_CONTENT may contain other valid closed tags, cdata and any characters (see note1) EXCEPT unmatched <, unmatched start and end tag, and unmatched or closed tags with invalid TAG_NAME. Otherwise, the TAG_CONTENT is invalid.
A start tag is unmatched if no end tag exists with the same TAG_NAME, and vice versa. However, you also need to consider the issue of unbalanced when tags are nested.
A < is unmatched if you cannot find a subsequent >. And when you find a < or </, all the subsequent characters until the next > should be parsed as TAG_NAME (not necessarily valid).
The cdata has the following format : <![CDATA[CDATA_CONTENT]]>. The range of CDATA_CONTENT is defined as the characters between <![CDATA[ and the first subsequent ]]>.
CDATA_CONTENT may contain any characters. The function of cdata is to forbid the validator to parse CDATA_CONTENT, so even it has some characters that can be parsed as tag (no matter valid or invalid), you should treat it as regular characters.

Valid Code Examples:

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
37
38
Input: "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: True
Explanation:
The code is wrapped in a closed tag : <DIV> and </DIV>.
The TAG_NAME is valid, the TAG_CONTENT consists of some characters and cdata.
Although CDATA_CONTENT has unmatched start tag with invalid TAG_NAME, it should be considered as plain text, not parsed as tag.
So TAG_CONTENT is valid, and then the code is valid. Thus return true.
Input: "<DIV>>>  ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>"
Output: True
Explanation:
We first separate the code into : start_tag|tag_content|end_tag.
start_tag -> "<DIV>"
end_tag -> "</DIV>"
tag_content could also be separated into : text1|cdata|text2.
text1 -> ">>  ![cdata[]] "
cdata -> "<![CDATA[<div>]>]]>", where the CDATA_CONTENT is "<div>]>"
text2 -> "]]>>]"
The reason why start_tag is NOT "<DIV>>>" is because of the rule 6.
The reason why cdata is NOT "<![CDATA[<div>]>]]>]]>" is because of the rule 7.

Invalid Code Examples:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Input: "<A>  <B> </A>   </B>"
Output: False
Explanation: Unbalanced. If "<A>" is closed, then "<B>" must be unmatched, and vice versa.
Input: "<DIV>  div tag is not closed  <DIV>"
Output: False
Input: "<DIV>  unmatched <  </DIV>"
Output: False
Input: "<DIV> closed tags with invalid tag name  <b>123</b> </DIV>"
Output: False
Input: "<DIV> unmatched tags with invalid tag name  </1234567890> and <CDATA[[]]>  </DIV>"
Output: False
Input: "<DIV>  unmatched start tag <B>  and unmatched end tag </C>  </DIV>"
Output: False

Note:

For simplicity, you could assume the input code (including the any characters mentioned above) only contain letters, digits, '<','>','/','!','[',']' and ' '.

解法1：

此题比较繁琐，题目也巨长。实际上并不是很难。
主要要先总结一下要求：
字符串一定是以tag开头和结尾
tag的名字要符合：　
１．　１－　９个字符之内
２．　只能是upper case letters
３．　需要两两配对
４．　<!出现的话一定需要match ＣＤＡＴＡ

然后对于每一个tag,用一个stack去记录上一个tag的顺序即可。

C++

1

Java

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
public class Solution {
    public boolean isValid(String code) {
        // It should start with < and end with >
        if (code == null || code.length() == 0) {
            return false;
        }
        if (code.charAt(0) != '<' || code.charAt(code.length() - 1) != '>') {
            return false;
        }
        Stack<String> stack = new Stack<String>();
        boolean tagExist = false;
        for (int i = 0; i < code.length(); i++) {
            if (stack.isEmpty() && tagExist) {
                return false;
            }
            int last = -1;
            if (code.charAt(i) == '<') {
                if (!stack.isEmpty() && code.charAt(i + 1) == '!') {
                    last = code.indexOf("]]>", i + 1);
                    if (last == -1 || !isValidCdata(code.substring(i + 2, last))) {
                        return false;
                    }
                } else {
                    boolean close = false;
                    if (code.charAt(i + 1) == '/') {
                        close = true;
                        i++;
                    }
                    last = code.indexOf(">", i+1);
                    if (last == -1 || !isValidTagName(code.substring(i + 1, last))) {
                        return false;
                    }
                    if (close) {
                        if (stack.isEmpty() || !stack.peek().equals(code.substring(i + 1, last))) {
                            return false;
                        } else {
                            stack.pop();
                        }
                    } else {
                        tagExist = true;
                        stack.push(code.substring(i + 1, last));
                    }
                }
                i = last;   // move i to the end of the tag
            }
        }
        return stack.isEmpty() && tagExist;
    }
    private boolean isValidCdata(String content) {
        int tag = content.indexOf("[CDATA[");
        return tag == 0;
    }
    private boolean isValidTagName(String tag) {
        int len = tag.length();
        if (len < 1 || len > 9) {
            return false;
        }
        for (int i = 0; i < len; i++) {
            if (tag.charAt(i) < 'A' || tag.charAt(i) > 'Z') {
                return false;
            }
        }
        return true;
    }
}

发表于 | 分类于

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

解法1：DP　O(N) Time + O(N) Space

此题有多种解法。DP只是其中一种。
只有在碰到)的时候才需要去计算当前配对括号长度。
状态方程的解释是：
如果在)之前的符号是(，那么最长的合法字符串长度就是(之前的合法长度＋２
如果之前的符号是), dp[i - 1]代表了如果i - 1结尾的合法的最长长度，那么如果在dp[i - 1]之前的那个字符是（，
当前的合法长度就可以等于dp[i - 1] + dp[i - dp[i - 1] - 2]　＋　２
由此可以写出状态方程。

C++

1

Java

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
public class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] dp = new int[s.length()];
        int res = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;  // add () to dp[i - 2]
                } else if (s.charAt(i - 1) == ')') {
                    if (i - dp[i -1] >= 1 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;    
                    }
                }
                res = Math.max(dp[i], res);
            }
        }
        return res;
    }
}

发表于 | 分类于

Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.

A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.

The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn’t exist, return -1.

Example 1:

1
2
Input: "aba", "cdc", "eae"
Output: 3

Note:

All the given strings’ lengths will not exceed 10.
The length of the given list will be in the range of [2, 50].

解法1：O(N^2 * X)

x is the average length of strings. N is the number of strings
这题的关键在于substring的定义要注意，和平时遇到的substring定义不同。
这里的substring是可以提取不连续的字符组成。
分析一下可以发现，如果存在答案的话，那么uncommon subsequence 一定是其中某一个string，那么就把每一个string和其他的相比，看是否为其他的substring，如果不是，那么更新最大值。

C++

1

Java

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
public class Solution {
    public int findLUSlength(String[] strs) {
        int j = 0;
        int res = -1;
        for (int i = 0; i < strs.length; i++) {
            for (j = 0; j < strs.length; j++) {
                if (j != i) {
                    if (isSubString(strs[i], strs[j])) {
                        break;
                    }
                }
            }
            if (j == strs.length) {
                res = Math.max(res, strs[i].length());
            }
        }
        return res;
    }
    private boolean isSubString(String x, String y) {
        // By definition, the substring can be derived by deleting some characters
        int j = 0;
        for (int i = 0; i < y.length() && j < x.length(); i++)
            if (x.charAt(j) == y.charAt(i))
                j++;
        return j == x.length();
    }
}

发表于 | 分类于

Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.

Example 1:

Input: [“23:59”,”00:00”]
Output: 1

Note:

The number of time points in the given list is at least 2 and won't exceed 20000.
The input time is legal and ranges from 00:00 to 23:59.

解法1： O(NlogN)

很直观的就是把array转化为分钟数的数组，然后两两比较，同时别忘了比较头和尾巴。

C++

1

Java

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 Solution {
    public int findMinDifference(List<String> timePoints) {
        if (timePoints == null || timePoints.size() == 0) {
            return 0;
        }
        int[] times = new int[timePoints.size()];
        for (int i = 0; i < timePoints.size(); i++) {
            int seperator = timePoints.get(i).indexOf(":");
            int hour = Integer.parseInt(timePoints.get(i).substring(0, seperator));
            int minute = Integer.parseInt(timePoints.get(i).substring(seperator + 1));
            times[i] = hour * 60 + minute;
        }
        Arrays.sort(times);
        int res = Integer.MAX_VALUE;
        int time24 = 24 * 60;
        for (int i = 0; i < times.length - 1; i++) {
            res = Math.min(res, Math.min(Math.abs(time24 + times[i] - times[i + 1]), Math.abs(times[i+1] - times[i])));
        }
        res = Math.min(res, Math.min(Math.abs(time24 + times[0] - times[times.length - 1]), Math.abs(times[0] - times[times.length - 1])));
        return res;
    }
}

解法2： O(N)

借鉴了bucket sort 的解法，因为这里分钟数的总个数是固定的。可以用一个60 * 24 = 1440的数组来记录每一个分钟数是否出现。
如果一个分钟数出现两次，那么最小值一定是0.
同时需要维护一个first和last来记录第一个和最后一个出现过的分钟数。
最后比较一下相邻出现过的分钟数以及头尾就可以了。
Java

1

发表于 | 分类于

Given a list of strings, you could concatenate these strings together into a loop, where for each string you could choose to reverse it or not. Among all the possible loops, you need to find the lexicographically biggest string after cutting the loop, which will make the looped string into a regular one.

Specifically, to find the lexicographically biggest string, you need to experience two phases:

Concatenate all the strings into a loop, where you can reverse some strings or not and connect them in the same order as given.
Cut and make one breakpoint in any place of the loop, which will make the looped string into a regular one starting from the character at the cutpoint.

And your job is to find the lexicographically biggest one among all the possible regular strings.

Example:

Input: “abc”, “xyz”
Output: “zyxcba”
Explanation: You can get the looped string “-abcxyz-“, “-abczyx-“, “-cbaxyz-“, “-cbazyx-“,
where ‘-‘ represents the looped status.
The answer string came from the fourth looped one,
where you could cut from the middle character ‘a’ and get “zyxcba”.

Note:

The input strings will only contain lowercase letters.
The total length of all the strings will not over 1,000.

解法1：O(N^2)　

此题参考了leetcode的解法：

order to understand how this solution works, firstly we'll look at some of the properties of the transformation involved. The first point to note is that the relative ordering of the strings doesn't change after applying the transformations(i.e. reversing and applying cuts).
1
2
3
4
5
6
7
8
9
10
The second property will be explained taking the help of an example. Consider the given list of strings: [s1,s2,s3,..,sj,..sn][s_1, s_2, s_3,..,s_j,..s_n][s​1​​,s​2​​,s​3​​,..,s​j​​,..s​n​​]. Now, assume that we choose sjs_js​j​​ to be the string on which the current cut is placed leading to the formation of two substrings from sjs_js​j​​, namely, say sjpres_{jpre}s​jpre​​, sjposts_{jpost}s​jpost​​. Thus, the concatenated string formed by such a cut will be: [sjpost,sj+1,...,sn,s1rev,s2rev,..,s(jpre)rev][s_{jpost}, s_{j+1},..., s_n, s_{1rev}, s_{2rev},.., s_{(jpre)rev}][s​jpost​​,s​j+1​​,...,s​n​​,s​1rev​​,s​2rev​​,..,s​(jpre)rev​​]. Here, sirevs_{irev}s​irev​​ means the reversed sis_is​i​​ string.
The concatenated string formed follows the same pattern irrespective of where the cut is placed in sjs_js​j​​. But still, the relative ordering of the strings persists, even if we include the reverse operation as well.
Now, if we consider only a single cut for the time being, in string sjs_js​j​​(not reversed) as discussed above, and allow for the reverse operation among the remaining strings, the lexicographically largest concatenated string will be given by: [sjpost,max(sj+1,s(j+1)rev),...,max(sn,s(n)rev),max(s1,s(1)rev),...,s(jpre)rev][s_{jpost}, \text{max}(s_{j+1},s_{(j+1)rev}) ,..., \text{max}(s_{n},s_{(n)rev}), \text{max}(s_{1},s_{(1)rev}), ..., s_{(jpre)rev}][s​jpost​​,max(s​j+1​​,s​(j+1)rev​​),...,max(s​n​​,s​(n)rev​​),max(s​1​​,s​(1)rev​​),...,s​(jpre)rev​​]. Here, max\text{max}max refers to the lexicographic maximum operation.
Thus, if a particular string sjs_js​j​​ is finalized for the cut, the largest lexicographic concatenated string is dependent only on whether the string sjs_js​j​​ is reversed or not, and also on the position of the cut. This happens because the reverse/not reverse operation for the rest of the strings is fixed for a chosen sjs_js​j​​ as shown above and thus, doesn't impact the final result.
Based on the above observations, we follow the given procedure. For every given string, we replace the string with the lexicographically larger string out of the original string and the reversed one. After this, we pick up every new string(chosen as the string on which the cuts will be applied), and apply a cut at all the positions of the currently picked string and form the full concantenated string keeping the rest of the newly formed strings intact. We also reverse the current string and follow the same process. While doing this, we keep a track of the largest lexicographic string found so far.

C++

1

Java

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
37
38
public class Solution {
    public String splitLoopedString(String[] strs) {
        for (int i = 0; i < strs.length; i++) {
            String rev = new StringBuilder(strs[i]).reverse().toString();
            if (strs[i].compareTo(rev) < 0) {
                strs[i] = rev;
            }
        }
        String res = "";    // store results
        for (int i = 0; i < strs.length; i++) {
            String rev = new StringBuilder(strs[i]).reverse().toString();
            for (String str : new String[] {strs[i], rev}) {
                for (int k = 0; k < str.length(); k++) {
                    // get the head
                    StringBuilder builder = new StringBuilder(str.substring(k));
                    // append i + 1 to n strings
                    for (int j = i + 1; j < strs.length; j++) {
                        builder.append(strs[j]);
                    }
                    // append 0 to i -1 strings
                    for (int j = 0; j < i; j++) {
                        builder.append(strs[j]);
                    }
                    builder.append(str.substring(0, k));
                    if (builder.toString().compareTo(res) > 0) {
                        // lexi order
                        res = builder.toString();
                    }
                }
            }
        }
        return res;
    }
}

发表于 | 分类于

Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms of their paths.

A group of duplicate files consists of at least two files that have exactly the same content.

A single directory info string in the input list has the following format:

“root/d1/d2/…/dm f1.txt(f1_content) f2.txt(f2_content) … fn.txt(fn_content)”

It means there are n files (f1.txt, f2.txt … fn.txt with content f1_content, f2_content … fn_content, respectively) in directory root/d1/d2/…/dm. Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.

The output is a list of group of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:

“directory_path/file_name.txt”

Example 1:

1
2
3
4
Input:
["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]
Output:  
[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

Note:

No order is required for the final output.
You may assume the directory name, file name and file content only has letters and digits, and the length of file content is in the range of [1,50].
The number of files given is in the range of [1,20000].
You may assume no files or directories share the same name in the same directory.
You may assume each given directory info represents a unique directory. Directory path and file info are separated by a single blank space.

Follow-up beyond contest:

Imagine you are given a real file system, how will you search files? DFS or BFS?
If the file content is very large (GB level), how will you modify your solution?
If you can only read the file by 1kb each time, how will you modify your solution?
What is the time complexity of your modified solution? What is the most time-consuming part and memory consuming part of it? How to optimize?
How to make sure the duplicated files you find are not false positive?

解法1：

没有难点，就是按部就班的把这个paths转换成为hashmap, 以content作为key.
C++

1

Java

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
public class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        HashMap<String, List<String>> map = new HashMap<String, List<String>>();
        for (String path : paths) {
            String[] temp = path.split(" ");
            String path_root = temp[0] + "/";
            for (int i = 1; i < temp.length; i++) {
                // seperate contents from string
                int leftBracket = temp[i].indexOf("(");
                String fileName = temp[i].substring(0, leftBracket);
                String content = temp[i].substring(leftBracket + 1, temp[i].length() - 1);  // get rid of the last bracket in the string
                String fullFileName = path_root + fileName;
                if (map.containsKey(content)) {
                    map.get(content).add(fullFileName);
                } else {
                    List<String> files = new ArrayList<String>();
                    files.add(fullFileName);
                    map.put(content, files);
                }
            }
        }
        List<List<String>> res = new ArrayList<List<String>>();
        for (String key : map.keySet()) {
            List<String> files = map.get(key);
            if (files.size() > 1) {
                res.add(files);
            }
        }
        return res;
    }
}

发表于 | 分类于

Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither.

IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots (“.”), e.g.,172.16.254.1;

Besides, leading zeros in the IPv4 is invalid. For example, the address 172.16.254.01 is invalid.

IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (“:”). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a valid one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases).

However, we don’t replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an invalid IPv6 address.

Besides, extra leading zeros in the IPv6 is also invalid. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is invalid.

Note: You may assume there is no extra space or special characters in the input string.

Example 1:

1
2
3
4
5
Input: "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

Example 2:

1
2
3
4
5
Input: "2001:0db8:85a3:0:0:8A2E:0370:7334"
Output: "IPv6"
Explanation: This is a valid IPv6 address, return "IPv6".

Example 3:

1
2
3
4
5
Input: "256.256.256.256"
Output: "Neither"
Explanation: This is neither a IPv4 address nor a IPv6 address.

解法1：

C++

1

Java

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Solution {
    public String validIPAddress(String IP) {
        if (IP == null || IP.length() == 0) {
            return "Neither";
        }
        if (IP.contains(":")) {
            return IPV6(IP) ? "IPv6" : "Neither";
        } else {
            return IPV4(IP) ? "IPv4" : "Neither";
        }
    }
    private boolean IPV6(String ip) {
        String[] temp = ip.split(":",-1);
        if (temp.length != 8) {
            return false;
        }
        for (String element : temp) {
            if (element.isEmpty() || element.length() > 4) {
                return false;
            }
            for(int i = 0;i<element.length();i++){
                char ch = element.charAt(i);
                if(!((ch >= '0' && ch <= '9') || (ch>='a' && ch<='f') || (ch>='A' &&ch<='F'))) return false;
            }
        }
        return true;
    }
    private boolean IPV4(String ip) {
        String[] temp = ip.split("\\.",-1);
        if (temp.length != 4) {
            return false;
        }
        for (String element : temp) {
            if (element.isEmpty()) {
                return false;
            }
            if (element.length() > 1 && element.charAt(0) == '0') {
                return false;   // leading zero is invalid
            }
            if (element.length() > 3) {
                return false;
            }
            if (element.compareTo("0") < 0 || element.compareTo("255") > 0) {
                return false;
            }
        }
        return true;        
    }
}