【数据结构练习题】Map与Set——1.只出过一次的数字2.复制带随机指针的链表3.宝石与石头4.坏键盘打字

本文主要是介绍【数据结构练习题】Map与Set——1.只出过一次的数字2.复制带随机指针的链表3.宝石与石头4.坏键盘打字,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述
♥♥♥♥♥个人主页♥♥♥♥♥
♥♥♥♥♥数据结构练习题总结专栏♥♥♥♥♥
♥♥♥♥♥【数据结构练习题】堆——top-k问题♥♥♥♥♥

文章目录

  • 1.只出过一次的数字
    • 1.1问题描述
    • 1.2思路分析
    • 1.3绘图分析
    • 1.4代码实现
    • 2.复制带随机指针的链表
    • 2.1问题描述
    • 2.2思路分析
    • 2.3绘图分析
    • 2.4代码实现
      • 3.宝石与石头
    • 3.1问题描述
    • 3.2思路分析
    • 3.3绘图分析
    • 3.4代码实现
        • 4.坏键盘打字
    • 4.1问题描述
    • 4.2思路分析
    • 4.3绘图分析
    • 4.4代码实现

1.只出过一次的数字

1.1问题描述

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

1.2思路分析

这个题我们有两种方式来解决这个问题,一个就是用异或来解决这个问题还有就是用Set集合来解决这个问题,这里我们用Set集合来解决这个问题。
Set集合有一个特点就是具备查重性,我们就可以利用这个特点来解决这个问题
第一步:先遍历数组
第二步:判断当前Set集合有没有这个遍历的元素,没有则添加到这个Set集合中,有则删除Set集合中这个元素
第三步:当数组遍历完之后,Set集合中剩下的元素就是只出现过一次的元素。

1.3绘图分析

在这里插入图片描述

1.4代码实现

public int singleNumber(int[] nums) {Set<Integer> set = new HashSet();for (int i = 0; i < nums.length; i++) {// 判断set集合中是否含有nums[i]if (!set.contains(nums[i])) {set.add(nums[i]);} else {set.remove(nums[i]);}}// 此时set集合中只剩下只出现了一次的元素for (int i = 0; i < nums.length; i++) {if (set.contains(nums[i])) {return nums[i];}}return -1;}

2.复制带随机指针的链表

2.1问题描述

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
上述描述了一堆文字,其实意思很简单就是复制一个与原链表大小规格,内容相同的链表即可。

2.2思路分析

这里我们需要用到Map中的key-value模型来解决这个问题
第一步:遍历原链表,并且同时创建以恶搞相同规格的链表,将原链表的结点和新链表的结点利用key-value模型的形式存储在Map中。
第二步:再遍历一次链表,通过Map中的get方法将新链表中的结点构成联系。

2.3绘图分析

在这里插入图片描述

2.4代码实现

  public Node copyRandomList(Node head) {Map<Node,Node> map = new HashMap<>();//1.第一次遍历原链表Node cur1 = head;while(cur1 != null) {//创建的新结点Node node = new Node(cur1.val);map.put(cur1,node);cur1 = cur1.next;}//2.第二次遍历原链表Node cur2 = head;while(cur2 != null) {map.get(cur2).next = map.get(cur2.next);map.get(cur2).random = map.get(cur2.random);cur2 = cur2.next;}return map.get(head);}

3.宝石与石头

3.1问题描述

给你一个字符串 jewels 代表石头中宝石的类型,另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。
意思就是在石头中找宝石的个数。

3.2思路分析

本质上还是一个查重问题,我们可以用Set集合来解决这个问题
第一步:我们将宝石数组中的宝石通过遍历的方式放在Set集合中。
第二步:遍历石头数组,与Set集合中的宝石比较相同即计数器+1

3.3绘图分析

在这里插入图片描述

3.4代码实现

 public int numJewelsInStones(String jewels, String stones) {Set<Character> set = new HashSet();int count = 0;for (int i = 0; i < jewels.length(); i++) {char ch = jewels.charAt(i);set.add(ch);}for (int i = 0; i < stones.length(); i++) {//比较char ch = stones.charAt(i);if(set.contains(ch)) {count++;}}return count;}
4.坏键盘打字

4.1问题描述

旧键盘上坏了几个键,于是在敲一段文字的时候,对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字,请你列出肯定坏掉的那些键。

4.2思路分析

这还是一个Set查重问题。
第一步:遍历实际输出的字符串数组将其中的元素放入Set集合中
第二步:接着遍历期望输出的字符串数组与Set集合比较,不相同则放入一个新的Set集合中setBorken,相同则不需要放入。

4.3绘图分析

在这里插入图片描述

4.4代码实现

import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str1 = in.nextLine();String str2 = in.nextLine();func(str1, str2);}}private static void func(String str1, String str2) {Set<Character> set = new HashSet<>();for (char s : str2.toUpperCase().toCharArray()) {set.add(s);}Set<Character> setBroken = new HashSet<>();for (char s : str1.toUpperCase().toCharArray()) {if (!set.contains(s) && !setBroken.contains(s)) {System.out.print(s);setBroken.add(s);}}}
}

这篇关于【数据结构练习题】Map与Set——1.只出过一次的数字2.复制带随机指针的链表3.宝石与石头4.坏键盘打字的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

Nginx指令add_header和proxy_set_header的区别及说明

《Nginx指令add_header和proxy_set_header的区别及说明》:本文主要介绍Nginx指令add_header和proxy_set_header的区别及说明,具有很好的参考价... 目录Nginx指令add_header和proxy_set_header区别如何理解反向代理?proxy

使用PyTorch实现手写数字识别功能

《使用PyTorch实现手写数字识别功能》在人工智能的世界里,计算机视觉是最具魅力的领域之一,通过PyTorch这一强大的深度学习框架,我们将在经典的MNIST数据集上,见证一个神经网络从零开始学会识... 目录当计算机学会“看”数字搭建开发环境MNIST数据集解析1. 认识手写数字数据库2. 数据预处理的

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》:本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v

通过Python脚本批量复制并规范命名视频文件

《通过Python脚本批量复制并规范命名视频文件》本文介绍了如何通过Python脚本批量复制并规范命名视频文件,实现自动补齐数字编号、保留原始文件、智能识别有效文件等功能,听过代码示例介绍的非常详细,... 目录一、问题场景:杂乱的视频文件名二、完整解决方案三、关键技术解析1. 智能路径处理2. 精准文件名