Map与Set高频面试算法题(只出现一次的数字,复制带随机指针的链表,宝石与石头,旧键盘,前k个高频单词)(Java实现)

简介: 给一个非空整数数组,只有一个元素出现了一次,剩余的元素都出现了两次,,请找出那个只出现一次的数字

LeetCode 136  只出现一次的数字

题目链接:只出现一次的数字


题目:

image.png

给一个非空整数数组,,只有一个元素出现了一次,剩余的元素都出现了两次,,请找出那个只出现一次的数字

方法一:


我们知道0异或任何数等于任何数,两个相等的数字异或为0,所以我们可以采用位运算,将所有的数依次异或,得到的数就是只出现一次的元素


代码展示:

class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0;i < nums.length;i++){
            ret = ret ^ nums[i];
        }
        return ret;
    }
}


方法二:


我们可以往HashSet中依次存放元素,因为set中不能存放重复元素,所以当某个元素插入失败时,说明set中已有该元素,将该元素从set中删掉,最后set中剩余的元素就是只出现一次的元素


代码展示:

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for(int i = 0;i < nums.length;i++){
            if(!s.add(nums[i])){
                s.remove(nums[i]);
            }
        }
        Object[] array = s.toArray();
        return (int)array[0]; 
    }
}


LeetCode 138 复制带随机指针的链表

题目链接:复制带随机指针的链表


题目:

image.png

示例:

微信图片_20221030133116.png


方法:


可以使用HashMap,K为原链表的结点,V为与K相对应的新节点,先复制完结点,再链接新结点,新结点要链接next和random指针域 ,链接方法如下:


next链接的方法:map.get(cur).next = map.get(cur.next),cur为遍历原链表的结点

random链接的方法:map.get(cur).random = map.get(cur.random)

代码展示:

class Solution {
    public Node copyRandomList(Node head) {
        Node cur = head;
        Map<Node,Node> m = new HashMap<>();
        while(cur != null){
            Node newNode = new Node(cur.val);
            m.put(cur,newNode);
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            m.get(cur).next = m.get(cur.next);
            m.get(cur).random = m.get(cur.random);
            cur = cur.next;
        }
        return m.get(head);
    }
}

leetCode 771 宝石与石头

题目链接:宝石与石头


题目:

image.png

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

方法:


我们可以借助HashSet,将宝石依次插入到set中,再依次遍历每个石头,判断宝石中是否包含该石头,如果包含则计数+1 ,返回最终计数


代码展示:

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


旧键盘打字

题目链接:旧键盘


题目:


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


输入描述:

image.png



输出描述:

image.png



注意:输出要求英文字母大写,所以我们在输入时直接将字符串准换成大写,求转换大写后的坏键


方法:


我们可以将实际输出的字符保存到HashSet中,然后依次将应该输出的字符往set中插入,如果插入成功说明该键是坏键,直接输出该键


代码展示:

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine().toUpperCase();//应该输出的
        String s2 = sc.nextLine().toUpperCase();//实际输出的
        Set<Character> s = new HashSet<>();
        for(int i = 0;i < s2.length();i++){
            s.add(s2.charAt(i));
        }
        for(int i = 0;i < s1.length();i++){
            if(s.add(s1.charAt(i))){
                System.out.print(s1.charAt(i));
            }
        }
        System.out.println();
    }
}


LeetCode 692 前K个高频单词

题目链接:前K个高频单词


题目:


给一个单词列表words和一个整数k,返回前k个出现次数最多的单词


注意:返回的单词应该按单词的出现频率依次排序,如果不同的单词具有相同的出现频率,则按照字典序排序


示例:

image.png


方法:使用Top-k思想解决


先使用HashMap统计各个单词以及对应的出现次数

map中存放的是K-V键值对,将前k个键值对插入到优先级队列中,键值对对应的类型为Map.Entry<K,V>

往优先级队列中插入键值对时,需要创建比较器类,使Map.Entry<K,V>类型可以比较大小

插入前k个后,后面插入的N-K个键值对需要和堆顶元素比较,如果比堆顶元素大则删除堆顶元素,插入该键值对

