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; } }
