1、只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

只出现一次的数字

1、利用set集合对元素的去重性，定义一个set去遍历数组，检查Set中是否存在这个元素，如果存在就删除，如果不存在，就加入到集合。
2、再次遍历数组，，如果set中存在，那么就只出现了一次

 /*** 只出现一次的数据* @param nums* @return*/public int singleNumber(int[] nums){//非空校验if(nums==null||nums.length==0){return -1;}//定义一个set再去遍历数组Set<Integer> set=new HashSet<>();for (int i = 0; i < nums.length; i++) {//1、检查Set中是否存在这个元素，如果不存在就加入，存在就删除if(set.contains(nums[i])){set.remove(nums[i]);}else {set.add(nums[i]);}}//再次遍历数组，如果Set中存在，那么就只出现了一次for (int i = 0; i < nums.length; i++) {if(set.contains(nums[i])){return nums[i];}}//不存在return -1;}

2、复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

复制带随机指针的链表

 /*** 复制带随机指针的链表* @param head* @return*/public Node randomNodeList(Node head){//创建一个HashmapMap<Node,Node> map=new HashMap<>();//1、第一次遍历链表Node current=head;while(current!=null){//2、根据当前节点的值创建一个值相等的新节点Node node=new Node(current.val);//3、用原节点当key,新节点当value加入到map中map.put(current,node);//移动当前节点到下一个current=current.next;}//4、第二次遍历链表current=head;while(current!=null){//5、根据当前节点从map中获取对应新节点Node node=map.get(current);//6、根据当前节点的Next和Random去map中找到相应的节点，赋值node.next=map.get(current.next);node.random=map.get(current.random);//向后移动current=current.next;}//返回新链表的头节点return map.get(head);}

3、宝石与石头

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

字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

​​​​​​宝石与石头

1、第一次遍历宝石字符串，依题意每一个字符都是一个宝石，把每个字符都加入到set中’

2、遍历石头字符串，取出每个宝石在的Set中查找是否存在相应的字符，如果有就计数加1

3、最后把计数返回

/*** 宝石与石头* @param jewels* @param stones* @return*/public int numJewelsInStones(String jewels,String stones){//非空校验if(jewels==null||jewels.isEmpty()||stones==null||stones.isEmpty()){return 0;}//1、定义一个存储宝石的setSet<Character> set=new HashSet<>();//2、遍历宝石字符串for (int i = 0; i < jewels.length(); i++) {char ch=jewels.charAt(i);set.add(ch);}//3、遍历石头字符串，在宝石的set中是否存在对应字符int count=0;for (int i = 0; i < stones.length(); i++) {char ch=stones.charAt(i);if(set.contains(ch)){count++;}}//返回计数return count;}

4、坏键盘打字

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

旧键盘 (20)__牛客网

1、接收输入的两个字符串

2、按照题目要求大写输出字母，就要先把两个字符串先转为大写，方便处理

3、把坏键输出的字符串中的每个字符都放入Set

4、遍历正常的字符串，取每个字符在Set中检查是否存在，如果不存在对应的键那么就是坏键，记录Set并打印坏键

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;/*** 坏键盘打字*/
public class TestSM1 {public static void main(String[] args) {Scanner sc=new Scanner(System.in);//获取输入的字符串while(sc.hasNextLine()){String strNormal=sc.nextLine();String strBroken=sc.nextLine();//处理逻辑processor(strNormal,strBroken);}}private static void processor(String strNormal, String strBroken) {//1、把两个字符串转成大写strNormal=strNormal.toUpperCase();strBroken=strBroken.toUpperCase();//把strBroken中每一个字符都放到set中Set<Character> set=new HashSet<>();for (Character ch:strBroken.toCharArray()) {set.add(ch);}//3、遍历正常字符串，如果正常字符串中有某个字符，但是坏键中却没有这个字符//那么就可以认为当前字符对应的键就是坏键//定义一个保存坏键的setSet<Character> brokenSet=new HashSet<>();for (int i = 0; i < strNormal.length(); i++) {char ch=strNormal.charAt(i);if(!set.contains(ch)&&!brokenSet.contains(ch)){//加入坏键setbrokenSet.add(ch);//打印坏键字符System.out.println(ch);}}}
}

5、前k个高频单词

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

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

前K个高频单词

1、遍历字符数组，统计字符出现的次数用HashMap<String,Integer>,字符当作key，出现次数当作value

2、创建一个优先级队列，容量可以根据k来确定，把map中的所有元素依次放入队列中，在放入的过程中处理排序和比较问题，

3、优先级队列中的元素加入到返回的集合中

  /*** 前k个高频单词* @param words* @param k* @return*/public List<String> topKFrequent(String[] words,int k){List<String> list=new ArrayList<>();//非空校验if(words.length==0||words==null||k<=0){return list;}//1、遍历字符串数组，统计单词出现的个数Map<String,Integer>map=new HashMap<>();for (int i = 0; i < words.length; i++) {int count=map.getOrDefault(words[i],0);count++;map.put(words[i],count);}//2、创建一个优先级队列，确定比较规则PriorityQueue<Map.Entry<String,Integer>> queue=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {@Overridepublic int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {//1、首先判断两个单词出现的次数是否相等if(o1.getValue()==o2.getValue()){//通过key的比较规则，按大根堆来处理return o2.getKey().compareTo(o1.getKey());}else{//按正常的小根堆的比较逻辑处理return o1.getValue()-o2.getValue();}}});//3、把map中的所有元素一次加入到优先级队列中for(Map.Entry<String,Integer> entry:map.entrySet()){//直接入队queue.offer(entry);//队列元素大于k时，直接出队队首元素if(queue.size()>k){queue.poll();}}//4、把优先级队列中的元素，依次加入到list中while(!queue.isEmpty()){list.add(queue.poll().getKey());}//5、解决翻转问题Collections.reverse(list);//6、返回return list;}