登录 注册

2021.1.24-2021.1.28 题解

本贴最后更新于 1271 天前，其中的信息可能已经东海扬尘

2021.1.24-2021.1.28 题解

  • 674.最长递增子序列 2021.1.24
    https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
    方法具体可以类比寻找最大值，只不过最大值变成了每个序列的递增长度，设置一个 curMax 和一个 max，如果序列一直在递增，就 curMax++，直到递减重置 curMax，然后根据 curMax 和 max 的大小对 max 进行更新。

    package _2021._01._0124._1;

/**
 * @author <a href="http://blog.chenforcode.cn">PKUCoder</a>
 * @date 2021/1/24 10:02 上午
 * @description 最长递增子序列，
 * 方法具体可以类比寻找最大值，只不过最大值变成了每个序列的递增长度，设置一个curMax
 * 和一个max，如果序列一直在递增，就curMax++，直到递减重置curMax，然后根据curMax
 * 和max的大小对max进行更新。
 */
public class Solution {
    public static int findLengthOfLCIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int max = 1;
        int curMax = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                curMax++;
            } else {
                curMax = 1;
            }
            max = Math.max(curMax, max);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = {2,2,2};
        System.out.println(findLengthOfLCIS(nums));
    }
}

  • 2.两数相加 2021.1.24
    https://leetcode-cn.com/problems/add-two-numbers/
    两数相加，数字是倒序存储的，所以可以直接遍历两个链表，让两个节点的值相加，如果存在大于等于 10 的情况就进位，下两个节点计算加上进位，如果最后两个节点还存在进位，那就新建立一个节点存储该进位。

    package _2021._01._0124._2;

/**
 * @author <a href="http://blog.chenforcode.cn">PKUCoder</a>
 * @date 2021/1/24 11:09 上午
 * @description 2.两数相加，数字是倒序存储的，所以可以直接遍历两个链表，让两个节点的值相加，
 * 如果存在大于等于10的情况就进位，下两个节点计算加上进位，如果最后两个节点还存在进位，那就新
 * 建立一个节点存储该进位。
 */
