LeetCode 第 159 场周赛

一、缀点成线(LeetCode-5230)

1.1 题目描述

1.2 解题思路

比较简单的一题，利用公式 y = kx + b,确定好k和b就好，并且要考虑一种情况，函数 x = h。

1.3 解题代码



public boolean checkStraightLine(int[][] coordinates) {

        int k = Integer.MIN_VALUE;

        int x1 = coordinates[0][0];

        int y1 = coordinates[0][1];

        int x2 = coordinates[1][0];

        int y2 = coordinates[1][1];

        int dy = y2 - y1;

        int dx = x2 - x1;

        if (dx != 0) {

            k = dy / dx;

        }

        int b = y1 - k * x1;

        boolean onLine = true;

        for (int i = 2; i < coordinates.length; i++) {

            if (k == Integer.MIN_VALUE) {

                if (coordinates[i][0] != x1) {

                    onLine = false;

                    break;

                }

            } else if (coordinates[i][1] != (k * (coordinates[i][0]) + b)) {

                onLine = false;

                break;

            }

        }

        return onLine;

    }

二、删除子文件夹(LeetCode-5231)

2.1 题目描述

2.2 解题思路

使用两层for循环会导致超时，需要使用字典树解决。

2.3 解题代码



class Solution {

    public Tree rootNode = null;

    public List<String> removeSubfolders(String[] folder) {

        rootNode = new Tree();

        rootNode.path = "/";

        rootNode.nextMap = new HashMap<>();

        List<String> res = new ArrayList<>();

        Arrays.sort(folder, (a, b) -> {

            return a.length() - b.length();

        });

        for (int i = 0; i < folder.length; i++) {

            if (!isCover(folder[i])) {

                res.add(folder[i]);

            }

        }

        return res;

    }

    public boolean isCover(String path) {

        boolean cover = false;

        String[] pathArray = path.split("/");

        int arrayLen = pathArray.length;

        Tree tmp = rootNode;

        for (int i = 1; i < arrayLen; i++) {

            Tree node = tmp.nextMap.get(pathArray[i]);

            if (node == null) {

                node = new Tree();

                node.path = pathArray[i];

                node.nextMap = new HashMap<>();

            } else {

                if (node.isRoot) {

                    cover = true;

                }

            }

            if (cover == false && i == arrayLen - 1) {

                node.isRoot = true;

            }

            tmp.nextMap.put(pathArray[i], node);

            tmp = node;

        }

        return cover;

    }

}

class Tree {

    public String path;

    //判断是否是根文件夹

    //例如 /a/b 可能是根文件夹，需要在b节点，记录isRoot = true;

    public boolean isRoot;

    public Map<String, Tree> nextMap;

}

巴特西

LeetCode 第 159 场周赛

一、缀点成线(LeetCode-5230)

1.1 题目描述

1.2 解题思路

1.3 解题代码

二、删除子文件夹(LeetCode-5231)

2.1 题目描述

2.2 解题思路

2.3 解题代码

最新文章

热门文章

巴特西

LeetCode 第 159 场周赛

一、 缀点成线(LeetCode-5230)

1.1 题目描述

1.2 解题思路

1.3 解题代码

二、 删除子文件夹(LeetCode-5231)

2.1 题目描述

2.2 解题思路

2.3 解题代码

最新文章

热门文章

一、缀点成线(LeetCode-5230)

二、删除子文件夹(LeetCode-5231)