当前位置: 首页 > news >正文

代码随想录之哈希表(力扣题号)

242. 有效的字母异位词

在这里插入图片描述
直接用数组模拟哈希表
只有小写字母,开26的数组就可以了

class Solution {public boolean isAnagram(String s, String t) {//24-28int[] hash = new int[26];Arrays.fill(hash,0);for(int i=0;i<s.length();i++){hash[s.charAt(i)-'a']++;}for(int i=0;i<t.length();i++){hash[t.charAt(i)-'a']--;}for(int i=0;i<hash.length;i++){if(hash[i]!=0) return false;}return true;}
}

49. 字母异位词分组

在这里插入图片描述
思路也是用hashmap,但是java的操作没有很熟练,遇到很多问题,最后看了题解还是没能一次性写完,中间还看了两次,之后需要再练习几次

class Solution {public List<List<String>> groupAnagrams(String[] strs) {//01-29Map<String, List<String>> mp= new HashMap<>();      for(int i=0;i<strs.length;i++){char[] arr = strs[i].toCharArray();Arrays.sort(arr);String key = new String(arr);List<String> list = mp.getOrDefault(key,new ArrayList<String>());list.add(strs[i]);mp.put(key,list);}return new ArrayList<List<String>>(mp.values());}
}

时间复杂度:
O(nklogk),其中 n 是 strs 中的字符串的数量,k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串,对于每个字符串,需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表,因此总时间复杂度是 O(nklogk)。

空间复杂度:O(nk),其中 n 是 strs中的字符串的数量,k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。

15 三数之和

在这里插入图片描述
在这里插入图片描述

这题和之前牛客做过的一样,还是一样的思路:在两数之和的基础上遍历,然后用set去重,这题不要求输出结果也排序。但是这题的数据范围更大,按照之前的写法会超时,所以加了个排序,然后如果是重复的数字就跳过遍历。

class Solution {public List<List<Integer>> threeSum(int[] nums) {//57-40Arrays.sort(nums);List<List<Integer>> res= new ArrayList<List<Integer>>();List<List<Integer>> ress= new ArrayList<List<Integer>>();for(int i=0;i<nums.length;i++){int target = -nums[i];if(i>0&&nums[i]==nums[i-1]) continue;//跳过遍历,否则会超时Map<Integer,Integer> mp = new HashMap<>();for(int j = i+1;j<nums.length;j++){if(mp.containsKey(nums[j])){List<Integer> row = new ArrayList<>();row.add(nums[i]);row.add(target-nums[j]);row.add(nums[j]);row.sort((a,b)->a-b);  res.add(row);}mp.put(target-nums[j],j);              }}Set<List<Integer>> s = new HashSet<List<Integer>>();for(int i=0;i<res.size();i++){s.add(res.get(i));}for( List<Integer> r:s){ress.add(r);}return ress;}
}

但是这样还是三重循环,时间复杂度还是N的三次方。
可以继续改进:当a+b+c=0的时候,第二层b’>b,要让条件满足的c‘一定<c,所以可以让第三层指针从右往左,和第二层的指针合并为一层,将时间复杂度降为O(N^2)

class Solution {public List<List<Integer>> threeSum(int[] nums) {//57-40Arrays.sort(nums);List<List<Integer>> res= new ArrayList<List<Integer>>();List<List<Integer>> ress= new ArrayList<List<Integer>>();for(int i=0;i<nums.length-2;i++){int target = -nums[i];if(i>0&&nums[i]==nums[i-1]) continue;Map<Integer,Integer> mp = new HashMap<>();int left = i+1;int right = nums.length-1;while(left<right){if(nums[left]+nums[right]<target) left++;else if(nums[left]+nums[right]>target) right--;else{while(left + 1 < right && nums[left] == nums[left + 1])//去重left++;while(right - 1 > left && nums[right] == nums[right - 1])//去重right--;List<Integer> row = new ArrayList<>();row.add(nums[i]);row.add(nums[left]);row.add(nums[right]);res.add(row);left++;right--;}}                         }return res;}
}

18 四数之和

在这里插入图片描述
在这里插入图片描述
和三数之和的思路一样,就是多了一层循环,但是四数有一个坑点在于用int会溢出,要转换成long

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {//47-04List<List<Integer>> res = new ArrayList<List<Integer>>();Arrays.sort(nums);for(int i=0;i<nums.length-3;i++){if(i>0&&nums[i]==nums[i-1]) continue;for(int j = i+1;j<nums.length-2;j++){if(j>i+1&&nums[j]==nums[j-1]) continue;int left = j+1;int right = nums.length-1;while(left<right){//注意要转换成long,否则会溢出long sum = (long)nums[i]+(long)nums[j]+(long)nums[left]+(long)nums[right];if(sum>target) right--;else if(sum<target) left++;else{List<Integer> tmp = new ArrayList<Integer>();tmp.add(nums[i]);tmp.add(nums[j]);tmp.add(nums[left]);tmp.add(nums[right]);res.add(tmp);//可以用一句解决//res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while(left<right&&nums[left+1]==nums[left]) left++;while(left<right&&nums[right-1]==nums[right]) right--;left++;right--;}}}}return res;}
}

相关文章:

代码随想录之哈希表(力扣题号)

242. 有效的字母异位词 直接用数组模拟哈希表 只有小写字母&#xff0c;开26的数组就可以了 class Solution {public boolean isAnagram(String s, String t) {//24-28int[] hash new int[26];Arrays.fill(hash,0);for(int i0;i<s.length();i){hash[s.charAt(i)-a];}for(i…...

如何在知行之桥EDI系统中定时自动更换交易伙伴AS2证书?

为了保证客户与交易伙伴之间数据传输的安全性&#xff0c;AS2传输协议中&#xff0c;通常会通过一对数字证书对传输数据进行签名和加密。但是证书是有有效期的&#xff0c;在证书到期之前&#xff0c;需要贸易双方及时更换新的证书。 在更新证书时&#xff0c;由于客户通常是和…...

辽宁千圣文化:抖音店铺怎么做二次优化?

抖音商品卡订单是指永华在抖音、抖音极速版&#xff0c;通过直播的方式出现短视频页面商品卡之后&#xff0c;直接成交商品详情页直接成交后的订单&#xff0c;那么跟着辽宁千圣文化小编来一起看看吧&#xff01;一.与政策有关1.什么是「商品卡订单」&#xff1f;用户通过抖音、…...

检测js代码中可能导致内存泄漏的工具

JavaScript 中闭包等问题可能导致内存泄漏&#xff0c;因为闭包中引用的变量不会被垃圾回收器自动释放。以下是一些可以用来检测 JavaScript 代码中可能导致内存泄漏的工具&#xff1a; 1、Chrome 开发者工具 Chrome 开发者工具中有一个 Heap Profiler 工具&#xff0c;可以帮…...

linux和centos读写日期到文件并对日期进行比较

#!/bin/bash adate -d "${a}" %s #必须用数字 %s是取时间戳秒数 ddate -d "${c}" %s echo m$(($a - $d)) #必须2个小括号 a1date %s echo $a1 sleep 2 b1date %s echo $(($a1 - $b1)) #必须2个小括号 if [ $a1 -eq $b1 ];then #必须有空格 echo "…...

Espressif-IDE v2.8.0 新增功能及开发方向

在乐鑫最近发布的 Espressif-IDE 2.8.0 版本中&#xff0c;我们推出了分区表编辑器和 NVS 分区编辑器功能&#xff0c;优化现有调试器的配置功能并修复多项 Bug &#xff0c;进一步为用户提升了插件质量以及稳定性。 用户可以点此获取最新版本。 • 若您的设备为 Windows 系统…...

C++学习笔记之基础

目录前言一.零碎知识点二.C核心2.1.内存分区2.2.引用2.3.函数2.4.类和对象2.4.1.对象的初始化和清理2.4.2.构造函数和析构函数2.4.3.构造函数的分类和调用2.4.4.拷贝构造函数的调用时机2.4.5.深拷贝与浅拷贝2.4.6.初始化列表2.4.7.类对象作为类的成员2.4.8.静态成员2.4.9.C对象…...

博弈论小课堂:零和博弈(找到双方的平衡点)

文章目录 引言I 零和博弈1.1 零和博弈的策略1.2 博弈类型1.3 找到平衡点(equilibrium)II 多人博弈的投篮问题2.1 比赛规则2.2 零和博弈的计算引言 从概率论延伸出来的课题——博弈论,博弈论中最典型的两大类博弈,是“零和博弈”与“非零和博弈”。博弈论所研究的最优化问题…...

Redisson 分布式锁(基于v1.3.1)

Redisson 分布式锁 v1.0.0版本问题 v1.0.0版本的实现在持有锁的JVM或者持有锁的线程挂掉没有释放锁时&#xff0c;该锁不会被释放并且会一直占用&#xff0c;这个时候就使用DEL命令手动删除。 问题解决 v1.3.1版本通过key的ttl解决了这个问题&#xff0c;关键加锁逻辑改为了…...

go并发之美·多个channel合并/多个数据流合并

多个数据流&#xff08;来自于不同channel&#xff09;合并为一个流。 一般用于多个相同性质来源的数据进行合并为一处进行统一处理。 目录 背景 实现赖着不走 变个花样&#xff1a;学成出师 背景 最近在重温武侠剧&#xff0c;无意间想到了一些情形然后手痒&#xff0c;想…...

数据库多租户实现三种方式

1960年&#xff0c;许多公司需要使用更多的运算资源&#xff0c;向持有Mainframe的供应商租用运算资源。与此同时&#xff0c;Mainframe的供应商会根据用户登录系统时输入的数据匹配ID&#xff0c;利用ID来计算运算的资源使用量&#xff0c;包含CPU&#xff0c;存储器&#xff…...

单协议 2.4GHz CC2651R31T0RGZR/CC2651R31T0RKPR无线MCU 802.15.4,蓝牙5.2

CC2651R31T0RGZR描述&#xff1a;具有 352KB 闪存的 SimpleLink 32 位 Arm Cortex-M4 单协议 2.4GHz 无线 MCU 48-VQFN -40C ~ 105C48QFN&#xff08;明佳达电子&#xff09;【介绍】CC2651R3器件是一款单协议 2.4 GHz 无线微控制器 (MCU)&#xff0c;支持以下协议&#xff1a;…...

【项目精选】基于struts+hibernate的采购管理系统

点击下载 javaEE采购管理系统 本系统是一个独立的系统&#xff0c;用来解决企业采购信息的管理问题。采用JSP技术构建了一个有效而且实用的企业采购信息管理平台&#xff0c;目的是为高效地完成对企业采购信息的管理。经过 对课题的深入分析&#xff0c;采购系统需实现以下功能…...

在找docker命令和部署?看这一篇文章就够了。

一、docker 常用命令 docker ps -a #查看所有容器 docker images #查看所有images docker search rabbitmq #搜索rabbitmq docker pull rabbitmq #拉去rabbitmq docker run -id --namemy_rabbitmq -p 5672:5672 -p 15672:15672 rabbitmq # 创建一个容器并启动 docker exec -it…...

NTLM协议原理分析

LM Hash 和 NTLM Hashwindows用户的密码以哈希的形式保存在SAM文件中“%SystemRoot%\system32\config\SAM”。域用户的密码以哈希的形式保存在域控的 NTDS.dit 文件中。 密码的哈希值格式如下用域名:uid:LM哈希:NTLM哈希:::由于LM Hash 有安全缺陷&#xff0c;所以Windows Vist…...

SOC计算方法:电流积分+开路电压

最近小猿在学习soc的计算方法&#xff0c;soc的估算方法大致有五种&#xff1a;电流积分法、开路电压法、阻抗法、智能估算法、状态观测器。今天先给大家介绍前两种方法。 什么是SOC 电池的状态&#xff08;State of Charge&#xff0c;SOC&#xff09;是电池能够提供的电荷总…...

linux mysql启动报错处理方案

启动命令&#xff1a; systemctl start mysqld 一、关闭selinux setenforce 0 二、...

Qt配置VS的编译环境(以MSVC2015 64bit为例)

目录 一、原因 二、VS2015安装 三、配置套件&#xff08;Kits&#xff09; 一、原因 很多时候&#xff0c;由于VS版本切换&#xff0c;需要从高版本切换到低版本&#xff0c;或者从低版本升级到高版本&#xff0c;例如VS2019到VS2015&#xff0c;或者VS2010到VS2015。 以VS2…...

iOS 9.3.5越狱环境安装配置

前言 家里有几个iOS设备&#xff0c;iTouch&#xff0c;iPad&#xff0c;都老旧了&#xff0c;正好弄来搭建开发环境。 目标&#xff1a;在iOS越狱环境上搭建基本的软件&#xff0c;将它变成小型Unix服务器和一个能开发iOS应用的环境。 什么是iOS越狱&#xff08;iOS Jailbre…...

mac电脑解决Error: command failed: npm install --loglevel error --legacy-peer-deps

使用vue create xxx创建vue3项目的时候报错。 解决步骤&#xff1a; 1.sudo npm cache clean --force 2.再次创建就可以成功 补充&#xff1a;网上搜到很多方法&#xff0c;都尝试失败&#xff0c;因为遇到需要打开.vuerc,.npmrc的情况&#xff0c;记录一下怎样找到文件 1. 尝…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...