Java C++题解leetcode817链表组件示例

目录
  • 题目要求
  • 思路：模拟
    • Java
    • C++
    • Rust
  • 总结

题目要求

思路：模拟

Java

class Solution {
    public int numComponents(ListNode head, int[] nums) {
        int res = 0;
        Set<Integer> set = new HashSet<>();
        for (int x : nums)
            set.add(x); // 转存nums
        while (head != null) {
            if (set.contains(head.val)) {
                while (head != null && set.contains(head.val))
                    head = head.next;
                res++;
            }
            else {
                head = head.next;
            }
        }
        return res;
    }
}
  • 时间复杂度：O(n)，遍历整个链表
  • 空间复杂度：O(n)，转存nums

C++

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        int res = 0;
        unordered_set<int> set(nums.begin(), nums.end()); // 转存nums
        while (head) {
            if (set.count(head->val)) {
                while (head && set.count(head->val))
                    head = head->next;
                res++;
            }
            else {
                head = head->next;
            }
        }
        return res;
    }
};
  • 时间复杂度：O(n)，遍历整个链表
  • 空间复杂度：O(n)，转存nums

Rust

use std::collections::HashSet;
impl Solution {
    pub fn num_components(mut head: Option<Box<ListNode>>, nums: Vec<i32>) -> i32 {
        let mut head = head.as_ref();
        let mut res = 0;
        let mut status = false; // 是否处于同一个组件
        while let Some(node) = head {
            if nums.contains(&node.val) {
                if !status {
                    res += 1;
                    status = true;
                }
            } else {
                status = false;
            }
            head = node.next.as_ref();
        }
        res
    }
}
  • 时间复杂度：O(n)，遍历整个链表
  • 空间复杂度：O(n)，转存nums

总结

简单模拟题，没想到转存用哈希表的内置函数，还想着要排序方便查找……对于消耗空间的方法总是不太敏感。

