作者：学Java的冬瓜博客主页：☀冬瓜的主页????专栏：【Java 数据结构与算法】内容：1、只出现一次的数字 4、复制带随机指针的链表 5、石头里选出宝石 6、坏键盘打字
文章目录
一、正确选择Map和Set的实现类示例
Main方法：
public static void main(String[] args) {
Random random = new Random();
int[] arr = new int[10_0000];
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(100);
}
f1(arr);
1、统计10w个数中不重复的数据,这些数据0-99
- 使用Set容器来装这些数据
public static void f1(int[] arr){
Set<Integer> set = new HashSet<>(); // TreeSet也行，只是效率上看HashSet更快
for (int i = 0; i < arr.length; i++) {
set.add(arr[i]);
}
System.out.println(set);
}
2、打印10w个数中第一个重复的数据
- 创建一个Set容器，如果当前元素不在Set中，则add，如果已经在Set中，那么这个数据就是第一个重复的数据，打印然后直接return。
public static void f2(int[] arr){
Set<Integer> set = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
if(!set.contains(arr[i])){
// System.out.print(arr[i]+" "); //便于观察
set.add(arr[i]);
}else {
System.out.println();
System.out.println(arr[i]);
return;
}
}
}
3、统计10w个数据当中，每个数据出现的次数
- 遍历原来的数据，把a[i]作为map的key存入map中。遍历时，如果map中还没有以当前a[i]为key的数据，那就存入value=1，如果已经有了key对应的value，那就将value+1再存入。
public static void f3(int[] arr){
// 第一步：遍历原来的数据，统计每个数据出现的次数
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
int key = arr[i];
// 第二步：判断以arr[i]作为key的值是否已经存在
if (map.get(key) == null) {
map.put(key,1);
}else {
int val = map.get(key);
map.put(key, val + 1);
}
}
System.out.println(map);
}
二、Map和Set的OJ题
1、只出现一次的数字
法一：异或
- 相同的数异或结果为0，0和非0数异或结果为这个数。因为只有一个数只出现了1次，其它数都出现了两次，所以把数组中所以元素拿来异或，异或的结果就是这个只出现一次的数。
// 法一：使用异或
class Solution {
public int singleNumber(int[] nums) {
int x = nums[0];
for(int i=1; i<nums.length; i++){
x^=nums[i];
}
return x;
}
}
法二：Set解决
- 。因为只有一个数只出现了1次，其它数都出现了两次。遍历这个数组时，当我们遇到一个不在Set中的数据时，就把数据add进Set，当遇到一个在Set中的数据时，把这个数从Set中移除，这样Set中就只剩下了只出现一次的数据。
// 法二：使用集合Set
class Solution {
public int singleNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int i=0; i<nums.length; i++){
if(!set.contains(nums[i])){
set.add(nums[i]);
}else{
set.remove(nums[i]);
}
}
for(Integer x : set){
return x;
}
return -1;
}
}
法三：Map解决
- 先遍历一遍数组，使用Map统计各个数据出现的次数，再把Map拿来遍历，如果当前数据的Key对应的value == 1，那结果就是这个数据对应的key。
// 法三：使用集合Map
class Solution {
public int singleNumber(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++){
int key = nums[i];
if(map.get(key) == null){
map.put(key,1);
}else{
int val = map.get(key);
map.put(key,val+1);
}
}
// 开始遍历map,先把map变成set
Set<Map.Entry<Integer,Integer>> entrySet = map.entrySet();
for(Map.Entry<Integer,Integer> entry : entrySet){
if(entry.getValue() == 1){
return entry.getKey();
}
}
return -1;
}
}
2、只出现一次的数字II
// 使用Map解决
class Solution {
public int singleNumber(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++){
int key = nums[i];
if(map.get(key) == null){
map.put(key,1);
}else{
int val = map.get(key);
map.put(key,val+1);
}
}
// 开始遍历map,先把map变成set
Set<Map.Entry<Integer,Integer>> entrySet = map.entrySet();
for(Map.Entry<Integer,Integer> entry : entrySet){
if(entry.getValue() == 1){
return entry.getKey();
}
}
return -1;
}
}
3、只出现一次的数字 III
法一：Set解决
// 使用Set解决
class Solution {
public int[] singleNumber(int[] nums) {
// 法一：使用Set
Set<Integer> set = new HashSet<>();
for(int i=0; i<nums.length; i++){
if(!set.contains(nums[i])){
set.add(nums[i]);
}else{
set.remove(nums[i]);
}
}
List<Integer> list = new ArrayList<>();
for(Integer x : set){
list.add(x);
}
int[] ret = new int[list.size()];
for(int i=0; i<list.size(); i++){
ret[i] = list.get(i);
}
法二：Map解决
// 使用map解决
class Solution {
public int[] singleNumber(int[] nums) {
// 用Map统计每个元素出现的次数
Map<Integer,Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++){
int key = nums[i];
if(map.get(key) == null){
map.put(key,1);
}else{
int val = map.get(key);
map.put(key,val+1);
}
}
// 把结果放进ArrayList
List<Integer> list = new ArrayList<>();
int cnt = 0;
Set<Map.Entry<Integer,Integer>> entrySet = map.entrySet();
for(Map.Entry<Integer,Integer> entry : entrySet){
if(entry.getValue() == 1){
list.add(entry.getKey());
}
}
注意：遍历map时使用lambda表达式更简单
// map.forEach((k,v)->{
// if(v == 1){
// list.add(k);
// }
// });
// 把结果放进数组
int[] ret = new int[list.size()];
for(int i=0; i<list.size(); i++){
ret[i] = list.get(i);
}
return ret;
}
}
4、复制带随机指针的链表
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
Map<Node,Node> map = new HashMap<>();
Node cur = head;
// 第一步：第一次遍历链表，申请新的空间，传节点的val值，把旧节点作为key,对应位置的新节点作为value存入map。
while(cur != null){
Node newNode = new Node(cur.val);
map.put(cur,newNode);
cur = cur.next;
}
// 第二步：第二次遍历链表，把新节点的next和random引用根据map指向正确的节点
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);
}
}
- 第一次遍历链表，申请新的空间，传节点的val值，把旧节点作为key，对应位置的新节点作为value存入map。
第二次遍历链表，代码是map.get(cur).next = map.get(cur.next);当前cur是原节点，通过map和cur，map.get(cur)就是原节点对应的新节点，而map.get(cur.next)是原节点的下一个节点对应位置的新节点。
第三步，返回原链表对应头节点的新链表的头节点。
如果还有问题，在第二次开始遍历时，见下图：
5、石头里选出宝石
法一：两个for循环
//法一：使用两个for循环，借助ArrayList集合(或者使用个count计数也可)
class Solution {
public int numJewelsInStones(String jewels, String stones) {
List<Character> list = new ArrayList<>();
for (int i = 0; i < jewels.length(); i++) {
char a = jewels.charAt(i);
for (int j = 0; j < stones.length(); j++) {
char b = stones.charAt(j);
if (a == b) {
list.add(a);
}
}
}
return list.size();
法二：Set的contains方法
// 法二：使用Set的contains方法
class Solution {
public int numJewelsInStones(String jewels, String stones) {
int count = 0;
Set<Character> set = new HashSet<>();
for(int i=0; i<jewels.length(); i++){
char a = jewels.charAt(i);
set.add(a);
}
for(int i=0; i<stones.length(); i++){
char b = stones.charAt(i);
if(set.contains(b)){
count++;
}
}
return count;
}
}
6、坏键盘打字
链接：【牛客.旧键盘】
import java.util.*;
public class Main {
public static void func(String str1, String str2){
// 1、把str2实际输入的字符放进Set中
Set<Character> set = new HashSet<>();
for(char ch : str2.toUpperCase().toCharArray()){
set.add(ch);
}
// 2、遍历str1,把已经打印的破坏键盘字符放进setHaveRead，未打印的打印
Set<Character> setHaveRead = new HashSet<>();
for(char ch : str1.toUpperCase().toCharArray()){
// 注意：第一个条件用于过滤未破坏的键盘字符；第二个条件用于过滤破坏了的键盘的已经打印了的字符。
//那两者都非，才是破坏键盘又没有打印的字符。
if(!set.contains(ch) && !setHaveRead.contains(ch)){
setHaveRead.add(ch);
System.out.print(ch);
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str1 = in.nextLine();
String str2 = in.nextLine();
func(str1,str2);
}
}
-
使用set来存储未坏键盘的大写字符，然后来处理应输入字符的大写字符。
具体操作：1、把str2实际输入的字符放进Set中 2、遍历str1,把已经打印的破坏键盘字符放进setHaveRead，未打印的打印 -
满足条件
if(!set.contains(ch) && !setHaveRead.contains(ch)){ setHaveRead.add(ch);时才打印。第一个条件用于过滤未破坏的键盘字符；第二个条件用于过滤破坏了的键盘的已经打印了的字符。那两者都非，才是破坏键盘又没有打印的字符。 -
另一个思路是写第二个Set未brokenSet，装坏的键盘，让这些字符在brokenSet中自动去重。这种方法在牛客网这道题上过不了，在牛客网这道题中题目默认要求按照字符串从前到后打印破坏的键盘。而Set(TreeSet关于key有序，HashSet无序)，并不一定会按照题目从前到后的顺序打印坏的键盘。