双百 Clean Solution : 使用双指针求解 | Java 刷题打卡

简介: 双百 Clean Solution : 使用双指针求解 | Java 刷题打卡

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 1764. 通过连接另一个数组的子数组得到一个数组 ,难度为 中等


Tag : 「双指针」


给你一个长度为 n 的二维整数数组 groups ,同时给你一个整数数组 nums 。


你是否可以从 nums 中选出 n 个 不相交 的子数组,使得第 i 个子数组与 groups[i] (下标从 0 开始)完全相同,且如果 i > 0 ,那么第 (i-1) 个子数组在 nums 中出现的位置在第 i 个子数组前面。(也就是说,这些子数组在 nums 中出现的顺序需要与 groups 顺序相同)


如果你可以找出这样的 n 个子数组,请你返回 true ,否则返回 false 。


如果不存在下标为 k 的元素 nums[k] 属于不止一个子数组,就称这些子数组是 不相交 的。子数组指的是原数组中连续元素组成的一个序列。


示例 1:


输入:groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
输出:true
解释:你可以分别在 nums 中选出第 0 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 和第 1 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 。
这两个子数组是不相交的,因为它们没有任何共同的元素。
复制代码


示例 2:


输入:groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
输出:false
解释:选择子数组 [1,2,3,4,10,-2] 和 [1,2,3,4,10,-2] 是不正确的,因为它们出现的顺序与 groups 中顺序不同。
[10,-2] 必须出现在 [1,2,3,4] 之前。
复制代码


示例 3:


输入:groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
输出:false
解释:选择子数组 [7,7,1,2,3,4,7,7] 和 [7,7,1,2,3,4,7,7] 是不正确的,因为它们不是不相交子数组。
它们有一个共同的元素 nums[4] (下标从 0 开始)。
复制代码


提示:


  • groups.length == n
  • 1 <= n <= 10^3103
  • 1 <= groups[i].length, sum(groups[i].length) <= 10^3103
  • 1 <= nums.length <= 10^3103
  • -10^7107 <= groups[i][j], nums[k] <= 10^7107


朴素解法



网络异常,图片无法展示
|


本质上是道模拟题。


使用 i 指针代表 nums 当前枚举到的位置;j 代表 groups 中枚举到哪个数组。

cnt 代表匹配的数组个数。


  • i 开头的连续一段和 groups[j] 匹配:j 指针右移一位(代表匹配下一个数组),i 指针右移 groups[j].length 长度。
  • i 开头的连续一段和 groups[j] 不匹配:i 右移一位。


代码:


class Solution {
    public boolean canChoose(int[][] gs, int[] nums) {
        int n = nums.length, m = gs.length;
        int cnt = 0;
        for (int i = 0, j = 0; i < n && j < m;) {
            if (check(gs[j], nums, i)) {
                i += gs[j++].length;
                cnt++;
            } else {
                i++;
            }
        }
        return cnt == m;
    }
    boolean check(int[] g, int[] nums, int i) {
        int j = 0;
        for (;j < g.length && i < nums.length; j++, i++) {
            if (g[j] != nums[i]) return false;
        }
        return j == g.length;
    }
}
复制代码


  • 时间复杂度:O(n * m)O(nm)
  • 空间复杂度:O(1)O(1)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.1764 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
11月前
|
Java 测试技术 Maven
Maven clean 提示文件 java.io.IOException
在使用Maven进行项目打包时,遇到了`Failed to delete`错误,尝试手动删除目标文件也失败,提示`java.io.IOException`。经过分析,发现问题是由于`sys-info.log`文件被其他进程占用。解决方法是关闭IDEA和相关Java进程,清理隐藏的Java进程后重新尝试Maven clean操作。最终问题得以解决。总结:遇到此类问题时,可以通过任务管理器清理相关进程或重启电脑来解决。
|
Java 容器
双指针(JAVA语言)
双指针(JAVA语言)
双指针(JAVA语言)
|
Java
2022蓝桥杯大赛软件类国赛Java大学B组 左移右移 空间换时间+双指针
2022蓝桥杯大赛软件类国赛Java大学B组 左移右移 空间换时间+双指针
149 3
|
缓存 Java 数据库连接
Java演进问题之指针的间接获取现在对性能的影响变得更大如何解决
Java演进问题之指针的间接获取现在对性能的影响变得更大如何解决
|
算法 Java C++
【Java 刷题记录】位运算
【Java 刷题记录】位运算
186 2
|
算法 Java
Java刷题有感
Java刷题有感
|
安全 Java
Java为什么不让用指针?
总之,Java的设计目标之一是提供一个安全、稳定和易于开发的平台,通过禁止直接使用指针来实现这些目标。虽然指针可以提供更大的灵活性,但也带来了许多潜在的问题和安全风险。因此,Java采用了更高级的内存管理和安全性机制,以减少这些问题的发生。
183 1
|
Java
2022蓝桥杯大赛软件类省赛Java大学B组真题 刷题统计
2022蓝桥杯大赛软件类省赛Java大学B组真题 刷题统计
164 0
|
Java
JAVA数据结构刷题 -- 二叉树进阶
JAVA数据结构刷题 -- 二叉树进阶
103 0
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
104 0

热门文章

最新文章