/**
 * 統(tǒng)計一組數(shù)據中的每個數(shù)據出現(xiàn)了多少次
 */
 
import java.util.HashMap;
import java.util.Map;

public class Test {
    public static void main(String[] args) {
        char[] arr = {'a','c','e','c','b','d','f','c','d'};
        Map<Character,Integer> map = computer(arr);
        System.out.println(map);
    }

    public static Map<Character,Integer> computer(char[] arr){
        Map<Character,Integer> map = new HashMap<>();
        
        //如果在 map 中沒有數(shù)組對應的 Key，那么就添加 1個 Key 進去
        //如果在 map 中包含了和數(shù)組對應的 Key，且 Key 對應 count個 Val,
        //那么就添加 count + 1個 Key 進去
        for (char x :arr) {
            if(map.containsKey(x)){
                int count = map.get(x);
                map.put(x, count+1);
            }else {
                map.put(x,1);
            }
        }
        return map;
    }
}

/**
 * 將一組數(shù)據中多余的數(shù)據去重
 */
 
import java.util.HashSet;
import java.util.Set;

public class Test {
    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,3,2,4,6,8,5,4,6};

        Set<Integer> set = new HashSet<>();
        for (int x : arr) {
            set.add(x);
        }
        System.out.println(set);
    }
}

/**
 * 在一組數(shù)據中，找出第一個重復出現(xiàn)的數(shù)據
 */
 
import java.util.HashSet;
import java.util.Set;

public class Test6 {
    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,3,2,4,6,8,5,4,6};
        
        Set<Integer> set = new HashSet<>();
        int i = 0;
        //如果在添加元素到 set 之前，就已經發(fā)現(xiàn)了 set 中包含某個數(shù)組的元素，
        //那么就 break
        for (i = 0; i < arr.length; i++) {
            if(set.contains(arr[i])){
                break;
            }
            set.add(arr[i]);
        }
        System.out.println(arr[i]); //拿到的就是第一次出現(xiàn)的重復值
    }
}

/**
 * 利用兩兩元素之間異或，最終得出的就是單獨元素
 */
class Solution {
    public int singleNumber(int[] nums) {
        int x = nums[0];
        for(int i= 1; i<nums.length; i++){
            x = x^nums[i];
        }
        return x;
    }
}

/**
 * 利用集合 Set
 * 如果集合中有相同元素，就移除，反之，就添加
 */
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;
    }
}

/**
 * 通過 Map 的映射關系
 * 知道了 Key 的狀態(tài)，實現(xiàn) Value 的狀態(tài)
 * 即通過舊節(jié)點之間的關系，實現(xiàn)新節(jié)點之間的關系
 */
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        
        //Key - 舊節(jié)點，Value - 新節(jié)點
        Map<Node,Node> map = new HashMap<>(); 
        Node cur = head;
        
        //1. 創(chuàng)建新的節(jié)點
        while(cur != null){
            map.put(cur, new Node(cur.val)); 
            cur = cur.next;
        }

        cur = head;
        //2. 連接各個節(jié)點
        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);
    }
}

/**
 * 方法一
 * 1. 將 jewels 字符串中的字符放入集合 set 中
 * 2. 查看集合 set 中是否包含 stones 字符數(shù)組中字符
 * 3. 用 count 計數(shù)，最后返回
 */
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
    
        Set<Character> set = new HashSet<>();
        for(char x:jewels.toCharArray()){ //1.
            set.add(x);
        }

        int count = 0;
        for(char j:stones.toCharArray()){ //2.
            if(set.contains(j)){
                count++;
            }
        }
        return count; //3.
    }
}

/**
 * 方法二
 * 兩層 for 循環(huán)  
 */
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int count = 0;
        for(int i=0; i<jewels.length(); i++){
            for(int j=0; j<stones.length();j++){
                if( jewels.charAt(i) == stones.charAt(j) ){
                    count++;
                }
            }
        }
        return count;
    }
}

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;


/**
 * 1. 將實際輸入的文字 str2 放在集合 set 中
 * 2. for 循環(huán)遍歷應該輸入的文字 str1, 
 * 若集合 set 不包含某個字符，且線性表之前也未出現(xiàn)該字符，就輸出打印
 * 3. 將步驟 2 中不包含的字符放入順序表中,以便下一次判斷
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String str1 = scanner.nextLine(); //應該輸入的文字
        String str2 = scanner.nextLine(); //實際輸入的文字
        out(str1,str2);
    }

    public static void out(String str1, String str2){
        Set<Character> set = new HashSet<>();
        ArrayList<Character> list = new ArrayList<>();

        for (char x:str2.toUpperCase().toCharArray()) {
            set.add(x); //1.
        }

        for(char x:str1.toUpperCase().toCharArray()){ //2.
            if(!set.contains(x) && !list.contains(x)){ 
                System.out.print(x);
            }
            list.add(x); //3.
        }
    }
}

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> hashMap =new HashMap<>();
        for(String s: words) {
            if(hashMap.get(s) == null) {
                hashMap.put(s,1);
            }else {
                hashMap.put(s,hashMap.get(s)+1);
            }
        }
        //2、建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(
                k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        }
        );
        //3、遍歷hashMap 把里面 的數(shù)據 放到小根堆
        for(Map.Entry<String,Integer> entry : hashMap.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                //小根堆放滿了K個，下一個entry和堆頂元素比較
                Map.Entry<String,Integer> top = minHeap.peek();
                //堆頂?shù)念l率小于當前entry的頻率 就出隊 然后入隊entry
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.add(entry);
                }else {
                    //頻率相同的情況
                    if(top.getValue().compareTo(entry.getValue()) == 0) {
                        if(top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.add(entry);
                        }
                    }
                }
            }
        }
        //4、 此時小根堆當中已經有了結果
        //System.out.println(minHeap);
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String key = minHeap.poll().getKey();
            ret.add(key);
        }
        Collections.reverse(ret);
        //System.out.println("ret: "+ret);
        return ret;
    }
}