插入完所有的键值对后,使用依次从优先级队列中删除后往List中添加

因为堆顶元素是最小的,而题目要求是按照频率高往低输出,故List中保存的顺序是与题目要求相反的

将List中的内容逆置后返回

分析如何创建比较器类及重写compare的方法 :


我们往优先级队列中插入的是键值对,类型为Map.Entry<String,Integer>,我们要的前K个高频,从次数上看,是小堆的方式,堆顶元素出现的次数是最低的,后面的N-k个元素与堆顶元素比较时,次数大于堆顶元素时替换堆顶元素,从字典序上看,是大堆的方式,当元素出现的次数相同时,堆顶元素应为字典序大的


代码展示:

//比较器类
class KVCmp implements Comparator<Map.Entry<String,Integer>>{
    public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){
        if(o1.getValue() > o2.getValue()){
            return 1;
        }
        if(o1.getValue()==o2.getValue() && o2.getKey().compareTo(o1.getKey())>0){
            return 1;
        }
        if(o1.getValue()==o2.getValue() && o2.getKey().compareTo(o1.getKey())==0){
            return 0;
        }
        return -1;
    }
}
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> m = new HashMap<>();
        //统计次数
        for(int i = 0;i < words.length;i++){
            m.put(words[i],m.getOrDefault(words[i],0)+1);
        }
        //new比较器类
        KVCmp cmp = new KVCmp();
        //创建优先级队列,传入比较器
        PriorityQueue<Map.Entry<String,Integer>> p = new PriorityQueue<>(cmp);
        Set<Map.Entry<String,Integer>> s = m.entrySet();
        int i = 0;
        //将键值对插入到优先级队列中
        for(Map.Entry<String,Integer> kv : s){
            //前k个直接插入
            if(i < k){
                p.offer(kv);
                i++;
            }else {
                //后面的经过比较后再插入
                if(cmp.compare(kv,p.peek()) > 0){
                    p.poll();
                    p.offer(kv);
                }
            }
        }
        List<String> ret = new ArrayList<>();
        //往list中插入键值对的V,也就是单词
        for(i = 0;i < k;i++){
            ret.add(p.poll().getKey());
        }
        Collections.reverse(ret);//逆置
        return ret;
    }
    }





相关文章
|
10天前
|
存储 安全 Java
Java面试题:请解释Java内存模型(JMM)是什么,它如何保证线程安全?
Java面试题:请解释Java内存模型(JMM)是什么,它如何保证线程安全?
52 13
|
10天前
|
存储 Java 程序员
Java面试题:请解释Java中的永久代(PermGen)和元空间(Metaspace)的区别
Java面试题:请解释Java中的永久代(PermGen)和元空间(Metaspace)的区别
40 11
|
10天前
|
Java 测试技术 开发者
Java面试题:解释CountDownLatch, CyclicBarrier和Semaphore在并发编程中的使用
Java面试题:解释CountDownLatch, CyclicBarrier和Semaphore在并发编程中的使用
31 11
|
10天前
|
存储 Java 程序员
Java面试题:方法区在JVM中存储什么内容?它与堆内存有何不同?
Java面试题:方法区在JVM中存储什么内容?它与堆内存有何不同?
35 10
|
10天前
|
存储 运维 Java
Java面试题:JVM的内存结构有哪些主要部分?请简述每个部分的作用
Java面试题:JVM的内存结构有哪些主要部分?请简述每个部分的作用
29 9
|
10天前
|
缓存 监控 算法
Java面试题:描述Java垃圾回收的基本原理,以及如何通过代码优化来协助垃圾回收器的工作
Java面试题:描述Java垃圾回收的基本原理,以及如何通过代码优化来协助垃圾回收器的工作
37 8
|
10天前
|
缓存 安全 Java
Java面试题:解释volatile关键字的作用,以及它如何保证内存的可见性
Java面试题:解释volatile关键字的作用,以及它如何保证内存的可见性
24 4
|
8天前
|
NoSQL Java 应用服务中间件
Java高级面试题
Java高级面试题
|
8天前
|
网络协议 安全 前端开发
java面试题
java面试题
|
5天前
|
安全 机器人 Java