当前位置:网站首页>[Map and Set] LeetCode & Niu Ke exercise
[Map and Set] LeetCode & Niu Ke exercise
2022-07-31 01:39:00 【Come to the pot】
目录
1. 只出现一次的数字
题目链接:136. 只出现一次的数字
题目要求:
分析一下:
上代码:
//2.使用集合
//时间复杂度:O(n)
public int singleNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int i = 0; i < nums.length; i++) {
int key = nums[i];
if(!set.contains(key)) {
set.add(nums[i]);
}else {
set.remove(key);
}
}
//此时集合,就剩一个元素了 找到这个元素
for(int i = 0; i < nums.length; i++) {
int key = nums[i];
if(set.contains(key)) {
return nums[i];
}
}
return -1;
}
2. 复制带随机指针的链表
题目链接:138. 复制带随机指针的链表
题目要求:
分析一下:
上代码:
class Solution {
public Node copyRandomList(Node head) {
//注意不能使用treemapOtherwise it can't be compared
Map<Node,Node> map = new HashMap<>();
//1.第一次遍历链表
Node cur = head;
while(cur != null) {
Node node = new Node(cur.val);
map.put(cur,node);
cur = cur.next;
}
//2.第二次遍历链表
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);
}
}
3. 宝石与石头
题目链接:771. 宝石与石头
题目要求:
分析一下:
上代码:
class Solution {
public int numJewelsInStones(String jewels, String stones) {
Set<Character> set = new HashSet<>();
//Put the gems into the collection
for(char ch : jewels.toCharArray()) {
set.add(ch);
}
int count = 0;
//遍历石头,在石头中找宝石,计数++
for(char ch : stones.toCharArray()) {
if(set.contains(ch)) {
count++;
}
}
return count;
}
}
4. 旧键盘
题目链接:旧键盘 (20)__牛客网 (nowcoder.com)
题目要求:
分析一下:
上代码:
import java.util.*;
public class Main {
public static void func(String str1,String str2) {
Set<Character> set = new HashSet<>();
//str2先转大写,再转数组,然后放入集合
for(char ch : str2.toUpperCase().toCharArray()) {
set.add(ch);
}
//Iterate over the desired input,转为大写,再转数组,Compare with actual input
Set<Character> set2 = new HashSet<>();
for(char ch : str1.toUpperCase().toCharArray()) {
if(!set.contains(ch) && !set2.contains(ch)) {
System.out.print(ch);
set2.add(ch);
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNextLine()) {
String str1 = scan.nextLine();//wish to enter
String str2 = scan.nextLine();//实际输入的
func(str1,str2);
}
}
}
5. 前k个高频单词
题目链接:692. 前K个高频单词
题目要求:
分析一下:
上代码:
class Solution {
public List<String> topKFrequent(String[] words, int k) {
//1.统计单词出现的次数
Map<String,Integer> map = new HashMap<>();
for(String key : words) {
if(map.get(key) == null) {
map.put(key,1);
}else {
int val = map.get(key);
map.put(key,val+1);
}
}
//2.建立大小为k的小根堆
PriorityQueue<Map.Entry<String,Integer>> minQ = new PriorityQueue<>(k,new Comparator<Map.Entry<String,Integer>>(){
@Override
public int compare(Map.Entry<String,Integer> o1, Map.Entry<String,Integer> o2) {
//When the word appears the same number of times,调整以key为准的大根堆
if(o1.getValue().compareTo(o2.getValue()) == 0) {
return o2.getKey().compareTo(o1.getKey());
}
return o1.getValue().compareTo(o2.getValue());
//Create a small root heap based on the number of occurrences of a word
}
});
//3.遍历map,Fill the small roots firstk个,然后从第k+1开始,和堆顶元素比较
for(Map.Entry<String,Integer> entry : map.entrySet()) {
if(minQ.size() < k) {
//If the small root pile is not full,just keep putting it
minQ.offer(entry);
}else {
//如果已经放满了小根堆,Then we need to compare the current element and the top element of the heap at this time
Map.Entry<String,Integer> top = minQ.peek();
if(top != null) {
if(entry.getValue() > top.getValue()) {
minQ.poll();
minQ.offer(entry);
}else {
//如果此时<不用管,但如果=,Arrange them in lexicographical order according to the meaning of the questions
if(top.getValue().compareTo(entry.getValue()) == 0) {
//value一样,看key
if(top.getKey().compareTo(entry.getKey()) > 0) {
minQ.poll();
minQ.offer(entry);
}
}
}
}
}
}
//此时前k个次数最多的单词,All have been put into the heap,Remove the elements from the heap from the heap
List<String> ret = new ArrayList<>();
for(int i = 0; i < k; i++) {
Map.Entry<String,Integer> top = minQ.poll();
if(top != null) {
ret.add(top.getKey());
}
}
//The front is a pile of small roots,According to the number of high to low requirements,This is reversed
Collections.reverse(ret);
return ret;
}
}
边栏推荐
猜你喜欢
《云原生的本手、妙手和俗手》——2022全国新高考I卷作文
The difference between 4G communication module CAT1 and CAT4
Centos 7.9 install PostgreSQL14.4 steps
【网络安全】文件上传靶场通关(1-11关)
Multiplication, DFS order
想要写出好的测试用例,先要学会测试设计
1782. 统计点对的数目 双指针
case语句的综合结果,你究竟会了吗?【Verilog高级教程】
剑指offer17---打印从1到最大的n位数
System design. Short chain system design
随机推荐
认识DTU什么是4GDTU设备
87. Convert String to Integer
What is the ideal college life?
ROS Action communication
计算S=a+aa+…+aa…a
Analyze the capabilities and scenarios of the cloud native message flow system Apache Pulsar
Kyushu cloud as cloud computing standardization excellent member unit
tkinter模块高级操作(二)—— 界面切换效果、立体阴影字效果及gif动图的实现
倍增、DFS序
勾股数元组 od js
SQLserver查询最近三个月的数据,语句该怎么写sqlserver
蛮力法/邻接表 广度优先 有向带权图 无向带权图
The sword refers to offer17---print the n digits from 1 to the largest
手把手教你配置Jenkins自动化邮件通知
Ticmp - 更快的让应用从 MySQL 迁移到 TiDB
PDF split/merge
C语言_结构体指针数组函数选票系统
【952. Calculate the maximum component size according to the common factor】
小黑leetcode之旅:104. 二叉树的最大深度
System design. Short chain system design