public class Solution {
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode h = head;
        boolean jinwei = false;
        while (l1 != null || l2 != null) {
            int sum = 0;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            if (jinwei) {
                sum++;
            }
            h.next = new ListNode(sum % 10);
            h = h.next;
            jinwei = (sum >= 10);
        }
        if (jinwei) {
            h.next = new ListNode(1);
        }
        return head.next;
    }

    public static void main(String[] args) {
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

  • 959.由斜杠划分区域 2021.1.25
    https://leetcode-cn.com/problems/regions-cut-by-slashes/
    将 1x1 的格子扩大成为 3x3 的迷宫,扩大成为 6x6，然后把两种斜线写入迷宫计 1，然后计算最终有多少个区域即可

    package _2021._01._0125;

/**
 * @author Ariel
 * @date 2021/1/25 10:37
 * @description 959. 由斜杠划分区域。
 * 将1*1的格子扩大成为3*3的迷宫，2*2扩大成为6*6，然后把两种斜线写入迷宫计1，然后计算最终有多少个
 * 区域即可
 */
public class Solution {
    private static int[][] next = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    public static int regionsBySlashes(String[] grid) {
        int count = 100;//记录有多少个区域，深搜一次说明就有一个
        int [][] g = new int[grid.length * 3][grid[0].length() * 3];
        //初始化
        for (int i = 0; i < g.length; i++) {
            for (int j = 0; j < g[0].length; j++){
                g[i][j] = 0;
            }
        }
        //填迷宫
        for (int i = 0; i < grid.length; i++) {
            char[] chars = grid[i].toCharArray();
            for (int j = 0; j < chars.length; j++) {
                if (chars[j] == '/') {
                    g[i * 3 + 2][j * 3] = 1;
                    g[i * 3 + 1][j * 3 + 1] = 1;
                    g[i * 3][j * 3 + 2] = 1;
                }
                if(chars[j] == '\\'){
                    g[i * 3][j * 3] = 1;
                    g[i * 3 + 1][j * 3 + 1] = 1;
                    g[i * 3 +2][j * 3 + 2] = 1;
                }
            }
        }
        //开始深搜
        for (int i = 0; i < g.length; i++) {
            for (int j = 0; j < g[0].length; j++) {
                if(g[i][j] == 0){
                    g[i][j]= count;
                    dfs(g, i, j, count);
                    count++;
                }
            }
        }
        return count - 100;
    }
    static void dfs(int[][]g, int i, int j, int count){
        for (int m = 0; m < 4; m++) {
            int nextX = next[m][0] + i;
            int nextY = next[m][1] + j;
            if (nextX >= 0 && nextX < g.length && nextY >= 0 && nextY < g[0].length && g[nextX][nextY] == 0) {
                g[nextX][nextY] = count;
                dfs(g, nextX, nextY, count);
            }
        }
    }

    public static void main(String[] args) {
        String[] grid = new String[2];
        grid[0] = "//";
        grid[1] = "/ ";
        System.out.println(regionsBySlashes(grid));
    }
}

  • 1128.等价多米诺骨牌对的数量 2021.1.26
    https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs/
    对于 12，21 这种我们统一看成 12，并将 12 看成 key，value 看成有多少个组是 12，然后对 value 进行组合计算，求和得到最终的结果。

    package _2021._01._0126;

import java.util.HashMap;
import java.util.Set;

/**
 * @author <a href="http://blog.chenforcode.cn">PKUCoder</a>
 * @date 2021/1/26 9:52 上午
 * @description 1128.等价多米诺骨牌对的数量
 * 给出n个二元组，两个组，相同或者相反代表是相同的一组，查一共有多少个相同组。
 * 例如 (1,2)(2,1)(3,4)(4,5)只有前两个是相同的一组，输出为1
 * 解法：对于12，21这种我们统一看成12，并将12看成key，value看成有多少个组是12，然后对value进行
 * 组合计算，求和得到最终的结果。
 */
public class Solution {
    public static int numEquivDominoPairs(int[][] dominoes) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < dominoes.length; i++) {
            int[] row = dominoes[i];
            int key = 0;
            if (row[0] > row[1]) {
                key = row[0] * 10 + row[1];
            } else {
                key = row[1] * 10 + row[0];
            }

            if (!hashMap.containsKey(key)) {
                hashMap.put(key, 1);
            } else {
                hashMap.put(key, hashMap.get(key) + 1);
            }
        }
        Set<Integer> integers = hashMap.keySet();
        int ans = 0;
        for (Integer integer : integers) {
            int val = hashMap.get(integer);
            if (val >= 2) {
                ans += (val * (val - 1) / 2);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int [][]res = {{1,2},{2,1},{2,1},{5,6}};
        System.out.println(numEquivDominoPairs(res));
    }
}

  • 461.汉明距离 2021.1.26
    https://leetcode-cn.com/problems/hamming-distance/
    汉明距离是求两个数字中，不同位的数字的个数。因此可以先进行异或，然后结果里边的所有的 1 就是最终结果。因此提供两种解法：第一种就是一位一位的移动，计算 1 的个数。第二种是叫做布赖恩·克尼根算法，他是可以直接计算 1，可以跳过 0。如图，让 x & (x-1)就可以去除掉 x 中的最后一个 1，以此类推，该操作的次数就是结果里边 1 的个数。
    img

    package _2021._01._0126._2;

/**
 * @author <a href="http://blog.chenforcode.cn">PKUCoder</a>
 * @date 2021/1/26 11:16 上午
 * @description 461.汉明距离
 */
public class Solution {
    public static int hammingDistance(int x, int y) {
        int result = x ^ y;
        int dis = 0;
        //相与计算
//        while (result != 0) {
//            //每做一次该操作，都消除了一个1
//            result = (result & (result - 1));
//            dis++;
//        }
        //移位计算
        while (result != 0) {
            if (result % 2 == 1) {
                dis++;
            }
            result = result >> 1;
        }
        return dis;
    }

    public static void main(String[] args) {
        System.out.println(hammingDistance(1, 4));
    }
}

  • 1579.保证图可完全遍历 2021.1.27
    https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/
    这个题的主要思路有点类似于克鲁斯卡尔求最小生成树，但是不同的是这个图没有权重，因此可以按照边的顺序进行依次加边。而且判断连通也不是整个图连通，而是判断两个点是否连通，如果这两个点已经连通了，那么如果再对这两个点加边就是多余的，此时最终的答案 +1。然后具体判断两个点是否连通可以用并查集。

    package _2021._01._0127;

import java.util.Arrays;

/**
 * @author <a href="http://blog.chenforcode.cn">PKUCoder</a>
 * @date 2021/1/27 11:26 上午
 * @description 1579.保证图可完全遍历
 * 因为没有权重，所以按照顺序遍历，依次加边，然后判断联通，如果两点已经联通，那么下次连接
 * 这两点的边就是多余的，不再加边，记录可删除数字+1。先加公共边，然后加alice，加bob。
 * 二者分别有一个并查集来判断任意两点是否联通。最后各自的并查集数目为1代表合并完成，可连通。
 * 并查集可以看成是几个联通点的集合，他们几个之间类似树的关系，有一个祖先节点。
 */
public class Solution {
    public static int maxNumEdgesToRemove(int n, int[][] edges) {
        init(edges);
        Union alice = new Union(n);
        Union bob = new Union(n);
        int ans = 0;
        for (int[] edge : edges) {
            if (edge[0] == 3) {
                if (!alice.isConnected(edge[1], edge[2])) {
                    alice.merge(edge[1], edge[2]);
                    bob.merge(edge[1], edge[2]);
                } else {
                    ans++;
                }
            }
        }
        for (int[] edge : edges) {
            if (edge[0] == 1) {
                if (!alice.isConnected(edge[1], edge[2])) {
                    alice.merge(edge[1], edge[2]);
                } else {
                    ans++;
                }
            }
            if (edge[0] == 2) {
                if (!bob.isConnected(edge[1], edge[2])) {
                    bob.merge(edge[1], edge[2]);
                } else {
                    ans++;
                }
            }
        }
        return (alice.count == 1 && bob.count == 1) ? ans : -1;
    }

    public static void init(int[][] edges) {
        for (int[] edge : edges) {
            edge[1]--;
            edge[2]--;
        }
    }

    public static void main(String[] args) {
//        int[][] edges = {{3, 1, 2}, {3, 2, 3}, {1, 1, 3}, {1, 2, 4}, {1, 1, 2}, {2, 3, 4}};
//        System.out.println(maxNumEdgesToRemove(4, edges));
//        int n = 2;
//        int[][] edges = {{1, 1, 2}, {2, 1, 2}, {3, 1, 2}};
        int n = 13;
        int[][] edges = {{1,1,2},{2,1,3},{3,2,4},{3,2,5},{1,2,6},{3,6,7},{3,7,8},{3,6,9},{3,4,10},{2,3,11},{1,5,12},{3,3,13},{2,1,10},{2,6,11},{3,5,13},{1,9,12},{1,6,8},{3,6,13},{2,1,4},{1,1,13},{2,9,10},{2,1,6},{2,10,13},{2,2,9},{3,4,12},{2,4,7},{1,1,10},{1,3,7},{1,7,11},{3,3,12},{2,4,8},{3,8,9},{1,9,13},{2,4,10},{1,6,9},{3,10,13},{1,7,10},{1,1,11},{2,4,9},{3,5,11},{3,2,6},{2,1,5},{2,5,11},{2,1,7},{2,3,8},{2,8,9},{3,4,13},{3,3,8},{3,3,11},{2,9,11},{3,1,8},{2,1,8},{3,8,13},{2,10,11},{3,1,5},{1,10,11},{1,7,12},{2,3,5},{3,1,13},{2,4,11},{2,3,9},{2,6,9},{2,1,13},{3,1,12},{2,7,8},{2,5,6},{3,1,9},{1,5,10},{3,2,13},{2,3,6},{2,2,10},{3,4,11},{1,4,13},{3,5,10},{1,4,10},{1,1,8},{3,3,4},{2,4,6},{2,7,11},{2,7,10},{2,3,12},{3,7,11},{3,9,10},{2,11,13},{1,1,12},{2,10,12},{1,7,13},{1,4,11},{2,4,5},{1,3,10},{2,12,13},{3,3,10},{1,6,12},{3,6,10},{1,3,4},{2,7,9},{1,3,11},{2,2,8},{1,2,8},{1,11,13},{1,2,13},{2,2,6},{1,4,6},{1,6,11},{3,1,2},{1,1,3},{2,11,12},{3,2,11},{1,9,10},{2,6,12},{3,1,7},{1,4,9},{1,10,12},{2,6,13},{2,2,12},{2,1,11},{2,5,9},{1,3,8},{1,7,8},{1,2,12},{1,5,11},{2,7,12},{3,1,11},{3,9,12},{3,2,9},{3,10,11}};
        System.out.println(maxNumEdgesToRemove(n, edges));
    }
}

class Union {
    int[] parent;
    int[] size;
    int count;
    int n;

    public Union(int n) {
        this.n = n;
        this.count = n;
        parent = new int[n];
        size = new int[n];
        Arrays.fill(size, 1);
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }

    public int findRoot(int x) {
        //判断是否找到了最后的祖先。即判断x本身是否为祖先
        if (x == parent[x]) {
            return x;
        }
        //如果x不是祖先，那就接着判断x的父亲是不是祖先，并且更新x的父亲为找到的祖先结果
        parent[x] = findRoot(parent[x]);
        return parent[x];
    }

    public boolean merge(int x, int y) {
        //注意这里并查集的合并不能简单的将两个点合并，而是将两个点所在的集合合并
        //因此操作的是root(x)和root(y)
        if (findRoot(x) == findRoot(y)) {
            return false;
        }
        parent[findRoot(x)] = findRoot(y);
        parent[x] = y;
        this.count--;
        return true;
    }

    public boolean isConnected(int x, int y) {
        return findRoot(x) == findRoot(y);
    }
}

  • 617.合并二叉树 2021.1.27
    https://leetcode-cn.com/problems/merge-two-binary-trees/
    这个题就正常做，遍历两棵树，计算相应的值作为新树的节点，然后新树的左子树为递归遍历两棵树的左子树。右子树同理

    package _2021._01._0127._2;

/**
 * @author <a href="http://blog.chenforcode.cn">PKUCoder</a>
 * @date 2021/1/27 10:56 下午
 * @description 617.合并二叉树
 */
public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode root = new TreeNode(t1.val + t2.val);
        root.left = mergeTrees(t1.left, t2.left);
        root.right = mergeTrees(t1.right, t2.right);
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

  • 724.寻找数组的中心索引 2021.1.28
    https://leetcode-cn.com/problems/find-pivot-index/
    这题的思路也很明确，就是遍历每一个点，都尝试当做中心索引，然后是否左右相等。但是该题如果对每个中心节点的左右都计算一次太慢。我们只需要判断最后的条件，即 sum 左 + sum 右 + num[i] == total。然后 sum 左和 sum 右是相等的，因此直接 2 * sum 左 + num[i] == total 即可，然后 sum 左可以在遍历 num[i]的时候就计算出来。

    package _2021._01._0128;

import java.util.Arrays;

/**
 * @author <a href="http://blog.chenforcode.cn">PKUCoder</a>
 * @date 2021/1/28 9:22 上午
 * @description 724.寻找数组的中心索引
 */
public class Solution {
    public static int pivotIndex(int[] nums) {
        int total = Arrays.stream(nums).sum();
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum * 2 + nums[i] == total) {
                return i;
            }
            sum += nums[i];
        }

        return -1;
    }

    public static void main(String[] args) {
//        int[] nums = {-1,-1,-1,-1,-1,-1};
        int []nums = {1, 7, 3, 6, 5, 6};
        System.out.println(pivotIndex(nums));
    }
}
  • LeetCode

    LeetCode（力扣）是一个全球极客挚爱的高质量技术成长平台，想要学习和提升专业能力从这里开始，充足技术干货等你来啃，轻松拿下 Dream Offer！

    209 引用 • 72 回帖
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3169 引用 • 8208 回帖
北京 位置
263 20 30 68 10 6 125

