赞
踩
♥♥♥♥♥个人主页♥♥♥♥♥
♥♥♥♥♥数据结构练习题总结专栏♥♥♥♥♥
♥♥♥♥♥【数据结构练习题】堆——top-k问题♥♥♥♥♥
给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
这个题我们有两种方式来解决这个问题,一个就是用异或来解决这个问题还有就是用Set集合来解决这个问题,这里我们用Set集合来解决这个问题。
Set集合有一个特点就是具备查重性,我们就可以利用这个特点来解决这个问题
第一步:先遍历数组
第二步:判断当前Set集合有没有这个遍历的元素,没有则添加到这个Set集合中,有则删除Set集合中这个元素
第三步:当数组遍历完之后,Set集合中剩下的元素就是只出现过一次的元素。
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; }
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
上述描述了一堆文字,其实意思很简单就是复制一个与原链表大小规格,内容相同的链表即可。
这里我们需要用到Map中的key-value模型来解决这个问题
第一步:遍历原链表,并且同时创建以恶搞相同规格的链表,将原链表的结点和新链表的结点利用key-value模型的形式存储在Map中。
第二步:再遍历一次链表,通过Map中的get方法将新链表中的结点构成联系。
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); }
给你一个字符串 jewels 代表石头中宝石的类型,另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。
意思就是在石头中找宝石的个数。
本质上还是一个查重问题,我们可以用Set集合来解决这个问题
第一步:我们将宝石数组中的宝石通过遍历的方式放在Set集合中。
第二步:遍历石头数组,与Set集合中的宝石比较相同即计数器+1
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; }
旧键盘上坏了几个键,于是在敲一段文字的时候,对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字,请你列出肯定坏掉的那些键。
这还是一个Set查重问题。
第一步:遍历实际输出的字符串数组将其中的元素放入Set集合中
第二步:接着遍历期望输出的字符串数组与Set集合比较,不相同则放入一个新的Set集合中setBorken,相同则不需要放入。
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 处理多个 case String 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); } } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。