【力扣hot100】1. 两数之和 49.字母异位词分组 128. 最长连续序列

在这里插入图片描述

目录

    • 1. 两数之和
      • 题目描述
      • 做题思路
      • 参考代码
    • 49.字母异位词分组
      • 题目描述
      • 做题思路
      • 参考代码
    • 128. 最长连续序列
      • 题目描述
      • 做题思路
      • 参考代码

1. 两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

提示:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

进阶: 你可以想出一个时间复杂度小于 O(n2) 的算法吗?

做题思路

使用HashMapkey为元素,value为下标

参考代码

package hot100;

import java.util.HashMap;
public class _0001_TwoSum {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();//key为数,value为下标
        for(int i = 0; i < nums.length; i++){
            int choose = nums[i];//当前元素
            int diff = target - choose;//diff为目标和与当前元素之差,即要找的另一个元素
            if(map.containsKey(diff)){//如果map中存在diff
                return new int[]{map.get(diff),i};//返回结果
            }
            map.put(choose, i);//否则添加元素
        }
        return new int[0];//返回空
    }
}

49.字母异位词分组

题目描述

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示:

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母

做题思路

使用HashMap,将所有字符串按照字典序排序,那么每一组字母异位词将排序成同一个字符串,key为排序后的字符串,value为所有符合条件的字母异位词

参考代码

package hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class _0049_GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();//key为字典序字符串,value为所有满足结果字符串集合
        for (String str : strs) {
            char[] chars = str.toCharArray();//字符串转化为字符数组
            Arrays.sort(chars);//排序
            String sortKeys = new String(chars);//将排序后的字符数组转回字符串
            if (map.containsKey(sortKeys)) {//如果map中有key
                map.get(sortKeys).add(str);//添加原字符串
            } else {//如果map中没有key
                List<String> s = new ArrayList<>();//新建List
                s.add(str);//添加原字符串
                map.put(sortKeys, s);//添加原字符串
            }
        }
        return new ArrayList<>(map.values());//打印map中所有values
    }
}

128. 最长连续序列

题目描述

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2:

输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9

提示:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

做题思路

每一个连续数列都存在头结点和尾结点,本题关键在于如何判断头尾节点。

参考代码

package hot100;

import java.util.HashSet;

public class _0128_LongestConsecutiveSequence {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int n : nums){
            set.add(n);
        }
        int count = 0;//计数
        int res = 0;//结果
        for(int n : set){
            if(!set.contains(n-1)){//如果当前元素n是头节点,那么n-1不在set中
                int curr = n;//指针
                count = 1;//计数
                //开始向后遍历
                while(set.contains(curr+1)){//如果当前元素n为中节点,那么n+1在set中
                    count++;//计数+1
                    curr++;//指针右移
                }
                //如果当前元素n为尾节点,那么n+1不在set中,即while循环跳出
                res = Math.max(res, count);//结果取最大值
            }
        }
        return res;
    }

}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/482621.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

子网掩码,网段,网关

IP地址、子网掩码、网段、网关【网络常识 2】_哔哩哔哩_bilibili 网关&#xff1a; 什么时候需要用到网关&#xff1a; 若目标IP在同一网段则可以直接通信不需要经过网关&#xff0c;否则需要。 怎么判断对方的ip是否与我在同一网段呢&#xff1f; 判断网络号是否相同。 电…

Android Studio 和 lombok 的版本适配、gradle依赖配置、插件安装及使用

文章目录 Intro注意事项Android Studio 和 lombok 的版本选择及下载下载链接 在 Android Studio 中安装一次 lombok 插件在每个 gradle 项目中添加 lombok 相关依赖(如要用到)使用ref Intro 用惯了 JavaMavenIDEA 开发后端服务&#xff0c;突然有一天用 JavaGradleAndroidStud…

【Flink】窗口实战:TUMBLE、HOP、SESSION

窗口实战&#xff1a;TUMBLE、HOP、SESSION 1.TUMBLE WINDOW1.1 语法1.2 标识函数1.3 模拟用例 2.HOP WINDOW2.1 语法2.2 标识函数2.3 模拟用例 3.SESSION WINDOW3.1 语法3.2 标识函数3.3 模拟用例 4.更多说明 在流式计算中&#xff0c;流通常是无穷无尽的&#xff0c;我们无法…

【PyQt】17.1-日历控件 不同风格的日期和时间、以及高级操作

日历控件puls版本 前言一、日历控件中不同风格的日期和时间1.1 代码1.2 注意事项格式设置m的大小写问题QTime和QDateTime的区别 1.3 运行结果 二、高级操作2.1 成倍调整2.2 下拉出日历2.3 事件函数2.4 获取设置的日期和时间 完整代码 前言 1、不同风格的日期和时间展示 2、高级…

Codeforces Round 930 (Div. 2)(A,B,C,D)

比赛链接 C是个交互&#xff0c;D是个前缀和加二分。D还是很难写的。 A. Shuffle Party 题意&#xff1a; 您将得到一个数组 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1​,a2​,…,an​ 。最初&#xff0c;每个 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n 对应 a i i a_ii…

深度学习十大算法之长短时记忆网络(LSTM)

