专栏首页机器学习入门LeetCode Weekly Contest 35解题思路

LeetCode Weekly Contest 35解题思路

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/72859739

LeetCode Weekly Contest 35解题思路

详细代码可以fork下Github上leetcode项目,不定期更新。

赛题

本次周赛主要分为以下4道题:

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

思路: 树的题目都是天然的递归子问题思路,所以只要找到构建子问题的步骤即可。

分为:根,左子树,右子树
根不存在,直接返回 ""

根存在 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();
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法细节系列(23):回溯

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

    用户1147447
  • LeetCode Weekly Contest 33解题思路

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

    用户1147447
  • 挑战程序竞赛系列(77):4.3 2-SAT(1)

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

    用户1147447
  • App进程启动流程

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

    用户2929716
  • 优化延迟的最佳视频传输方案(一)

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

    用户1324186
  • 4.1.java8新特性持续更新

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

    itjim
  • 软件工程个人作业01

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

    CN_Simo
  • Spring Boot 中,Json 数据传值方式

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

    水货程序员
  • 概率校准

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

    用户3577892
  • cmake:vs2015/MinGW静态编译leveldb

    leveldb是google的开源项目(https://github.com/google/leveldb), 在linux下编译很方便,然而官方版本却没有提供...

    用户1148648

扫码关注云+社区

领取腾讯云代金券