1. 只出现一次的数字

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

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

💯解题思路:

思路1：

使用异或 ; 相同的两个数异或的结果是0，把数组所有数异或一遍，由于给定的数据一定有一个唯一的，所以最终得到的结果就是唯一数。

思路2：

使用Set，Set中的元素不重复，遍历数组 , 判断Set中是否含有这个数，如果含有这个数，就将Set里面的这个数删除，否则存入该数，最终Set剩下的数为唯一数。

class Solution {
    //方法一:练习使用Set
    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 (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }
    //方法二:使用异或
    /*public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }
        return ret;
    }*/
}

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

在线OJ : 138. 复制带随机指针的链表

给你一个长度为 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：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。

💯解题思路:

使用Map，键值对为<已知链表结点地址, 复制链表结点地址>

第一次遍历已知链表时，创建复制链表对象的结点并将它们结点地址以<已知链表结点地址, 复制链表结点地址>键值对的形式存入Map中，然后第二次遍历已知链表，根据已知链表结点找到Map中对应复制链表的结点将复制链表结点链接起来 .

/*
// 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;
        while(cur != null) {
            Node node = new Node(cur.val);
            map.put(cur, node);
            cur = cur.next;
        }
        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. 宝石与石头

在线OJ : 771. 宝石与石头

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

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

示例 1：

输入：jewels = "aA", stones = "aAAbbbb"
输出：3

示例 2：

输入：jewels = "z", stones = "ZZ"
输出：0

提示：

1 <= jewels.length, stones.length <= 50
jewels 和 stones 仅由英文字母组成
jewels 中的所有字符都是 唯一的

💯解题思路:

将宝石 jewels 放入Set中，设置一个计数器 , 然后遍历石头stones 判断 jewels中是否含有stones 中的字符，含有则计数器++ .

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++) {
            set.add(jewels.charAt(i));
        }
        for (int i = 0; i < stones.length(); i++) {
            if(set.contains(stones.charAt(i))) {
                count++;
            }
        }
        return count;
    }
}

4. 旧键盘

在线OJ : [编程题]旧键盘

题目详情：

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

输入描述:

输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、以及下划线“_”（代表空格）组成。题目保证2个字符串均非。

输出描述:

按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。

输入 :

7_This_is_a_test
_hs_s_a_es

输出 :

7TI

💯解题思路:

对比应该输入的字符串和实际得到的字符串，如果应该输入字符串中的字母没有出现在实际得到的字符串中，则这些字母就是键盘中坏了的字母键。

我们可将实际被输入的字符串添加到Set中，然后遍历应该输入的字符串，找到Set中不存在的字母，并输出这些字母，

由于应该输入的字符串中可能存在重复的字符，且要按顺序输出，我们可以采用一个辅助的集合Set用来查重，就是输出前判断这个集合中是否含有这个字符，如果含有则不输出，不含有则输出并将该元素放入辅助集合中。

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
    public static void func(String strInput, String strOutput) {
        Set<Character> set = new HashSet<>();
        for (char ch : strOutput.toUpperCase().toCharArray()) {
            set.add(ch);
        }
        Set<Character> badSet = new HashSet<>();
        for (char ch : strInput.toUpperCase().toCharArray()) {
            if(!badSet.contains(ch) && !set.contains(ch)) {
                badSet.add(ch);
                System.out.print(ch);
            }
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String strInput = scanner.nextLine();
        String strOutput = scanner.nextLine();
        func(strInput, strOutput);
    }
}

5. 前K个高频单词

在线OJ : 692. 前K个高频单词

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

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

示例 1：

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。

注意：

1 <= words.length <= 500
1 <= words[i] <= 10
words[i] 由小写英文字母组成。
k 的取值范围是 [1, 不同 words[i] 的数量]

进阶：尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

💯解题思路:

使用Map统计单词词频。
利用topK求前k个词频频率最高的元素（所以需要小根堆），如果出现词频相同的单词，优先保留字典顺序在前的。
将堆里面的元素存入List，并使用Collections类工具逆序List。
返回List。

注意: 我们在一开始构造完大小为K的小根堆时 , 堆中可能会有相同频率的元素, 题目要求频率相同时, 要以字典顺序在前的优先 ; 所以当频率相同时, 我们需要更改比较器的比较方式, 让其以字符串去比较; 也就是说在重写比较器的compare方法时，除了考虑单词频，还需要考虑词频相同时，将字典顺序较大的单词放在堆顶。

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        //统计每个单词出现的次数
        Map<String, Integer> map = new HashMap<>();
        for (String word:words) {
            if(map.get(word) == null)  {
                map.put(word,1);
            }else {
                Integer val = map.get(word);
                map.put(word, val+1);
            }
        }
        //建立大小为k的小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if(entry.getValue().compareTo(top.getValue()) > 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    if(entry.getValue().compareTo(top.getValue()) == 0) {
                        if(entry.getKey().compareTo(top.getKey()) < 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            ret.add(minHeap.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}

6. 下厨房

在线OJ : WY8 下厨房

题目详情：

牛牛想尝试一些新的料理，每个料理需要一些不同的材料，问完成所有的料理需要准备多少种不同的材料。

输入描述:

每个输入包含 1 个测试用例。每个测试用例的第 i 行，表示完成第 i 件料理需要哪些材料，各个材料用空格隔开，输入只包含大写英文字母和空格，输入文件不超过 50 行，每一行不超过 50 个字符。

输出描述:

输出一行一个数字表示完成所有料理需要多少种不同的材料。

输入:

BUTTER FLOUR
HONEY FLOUR EGG

输出:

💯解题思路:

题目中有多组输入
利用split()方法将输入的字符串以空格分割到数组当中, 再遍历数组放到一个Set中
输出Set中元素个数即可.

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Set<String> set = new HashSet<>();
        while (scanner.hasNext()) {
            String str = scanner.nextLine();
            String[] strs = str.split(" ");
            for (String s : strs) {
                set.add(s);
            }
        }
        System.out.println(set.size());
    }
}

【LC】HashMap和HashSet应用OJ

1. 只出现一次的数字

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

3. 宝石与石头

4. 旧键盘

5. 前K个高频单词

6. 下厨房

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【LC】HashMap和HashSet应用OJ

1. 只出现一次的数字

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

3. 宝石与石头

4. 旧键盘

5. 前K个高频单词

6. 下厨房

热门文章

最新文章

相关电子书