数据结构：Map set - 习题（三）

一、只出现一次的数字

题目链接https://leetcode.cn/problems/single-number/description/

描述：

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

解析：我们创建一个set，如果set中没有这个元素我们就将这个元素放入set中，如果set中存在这个元素我们就将这个元素在set中移除。最后我们set中的元素就是只出现一次的元素，因此我们可以在遍历一遍数组查看是哪个元素。

java">class Solution {
    public int singleNumber(int[] nums) {
       Set<Integer> set = new HashSet<>();
       for(int i = 0;i < nums.length;i++){
        if(!set.contains(nums[i])){
            set.add(nums[i]);
        }else{
            set.remove(nums[i]);
        }
       }

       for(int i = 0;i < nums.length;i++){
        if(set.contains(nums[i])){
            return nums[i];
        }
       }
       return -1;
    }
}

但是上述方法并不是最最快的解法，我们最快的解法是利用位运算的方式，我们利用异或的方式来解决：我们依次得到所有的元素进行异或，我们创建一个变量n=0,而0^1 = 1,当我们遇到相同的元素时 1^1 = 0,因此我们遇到没有重复的元素时，经过异或就能得到这个只出现一次的元素：1^1^2=2

java">class Solution {
    public int singleNumber(int[] nums) {
        int n = 0;
        for(int num : nums){
            n^=num;
        }
        return n;
    }
}

二、随机链表的复制

习题链接https://leetcode.cn/problems/copy-list-with-random-pointer/description/

描述：

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

这道题，我们想要直接拷贝我们发现这其实时不可以，因为我们发现当我们拷贝完后发现，我们的next和random所指向的就不是我们拷贝完后的结点了。同时我们也可以发现我们的random的指向的下一个结点是跳跃的指向，自己本身或者指向的是空。

既让是这样，我们可以利用我们的Map,Map里存放的是<Node,Node>,我们根据我们的链表将拷贝后结点的val值存放到新的结点中，然后我们在根据我们拷贝到Map的结点值将对应的next和random拷贝到新的结点当中。

java">class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = 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);
    }
}

三、宝石与石头

习题链接https://leetcode.cn/problems/jewels-and-stones/description/

描述：

给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

解析：我们可以利用set,把宝石中的每个字符放到set中，然后遍历石头的所有字符，每遍历一个字符就到set中查看是否存在，如果存在就让count++;

java">class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for(int i = 0;i < jewels.length();i++){
            char ch = jewels.charAt(i);
            set.add(ch);
        }
        int count = 0;
        for(int i = 0;i < stones.length();i++){
            char ch = stones.charAt(i);
            if(set.contains(ch)){
                count++;
            }
        }
        return count;
    }
}

四、旧键盘

习题链接https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e

描述：

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

解析：我们知道Set是天然去重的因此我们可以将错误键盘打印出来的结果放到set1中，这样set1中的结果就是我们好的键，之后我们在遍历我们原本要打印的结果，如果set1中不存在并且set2中不存在就将这个字符打印并存入set2中

java">import java.util.*;

// 注意类名必须为 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();
            fun(str1,str2);
        }
    }

    public static void fun(String str1,String str2){
        Set<Character> set1 = new HashSet<>();
        for(char ch : str2.toUpperCase().toCharArray()){
            set1.add(ch);
        }
        Set<Character> set2 = new HashSet<>();
        for(char ch : str1.toUpperCase().toCharArray()){
            if(!set1.contains(ch) && !set2.contains(ch)){
                System.out.print(ch);
                set2.add(ch);
            }
        }

    }
}

好了，今天的讲解就到这里了，还请大家多多关注，我们下一篇见！