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

2024-04-09 08:44
文章标签 算法 随想录 代码 数组 有效 训练营 两个 交集 两数 字母 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。

相关文章

Java的栈与队列实现代码解析

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念（Stack）栈的实现代码队列（Queue）模拟实现队列(双链表实现)循环队列（循环数组
阅读更多...
Python实现特殊字符判断并去掉非字母和数字的特殊字符

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa
阅读更多...
Java数组初始化的五种方式

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化：简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化：灵活但需手动管理代
阅读更多...
使用Java将DOCX文档解析为Markdown文档的代码实现

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown（MD）因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析
阅读更多...
C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
shell编程之函数与数组的使用详解

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》：本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
使用Python实现全能手机虚拟键盘的示例代码

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景：会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作？今天我要分享的Pyth... 目录一、项目概述：不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求
阅读更多...
Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》：本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2