[Map and Set] LeetCode & Niu Ke exercise

目录

1. 只出现一次的数字

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

3. 宝石与石头

4. 旧键盘

5. 前k个高频单词

---

1. 只出现一次的数字

题目链接：136. 只出现一次的数字

题目要求：

分析一下：

 上代码：

    //2.使用集合 
    //时间复杂度：O(n)
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            int key = nums[i];
            if(!set.contains(key)) {
                set.add(nums[i]);
            }else {
                set.remove(key);
            }
        }
        //此时集合,就剩一个元素了 找到这个元素
        for(int i = 0; i < nums.length; i++) {
            int key = nums[i];
            if(set.contains(key)) {
                return nums[i];
            }
        }
        return -1;
    }

---

 

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

题目链接：138. 复制带随机指针的链表

题目要求：

分析一下：

上代码：

class Solution {
    public Node copyRandomList(Node head) {
        //注意不能使用treemapOtherwise it can't be compared
        Map<Node,Node> map = new HashMap<>();
        //1.第一次遍历链表
        Node cur = head;
        while(cur != null) {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        //2.第二次遍历链表
        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);
    }
}

---

 

3. 宝石与石头

题目链接：771. 宝石与石头

题目要求：

 分析一下：

 

上代码：

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        //Put the gems into the collection
        for(char ch : jewels.toCharArray()) {
            set.add(ch);
        }
        int count = 0;
        //遍历石头,在石头中找宝石,计数++
        for(char ch : stones.toCharArray()) {
            if(set.contains(ch)) {
                count++;
            }
        }
        return count;
    }
}

---

 

4. 旧键盘

题目链接：旧键盘 (20)__牛客网 (nowcoder.com)

题目要求：

分析一下：

上代码：

import java.util.*;

public class Main {
    public static void func(String str1,String str2) {
        Set<Character> set = new HashSet<>();
        //str2先转大写,再转数组,然后放入集合
        for(char ch : str2.toUpperCase().toCharArray()) {
            set.add(ch);
        }
        //Iterate over the desired input,转为大写,再转数组,Compare with actual input
         Set<Character> set2 = new HashSet<>();
         for(char ch : str1.toUpperCase().toCharArray()) {
            if(!set.contains(ch) && !set2.contains(ch)) {
                System.out.print(ch);
                set2.add(ch);
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextLine()) {
            String str1 = scan.nextLine();//wish to enter
            String str2 = scan.nextLine();//实际输入的
            
            func(str1,str2);
        }
    }
}

---

 

5. 前k个高频单词

题目链接：692. 前K个高频单词

题目要求：

分析一下：

 上代码：

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        //1.统计单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for(String key : words) {
            if(map.get(key) == null) {
                map.put(key,1);
            }else {
                int val = map.get(key);
                map.put(key,val+1);
            }
        }
        //2.建立大小为k的小根堆
        PriorityQueue<Map.Entry<String,Integer>> minQ = new PriorityQueue<>(k,new Comparator<Map.Entry<String,Integer>>(){
            @Override
            public int compare(Map.Entry<String,Integer> o1, Map.Entry<String,Integer> o2) {
                //When the word appears the same number of times,调整以key为准的大根堆
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
                //Create a small root heap based on the number of occurrences of a word
            }
        });

        //3.遍历map,Fill the small roots firstk个,然后从第k+1开始,和堆顶元素比较
        for(Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minQ.size() < k) {
            //If the small root pile is not full,just keep putting it    
                minQ.offer(entry);
            }else {
                //如果已经放满了小根堆,Then we need to compare the current element and the top element of the heap at this time
                Map.Entry<String,Integer> top = minQ.peek();
                if(top != null) {
                    if(entry.getValue() > top.getValue()) {
                    minQ.poll();
                    minQ.offer(entry);
                    }else {
                        //如果此时<不用管,但如果=,Arrange them in lexicographical order according to the meaning of the questions
                        if(top.getValue().compareTo(entry.getValue()) == 0) {
                            //value一样,看key
                            if(top.getKey().compareTo(entry.getKey()) > 0) {
                                minQ.poll();
                                minQ.offer(entry);
                            }
                        }
                    }
                }
                
            }
        }
        //此时前k个次数最多的单词,All have been put into the heap,Remove the elements from the heap from the heap
        List<String> ret = new ArrayList<>();
        for(int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top  = minQ.poll();
            if(top != null) {
                ret.add(top.getKey());
            }
            
        }
        //The front is a pile of small roots,According to the number of high to low requirements,This is reversed
        Collections.reverse(ret);
        return ret;
    }
}

---