JAVAMAP和Set相关习题8

1.字符串中第一个只出现一次字符

class Solution {
    public int firstUniqChar(String s) {
        int[] count=new int[26];
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            count[ch-'a']++;
        }
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(count[ch-'a']==1){
                return i;
            }
        }
        return -1;
    }  
}

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

2. 只出现一次的数字

136. 只出现一次的数字 - 力扣（LeetCode）

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.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;
    }
}

 3.随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<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);
    }
}

 4.宝石与石头

771. 宝石与石头 - 力扣（LeetCode）

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

5.坏键盘

旧键盘 (20)__牛客网 (nowcoder.com)

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 s1=in.nextLine();
            String s2=in.nextLine();
            func(s1,s2);
        }
    }
    public static void func(String s1,String s2){
        Set<Character> set=new HashSet<>();
        for(char ch:s2.toUpperCase().toCharArray()){
            set.add(ch);
        }
        Set<Character> set1=new HashSet<>();
        for(char ch:s1.toUpperCase().toCharArray()){
            if(!set.contains(ch)&&!set1.contains(ch)){
                System.out.print(ch);
                set1.add(ch);
            }
        }
    }
}

6.前k个高频单词

692. 前K个高频单词 - 力扣（LeetCode）

1.统计每个单词出现的次数

2.放入优先级队列中（建立小根堆）

public List<String> topKFrequent(String[] words, int k) {



        //1、统计每个单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for (String word : words) {
            if(map.get(word) == null) {
                map.put(word,1);
            }else {
                int val = map.get(word);
                map.put(word,val+1);
            }
        }


        //2、建立小根堆,指定比较的方式
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>
                (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()-o2.getValue();
            }
        });

        //3、遍历map 调整优先级队列

        for(Map.Entry<String,Integer> entry: map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                //如果当前频率相同
                if(top.getValue().compareTo(entry.getValue()) == 0) {
                    // 字母顺序小的进来
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        //出队
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    if(top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top  = minHeap.poll();
            ret.add(top.getKey());
        }

        Collections.reverse(ret);

        return ret;

    }