# LeetCode Weekly Contest 35解题思路

## 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.

```0: 1朵
00: 1朵
000: 2朵
0000: 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;
}```

```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;
}```

```m += (c + 1) / 2;

m += (c + 1 - 2) / 2;```

```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 / 4 Output: “1(2(4))(3)” Explanation: Originallay it needs to be “1(2(4)())(3()())”, but you need to omit all the unnecessary empty parenthesis pairs. 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, except we can’t omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

```分为：根，左子树，右子树

```    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.

```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()){
}

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;
}```

```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分)

```当遇到"<"字符时，都需要进行一次closeTag的检查，有三种情况：
"<#"  起始tag标志
"</"  结束tag标志
"<!"  cdata开始标志

a. 检查<TAG> content </TAG>

b. 检查content

b1. "<#" #表示任意字符，新一轮closedTag检查（因为这是起始tag的标志）
b2. "<!" cdata开始标志，进行cdata合法性检查
b3. "</" 遇到tag结束符，<之前的内容为TRUE，在closedTag中检查合法性。

c. 检查</TAG>是否为<TAG>的closedTag

closedTag的检查允许出现：

```    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()专注于解决包含关系
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();
}```

0 条评论

• ### 算法细节系列（23）：回溯

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### LeetCode Weekly Contest 33解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（77）：4.3 2-SAT（1）

挑战程序竞赛系列（77）：4.3 2-SAT（1） 传送门：POJ 3683: Priest John’s Busiest Day 题意： 有n个婚礼，每个...

• ### App进程启动流程

在上一节Activity的启动流程中，当app进程不存在（第一次启动）时，会先去创建进程。这里我们通过源码来解读app进程的启动流程。

• ### 优化延迟的最佳视频传输方案（一）

流媒体服务逐渐成为全球媒体和娱乐业务的核心，根据目前市场的数据，由于增长率是传统电视的10倍，OTT视频已经占到了行业总收入的15％，预计到2022年将占据市场...

• ### 4.1.java8新特性持续更新

记得我在以前找工作的经历中，遇到过一个面试官问过我一个很基础的问题。问题是：有一个List中有10个元素，我现在想从中删除3个元素，请问怎么做？我...

• ### 软件工程个人作业01

题目：      像二柱子那样，花二十分钟写一个能自动生成三十道小学四则运算题目的 “软件”，要求：除了整数以外，还要支持真分数的四则运算（需要验证结果的正确...

• ### Spring Boot 中，Json 数据传值方式

之前整理过一篇 Spring MVC 中的传值方式。《Spring MVC 传值方式总结》

• ### 概率校准

使用sklearn自动生成二分类数据集，划分训练集、验证集和测试集对不同的分类器，画出可靠性曲线在训练集上：在验证集上如何进行概率校准（probability ...