R语言 字节跳动 Eclipse svg canvas syntax UIkit LimeJS progressjs js事件绑定 jq获取元素宽度 android逆向工程师 idea整理代码格式 matlab向量的模 matlab中axis ubuntu查看python版本 数据库教程 python中assert python的random函数 python安装 简单python脚本实例 python正则匹配空格 java类 java环境配置 java接口文档 java基础框架 java语言运算符 java数据类型转换 怎么安装linux linux格式化命令 心理学与生活txt 右键菜单背景 系统集成项目管理工程师教程 图片链接生成器 脚本软件 big5 编辑软件 混沌世界隐藏英雄密码 批处理if 保留小数点后两位
当前位置: 首页 > 学习教程  > 编程语言

Leetcode刷题 2021.01.28

2021/1/28 23:29:30 文章标签:

Leetcode刷题 2021.01.28Leetcode724 寻找数组的中心索引Leetcode802 找到最终的安全状态Leetcode886 可能的二分法Leetcode724 寻找数组的中心索引 给你一个整数数组 nums,请编写一个能够返回数组 “中心索引” 的方法。 数组 中心索引 是数组的一个索引&#xf…

Leetcode刷题 2021.01.28

  • Leetcode724 寻找数组的中心索引
  • Leetcode802 找到最终的安全状态
  • Leetcode886 可能的二分法

Leetcode724 寻找数组的中心索引

给你一个整数数组 nums,请编写一个能够返回数组 “中心索引” 的方法。

数组 中心索引 是数组的一个索引,其左侧所有元素相加的和等于右侧所有元素相加的和。

如果数组不存在中心索引,返回 -1 。如果数组有多个中心索引,应该返回最靠近左边的那一个

注意:中心索引可能出现在数组的两端

简单题就是会做的一眼就能看出来。这题知道前缀和的技巧的话应该就没问题了,之前看到字节的一道面试题就是这题的二维版本而已。话说面试的时候就算一眼就能看出来或者刷过题,还是装下样子,和面试官讨论讨论吧。

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        if (n == 0) return -1;
        int[] help = new int[n];
        int sum = 0;
        //朴素版前缀和,构建辅助数组,也可以不用,只算一次总和。
        for(int i = 0; i < n; i++){
            help[i] = sum + nums[i];
            sum = help[i];
        }
        for(int i = 0; i < n; i++){
            if (help[i] - nums[i] == help[n - 1] - help[i]){
                return i;
            }
        }

        return -1;
    }
}

Leetcode802 找到最终的安全状态

在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。

现在, 如果我们最后能走到终点,那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 K, 无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。

哪些节点最终是安全的? 结果返回一个有序的数组。

该有向图有 N 个节点,标签为 0, 1, …, N-1, 其中 N 是 graph 的节点数. 图以以下的形式给出: graph[i] 是节点 j 的一个列表,满足 (i, j) 是图的一条有向边。

仔细观察的话其实就能发现就是检查有向图是否有环,那就是拓扑排序了。不过这题要注意的是构建邻接表的时候要反过来,有向图的话最先想到的应该就是拓扑排序了吧。

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> eventualSafeNodes(int[][] graph) {
        if (graph.length == 0) return res;
        int n = graph.length;
        //邻接表
        List<List<Integer>> edge = new ArrayList<>();
        //BFS用队列
        Queue<Integer> queue = new LinkedList<>();
        //记录入度
        int[] indegree = new int[n];

        for(int i = 0; i < n; i++){
            edge.add(new ArrayList<>());
        }
        //反向构建邻接表
        for(int i = 0; i < n; i++){
            for(int ele : graph[i]){
                edge.get(ele).add(i);
                indegree[i]++;
            }
            //入度为0加入队列
            if (indegree[i] == 0) queue.offer(i);
        }

        while (!queue.isEmpty()){
            int temp = queue.poll();
            //把相邻点的入度减一,如果入度为0就入队
            for(int ele : edge.get(temp)){
                indegree[ele]--;
                if (indegree[ele] == 0) queue.offer(ele);
            }
        }
        //因为要返回有序的数组,所以再从头到尾遍历一次
        for(int i = 0; i < n; i++){
            if (indegree[i] == 0) res.add(i);
        }

        return res;
    }

}

Leetcode886 可能的二分法

给定一组 N 人(编号为 1, 2, …, N), 我们想把每个人分进任意大小的两组。

每个人都可能不喜欢其他人,那么他们不应该属于同一组。

形式上,如果 dislikes[i] = [a, b],表示不允许将编号为 a 和 b 的人归入同一组。

当可以用这种方法将所有人分进两组时,返回 true;否则返回 false。

一开始以为就是判断无向图是否有环,但是不是这样的。还是应该对点进行分类,参考了下题解,用最近做的很多的并查集来做。对于每个要分到不同类的两个点x, y,都让(x, x +n), (y, y + n)进行合并。如果后面出现矛盾的话就返回false了,比较有技巧的一个解法。

class Solution {
     public boolean possibleBipartition(int N, int[][] dislikes) {
     	//开一个2n大小的并查集
         UnionFind uf = new UnionFind(2 * N);
         //让序号从0开始,并且对于不同类的两个点,都和(x, x +n), (y, y + n)进行合并
         for(int[] ele : dislikes){
             ele[0]--;
             ele[1]--;
             if (uf.find(ele[0]) == uf.find(ele[1])) return false;
             uf.uinion(ele[0], ele[1] + N);
             uf.uinion(ele[0] + N, ele[1]);
         }
		
		//没有矛盾就返回true了。
         return true;
     }

    class UnionFind{
        int[] parent;

        public UnionFind(int n ){
            parent = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
            }
        }

        public int find(int i){
            if (parent[i] == i){
                return i;
            }

            return parent[i] = find(parent[i]);
        }

        public void uinion(int i, int j){
            int root1 = find(i);
            int root2 = find(j);
            if (root1 == root2) return;
            parent[root1] = root2;
        }
    }
}

本文链接: http://www.dtmao.cc/news_show_650227.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?