- 只出现一次的数字
- 复制带随机指针的链表（百度面试题）
- 宝石与石头
- 坏键盘打字
- 前K个高频单词（有难度，你确定不来挑战一下？）
- 字符串中的第一个唯一字符
链接：LeetCode136：只出现一次的数字
题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。
找出那个只出现了一次的元素。
思路：
① 去重：我们可以用HashSet把成对的元素去掉，留下的就是只出现一次的元素了，时间复杂度O(n)
② 位运算：只要是不占用额外空间来实现，就往位运算上考虑。
异或 *** 作，相同为1，不同为0
代码：
//方法一：去重
class Solution {
public int singleNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for(Integer i : nums){
if(!set.contains(i)){
//如果不在set中，add *** 作
set.add(i);
}else{
//如果在set中，将该元素删除！
set.remove(i);
}
}
for(int i=0;i<nums.length;i++){
if(set.contains(nums[i])){
return nums[i];
}
}
return -1;
}
}
//方法二：位运算(异或 *** 作：不同为1，相同为0)
class Solution {
public int singleNumber(int[] nums) {
int num = 0;
for(int i=0;i<nums.length;i++){
num^=nums[i];
}
return num;
}
}
链接：LeetCode138：复制带随机指针的链表
题目：给你一个长度为 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 作为传入参数。
思路：看到深拷贝链表，就想到，不能直接进行单个结点的拷贝，而是应该建立新结点和旧结点之间的映射关系。
利用哈希表，我们将旧结点和新结点存储起来，形成键值对的形式，方便查找next和random指针。
如下图所示：
①首先我们从head开始遍历链表，建立新结点，将next和random都置为null；
②其次再遍历一遍链表，查询哈希表，补充next和random的指向；
③最后返回新head结点。
代码：
//哈希表
class Solution {
public Node copyRandomList(Node head) {
if(head==null) return null;
//构造一个哈希表，用来存储<旧结点引用，新结点引用>
HashMap<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);
}
}
链接：LeetCode771：宝石与石头
题目： 给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。
stones 中每个字符代表了一种你拥有石头的类型，你想知道你拥有的石头中有多少是宝石。
(提示：jewels 中的所有字符都是 唯一的)
例如：输入：jewels = “aA”, stones = “aAAbbbb” 输出：3
思路：题目说的青菜萝卜一大筐！实际上就是统计stones字符串中有多少个与jewels字符串重复的字符（区分大小写）。
我们可以将jewels中的字母放到集合当中，依次遍历stones中的字母 ，如果存在，count+1，否则，遍历下一个。
代码：注意！字符串转数组：toCharArray()方法，取出字符串中的字母：charAt()方法
class Solution {
public int numJewelsInStones(String jewels, String stones) {
//首先 提供一个set容器
HashSet<Character> set = new HashSet<>();
int count = 0;
//①将jewels中的字母存放至set中
for(int i = 0;i<jewels.length; i++){
set.add(jewels.charAt(i));
}
//②依次遍历stones
for(char ch:stones.toCharArray()){
if(set.contains(ch)){
count++;
}
}
return count;
}
}
链接：牛客网：坏键盘打字
题目：旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。
现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。
输入描述：输入在2行中分别给出应该输入的文字、以及实际被输入的文字。
每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、以及下划线“_”（代表空格）组成。
题目保证2个字符串均非空。
输出描述：按照发现顺序，在一行中输出坏掉的键。
其中英文字母只能输出大写，每个坏键只输出一次。
题目保证至少有1个坏键。
例如：期望的是7_This_is_a_test 实际的是_hs_s_a_es
输出：7TI
思路：考查set集合，我们首先将实际输出的字符串全部转为大写，放入set集合中；也将期望输出的字符串转为大写依次遍历，如果包含在set集合中，则跳过，否则，输出该字符（set筛选的过程）
代码：
import java.util.*;
public class Main {
public static void main(String[] args){
//提供一个setActual容器，用于存储实际输入的字符串
HashSet<Character> setActual = new HashSet<>();
Scanner scanner = new Scanner(System.in);
String str1 = scanner.nextLine(); //期望的输入
String str2 = scanner.nextLine();//实际的输入
//将实际的输入存储至set中
for(char ch:str2.toUpperCase().toCharArray()){
setActual.add(ch);
}
//我们将没输出的字符放到setBroken集合中进行去重
HashSet<Character> setBroken = new HashSet<>();
//先将str1全部转为大写，依次遍历，如果不在set中就打印！
for(char ch:str1.toUpperCase().toCharArray()){
if(!setActual.contains(ch) && !setBroken.contains(ch)){
setBroken.add(ch);
System.out.print(ch);
}
}
}
}
链接：LeetCode692：前K个高频单词
题目：给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。
如果不同的单词有相同出现频率， 按字典顺序 排序。
输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”]
思路：
首先我们进行词频统计。
利用哈希表将单词和频率存储起来；
建有K个元素的小顶堆。
根据题目要求处理不同的情况；
将最后建好的小顶堆输出至List集合中（此时输出的频率是由低到高的），最后逆序输出（因为输出要按单词出现频率由高到低排序）。
代码：
class Solution {
public List<String> topKFrequent(String[] words, int k) {
if(words.length==0) return null;
//①词频统计，得到一张哈希表<单词，频次>
HashMap<String, Integer> map = new HashMap<>();
for (String word: words) {
if(!map.containsKey(word)){
map.put(word,1);
}else{
int count = map.get(word);
map.put(word,count+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) {
//堆还没建满 (词频相同的情况下) 原本应该是o1-o2 但由于最后还要反转，所以我们在处理词品相同的情况时，一开始就建大顶堆。
if(o1.getValue().compareTo(o2.getValue())==0){
return o2.getKey().compareTo(o1.getKey());
}
//按照频次建小顶堆
return o1.getValue()-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(top!=null){
if(entry.getValue().compareTo(top.getValue())==0){
//词频相同，判断单次顺序，首字母靠前的入堆
if(entry.getKey().compareTo(top.getKey())<0){
minHeap.poll();
minHeap.offer(entry);
}
}else{
//词频不同
if(entry.getValue() > top.getValue()){
minHeap.poll();
minHeap.offer(entry);
}
}
}
}
}
//③top出堆，进List
ArrayList<String> ret = new ArrayList<>();
for (int i = 0; i < k; i++) {
Map.Entry<String, Integer> top = minHeap.poll();
if(top!=null){
ret.add(top.getKey());
}
}
//因为输出是按词频由高到低排序，所以对链表进行反转
Collections.reverse(ret);
return ret;
}
}
链接：LeetCode387：字符串中的第一个唯一字符
题目：给定一个字符串s, 找到它的第一个不重复的字符，并返回它的索引。
如果不存在，则返回-1。
思路：首先想到的就是采用HashMap容器做词频统计，返回出现频率为1的单词下标。
代码：
//法1：哈希表解法
class Solution {
public int firstUniqChar(String s) {
if(s==null) return -1;
//词频统计
HashMap<Character, Integer> map = new HashMap<>();
for(int i = 0;i<s.length();i++){
char ch = s.charAt(i);
if(!map.containsKey(ch)){
map.put(ch, 1);
}else{
int count = map.get(ch);
map.put(ch,count+1);
}
}
//遍历哈希表，找到词频为1的单词的下标
for(int i = 0;i<s.length();i++){
if(map.get(s.charAt(i))==1){
return i;
}
}
return -1;
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）