1. 只出现一次的数字
- 思路：
只出现一次：用for循环+异或^
也可以使用Map 或 Set
- 源码：
/**
* 只出现一次的数字
*/
// 方法1：使用for循环+异或^
public int singleNumber1(int[] nums) {
int ret = 0;
for (int i = 0; i < nums.length; i++) {
ret ^= nums[i];
}
return ret;
}
// 方法2：使用Map（因为要统计词频）：HashMap、TreeMap都ok
public int singleNumber(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
// 首先遍历一遍记录
// 再遍历一遍查看value是1的数据
for (int i = 0; i < nums.length; i++) {
// 判断之前是否已经出现过
if(map.get(nums[i]) == null) {
// 没有出现
map.put(nums[i],1);
} else {
// 出现了就增加value值
// 注意map.get获取到的是频率value
int value = map.get(nums[i]);
map.put(nums[i],value+1);
}
}
// 再进行一次遍历查看value==1的数据key
for (int i = 0; i < nums.length; i++) {
if(map.get(nums[i])==1) {
return nums[i];
}
}
return -1;
}
// 方法3：使用Set：遍历看有没有该元素，有就删掉已经放入的数据，没有就进行添加
// 时间复杂度：O(N*logN)；N遍历、logN查找
public int singleNumber2(int[] nums) {
Set<Integer> set = new TreeSet<>();
// 也可以是HashSet：速度更快 时间复杂度是O(N)
//Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
int key = nums[i];
if(!set.contains(key)) {
// 还不存在就添加
set.add(key);
} else {
// 已经存在就删除
set.remove(key);
}
}
// 来到这儿：说明set还剩一个数据
// 问题：如何找到这个数据：再次遍历数据，看是否包含在set集合中，包含就输出
for (int i = 0; i < nums.length; i++) {
if(set.contains(nums[i])) {
return nums[i];
}
}
// 来到这儿说明：没有找到
return -1;
}
2. 复制带随机指针的链表
- 思路：
之前百度电话面试的试题
也就是说：需要全新的节点，但是链表指向保持一致：
只要cur不为空就new一个结点，拷贝val值；
然后老节点和新节点使用Map进行存储，老节点地址存储于key，新节点地
址存储于val。（保证新老结点地址的对应关系，val(新)=map.get(key老)）
所以：map.get(cur).next （新的next） = map.get(cur.next);
map.get(cur).rand （新的rand） = map.get(cur.rand);
- 思路：1）遍历链表：new一个结点，并记录新老结点的对应关系（Map）
2）再次遍历链表，修改对应关系
（注意：该题不适合用TreeMap：因为TreeMap的key值必须可以比较）
- 源码：
/**
* 复制带随机指针的链表
*/
public Node copyRandomList(Node head) {
// Map用于存储新老结点
// 这里不能使用TreeMap，因为TreeMap的key要是可以比较的，而这里的自定义类型Node不需要进行比较，
// 也没有实现Comparable接口重写compareTo方法
Map<Node,Node> map = new HashMap<>();
Node cur = head;
// 第一次遍历链表：新建结点+map存储
while(cur != null) {
Node node = new Node(cur.val);
map.put(cur,node);
cur = cur.next;
}
// 第二次遍历链表：修改对应关系
cur = head; // 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. 宝石与石头
- 思路：
石头中有多少个宝石：把宝石放到集合Set中，然后遍历石头，如果相同就进行数量的++
（注意：在遍历时要将字符串转变为字符数组后再进行遍历）
- 源码：
/**
* 宝石与石头：
* 找石头中有多少个宝石：宝石放到集合Set中，遍历石头并与宝石进行比较，相同就数量++
*/
public int numJewelsInStones(String jewels, String stones) {
// 把宝石放到Set集合中:但是注意是将String拆成char类型的进行零散存储、进行零散比较
Set<Character> set = new HashSet<>();
// 注意使用for-each进行遍历：元素类型是插入，但是数组是要（String.toChararray()）进行转换的。
for (char ch : jewels.toCharArray()) {
set.add(ch);
}
// 遍历石头：与宝石进行比较，相同就数量++
int count = 0;
for (char ch : stones.toCharArray()) {
if(set.contains(ch)) {
// 包含就++
count++;
}
}
return count;
}
4. 坏键盘打字
- 思路：
根据期望输入与实际输入找到坏掉的键盘：也就是没有输入的字符就是坏掉的。重复的只输出一次，且只输出大写形式。
- 思路：把实际输入的键放在集合Set中，遍历期望输入的数据，与集合进行对比，实际没有的就进行输出（注意小写转大写,且相同的只输出一次）
- 源码：
/**
* 坏键盘打字：
*/
class Main {
// 查找坏键盘
private static void findBad(String str1, String str2) {
// 集合Set中放入实际输入的
Set<Character> set = new HashSet<>();
// 注意：因为最后要求的是大写形式，所以在存入集合前就将其全部变成大写的形式，然后再转为字符数组
for (char ch : str2.toUpperCase().toCharArray()) {
set.add(ch);
}
// 遍历期望输入的字符串，同样转为大写，和集合中的字符进行比较
Set<Character> setBad = new HashSet<>();
for (char ch : str1.toUpperCase().toCharArray()) {
/*if(!set.contains(ch)) {
// 如果不包含在实际输入中说明是坏键，应该打印
// 但是要注意会存在一个问题：会出现重复打印
// 为了避免坏键重复：再使用一个集合Set存储坏键，每次在实际输入中不包含时就与坏键集合对比，
// 坏键集合中也不包含时就存入坏键集合并进行输出
if(!setBad.contains(ch)) {
setBad.add(ch);
System.out.print(ch);
}
}*/
// 这里可以修改为：
if(!set.contains(ch) && !setBad.contains(ch)) {
System.out.print(ch);
setBad.add(ch);
}
}
}
public static void main(String[] args) {
// 要进行两行字符串的输入
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextLine()) {
String str1 = scanner.nextLine(); // 期望输入
String str2 = scanner.nextLine(); // 实际输入
// 进行查找坏键盘:注意实际使用的地方是在循环中！！
findBad(str1,str2);
}
}
}
5. 前K个高频单词
- 思路：
1）遍历数组，使用Map（HashMap）进行词频的统计
2）建立一个优先级队列：大小为k的小根堆！！
（注意类型以及要根据词频进行比较：实现可比较接口）
3）遍历map集合，先给优先级队列放入k个数据，然后从第（k+1）个开始和堆顶元素进行比较（一定要注意map的遍历方式！！！！Entry）
- 源码：
/**
* 前k个高频单词：
* 返回前k个出现次数最多的单词
* 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
* （词频）：Map
*
* 之前学过topK问题：使用大小根堆 、 优先队列 （前k大：大根堆 升序：大根堆）
*/
public List<String> topKFrequent(String[] words, int k) {
Map<String,Integer> map = new HashMap<>(); // 存储单词以及出现次数
// 进行数组遍历：如果出现过就value+1，没有出现过put
for (String key : words) {
if(map.get(key) == null) {
map.put(key,1);
} else {
int val = map.get(key);
map.put(key,val+1);
}
}
// 数据放到优先级队列中（前k大：小根堆！！）
// 小根堆的原因：小的在堆顶，而比较就与堆顶比较，换掉堆顶后再向下进行小堆排序，小的再换到堆顶，依次进行
// 其实也就是建立一个大小为k的小根堆:注意小根堆中的数据类型!!!
// 优先级队列默认是小根堆
PriorityQueue<Map.Entry<String,Integer>> minQue =
new PriorityQueue<>(k,new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
//return o1.getValue()-o2.getValue(); // 比较词频
// 但是注意引用类型比较大小compareTo！！
/*return o1.getValue().compareTo(o2.getValue());
*/
// 进行改写：
// 同频就比较key的字母顺序
if(o1.getValue().compareTo(o2.getValue()) == 0) {
// 词频一样，把字母顺序大的方在堆顶（因为最后要倒转)
return (o2.getKey().compareTo(o1.getKey()));
// 注意是o2-o1：因为是小根堆排序方式<0就小根堆（小于的在堆顶）
}
// 如果不相等 就进行频率比较返回
return o1.getValue().compareTo(o2.getValue());
}
});
// 遍历map集合，先给小根堆放满k个，然后从第（k+1）个开始和堆顶元素比较
// 注意map的遍历方式
for (Map.Entry<String,Integer> entry : map.entrySet()) {
if(minQue.size() < k) {
// 还没有放满,则继续放入
minQue.offer(entry);
} else {
// 已经放满：当前元素就与堆顶元素比较
Map.Entry<String,Integer> top = minQue.peek();
// 换入大的把小的弹出，自动向下排序
// 意思也就是说（小根堆的堆顶是最小的数据，把大于的换进去，最小的元素弹出来，剩下的就是较大的）
if(entry.getValue().compareTo(top.getValue()) > 0) {
// 大于就进行替换（弹出堆顶元素，放入新的元素）
minQue.poll();
minQue.offer(entry);
} else {
// == or <
// < 不放入 == 要考虑情况:按照字典顺序排序
// 引用类型：compareTo
// 相同词频时，弹出字母大的，放入小的
if(top.getValue().compareTo(entry.getValue())==0) {
// 引用类型：compareTo
if(top.getKey().compareTo(entry.getKey())>0) {
// 字典顺序小的放入,大的弹出
minQue.poll();
minQue.offer(entry);
}
}
}
}
}
// 遍历比较完成，小根堆ok
// 但是要输出频率最高->最低，输出的只是单词String,存入链表后进行反转
List<String> ret = new LinkedList<>(); // 最后只输出单词，并不输出词频
for (int i = 0; i < k; i++) {
ret.add(minQue.poll().getKey());
}
// 小根堆：从小到大排序，但是实际要求是从大到小，需要进行反转：
Collections.reverse(ret); // 反转链表，大的在前
return ret;
}
public static void main(String[] args) {
String[] words = {"hello","top","nice","top","hi","top","nice","hello"};
Practice practice = new Practice();
List<String> ret = practice.topKFrequent(words,3);
System.out.println(ret);
// 注意：当存在两个相同频率的单词时，在弹出堆顶元素后会存在一个问题，频率一样的两个单词谁去堆顶呢？
// 注意查看poll方法的源码：注意到在向下调整过程中经历重写的compareTo方法时比较的只是频率val值
// 此时因为两个单词的词频一样就会直接返回，没有进行过新的排序，所以可能就会存在输出顺序不对的问题
// 所以：要重新调整类的compareTo方法
}
THINK
- 关键要注意每题的解题思路！！
- 注意map的遍历方式（使用Map.Entry）
for (Map.Entry<String,Integer> entry : map.entrySet())
本文含有隐藏内容，请 开通VIP 后查看