一、长短时记忆网络&#xff08;LSTM&#xff09;的基本概念 长短时记忆网络&#xff08;LSTM&#xff09;是一种特殊类型的循环神经网络&#xff08;RNN&#xff09;&#xff0c;主要用于处理和预测序列数据的任务。LSTM由Hochreiter和Schmidhuber于1997年提出&#xff0c;其…

41-Vue-webpack基础

webpack基础 前言什么是webpackwebpack的基本使用指定webpack的entry和output 前言 本篇开始来学习下webpack的使用 什么是webpack webpack: 是前端项目工程化的具体解决方案。 主要功能&#xff1a;它提供了友好的前端模块化开发支持&#xff0c;以及代码压缩混淆、处理浏览…

海康威视-AIOT的业务转型

海康威视的转型和定位为智能物联网&#xff08;AIoT&#xff09;解决方案和大数据服务的提供商。 公司不仅仅聚焦于其核心的视频监控业务&#xff0c;而且正在积极拓展到新的技术领域和市场。通过专注于物联感知、人工智能、大数据等技术的创新&#xff0c;对未来技术发展方向的…

golang import引用项目下其他文件内函数

初始化项目 go mod init [module名字] go mod init project 项目结构 go mod 文件 代码 需要暴露给外界使用的变量/函数名必须大写 在main.go中引入&#xff0c;当前项目模块名/要引用的包名 package mainimport (// 这里的路径开头为项目go.mod中的module"project/…

微信小程序----猜数字游戏.

目标&#xff1a;简单猜字游戏&#xff0c;系统随机生成一个数&#xff0c;玩家可以猜8次&#xff0c;8次未猜对&#xff0c;游戏结束&#xff1b;未到8次猜对&#xff0c;游戏结束。 思路和要求&#xff1a; 创建四个页面&#xff0c;“首页”&#xff0c;“开始游戏”&#…

hadoop基本概念

一、概念 Hadoop 是一个开源的分布式计算和存储框架。 Hadoop 使用 Java 开发&#xff0c;所以可以在多种不同硬件平台的计算机上部署和使用。其核心部件包括分布式文件系统 (Hadoop DFS&#xff0c;HDFS) 和 MapReduce。 二、HDFS 命名节点 (NameNode) 命名节点 (NameNod…

STM32 | Systick定时器(第四天)

STM32 第四天 一、Systick定时器 1、定时器概念 定时器:是芯片内部用于计数从而得到时长的一种外设。 定时器定时长短与什么有关???(定时器定时长短与频率及计数大小有关) 定时器频率换算单位:1GHZ=1000MHZ=1000 000KHZ = 1000 000 000HZ 定时器定时时间:计数个数…

Django缓存(二)

一、视图缓存 Django的缓存可以设置缓存指定的视图,具体方式使用django.views.decorators.cache.cache_page, 方法有2种方式: 装饰器:以方法以装饰器的方式使用 from django.views.decorators.cache import cache_page@cache_page(60 * 15,cache="default") def…

CRC计算流程详解和FPGA实现

一、概念 CRC校验&#xff0c;中文翻译过来是&#xff1a;循环冗余校验&#xff0c;英文全称是&#xff1a;Cyclic Redundancy Check。是一种通过对数据产生固定位数的校验码&#xff0c;以检验数据是否存在错误的技术。 其主要特点是检错能力强、开销小&#xff0c;易于电路实…

【prompt六】MaPLe: Multi-modal Prompt Learning

1.motivation 最近的CLIP适应方法学习提示作为文本输入,以微调下游任务的CLIP。使用提示来适应CLIP(语言或视觉)的单个分支中的表示是次优的,因为它不允许在下游任务上动态调整两个表示空间的灵活性。在这项工作中,我们提出了针对视觉和语言分支的多模态提示学习(MaPLe),以…

“架构(Architecture)” 一词的定义演变历史(依据国际标准)

深入理解“架构”的客观含义&#xff0c;不仅能使IT行业的系统架构设计师提升思想境界&#xff0c;对每一个积极的社会行动者而言&#xff0c;也具有长远的现实意义&#xff0c;因为&#xff0c;“架构”一词&#xff0c;不只限于IT系统&#xff0c;而是指各类系统(包括社会系统…

python(django)之流程接口管理后台开发

1、在models.py中加入流程接口表和单一接口表 代码如下&#xff1a; from django.db import models from product.models import Product# Create your models here.class Apitest(models.Model):apitestname models.CharField(流程接口名称, max_length64)apitester model…

C#,图论与图算法,计算图(Graph)的岛(Island)数量的算法与源程序

1 孤岛数 给定一个布尔矩阵,求孤岛数。一组相连的1形成一个岛。例如,下面的矩阵包含5个岛: 在讨论问题之前,让我们先了解什么是连接组件。无向图的连通分量是一个子图,其中每两个顶点通过一条路径相互连接,并且不与子图外的其他顶点连接。 所有顶点相互连接的图只有一个…

java数据结构与算法基础-----字符串------正则表达式---持续补充中

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 目前校招的面试&#xff0c;经常会遇到各种各样的有关字符串处理的算法。掌…

【docker系列】深入理解 Docker 容器管理与清理

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…