目录
LeetCode 136? 只出现一次的数字
题目链接：只出现一次的数字
题目：
给一个非空整数数组，，只有一个元素出现了一次，剩余的元素都出现了两次，，请找出那个只出现一次的数字
示例：
方法一：
我们知道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 复制带随机指针的链表?
题目链接：复制带随机指针的链表?
题目：
??
示例：
方法：
可以使用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 宝石与石头
题目链接：宝石与石头?
题目：
给你一个字符串 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;
}
}旧键盘打字
题目链接：旧键盘
题目：
旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。?
输入描述：
输出描述：
注意：输出要求英文字母大写，所以我们在输入时直接将字符串准换成大写，求转换大写后的坏键
方法：
我们可以将实际输出的字符保存到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个出现次数最多的单词
注意：返回的单词应该按单词的出现频率依次排序，如果不同的单词具有相同的出现频率，则按照字典序排序
示例：
方法：使用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;
}
}