代码随想录之哈希表(力扣题号)
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. 有效的字母异位词 直接用数组模拟哈希表 只有小写字母,开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证书?
为了保证客户与交易伙伴之间数据传输的安全性,AS2传输协议中,通常会通过一对数字证书对传输数据进行签名和加密。但是证书是有有效期的,在证书到期之前,需要贸易双方及时更换新的证书。 在更新证书时,由于客户通常是和…...

辽宁千圣文化:抖音店铺怎么做二次优化?
抖音商品卡订单是指永华在抖音、抖音极速版,通过直播的方式出现短视频页面商品卡之后,直接成交商品详情页直接成交后的订单,那么跟着辽宁千圣文化小编来一起看看吧!一.与政策有关1.什么是「商品卡订单」?用户通过抖音、…...
检测js代码中可能导致内存泄漏的工具
JavaScript 中闭包等问题可能导致内存泄漏,因为闭包中引用的变量不会被垃圾回收器自动释放。以下是一些可以用来检测 JavaScript 代码中可能导致内存泄漏的工具: 1、Chrome 开发者工具 Chrome 开发者工具中有一个 Heap Profiler 工具,可以帮…...
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 版本中,我们推出了分区表编辑器和 NVS 分区编辑器功能,优化现有调试器的配置功能并修复多项 Bug ,进一步为用户提升了插件质量以及稳定性。 用户可以点此获取最新版本。 • 若您的设备为 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或者持有锁的线程挂掉没有释放锁时,该锁不会被释放并且会一直占用,这个时候就使用DEL命令手动删除。 问题解决 v1.3.1版本通过key的ttl解决了这个问题,关键加锁逻辑改为了…...
go并发之美·多个channel合并/多个数据流合并
多个数据流(来自于不同channel)合并为一个流。 一般用于多个相同性质来源的数据进行合并为一处进行统一处理。 目录 背景 实现赖着不走 变个花样:学成出师 背景 最近在重温武侠剧,无意间想到了一些情形然后手痒,想…...
数据库多租户实现三种方式
1960年,许多公司需要使用更多的运算资源,向持有Mainframe的供应商租用运算资源。与此同时,Mainframe的供应商会根据用户登录系统时输入的数据匹配ID,利用ID来计算运算的资源使用量,包含CPU,存储器ÿ…...

单协议 2.4GHz CC2651R31T0RGZR/CC2651R31T0RKPR无线MCU 802.15.4,蓝牙5.2
CC2651R31T0RGZR描述:具有 352KB 闪存的 SimpleLink 32 位 Arm Cortex-M4 单协议 2.4GHz 无线 MCU 48-VQFN -40C ~ 105C48QFN(明佳达电子)【介绍】CC2651R3器件是一款单协议 2.4 GHz 无线微控制器 (MCU),支持以下协议:…...

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

在找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 有安全缺陷,所以Windows Vist…...
SOC计算方法:电流积分+开路电压
最近小猿在学习soc的计算方法,soc的估算方法大致有五种:电流积分法、开路电压法、阻抗法、智能估算法、状态观测器。今天先给大家介绍前两种方法。 什么是SOC 电池的状态(State of Charge,SOC)是电池能够提供的电荷总…...
linux mysql启动报错处理方案
启动命令: systemctl start mysqld 一、关闭selinux setenforce 0 二、...

Qt配置VS的编译环境(以MSVC2015 64bit为例)
目录 一、原因 二、VS2015安装 三、配置套件(Kits) 一、原因 很多时候,由于VS版本切换,需要从高版本切换到低版本,或者从低版本升级到高版本,例如VS2019到VS2015,或者VS2010到VS2015。 以VS2…...
iOS 9.3.5越狱环境安装配置
前言 家里有几个iOS设备,iTouch,iPad,都老旧了,正好弄来搭建开发环境。 目标:在iOS越狱环境上搭建基本的软件,将它变成小型Unix服务器和一个能开发iOS应用的环境。 什么是iOS越狱(iOS Jailbre…...

mac电脑解决Error: command failed: npm install --loglevel error --legacy-peer-deps
使用vue create xxx创建vue3项目的时候报错。 解决步骤: 1.sudo npm cache clean --force 2.再次创建就可以成功 补充:网上搜到很多方法,都尝试失败,因为遇到需要打开.vuerc,.npmrc的情况,记录一下怎样找到文件 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,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...

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

DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

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

对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
在鸿蒙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️⃣ 成功效果。…...