数据结构(Java)——Map与Set相关高频面试题
Map与Set相关高频面试题
1.只出现一次的数字
题目描述:给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例1
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
1.思路
1.最容易想到的思路:先判断数组的长度是奇数还是偶数,偶数直接返回空,奇数的话先排序,然后遍历数组,找出只出现了一次的数字
2.数学思维:用异或的方法来做,首先要知道,一个数字与其本身异或为0,与0异或还是其数字本身,所以我们设置一个index=0,与数组中的每一个数字异或,因为该数字只出现了一次,所以最后异或得到的结果就是我们要求得数字
3.遍历数组并挨个将元素放进进集合，如果集合中存在这个元素，则将它remove掉，如果不存在则add。按题目的意思，最后这个集合中就只有这个只出现一次的元素了
2.代码
public int singleNumber(int[] nums) {
//方法1:暴力
// Arrays.sort(nums);
// for (int i = 0; i < nums.length-1; i+=2) {
// if (nums[i] != nums[i+2]){
// return nums[i];
// }
// }
// return nums[nums.length-1];
// }
//方法2:异或
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
//方法3:哈希表
//
// HashSet<Integer> set = new HashSet<>();
// //这样最后的set就只包含这个不重复的元素了
// for(int i = 0; i < nums.length; i++){
// if(set.contains(nums[i])){
// set.remove(nums[i]);
// }else{
// set.add(nums[i]);
// }
// }
// int res = 0;
// for(int i = 0; i < nums.length; i++){
// if(set.contains(nums[i])){
// res = nums[i];
// break;
// }
// }
// return res;
}
2.复制带随机指针的链表
题目描述:给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的深拷贝。深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值.新节点的 next 指针和random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有
x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到
n-1）；如果不指向任何节点，则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。
1.思路
1.先说一种简单粗暴的思路:先把链表按照普通链表的方式复制一份,遍历每个节点看该节点random指针指向的位置相对于头节点的偏移量是几(从头结点出发走几步能到达random指向位置),然后根据这个偏移量决定新链表中的每个节点的random的指向,但是改代码比较麻烦
2.更简单而且比较容易理解的方法:创建一个Map<Node,Node> key代表旧链表上的节点,value代表旧链表对应节点的拷贝(也就是新链表的拷贝)
2.代码
public Node copyRandomList(Node head) {
//1.遍历旧链表,把旧链表的每个结点一次插入到map中,key是旧链表,value是拷贝出来得新链表
Map<Node,Node> map=new HashMap<>();
for (Node cur=head;cur != null;cur=cur.next) {
map.put(cur,new Node(cur.val));
}
//2.再次遍历链表,修改新链表节点中的next和random
for (Node cur=head;cur != null;cur=cur.next) {
Node newCur=map.get(cur);
newCur.next=map.get(cur.next);
newCur.random=map.get(cur.random);
}
//返回新链表的头节点
return map.get(head);
}
3.宝石与石头
给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
字母区分大小写，因此 “a” 和 “A” 是不同类型的石头。
示例 1：
输入：jewels = “aA”, stones = “aAAbbbb”
输出：3
示例 2：
输入：jewels = “z”, stones = “ZZ”
输出：0
1.思路
首先对jewels进行遍历，将字符分别存到HashSet中，以便之后遍历stones的时候查找
遍历stones，并将每个字符与HashSet中的进行比对，如果存在，则结果ret++，遍历结束，返回ret
2.代码
public int numJewelsInStones(String jewels, String stones) {
//1.先遍历j边把所有的宝石类加入到一个Set中
Set<Character> set=new HashSet<>();
for (char c:jewels.toCharArray()) {
set.add(c);
}
//2.遍历S拿到每个元素取set中查找，如果能查找就说明是宝石
int ret=0;
for (char c:stones.toCharArray()) {
if (set.contains(c)){
ret++;
}
}
return ret;
}
复杂度分析
时间复杂度：O(m+n)，其中 m 是字符串jewels 的长度，n 是字符串 stones 的长度。遍历字符串jewels将其中的字符存储到哈希集合中，时间复杂度是 O(m)，然后遍历字符串 stones，对于stones 中的每个字符在 O(1) 的时间内判断当前字符是否是宝石
时间复杂度是: O(n)，因此总时间复杂度是 O(m+n)。
空间复杂度：O(m)，其中 m 是字符串 jewels 的长度。
4.坏键盘打字
输入描述:
输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、
以及下划线“_”（代表空格）组成。题目保证2个字符串均非空。
输出描述:
按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。
1.思路
1.循环读入两个字符串，第一个预期输出的内容，第二个实际输出的内容
2.把读入的两个字符串全部转成大写
3.题目中的主要任务是判定预期输出的哪些字符在实际输出的字符串中没有出现
4.先搞一个set把实际输出的每个字符都存进去，就可以遍历预期输出字符串，看看预期中的字符在这个set中出不出现
5. [注意事项]预期字符串中如果有重复的键要去重（可以使用set来去重）
2.代码
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
while (scanner.hasNext()){
//1.循环读入两个字符串，第一个字符串是与其输出的内容；第二个字符串时实际输出的内容
String expected=scanner.next();
String actual=scanner.next();
//2.把读入的两个字符串全都转成大写
expected=expected.toUpperCase();
actual=actual.toUpperCase();
//3.创建一个Set保存实际哪些字符输出了
Set<Character> actualSet=new HashSet<>();
for (int i=0;i < actual.length();i++){
//注意，set中的元素不能重复，如果add的时候发现这个元素已经存在，add就失败了
//没有任何负面影响
actualSet.add(actual.charAt(i));
}
//4.遍历预期输出的字符串，看看哪个字符没有被实际输出
Set<Character> brokenKeySet=new HashSet<>();
for (int i = 0; i < expected.length(); i++) {
char c=expected.charAt(i);
if (actualSet.contains(c)){
//这是一个好的键，即当前字符已经被输出
continue;
}
//当前这个见没被实际输出，就是坏了的键
//输出的格式也很重要，要不要空格，要不要换行
//这里还要考虑去重的问题
if (brokenKeySet.contains(c)){
//此处的brokenKeySet辅助去重，防止同一个坏键被打印多次
continue;
}
System.out.print(c);
brokenKeySet.add(c);
}// end for
}//end while
5.前K个高频单词
给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
1.思路
我们可以预处理出每一个单词出现的频率，然后依据每个单词出现的频率降序排序，最后返回前 k 个字符串即可。
具体地，我们利用哈希表记录每一个字符串出现的频率，然后将哈希表中所有字符串进行排序，排序时，如果两个字符串出现频率相同，那么我们让两字符串中字典序较小的排在前面，否则我们让出现频率较高的排在前面。最后我们只需要保留序列中的前 k 个字符串即可。
2.代码
class Solution {
static class MyComparator implements Comparator<String>{
private Map<String,Integer> map;
public MyComparator(Map<String, Integer> map) {
this.map = map;
}
@Override
public int compare(String o1, String o2) {
int count1= map.get(o1);
int count2= map.get(o2);
if (count1==count2){
//String自身实现了Comparable，自带字典序的比较功能的
//comperto就是在使用String默认的比较规则的
return o1.compareTo(o2);
//o1 < o2 返回 < 0
//o1 > o2 返回 > 0
//count1 - count2 升序排序 定义了出现次数少的比较小
//count2 - count1 降序排序 定义了出现次数多的比较大
//sort也是按照升序来排序
//这两样的表带是就是在重新定义“什么比较小”
//
}
return count2-count1;
}
}
public List<String> topKFrequent(String[] words, int k) {
//1.先统计每个单词出现的次数
Map<String,Integer> map=new HashMap<>();
for (String s:words) {
Integer count=map.getOrDefault(s,0);//没找到即出现0次
map.put(s,count+1);//有相同即加一
}
//2.把刚才这里统计到的字符串内容放到ArrayList中
//keySet相当于得到了一个Set，Set中存放的就是所有的key
ArrayList<String> arrayList=new ArrayList(map.keySet());
//3.按照刚才字符串出现次数，针对arrayList进行排序
//Sort默认是按照元素的自身大小进行升序排序（String的字典序）
//此处我们需要按照字符串出现次数来降序排序，需要通过比较器来自定制比较规则
Collections.sort(arrayList,new MyComparator(map));
return arrayList.subList(0,k);
}
}
22岁生日,没事儿干在这里写博客的还有谁hhhhhhhhhh(祝我自己生日快乐)