LeetCode Weekly Contest 35解题思路
LeetCode Weekly Contest 35解题思路
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434792
LeetCode Weekly Contest 35解题思路
详细代码可以fork下Github上leetcode项目，不定期更新。
赛题
本次周赛主要分为以下4道题：
- Leetcode 605. Can Place Flowers (4分)
- Leetcode 606. Construct String from Binary Tree (5分)
- Leetcode 609. Find Duplicate File in System (7分)
- Leetcode 591. Tag Validator (10分)
Leetcode 605. Can Place Flowers (4分)
Problem:
Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die. Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.
Example 1:
Input: flowerbed = 1,0,0,0,1, n = 1 Output: True
Example 2:
Input: flowerbed = 1,0,0,0,1, n = 2 Output: False
Note:
- The input array won’t violate no-adjacent-flowers rule.
- The input array size is in the range of 1, 20000.
- n is a non-negative integer which won’t exceed the input array size.
思路：
判断数组flowerbed最多能摆放多少花，如果大于等于n则返回true，如果小于n则返回false。
先考虑所有1元素，与它邻接的元素都可以排除。接着考虑0元素最多能摆放多少花，如：
0: 1朵
00: 1朵
000: 2朵
0000: 2朵
得到规律：
可摆放花朵数 = (连续0的个数 - 1) / 2代码如下：
public boolean canPlaceFlowers(int[] flowerbed, int n) {
if (n == 0)
return true;
for (int i = 0; i < flowerbed.length; i++) {
if (flowerbed[i] == 1) {
if (i - 1 != -1) flowerbed[i - 1] = -1;
if (i + 1 != flowerbed.length) flowerbed[i + 1] = -1;
}
}
int cnt = 0;
for (int i = 0; i < flowerbed.length; i++) {
if (flowerbed[i] == 0) {
int tt = dfs(flowerbed, i);
cnt += (tt + 1) / 2;
}
}
return cnt >= n;
}
private int dfs(int[] flowerbed, int next) {
if (next >= flowerbed.length || flowerbed[next] == -1)
return 0;
flowerbed[next] = -1;
int ans = 1;
ans += dfs(flowerbed, next + 1);
return ans;
}既然检测连续零元素的个数，可以省去第一个for循环，不需要对邻接元素进行标记，但需要判断数组起始位和数组结束位这两个特殊情况。
代码如下：
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int m = 0, c = 1;
for (int i : flowerbed){
if (i == 0){
++c;
}
else{
m += (c - 1) / 2;
c = 0;
}
}
++c;
m += (c - 1) / 2;
return m >= n;
}这思路相当清楚，c=1，是为了解决数组以0开始的特殊情况，而在for循环外的++c是为了解决数组以0结尾的特殊情况。而在数组内的连续0，计数总是从0开始，之前我们总结的规律为：
m += (c + 1) / 2;
此时没有排除1周围的0元素两个，所以还需要：
m += (c + 1 - 2) / 2;检测连续0元素，既然可以如此简单，服。核心思想可以总结为：
for {
if (不断满足条件){
//进行计数
}
else{
//终止计数，计数清零
}
}还是迭代方法简单的多。
Leetcode 606. Construct String from Binary Tree (5分)
Problem:
You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way. The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Input: Binary tree: 1,2,3,4 1 / \ 2 3 / 4undefined Output: “1(2(4))(3)” Explanation: Originallay it needs to be “1(2(4)())(3()())”,undefined but you need to omit all the unnecessary empty parenthesis pairs.undefined And it will be “1(2(4))(3)”.
Example 2:
Input: Binary tree: 1,2,3,null,4 1 / \ 2 3 \ 4 Output: “1(2()(4))(3)” Explanation: Almost the same as the first example,undefined except we can’t omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
思路：
树的题目都是天然的递归子问题思路，所以只要找到构建子问题的步骤即可。
分为：根，左子树，右子树
根不存在，直接返回 ""
根存在 append t.val + "";
左子树存在 append t.val + (左子问题的返回值);
注意： 此处需要做一个特殊处理！
左子树不存在，右子树存在，append t.val + "()";
右子树存在 append t.val + (左子问题的返回值) + (右子问题的返回值)代码如下：
public String tree2str(TreeNode t) {
return dfs(t);
}
private String dfs(TreeNode t){
if (t == null) return "";
String ans = t.val+"";
if (t.left != null){
ans += "(" + dfs(t.left) + ")";
}
if (t.left == null && t.right != null){
ans += "()";
}
if (t.right != null){
ans += "(" + dfs(t.right) + ")";
}
return ans;
}Leetcode 609. Find Duplicate File in System (7分)
Problem:
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:
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 a same directory.
- You may assume each given directory info represents a unique directory. Directory path and file infos are separated by a single blank space.
思路：
把路径，文件名，和文件内容解析出来，对文件内容建立map，最后扫一遍map中list的大小即可，有重复的list必然大于1。
代码如下：
class File{
String fileName;
String content;
}
public List<List<String>> findDuplicate(String[] paths) {
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < paths.length; i++){
String[] tmp = paths[i].split(" ");
String root = tmp[0];
for (int j = 1; j < tmp.length; j++){
File file = parseFile(tmp[j]);
map.computeIfAbsent(file.content, a -> new ArrayList<>()).add(root + "/" + file.fileName);
}
}
List<List<String>> ans = new ArrayList<>();
for (List<String> value : map.values()){
if (value.size() > 1) ans.add(value);
}
return ans;
}
private File parseFile(String path){
File file = new File();
int index = -1;
for (int i = 0; i < path.length(); i++){
if (path.charAt(i) == '('){
index = i;
break;
}
}
file.fileName = path.substring(0, index);
file.content = path.substring(index + 1, path.length() - 1);
return file;
}当然，我们也可以使用String自带的indexOf方法来优化parseFile方法，作用一样。代码如下：
private File parseFile(String path){
File file = new File();
int index = path.indexOf("(");
file.fileName = path.substring(0, index);
file.content = path.substring(index + 1, path.length() - 1);
return file;
}Leetcode 591. Tag Validator (10分)
题目大意：生成一个html代码检验器，合法code，返回true。
思路：
这道题关键要看清楚生成合法tag的规则，总结一下：
当遇到"<"字符时，都需要进行一次closeTag的检查，有三种情况：
"<#" 起始tag标志
"</" 结束tag标志
"<!" cdata开始标志
其他情况都属于内容，所以关键就在于找到每一次的"<"的开始位置。
构建过程：
a. 检查<TAG> content </TAG>
检查起始tag是否为TRUE？ 否则返回 FALSE
检查content是否为TRUE？ 否则返回 FALSE
b. 检查content
遇到非"<"起始字符，跳过。遇到"<",考虑三种情况：
b1. "<#" #表示任意字符，新一轮closedTag检查（因为这是起始tag的标志）
b2. "<!" cdata开始标志，进行cdata合法性检查
b3. "</" 遇到tag结束符，<之前的内容为TRUE，在closedTag中检查合法性。
c. 检查</TAG>是否为<TAG>的closedTag
closedTag的检查允许出现：
<TAG> .... </TAG>dasad 返回TRUE
所以在对最外层进行closedTag检查时，需要判断当前pos是否得到了code尾端，是返回true，否则返回false。代码如下：
int pos = 0, len = 0;
char[] cs;
public boolean isValid(String code) {
cs = code.toCharArray();
len = cs.length;
try{
if(!closedTag()) return false;
if(pos < len) return false;
return true;
}catch(Throwable t){
return false;
}
}
private boolean closedTag(){
if (! (pos < len && cs[pos] == '<')) return false;
pos ++;
StringBuilder sb = new StringBuilder();
while (pos < len && cs[pos] != '>'){
sb.append(cs[pos++]);
}
String tagName = sb.toString();
if (!isTagName(tagName)) return false;
pos++;
if (!content()) return false;
if (!(pos < len && cs[pos] == '<')) return false;
pos++;
if (!(pos < len && cs[pos] == '/')) return false;
pos++;
sb = new StringBuilder();
while (pos < len && cs[pos] != '>'){
sb.append(cs[pos++]);
}
String tagName2 = sb.toString();
if (!(isTagName(tagName2) && tagName.equals(tagName2))) return false;
if (! (pos < len && cs[pos] == '>')) return false;
pos++;
return true;
}
private boolean isTagName(String tagName){
if (!(tagName.length() >= 1 && tagName.length() <= 9)) return false;
for (char c : tagName.toCharArray()){
if (! (c >= 'A' && c <= 'Z')) return false;
}
return true;
}
private boolean content(){
while (pos < len){
while (pos < len && cs[pos] != '<') pos++;
if (pos == len) return true;
if (cs[pos + 1] == '/') return true;
if (cs[pos + 1] == '!'){
if (!cdata()) return false;
}else{
if (!closedTag()) return false;
}
}
return true;
}代码细节值得研究：
首先closedTag()方法返回TRUE的情况可以是：
<TAG>....</TAG>SAJDA
<DIV>....</DIV>
所以可以组合成：
<DIV> ...<TAG>...</TAG>SAJDA</DIV>
这样就省去了，最外层的特殊处理。
更加有趣的一点在于closedTag是忽略中间内容检测的方法，它只专注于解决外层的<TAG>识别。
而在content()方法中，它的工作主要在于解决，内容合并合法性问题！可以合并的只有两种情况:
"<#" 和 "<!"
所以说"<"这标识很重要，且"!"用来辨识CDATA又非常可爱。
总结：
closedTag()专注于解决包含关系
content()专注与解决合并关系凡是递归都可以使用栈解决？看了一种栈的方案，代码非常简短，很取巧。
public boolean isValid(String code) {
Stack<String> stack = new Stack<>();
for(int i = 0; i < code.length();){
//检测 <TAG>.....</TAG>DSAJSA or 检测 DSAJSA<TAG>...</TAG>这两种情况
if(i>0 && stack.isEmpty()) return false;
if(code.startsWith("<![CDATA[", i)){
int j = i+9;
i = code.indexOf("]]>", j);
if(i < 0) return false;
i += 3;
}else if(code.startsWith("</", i)){
int j = i + 2;
i = code.indexOf('>', j);
if(i < 0 || i == j || i - j > 9) return false;
for(int k = j; k < i; k++){
if(!Character.isUpperCase(code.charAt(k))) return false;
}
String s = code.substring(j, i++);
if(stack.isEmpty() || !stack.pop().equals(s)) return false;
}else if(code.startsWith("<", i)){
int j = i + 1;
i = code.indexOf('>', j);
if(i < 0 || i == j || i - j > 9) return false;
for(int k = j; k < i; k++){
if(!Character.isUpperCase(code.charAt(k))) return false;
}
String s = code.substring(j, i++);
stack.push(s);
}else{
i++;
}
}
return stack.isEmpty();
}