代码随想录算法训练营第六天| 242.有效字母的异位词、349.两个数组的交集、202快乐数、1.两数之和

news/2024/5/25 9:49:18/文章来源:https://blog.csdn.net/weixin_44041958/article/details/136654268

系列文章目录


目录

  • 系列文章目录
  • 242.有效的字母异位词
  • 349. 两个数组的交集
    • ①使用HashSet
    • ②使用Hash数组
  • 202. 快乐数
  • 1. 两数之和
    • ①暴力解法(时间复杂度不符合要求)
    • ②使用HashMap法


242.有效的字母异位词

这道题是数组在哈希表中的典型应用。

因为只有26个小写字母,且这26个元素是连续的,所以采用数组这种数据结构。将字符串的字母减去字母a得到的就是从02526个字母的下标索引。数组的值就是元素出现的次数,也就是遍历到这个元素,对应的数组值就++。这样就记录了第一个字符串中每个元素出现的次数。再遍历第二个字符串,让数组值--,最后判断数组值是否全为0即可。

class Solution {public boolean isAnagram(String s, String t) {int[] record = new int[26];for (int i = 0; i < s.length(); i++) {record[s.charAt(i) - 'a']++;// 并不需要记住字符a的ASCII,只要求出一个相对数值就可以了}for (int i = 0; i < t.length(); i++) {record[t.charAt(i) - 'a']--;}for (Integer i : record) {if(i!=0){// record数组如果有的元素不为零0,说明字符串s和t 一定是谁多了字符或者谁少了字符。return false;}}return true; // record数组所有元素都为零0,说明字符串s和t是字母异位词}
}

349. 两个数组的交集

①使用HashSet

将第一个数组放到Set中,然后看第二个数组的值有没有在里面出现,出现的话就记录。

剪枝:在已知不符合条件的情况下,剪枝避免做无效判断。因为遍历本质是在决策,决策是为了求得结果,已知结果的决策就没有必要进行了。

