Map和Set相关的oj习题
1. 只出现一次的数字
解题思路：判断当前元素是否存在于集合中，如果已经存在，则删除集合中相同的元素，如果不存在，则将该元素添加到集合中。
public int singleNumber(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums.length;i++) {
if(map.containsKey(nums[i])) {
map.remove(nums[i]);
}else {
map.put(nums[i],1);
}
}
for(int i = 0;i < nums.length;i++) {
if(map.containsKey(nums[i])) {
return nums[i];
}
}
return -1;
}2. 复制带随机指针的链表
解题思路：要注意的是对链表深拷贝,即不能直接将节点的赋给复制链表，这样不能满足复制链表中的指针都不应指向原链表中的节点。可以通过Map.Entry将原链表的节点放入key，将新链表的节点放入value。通过getkey()和getvalue()方法设置新链表的next和random
public Node copyRandomList(Node head) {
Map<Node,Node> map = new HashMap<>();
Node cur = head;
//1.现将现将原链表的节点放入map中，再将原链表的值拷贝到新链表当中放入map中
//使原链表和新链表对应的节点形成key-value型的键值对映射关系
while(cur != null) {
Node node = new Node(cur.val);
map.put(cur,node);
cur = cur.next;
}
cur = head;
//2.再将原节点的next和random通过映射的关系，拷贝到新的节点上
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. 宝石与石头
解题思路：将拥有的宝石字符串按字符的形式放入HashSet，key存放字符。然后再将拥有的石头字符串按字符的形式，通过contains()方法查找，如果为true则count++。
public int numJewelsInStones(String jewels, String stones) {
Set<Character> set = new HashSet<>();
for(int i = 0;i < jewels.length();i++) {
char ch = jewels.charAt(i);
set.add(ch);
}
int count = 0;
for(int i = 0;i < stones.length();i++) {
char ch = stones.charAt(i);
if(set.contains(ch)) {
count++;
}
}
return count;
}4. 坏键盘打字
解题思路：通过示例1可知，输入的小写字母被转化为了大写字母，所有我们可以在代码的开头就将字符串中的字符转化为大写。为了让坏了的键输出，可以将原始输出数据放入HashSet,然后再用实际输出的字符串以字符的形式判断HashSet中是否存在，如果存在，则删除。
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;
// 注意类名必须为 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 str1 = in.nextLine();
String str2 = in.nextLine();
getError(str1,str2);
}
}
private static void getError(String str1,String str2) {
str1 = str1.toUpperCase();
str2 = str2.toUpperCase();
Set<Character> actSet = new HashSet<>();
for(int i = 0;i < str2.length();i++) {
char ch = str2.charAt(i);
actSet.add(ch);
}
Set<Character> setBroke = new HashSet<>();
for(int i = 0;i < str1.length();i++) {
char ch = str1.charAt(i);
if(!actSet.contains(ch)&&!setBroke.contains(ch)) {
setBroke.add(ch);
System.out.print(ch);
}
}
}
}5. 前K个高频单词
解题思路：
1. 统计每个单词出现的次数，即将单词放入HashMap中，key存放单词，value存放单词出现的次数。
2. 创建一个堆，如果出现单词频率相同时，按大根堆排序，否则按照小跟堆排序，这是为了后面逆置时，打印出来的是从大到小的顺序。
3. 现将前k个Entry放入堆中，然后再将第k+1个节点依次与栈顶元素比较，如果比较的Entry的value值大于栈顶元素，则删除栈顶元素，再插入该元素,如果出现频率相同，当前Entry的key大于栈顶元素的key，则删除栈顶元素，再插入该元素。
4. 将堆元素放入链表，最后逆置返回链表即可
class Solution {
public List<String> topKFrequent(String[] words, int k) {
HashMap<String,Integer> hashMap = new HashMap<>();
//1.统计每个单词的个数
for(String word : words) {
if(hashMap.containsKey(word)){
int val = hashMap.get(word);
hashMap.put(word,val+1);
}else {
hashMap.put(word,1);
}
}
//2.创建小跟堆，存放key-value键值对
PriorityQueue<Map.Entry<String,Integer>> minHeap;
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().compareTo(o2.getValue());
//小跟堆--栈顶是堆中的最小元素，逆置后先打印的是频率最高的
}
});
//3.遍历
for(Map.Entry<String,Integer> entry : hashMap.entrySet()) {
if(minHeap.size() < k) {
minHeap.add(entry);
}else {
Map.Entry<String,Integer> top = minHeap.peek();
if(top.getValue() < entry.getValue()) {
minHeap.poll();
minHeap.add(entry);
}else if(top.getValue().equals(entry.getValue())) {
if(top.getKey().compareTo(entry.getKey()) > 0) {
minHeap.poll();
minHeap.add(entry);
}
}
}
}
//4.放入链表，逆置
ArrayList<String> arrayList = new ArrayList<>();
for (int i = 0; i < k; i++) {
Map.Entry<String,Integer> tmp = minHeap.poll();
arrayList.add(tmp.getKey());
}
Collections.reverse(arrayList);
return arrayList;
}
}原文地址：https://blog.csdn.net/2301_76515294/article/details/143725566
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！