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

LeetCode 136  只出现一次的数字

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

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

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

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

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

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

leetCode 771 宝石与石头

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

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++){
}
for(int i = 0;i < s1.length();i++){
System.out.print(s1.charAt(i));
}
}
System.out.println();
}
}

LeetCode 692 前K个高频单词

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

//比较器类
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++){
}
Collections.reverse(ret);//逆置
return ret;
}
}

|
10天前
|

Java面试题：请解释Java内存模型(JMM)是什么，它如何保证线程安全？
Java面试题：请解释Java内存模型(JMM)是什么，它如何保证线程安全？
52 13
|
10天前
|

Java面试题：请解释Java中的永久代（PermGen）和元空间（Metaspace）的区别
Java面试题：请解释Java中的永久代（PermGen）和元空间（Metaspace）的区别
40 11
|
10天前
|
Java 测试技术 开发者
Java面试题：解释CountDownLatch, CyclicBarrier和Semaphore在并发编程中的使用
Java面试题：解释CountDownLatch, CyclicBarrier和Semaphore在并发编程中的使用
31 11
|
10天前
|

Java面试题：方法区在JVM中存储什么内容？它与堆内存有何不同？
Java面试题：方法区在JVM中存储什么内容？它与堆内存有何不同？
35 10
|
10天前
|

Java面试题：JVM的内存结构有哪些主要部分？请简述每个部分的作用
Java面试题：JVM的内存结构有哪些主要部分？请简述每个部分的作用
29 9
|
10天前
|

Java面试题：描述Java垃圾回收的基本原理，以及如何通过代码优化来协助垃圾回收器的工作
Java面试题：描述Java垃圾回收的基本原理，以及如何通过代码优化来协助垃圾回收器的工作
37 8
|
10天前
|

Java面试题：解释volatile关键字的作用，以及它如何保证内存的可见性
Java面试题：解释volatile关键字的作用，以及它如何保证内存的可见性
24 4
|
8天前
|
NoSQL Java 应用服务中间件
Java高级面试题
Java高级面试题
22 1
|
8天前
|

java面试题
java面试题
14 1
|
5天前
|