        //判断条件if(nums1==null||nums1.length==0||nums2==null||nums2.length==0){return new int[0];}
import java.util.HashSet;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int[] intersection(int[] nums1, int[] nums2) {//判断条件if(nums1==null||nums1.length==0||nums2==null||nums2.length==0){return new int[0];}HashSet<Integer> set1 = new HashSet<>();HashSet<Integer> set2 = new HashSet<>();//遍历数组1
/*        for (int i = 0; i < nums1.length; i++) {set1.add(nums1[i]);}*/for (int i : nums1) {set1.add(i);}//遍历数组2的过程中判断哈希表中是否存在该元素// ①如果加不进去,则说明该元素在第一个数组中存在// ②直接使用contains方法来查看集合中是否有该元素
/*        for (int i = 0; i < nums2.length; i++) {if (!set1.add(nums2[i])) {//①如果加不进去,则说明该元素在第一个数组中出现过set2.add(nums2[i]);}*/for (int i : nums2) {if (set1.contains(i)) {//②直接使用contains方法来查看集合中是否有该元素set2.add(i);}}
/*        //方法1:将结果集合转为数组return set2.stream().mapToInt(x -> x).toArray();*///方法2:另外申请一个数组存放setRes中的元素,最后返回数组int[] arr = new int[set2.size()];int i = 0;for (Integer setnum : set2) {arr[i++] = setnum;}return arr;}
}

在这里插入图片描述
Set 的常用方法:add:添加单个元素;size:获取元素个数。contains:查找元素是否存在;也可再次加入元素看能否加进去来判断元素是否存在。需要注意的是,SettoArray的方法,该方法是重写接口Collection的方法。可返回包含此集合中所有元素的数组。
在这里插入图片描述

但是转换成数组的元素类型是object,所以还是建议重新创建一个数组来存放Set集合中的值。

//方法1:将结果集合转为数组return set2.stream().mapToInt(x -> x).toArray();
//方法2:另外申请一个数组存放setRes中的元素,最后返回数组int[] arr = new int[set2.size()];int i = 0;for (Integer setnum : set2) {arr[i++] = setnum;}return arr;

②使用Hash数组

class Solution {                                                                             public int[] intersection(int[] nums1, int[] nums2) {                                    int[] hash1 = new int[1003];                                                         int[] hash2 = new int[1003];                                                         //nums1中出现的字母在hash1数组中做记录                                                            for (int i = 0; i < nums1.length; i++) {                                             hash1[nums1[i]]++;                                                               }                                                                                    //nums2中出现的字母在hash2数组中做记录                                                            for (int i = 0; i < nums2.length; i++) {                                             hash2[nums2[i]]++;                                                               }                                                                                    //创建一个实现List集合的实现类来存相同元素,                                                            // ArrayList效率比Vector高,改查效率比LinkedList高                                              ArrayList<Integer> resList = new ArrayList<>();                                      for (int i = 0; i < hash1.length; i++) {                                             if (hash1[i] > 0 && hash2[i] > 0) {//如果相同下标位置值都大于0,说明元素有交集                       resList.add(i);                                                              }                                                                                }                                                                                    //方法1:将结果集合转为数组                                      //return resList.stream().mapToInt(x -> x).toArray();//方法2:另外申请一个数组存放setRes中的元素,最后返回数组                    int[] arr = new int[resList.size()];                 int index = 0;                                       for (Integer i : resList) {                          arr[index++] = i;                                }                                                    return arr;                                                                                                                }                                                                                        

在这里插入图片描述
toArray方法是重写接口Collection的方法,故ArrayList也能调用toArray方法。

//方法1:将结果集合转为数组                                      return resList.stream().mapToInt(x -> x).toArray();
//方法2:另外申请一个数组存放setRes中的元素,最后返回数组                    int[] arr = new int[resList.size()];                 int index = 0;                                       for (Integer i : resList) {                          arr[index++] = i;                                }                                                    return arr;

202. 快乐数

①当不知道一个数是几位数时,求各个位上的平方和的方法要记住。就取这个数的个位(模,即%10),然后将这个数/10,再求个位,while循环,判断的条件是这个数>0

        int sum = 0;while (n > 0) {int temp = n % 10;//得到末位数sum += temp * temp;n = n / 10;//缩小一位}

②主方法isHappy中退出循环需要两个条件①n1。②集合中已有该元素。故最后在返回值时需return n == 1;来判断当退出循环时是否是满足第①条件退出的。

class Solution {public boolean isHappy(int n) {HashSet<Integer> set = new HashSet<>();/*       while (n != 1) {if (!(set.add(n))) {//加过集合的元素再加就为falsereturn false;}n = getNextNumber(n);}return true;*///退出该循环有两个条件:①n为1②集合中已有该元素while (n != 1 && !set.contains(n)) {set.add(n);n = getNextNumber(n);}return n == 1;}private int getNextNumber(int n) {int sum = 0;while (n > 0) {int temp = n % 10;//得到末位数sum += temp * temp;n = n / 10;//缩小一位}return sum;}
}

1. 两数之和

①暴力解法(时间复杂度不符合要求)

class Solution {public int[] twoSum(int[] nums, int target) {//暴力解法for (int i = 0; i < nums.length; i++) {for (int j = i+1; j < nums.length; j++) {if(nums[i]==target-nums[j]){return new int[]{i,j};}}}return new int[0];}
}

在这里插入图片描述

②使用HashMap法

Mapkey值有没有出现过的判断方法:containsKey()
剪枝(自己没写),若数组为null或者长度为0则直接返回退出:

        //剪枝(自己没写)if (nums == null || nums.length == 0) {return res;}
import java.util.HashMap;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int[] twoSum(int[] nums, int target) {//使用HashMap法int[] res = new int[2];//只创建一个数组(自己创建了两个数组)//剪枝(自己没写)if (nums == null || nums.length == 0) {return res;}HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int temp = target - nums[i];// 遍历当前元素,并在map中寻找是否有匹配的keyif (map.containsKey(temp)) {//return new int[]{i, map.get(temp)};res[0] = i;res[1] = map.get(temp);return res;}map.put(nums[i], i); // 如果没找到匹配对,就把访问过的元素和下标加入到map中}//return new int[0];return res;}
}
//leetcode submit region end(Prohibit modification and deletion)

在这里插入图片描述


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

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

相关文章

Acer宏碁非凡Swift SFG16-71工厂模式原厂Win11系统,预装OEM系统恢复开箱状态

宏基笔记本电脑SFG16-71原装出厂Windows11系统安装工厂包下载&#xff0c;带恢复重置功能 链接&#xff1a;https://pan.baidu.com/s/1JK02kBbwKG_cIBNlEOzrOw?pwdzdfm 提取码&#xff1a;zdfm 原装工厂包系统自带所有驱动、Office办公软件、出厂时自带主题壁纸图片、系统…

伪分布式Spark集群搭建

一、软件环境 软 件 版 本 安 装 包 VMware虚拟机 16 VMware-workstation-full-16.2.2-19200509.exe SSH连接工具 FinalShell Linux OS CentOS7.5 CentOS-7.5-x86_64-DVD-1804.iso JDK 1.8 jdk-8u161-linux-x64.tar.gz Spark 3.2.1 spark-3.2.1-bin-…

STM32/GD32——I2C通信协议

芯片选型 Ciga Device — GD32F470系列 通讯规则 I2C协议&#xff08;或称IIC&#xff09;是由飞利浦&#xff08;现在的恩智浦半导体&#xff09;公司开发的一种通用的总线协议。它使用两根线&#xff08;时钟线和数据线&#xff09;来传输数据&#xff0c;支持多个设备共享…

如何用postman进行http接口测试?

HTTP的接口测试工具有很多&#xff0c;可以进行http请求的方式也有很多&#xff0c;但是可以直接拿来就用&#xff0c;而且功能还支持的不错的&#xff0c;我使用过的来讲&#xff0c;还是postman比较上手。 优点&#xff1a; 1、支持用例管理 2、支持get、post、文件上传、…

python 实现阿里云OSS文件上传

因为我们出口的带宽限制&#xff0c;测试经常找我给他上传个包到阿里云的对象存储&#xff0c;虽然传起来也不是很费事&#xff0c;但是出于运维的职业素养&#xff0c;特意写了一个自动上传的接口&#xff0c;代码如下&#xff1a; # -*- coding: UTF-8 -*- from flask imp…

docker-swarm集群管理命令

为什么选择swarm集群&#xff1f; 灵魂疑问&#xff1a;同样是集群&#xff0c;为什么选择docker swarm&#xff0c;而不不选择k8s或者k3s&#xff1f; 我的需求场景&#xff1a;不想直接用docker或者java -jar直接跑&#xff0c;修改前是使用java -jar方式&#xff0c;这两种…

java019 - Java内部类

1、内部类概述 1.1 内部类访问特点 内部类可以访问外部类的成员&#xff0c;包括私有外部类要访问内部类的成员&#xff0c;必须创建对象 代码&#xff1a; outer类&#xff1a;inner为内部类 2、成员内部类 2.1 成员内部类 代码&#xff1a; 外部类&#xff1a; 测试类中…

Linux系统安装APITable智能表格并结合内网穿透实现公网访问本地服务

文章目录 前言1. 部署APITable2. cpolar的安装和注册3. 配置APITable公网访问地址4. 固定APITable公网地址 前言 vika维格表作为新一代数据生产力平台&#xff0c;是一款面向 API 的智能多维表格。它将复杂的可视化数据库、电子表格、实时在线协同、低代码开发技术四合为一&am…

honle电源维修UV电源控制器维修EVG EPS60

好乐UV电源控制器维修&#xff1b;honle控制器维修&#xff1b;UV电源维修MUC-Steuermodul 2 LΛmpen D-82166 主要维修型号&#xff1a; EVG EPS 60/120、EVG EPS 100、EVG EPS200、EVG EPS 220、EVG EPS 340、EVG EPS40C-HMI、EVG EPS60 HONLE好乐uv电源维修故障包括&#…

【string一些函数用法的补充】

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言 string类对象的修改操作 我们来看 c_str 返回c格式的字符串的操作&#xff1a; 我们来看 rfind 和 substr 的操作&#xff1a; string类非成员函数 我们来看 r…

第五十五天| 583. 两个字符串的删除操作、72. 编辑距离

Leetcode 583. 两个字符串的删除操作 题目链接&#xff1a;583 两个字符串的删除操作 题干&#xff1a;给定两个单词 word1 和 word2 &#xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 思考&#xff1a;动态规划。本题中…

WebPack自动吐出脚本

window.c c; window.res ""; window.flag false;c function (r) {if (flag) {window.res window.res "${r.toString()}" ":" (e[r] "") ",";}return window.c(r); }代码改进了一下&#xff0c;可以过滤掉重复的方…

【Java并发知识总结 | 第二篇】乐观锁和悲观锁详讲

文章目录 2.乐观锁和悲观锁详讲2.1悲观锁2.2乐观锁2.3如何实现乐观锁2.3.1版本号机制2.3.2CAS算法2.3.3CAS底层 2.4乐观锁存在的问题2.4.1ABA问题&#xff08;1&#xff09;问题描述&#xff08;2&#xff09;解决 2.4.2循环时间长、开销大2.4.3只能保证一个共享变量的原子操作…

Remove Prefix

题目链接&#xff1a;Problem - B - Codeforces 解题思路&#xff1a; 从最后开始遍历&#xff0c;用map记录每个数出现的次数&#xff0c;再定义一个num记录遍历的次数&#xff0c;要是没超过1&#xff0c;次数加一&#xff0c;超过就结束循环&#xff0c;输出数组长度减去nu…

新 树莓派4B 温湿度监测 基于debian12的树莓派OS

前言 本文旨在完成通过外接温湿度传感器至树莓派使得树莓派不断记录并存储温湿度数据 这个领域有很多文章&#xff0c;但是部分文章已经缺乏了时效性&#xff0c;在最新系统不适用&#xff0c;本文目前适用 硬件 硬件连接 温湿度传感器常选用DHT11和DHT22&#xff0c;淘宝…

maven打包把所有依赖的jar copy到一个文件夹

在maven项目中&#xff0c;是使用依赖坐标来引入jar包&#xff0c;在引入jar包的时候&#xff0c;maven也会默默的帮助我们导入这个jar包所依赖的jar包。 但是当我们打包项目使用jar包运行的时候&#xff0c;往往会出现缺少jar的情况&#xff1a; 如果我们一个一个添加缺少的…

基于单片机的恒压供水控制器设计

摘 要 随着我国现代化的进程不断加快&#xff0c;城市居民生活水平不断提高&#xff0c;随之而来的是房屋的翻新和重建&#xff0c;但建筑层数的不断增高&#xff0c;使得供水所需压力不断提高&#xff0c;若建筑设计时对压力判断不足&#xff0c;会导致供水时无法供应到高楼层…

Retrofit

1.导入依赖 //Retrofit 核心库implementation("com.squareup.retrofit2:retrofit:2.9.0")//响应数据自动序列化//JSONimplementation("com.squareup.retrofit2:converter-gson:2.9.0")//String类型implementation("com.squareup.retrofit2:converter…

技术派整合MyBatis-Plus

Mybatis-Plus大家都熟悉了吧&#xff1f;是一个Mybatis的增强&#xff0c;提供了一些额外功能&#xff0c;比如条件构造器、分页插件、代码生成器等以便我们更专注于业务&#xff0c;而不是SQL语句的编写 官方教程&#xff1a;简介 | MyBatis-Plus 整合MyBatis-Plus 非常简单…

ThreadLocal基本原理

ThreadLocal基本原理 一、定义 ThreadLocal是java中所提供的线程本地存储机制&#xff0c;可以利用改机制将数据缓存在线程内部&#xff0c;该线程可以在任意时刻、任意方法中获取数据 二、底层原理 ThreadLocal底层是通过ThreadLocalMap来实现的&#xff0c;每个Thread对象中…