代码随想录-算法训练营day06【有效的字母异位词、两个数组的交集、快乐数、两数之和】

本文主要是介绍代码随想录-算法训练营day06【有效的字母异位词、两个数组的交集、快乐数、两数之和】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  1. 专栏笔记:https://blog.csdn.net/weixin_44949135/category_10335122.html
第三章 哈希表part01今日任务 ● 哈希表理论基础 
● 242.有效的字母异位词 
● 349. 两个数组的交集 
● 202. 快乐数
● 1. 两数之和   详细布置 哈希表理论基础 建议:大家要了解哈希表的内部实现原理,哈希函数,哈希碰撞,以及常见哈希表的区别,数组,set 和map。  什么时候想到用哈希法,当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。  这句话很重要,大家在做哈希表题目都要思考这句话。 文章讲解:https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html  242.有效的字母异位词 建议: 这道题目,大家可以感受到 数组 用来做哈希表 给我们带来的遍历之处。 题目链接/文章讲解/视频讲解: https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html  349. 两个数组的交集 建议:本题就开始考虑 什么时候用set 什么时候用数组,本题其实是使用set的好题,但是后来力扣改了题目描述和 测试用例,添加了 0 <= nums1[i], nums2[i] <= 1000 条件,所以使用数组也可以了,不过建议大家忽略这个条件。 尝试去使用set。 题目链接/文章讲解/视频讲解:https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html  202. 快乐数 建议:这道题目也是set的应用,其实和上一题差不多,就是 套在快乐数一个壳子 题目链接/文章讲解:https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html  1. 两数之和 建议:本题虽然是 力扣第一题,但是还是挺难的,也是 代码随想录中 数组,set之后,使用map解决哈希问题的第一题。 建议大家先看视频讲解,然后尝试自己写代码,在看文章讲解,加深印象。 题目链接/文章讲解/视频讲解:https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html

目录

0242_有效的字母异位词

0349_两个数组的交集

0202_快乐数

0001_两数之和


0242_有效的字母异位词

int[] record = new int[26];
for (int i = 0; i < s.length(); i++) {
        record[s.charAt(i) - 'a']++; //并不需要记住字符a的ASCII,只要求出一个相对数值就可以了
}