以上就是Java C++题解leetcode817链表组件示例的详细内容，更多关于Java C++题解链表组件的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Java C++题解leetcode1598文件夹操作日志搜集器

    Java C++题解leetcode1598文件夹操作日志搜集器

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 根据日志判断目前在哪一级子文件夹即可,级数就等于返回时的步数,主文件夹级数初始为000: xl:级数+1+1+1: ./:级数不变: ../:级数−1-1−1. Java class Solution { public int minOperations(String[] logs) { int res = 0; for (String l : logs) { if (l.equals("../"))

  • Java C++ leetcode执行一次字符串交换能否使两个字符串相等

    Java C++ leetcode执行一次字符串交换能否使两个字符串相等

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 Java class Solution { public boolean areAlmostEqual(String s1, String s2) { if (s1.length() != s2.length()) return false; int a = -1, b = -1; for (int i = 0; i < s1.length(); i++) { if (s1.charAt(i) == s2.charAt

  • Java C++题解leetcode判定是否为字符重排

    Java C++题解leetcode判定是否为字符重排

    目录 题目要求 思路一:排序 Java C++ Rust 思路二:词频统计 Java C++ Rust 总结 题目要求 思路一:排序 Java class Solution { public boolean CheckPermutation(String s1, String s2) { if(s1.length() != s2.length()) return false; char[] sort1 = s1.toCharArray(); Arrays.sort(sort1); char[]

  • Java C++题解 leetcode第k个数实例

    Java C++题解 leetcode第k个数实例

    目录 题目要求 思路一:小根堆 Java C++ 思路二:多路归并[多指针] Java C++ Rust 总结 题目要求 思路一:小根堆 中文题目描述不太清晰,但其实由题目可以发现,当x满足条件时,3x.5x.7x分别也都满足条件. 将满足条件的数依次放入优先队列存放用于后续计算,由于每次要取待计算队列中最小的数x,所以定义小根堆: 弹出x,计算3x.5x.7x并入队: 用一个哈希表记录防止重复入队. 每次取数(pop)时进行计数,到第k次结束,当前队首即为答案. Java <学到了> 1L也

  • Java C++题解leetcode字符串轮转KMP算法详解

    Java C++题解leetcode字符串轮转KMP算法详解

    目录 题目要求 思路一:双指针(模拟) Java C++ 思路二:子串 手写KMP Java dp C++ dp 调API Java C++ 总结 题目要求 思路一:双指针(模拟) Java class Solution { public boolean isFlipedString(String s1, String s2) { if (s1.length() != s2.length()) return false; int n = s1.length(); if (n == 0) retu

  • Java C++算法题解leetcode801使序列递增的最小交换次数

    Java C++算法题解leetcode801使序列递增的最小交换次数

    目录 题目要求 思路:状态机DP 实现一:状态机 Java C++ Rust 实现二:滚动数组 Java C++ Rust 总结 题目要求 思路:状态机DP 实现一:状态机 Java class Solution { public int minSwap(int[] nums1, int[] nums2) { int n = nums1.length; int[][] f = new int[n][2]; for (int i = 1; i < n; i++) f[i][0] = f[i][1]

  • Java C++题解leetcode817链表组件示例

    Java C++题解leetcode817链表组件示例

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 Java class Solution { public int numComponents(ListNode head, int[] nums) { int res = 0; Set<Integer> set = new HashSet<>(); for (int x : nums) set.add(x); // 转存nums while (head != null) { if (set.cont

  • Java语言实现反转链表代码示例

    问题描述 定义一个函数,输入一个链表的头结点,反转该链表并输出反转后的链表的头结点.链表结点如下: public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } 思路1: 要想反转链表,对于结点i,我们要把它的next指向它的前趋,因此我们需要保存前趋结点,同时,如果我们已经把i的next重新赋值,会无法找到i的后继,因此,在重新赋值之前,我们要保存i的后继. 代码:

  • Java C++题解leetcode672灯泡开关示例

    Java C++题解leetcode672灯泡开关示例

    目录 题目要求 思路:找规律 Java C++ Rust 总结 题目要求 思路:找规律 找到尽可能最精简的通项表达,今日参考:京城打工人 首先,归纳每个开关会影响的灯,其中(k=0,1,2,…): 开关 反转灯编号 一 k 二 2k 三 2k+1 四 3k+1 可见灯以6盏为周期具有相同变化,所以以下只需要推导第一个周期里的6盏灯即可. 观察前6盏灯: 灯 开关 1 一.三.四 2 一.二 3 一.三 4 一.二.四 5 一.三 6 一.二 发现灯2.6和3.5分别受同样的开关影响,所以状态相同

  • Java C++题解leetcode915分割数组示例

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • Java C++题解leetcode816模糊坐标示例

    目录 题目 思路:枚举 Java C++ Rust 总结 题目 题目要求 思路:枚举 既然要输出每种可能了,那必然不能“偷懒”,就暴力枚举咯: 在每个间隔处添加逗号: 定义函数decPnt(sta, end)分别列举逗号左右两边的数能构成的可能性: 同样在每个间隔添加小数点: 注意两种不合法的结构——前导0和后缀0: 不要忘记无小数点的整数版本, 分别组合两边的不同可能性,根据要求各式加入答案. Java class Solution { String str; public List<Stri

  • Java C++题解leetcode1441用栈操作构建数组示例

    目录 题目要求 思路:模拟[双指针] Java C++ Rust 题目要求 思路:模拟[双指针] 按题意模拟即可: 一个指针cur依次指向target中的每个元素,另一个指针i依次指向1∼n的数字: 对i所指向的每个数字进行Push操作,然后判断当前数字与target[cur]是否相等: 相等则判断下一个数字,同时将cur指向下一个元素: 否则需进行Pop操作. 过程中需注意cur的越界,当其越界则target构造完毕. Java class Solution { public List<Str

  • Java C++题解leetcode 1684统计一致字符串的数目示例

    目录 题目 思路:模拟 Java C++ Rust 题目 题目要求 思路:模拟 用一个哈希表记录可出现的字母,然后逐一遍历每个单词每个字母,符合条件则结果加一. Java class Solution { public int countConsistentStrings(String allowed, String[] words) { boolean[] hash = new boolean[26]; for (var a : allowed.toCharArray()) hash[a -

  • Java合并两个及以上有序链表的示例详解

    目录 题目一:合并两个有序链表 题目一思路 题目一完整代码 题目二:合并多个有序链表 题目二关键思路 题目二完整代码 题目一:合并两个有序链表 题目链接 题目一思路 设置两个指针,一个指针(t1)指向l1链表头,另外一个指针(t2)指向l2链表头. 首先判断l1和l2的第一个元素,谁小,谁就是最后要返回的链表的头节点,如果l1和l2的第一个元素相等,随便取哪个都可以. 这样,我们就设置好了要返回链表的头节点,假设头节点是head, 依次移动t1和t2指针,谁小,谁就接入进来.依次操作,直到两个链

  • java算法题解牛客BM99顺时针旋转矩阵示例

    目录 题目描述 解题思路 实践代码 解法1 解法2 题目描述 BM99 顺时针旋转矩阵 描述 有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度. 给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵. 数据范围:0<n<300,矩阵中的值满足0≤val≤1000 要求:空间复杂度 O(N^2),时间复杂度 O(N^2) 进阶:空间复杂度 O(1),时间复杂度 O(N^2) 示例1输入:[[1,2,3],[4,5,6],[7,8,9]],3返回值:[[7,4,1],[8,5

  • Java实现双链表的示例代码

    目录 一.双向链表是什么 二.具体方法实现 定义结点 下标访问异常 获取链表长度 打印链表 清空链表 头插法 尾插法 指定位置插入 查找元素 删除第一次出现的关键字 删除所有值为key的节点 三.完整代码 一.双向链表是什么 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. LinkedList底层就是一个双向链表,我们来实现一个双向链表. 这

随机推荐