Java数据结构中的Map与Set该怎么理解
这篇文章主要为大家分析了Java数据结构中的Map与Set该怎么理解的相关知识点,内容详细易懂,操作细节合理,具有一定参考价值。如果感兴趣的话,不妨跟着跟随小编一起来看看,下面跟着小编一起深入学习"Java数据结构中的Map与Set该怎么理解"的知识吧。
①只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
输入: [2,2,1]
输出: 1
首相我们可能会想到用位运算直接解决,但我们也可以用hash色条解决。
public int singleNumber(int[] nums) { int single = 0; for (int num : nums) { single ^= num; } return single; }
hashset也已轻松解决这个问题,将整个数组中的元素放入set,因为只出现一次的数字只有一次,所以我们将多次出现相同的数字移除
public int singleNumber(int[] nums){ HashSetset = new HashSet<>(); for (int i = 0; i < nums.length; i++){ if (set.contains(nums[i])){ set.remove(nums[i]); }else { set.add(nums[i]); } } for (int i = 0; i < nums.length; i++){ if (set.contains(nums[i])){ return nums[i]; } } return -1; }
②宝石与石头
给你一个字符串 jewels 代表石头中宝石的类型,另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。
字母区分大小写,因此 "a"
和 "A"
是不同类型的石头。
输入:jewels = "aA", stones = "aAAbbbb"
输出:3
这道题和第一道题一样,这里是统计不同的个数。因为要区分大小写,所以我们将小写转大写,不影响我们做出判断
public int numJewelsInStons(String jewels,String stons){ stons.toUpperCase(Locale.ROOT).toCharArray(); HashSetset = new HashSet<>(); for (int i = 0; i < jewels.length(); i++){ set.add(jewels.charAt(i)); } int count = 0; for (char ch:stons.toCharArray()) { if(set.contains(ch)){ count++; } } return count; }
③坏键盘打字
旧键盘上坏了几个键,于是在敲一段文字的时候,对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字,请你列出肯定坏掉的那些键。
输入
7_This_is_a_test
_hs_s_a_es
输出
7TI
这道题我们要分两个set,一个setActual记录真实打出的字母,一个setBroken统计坏掉的字母,判断条件是符合的字母既不是包含setActual中已经存在的,也不是setActual与setBroken相同的字母。主要是同时对比setActual与setBroken。
public static void main(String[] args) { Scanner scan = new Scanner(System.in); String str1 = scan.nextLine(); String str2 = scan.nextLine(); HashSetsetActual = new HashSet<>(); for (char ch:str2.toUpperCase(Locale.ROOT).toCharArray()) { setActual.add(ch); } HashSet setBroken = new HashSet<>(); for (char ch: str1.toUpperCase(Locale.ROOT).toCharArray()) { if(!setActual.contains(ch) && !setBroken.contains(ch)){ setBroken.add(ch); System.out.print(ch);; } } }
④复制带随机指针的链表
给你一个长度为 n
的链表,每个节点包含一个额外增加的随机指针 random
,该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。
例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; }} public Node copyRandomList(Node head){ if (head == null) return null; HashMapmap = new HashMap<>(); Node cur = head; while (cur != null){ Node node = new Node(cur.val); map.put(cur,node); cur = cur.next; } cur = head; while (cur != null){ map.get(cur).next = map.get(cur.next); map.get(cur).random = map.get(cur.random); cur = cur.next; } return map.get(head); }
关于"Java数据结构中的Map与Set该怎么理解"就介绍到这了,更多相关内容可以搜索以前的文章,希望能够帮助大家答疑解惑,请多多支持网站!