相关帖子

回帖
2021.1.24-2021.1.28 题解

欢迎来到这里！

我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。

注册 关于
请输入回帖内容 ...
ChenforCode
北京
回帖
6
 帖子
33
 积分
99

近期热议

推荐标签 标签

  • Openfire

    Openfire 是开源的、基于可拓展通讯和表示协议 (XMPP)、采用 Java 编程语言开发的实时协作服务器。Openfire 的效率很高，单台服务器可支持上万并发用户。

    6 引用 • 7 回帖 • 94 关注
  • 倾城之链
    23 引用 • 66 回帖 • 120 关注
  • 996

    “工作 996， 生病 ICU”

    13 引用 • 200 回帖 • 6 关注
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器，在 1999 年被捐献给 ASF（Apache Software Foundation），隶属于 Jakarta 项目，现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范，同时也提供 HTTP 服务，是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖
  • 博客

    记录并分享人生的经历。

    272 引用 • 2386 回帖
  • CodeMirror
    1 引用 • 2 回帖 • 125 关注
  • Bug

    Bug 本意是指臭虫、缺陷、损坏、犯贫、窃听器、小虫等。现在人们把在程序中一些缺陷或问题统称为 bug（漏洞）。

    71 引用 • 1737 回帖 • 1 关注
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务，可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 51 关注
  • Kafka

    Kafka 是一种高吞吐量的分布式发布订阅消息系统，它可以处理消费者规模的网站中的所有动作流数据。 这种动作（网页浏览，搜索和其他用户的行动）是现代系统中许多功能的基础。 这些数据通常是由于吞吐量的要求而通过处理日志和日志聚合来解决。

    35 引用 • 35 回帖
  • 脑图

    脑图又叫思维导图，是表达发散性思维的有效图形思维工具 ，它简单却又很有效，是一种实用性的思维工具。

    21 引用 • 58 回帖
  • SOHO

    为成为自由职业者在家办公而努力吧！

    7 引用 • 55 回帖 • 65 关注
  • GitLab

    GitLab 是利用 Ruby 一个开源的版本管理系统，实现一个自托管的 Git 项目仓库，可通过 Web 界面操作公开或私有项目。

    46 引用 • 72 回帖
  • JavaScript

    JavaScript 一种动态类型、弱类型、基于原型的直译式脚本语言，内置支持类型。它的解释器被称为 JavaScript 引擎，为浏览器的一部分，广泛用于客户端的脚本语言，最早是在 HTML 网页上使用，用来给 HTML 网页增加动态功能。

    713 引用 • 1174 回帖 • 104 关注
  • Bootstrap

    Bootstrap 是 Twitter 推出的一个用于前端开发的开源工具包。它由 Twitter 的设计师 Mark Otto 和 Jacob Thornton 合作开发，是一个 CSS / HTML 框架。

    18 引用 • 33 回帖 • 680 关注
  • Android

    Android 是一种以 Linux 为基础的开放源码操作系统，主要使用于便携设备。2005 年由 Google 收购注资，并拉拢多家制造商组成开放手机联盟开发改良，逐渐扩展到到平板电脑及其他领域上。

    334 引用 • 323 回帖 • 19 关注
  • 面试

    面试造航母，上班拧螺丝。多面试，少加班。

    324 引用 • 1395 回帖
  • 正则表达式

    正则表达式（Regular Expression）使用单个字符串来描述、匹配一系列遵循某个句法规则的字符串。

    31 引用 • 94 回帖
  • 黑曜石

    黑曜石是一款强大的知识库工具，支持本地 Markdown 文件编辑，支持双向链接和关系图。

    A second brain, for you, forever.

    10 引用 • 88 回帖
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 5 关注
  • abitmean

    有点意思就行了

    • 38 关注
  • Logseq

    Logseq 是一个隐私优先、开源的知识库工具。

    Logseq is a joyful, open-source outliner that works on top of local plain-text Markdown and Org-mode files. Use it to write, organize and share your thoughts, keep your to-do list, and build your own digital garden.

    5 引用 • 62 回帖
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器，也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的，第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    311 引用 • 546 回帖 • 1 关注
  • 星云链

    星云链是一个开源公链，业内简单的将其称为区块链上的谷歌。其实它不仅仅是区块链搜索引擎，一个公链的所有功能，它基本都有，比如你可以用它来开发部署你的去中心化的 APP，你可以在上面编写智能合约，发送交易等等。3 分钟快速接入星云链 (NAS) 测试网

    3 引用 • 16 回帖 • 1 关注
  • Hprose

    Hprose 是一款先进的轻量级、跨语言、跨平台、无侵入式、高性能动态远程对象调用引擎库。它不仅简单易用，而且功能强大。你无需专门学习，只需看上几眼，就能用它轻松构建分布式应用系统。

    9 引用 • 17 回帖 • 600 关注
  • 学习

    “梦想从学习开始，事业从实践起步” —— 习近平

    163 引用 • 473 回帖
  • Firefox

    Mozilla Firefox 中文俗称“火狐”（正式缩写为 Fx 或 fx，非正式缩写为 FF），是一个开源的网页浏览器，使用 Gecko 排版引擎，支持多种操作系统，如 Windows、OSX 及 Linux 等。

    7 引用 • 30 回帖 • 429 关注
  • PHP

    PHP（Hypertext Preprocessor）是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点，主要适用于 Web 开发领域，据说是世界上最好的编程语言。

    165 引用 • 407 回帖 • 510 关注

最新标签