import java.util.Arrays;class Solution0242 {public boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}char ss[] = s.toCharArray();Arrays.sort(ss);char tt[] = s.toCharArray();Arrays.sort(tt);for (int i = 0; i < ss.length; i++) {if (ss[i] != tt[i]) {return false;}}return true;}/*** 242. 有效的字母异位词 字典解法* 时间复杂度O(m+n) 空间复杂度O(1)*/public boolean isAnagram2(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 (int count : record) {if (count != 0) {//record数组如果有的元素不为零0,说明字符串s和t中,一定是谁多了字符或者谁少了字符。return false;}}return true;//record数组所有元素都为零0,说明字符串s和t是字母异位词}
}

0349_两个数组的交集

  • 取并集(Union):将两个集合中的所有元素合并在一起,去除重复项。
    • Set<Integer> unionSet = new HashSet<>(set1);
    • unionSet.addAll(set2);
  • 取差集(Difference):从第一个集合中移除与第二个集合相同的元素。
    • Set<Integer> differenceSet = new HashSet<>(set1);
    • differenceSet.removeAll(set2);
  • 取交集(Intersection):仅保留两个集合中共同存在的元素。
    • Set<Integer> intersectionSet = new HashSet<>(set1);
    • intersectionSet.retainAll(set2);

将结果集合转为数组:

  1. int res[] = set.stream().mapToInt(x -> x).toArray();
  2. int res[] = list.stream().mapToInt(Integer::intValue).toArray();
class Solution0349 {public int[] intersection1(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<>();Set<Integer> set2 = new HashSet<>();for (Integer i : nums1) {set1.add(i);}for (Integer i : nums2) {set2.add(i);}set1.retainAll(set2);int[] res = new int[set1.size()];int index = 0;for (Integer i : set1) {res[index++] = i;}return res;}public int[] intersection2(int[] nums1, int[] nums2) {HashSet<Integer> hashSet1 = new HashSet<>();for (int i = 0; i < nums1.length; i++) {hashSet1.add(nums1[i]);}HashSet<Integer> hashSet2 = new HashSet<>();for (int i = 0; i < nums2.length; i++) {hashSet2.add(nums2[i]);}ArrayList<Integer> list = new ArrayList<>();for (int x : hashSet1) {for (int y : hashSet2) {if (x == y) {list.add(x);}}}int res[] = list.stream().mapToInt(Integer::intValue).toArray();return res;}
}
class Solution0349_2 {//版本一:使用HashSetpublic int[] intersection(int[] nums1, int[] nums2) {if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {return new int[0];}Set<Integer> set1 = new HashSet<>();Set<Integer> resSet = new HashSet<>();//遍历数组1for (int i : nums1) {set1.add(i);}//遍历数组2的过程中判断哈希表中是否存在该元素for (int i : nums2) {if (set1.contains(i)) {resSet.add(i);}}//方法1:将结果集合转为数组return resSet.stream().mapToInt(x -> x).toArray();//方法2:另外申请一个数组存放setRes中的元素,最后返回数组int[] arr = new int[resSet.size()];int j = 0;for (int i : resSet) {arr[j++] = i;}return arr;}//版本二:使用Hash数组public int[] intersection2(int[] nums1, int[] nums2) {int[] hash1 = new int[1002];int[] hash2 = new int[1002];for (int i : nums1)hash1[i]++;for (int i : nums2)hash2[i]++;List<Integer> resList = new ArrayList<>();for (int i = 0; i < 1002; i++)if (hash1[i] > 0 && hash2[i] > 0)resList.add(i);int index = 0;int res[] = new int[resList.size()];for (int i : resList)res[index++] = i;return res;}
}

0202_快乐数

while ((n = execute(n)) != 1) {...}

import java.util.HashSet;
import java.util.Set;class Solution0202 {public boolean isHappy(int n) {int index = 0;while (index++ < 1000) {if (execute(n) == 1) {return true;}n = execute(n);}return false;}private int execute(int n) {int sum = 0;while (n != 0) {sum += (n % 10) * (n % 10);n /= 10;}return sum;}
}class Solution0202_2 {public boolean isHappy(int n) {int flag = 0;while (execute(n) != 1) {//n % 10 != n//System.out.println("n:" + n);n = execute(n);flag++;if (flag == 100000) {return false;}}return true;}public int execute(int n) {int len = (n + "").length();int sum = 0;while (len-- >= 0) {sum += (n % 10) * (n % 10);n /= 10;}//System.out.println("sum:" + sum);return sum;}
}class Solution0202_3 {public boolean isHappy(int n) {int flag = 0;while ((n = execute(n)) != 1) {flag++;if (flag == 100000) {return false;}}return true;}public int execute(int n) {int len = (n + "").length();int sum = 0;while (len-- >= 0) {sum += (n % 10) * (n % 10);n /= 10;}return sum;}
}class Solution0202_4 {public boolean isHappy(int n) {Set<Integer> record = new HashSet<>();while (n != 1 && !record.contains(n)) {record.add(n);n = getNextNumber(n);}return n == 1;}private int getNextNumber(int n) {int res = 0;while (n > 0) {int temp = n % 10;res += temp * temp;n = n / 10;}return res;}
}

0001_两数之和

本题其实有四个重点:

  1. 为什么会想到用哈希表
  2. 哈希表为什么用map
  3. 本题map是用来存什么的
  4. map中的key和value用来存什么的

把这四点想清楚了,本题才算是理解透彻了。

System.arraycopy() 是 Java 中用于数组复制的方法。它允许你从一个源数组复制一个指定范围的元素到目标数组的指定位置上。

方法签名如下所示:

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

参数解释:

  1. src:源数组。
  2. srcPos:源数组中的起始位置。
  3. dest:目标数组。
  4. destPos:目标数组中的起始位置。
  5. length:要复制的元素数量。

这个方法会将源数组 src 中从 srcPos 开始的 length 个元素复制到目标数组 dest 中,从 destPos 开始的位置开始存放。源数组和目标数组可以是同一个数组,但是复制的范围不可以重叠。

以下是一个示例用法:

int[] sourceArray = {1, 2, 3, 4, 5};
int[] destinationArray = new int[5];// 将源数组 sourceArray 的前三个元素复制到目标数组 destinationArray 中
System.arraycopy(sourceArray, 0, destinationArray, 0, 3);// 输出目标数组的内容
for (int i : destinationArray) {System.out.println(i); // 输出:1, 2, 3, 0, 0
}

这个例子将 sourceArray 中的前三个元素复制到 destinationArray 的起始位置,所以 destinationArray 中的前三个位置变成了 sourceArray 中的元素。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;class Solution {public int[] twoSum(int[] nums, int target) {int[] index = new int[2];for (int i = 0; i < nums.length; i++) {for (int j = 0; j < nums.length; j++) {if (nums[i] + nums[j] == target && i != j) {index[0] = i;index[1] = j;return index;}}}return index;}public int[] twoSum2(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {for (int j = 0; j < nums.length; j++) {if (nums[i] + nums[j] == target && i != j) {//System.out.println(i + " " + j);return new int[]{i, j};}}}return new int[]{0, 1};}//使用哈希表public int[] twoSum3(int[] nums, int target) {int[] res = new int[2];if (nums == null || nums.length == 0) {return res;}Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int temp = target - nums[i];//遍历当前元素,并在map中寻找是否有匹配的keyif (map.containsKey(temp)) {res[1] = i;res[0] = map.get(temp);break;}map.put(nums[i], i);//如果没找到匹配对,就把访问过的元素和下标加入到map中}return res;}//使用双指针public int[] twoSum4(int[] nums, int target) {int m = 0, n = 0, k, board = 0;int[] res = new int[2];int[] tmp1 = new int[nums.length];//备份原本下标的nums数组System.arraycopy(nums, 0, tmp1, 0, nums.length);//将nums排序Arrays.sort(nums);//双指针for (int i = 0, j = nums.length - 1; i < j; ) {if (nums[i] + nums[j] < target)i++;else if (nums[i] + nums[j] > target)j--;else if (nums[i] + nums[j] == target) {m = i;n = j;break;}}//找到nums[m]在tmp1数组中的下标for (k = 0; k < nums.length; k++) {if (tmp1[k] == nums[m]) {res[0] = k;break;}}//找到nums[n]在tmp1数组中的下标for (int i = 0; i < nums.length; i++) {if (tmp1[i] == nums[n] && i != k)res[1] = i;}return res;}
}

这篇关于代码随想录-算法训练营day06【有效的字母异位词、两个数组的交集、快乐数、两数之和】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/887679

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时