- Leetcode 349 两个数组的交集
- Leetcode 350 两个数组的交集 II
- Leetcode 242 有效的字母异位词
- Leetcode 202 快乐数
- Leetcode 290 单词规律
- Leetcode 205 同构字符串
- Leetcode 451 根据字符出现频率排序
- Leetcode 454 四数相加 II
- Leetcode 49 字母异位词分组
- Leetcode 447 回旋镖的数量
- Leetcode 219 存在重复元素 II
- Leetcode 217 存在重复元素
- Leetcode 220 存在重复元素 III
- Leetcode 5603 确定两个字符串是否接近
- Leetcode 299 猜数字
常见的查找问题分为两类
- 查找有无 如：元素 a 是否存在，一般使用的是 set
- 查找对应关系 如：元素 a 出现了几次，一般使用的是 map
Leetcode 349 两个数组的交集
一个很简单的方法就是使用 Set 的 retainAll 方法，该方法可以求出两个 Set 集合的交集
class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> integers = Arrays.stream(nums1).boxed().collect(Collectors.toSet());Set<Integer> integers2 = Arrays.stream(nums2).boxed().collect(Collectors.toSet());HashSet<Integer> hashSet = new HashSet<>(integers);integers.retainAll(integers2);int[] ints = new int[integers.size()];int i = 0;for (Integer integer : integers) {ints[i++] = integer;}return ints;}}
或者不使用内置的 API，而是使用遍历的方式
class Solution{public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> integers = Arrays.stream(nums1).boxed().collect(Collectors.toSet());Set<Integer> result = new HashSet<>();for (int i = 0; i < nums2.length; i++) {if(integers.contains(nums2[i])){result.add(nums2[i]);}}return result.stream().mapToInt(Integer::intValue).toArray();}}
甚至如果 Stream 更熟练一些，就可以写个一句话版本的
class Solution{public int[] intersection(int[] nums1, int[] nums2) {return Arrays.stream(nums1).boxed().collect(Collectors.toSet()).stream().filter(t-> Arrays.stream(nums2).boxed().collect(Collectors.toSet()).contains(t)).mapToInt(Integer::intValue).toArray();}}
Leetcode 350 两个数组的交集 II
这题需要注意的点是：两个数组的交集中可以出现重复的元素，且重复元素出现的次数是两个数组中该元素出现的最少次数
因此不难想到使用 Map，通过对数字的出现频次进行统计后，遍历判断交集元素后根据频次较少的那一边将对应元素加入到列表中，最后转为数组并返回
class Solution {public int[] intersect(int[] nums1, int[] nums2) {HashMap<Integer, Integer> n1 = new HashMap<>();HashMap<Integer, Integer> n2 = new HashMap<>();//记录出现的数字和其频度for (int i : nums1) {n1.put(i, n1.getOrDefault(i, 0)+1);}for (int i : nums2) {n2.put(i, n2.getOrDefault(i, 0)+1);}ArrayList<Integer> list = new ArrayList<>();//储存出现次数较少的 keyfor(int key: n1.keySet()){if(n2.containsKey(key)){for(int i = 0; i<Math.min(n1.get(key), n2.get(key)); i++){list.add(key);}}}return list.stream().mapToInt(Integer::intValue).toArray();}}
Leetcode 242 有效的字母异位词
没啥好说的，比较频度和 key 即可，直接开干
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) return false;
HashMap<Character, Integer> smap = new HashMap<>();
HashMap<Character, Integer> tmap = new HashMap<>();
for (char c : s.toCharArray()) {
smap.put(c, smap.getOrDefault(c, 0)+1);
}
for (char c : t.toCharArray()) {
tmap.put(c, tmap.getOrDefault(c, 0)+1);
}
for(Character c: smap.keySet()){
if(!tmap.containsKey(c) || !tmap.get(c).equals(smap.get(c))){
return false;
}
}
return true;
}
}
Leetcode 202 快乐数
对于这道题，首先需要明确：当出现了重复元素时，就永远不会有结果
因此，这道题的基本思路是
使用 Set，判断当前集合中是否有该元素，如果没有，则进行添加，然后将该元素分解求和；如果有，则返回 false
最后返回 n==1
class Solution {
public boolean isHappy(int n) {
HashSet<Integer> set = new HashSet<>();
while( n!=1 && !set.contains(n) ){
set.add(n);
n = splitNum(n);
}
return 1==n;
}
public int splitNum(int n){
int sum = 0;
while(n>0){
int a = n%10;
n /= 10;
sum += a*a;
}
return sum;
}
}
Leetcode 290 单词规律
class Solution {
public boolean wordPattern(String pattern, String str) {
String[] s = str.split(" ");
if(s.length != pattern.length()) return false;
Map<Character,String> map = new HashMap();
//这是一种强映射关系，一个字母一定只与一个单词对应，且当前单词必须与字母对应的单词相同
for(int i = 0;i<pattern.length();i++){
char key = pattern.charAt(i);
//如果不存在这个键，则加入映射
if(!map.containsKey(key)){
//不存在键，但是存在值， 说明一个值对应了两个键，返回 false
if(map.containsValue(s[i])) return false;
//建立映射
map.put(key,s[i]);
}else{
//当前取出的 pattern 存在，但是对应的值与当前的单词不匹配，则返回 false
if(!map.get(key).equals(s[i])) return false;
}
}
return true;
}
}
Leetcode 205 同构字符串
这个题和上一个题很类似，甚至可以说是相同，只不过强映射关系从 c to s 到了 c to c，因此直接套上一题的模板
class Solution {
public boolean isIsomorphic(String s, String t) {
Map< Character, Character> map = new HashMap<>();
char[] chars = t.toCharArray();
for(int i = 0; i<t.length(); i++){
char c = s.charAt(i);
if(!map.containsKey(c)){
if(map.containsValue(chars[i])) return false;
map.put(c, chars[i]);
}else{
if(!map.get(c).equals(chars[i])) return false;
}
}
return true;
}
}
Leetcode 451 根据字符出现频率排序
看到这类具有映射关系的题目首先都应该想到使用 Map。而这道题的这难点在于如何处理 Map 中的数据
假设有这样一条字符串： “abccedd”，使用 Map 构建字符到其出现次数的映射
那么 Map 中映射的结果就应该是
a:1 b:1 c:2 e:1 d:2
同时，题目对于相同长度的字符的顺序并没有要求，因此有一个简单的思路就是遍历 Map 中的数据，遍历一次就将当前字符对应的 value - 1，最先达到 0 的字符说明其长度最短，将其加入一个 StringBuilder 中，所以我们需要遍历 s.length 次，才能将 Map 中所有的字符都遍历完成 ( value 全部归 0 )，最后的 StringBuilder 则是按照出现次数递增的字符组成的，然后 reverse 一下并返回即可
class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0)+1);
}
StringBuilder res = new StringBuilder();
Map<Character, Integer> tmp = new HashMap<>(map);
//遍历所有的字符 length() 次，保证所有的字符都会被遍历完成
//当次数为 0 时，从原来的 map 中取出该 map 的次数驾到 sb 中
//最先归 0 的字符说明其出现次数最少！
for (int i = 0; i < s.length(); i++) {
for (char c: tmp.keySet()) {
tmp.put(c, tmp.get(c) - 1);
if (tmp.get(c) == 0) {
for (int j = 0; j < map.get(c); j++) {
res.append(c);
}
}
}
}
return res.reverse().toString();
}
}
Leetcode 454 四数相加 II
题目中已经给出了数据规模为 [0, 500]， 因此我们应该先思考什么样的时间复杂度是可以承受的
如果是暴力解法的话，四层循环就需要 500 次基本操作
假设使用查找表对四个数组中的任意一个数组进行映射
那么问题就变成了对另外三个数组进行循环，然后求与查找表相加为 0 的情况，但是 500 同样也是难以接受的
因此我们可以将四个数组中的两个数组的所有可能的相加结果及其出现次数作为查找表的元素，这样只需要遍历另外两个数组就可以找到解，从而让基本操作次数就只有 500 次了， 而这个查找表的大小最大情况下就有 500*500 个元素
class Solution {
public int fourSumCount(int[] a, int[] b,
int[] c, int[] d) {
//记录相加的值及其出现的次数
Map<Integer, Integer> map = new HashMap<>();
//遍历所有可能性
for (int value : c) {
for (int i : d) {
map.put(value + i, map.getOrDefault(value + i, 0) + 1);
}
}
int result = 0;
//遍历另外两个数组，找到组合
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b.length; j++) {
if(map.containsKey(-(a[i] + b[j]))){
//与 -(a[i]+b[j]) 相等的值出现了多少次就有多少个解
//比如 a=1 b=-3 c=3 d=-1 和 a=-3 b=1 c=-1 d=3
//就相当于两个解
result += map.get(-(a[i] + b[j]));
}
}
}
return result;
}
}
用上面的思路类推，我们可以尝试将 A+B 和 C+D 的每一种可能放入两个查找表中，然后遍历其中一个查找表找出与另一个查找表中相反的 k，将二者的 v 相乘就得出了所有的解
class Solution {
public int fourSumCount(int[] a, int[] b,
int[] c, int[] d) {
Map<Integer, Integer> abMap = new HashMap<>();
Map<Integer, Integer> cdMap = new HashMap<>();
for (int aValue : a) {
for (int bValue : b) {
abMap.put(aValue+bValue, abMap.getOrDefault(aValue+bValue, 0)+1);
}
}
for (int cValue : c) {
for (int dValue : d) {
cdMap.put(cValue+dValue, cdMap.getOrDefault(cValue+dValue, 0)+1);
}
}
int result = 0;
for (Map.Entry<Integer, Integer> abEntry : abMap.entrySet()) {
if(cdMap.containsKey(-abEntry.getKey())){
result += abEntry.getValue() * cdMap.get(-abEntry.getKey());
}
}
return result;
}
}
Leetcode 49 字母异位词分组
首先我们可以做一个 String 到 List
于是现在的问题就是如何找到一个字符串的异构词了。仔细思考一下：eat，tea，ate 三个异构词，通过排序后最终都会是一个词 aet，因此我们可以把 aet 这个词当做 key，在后续的每一次排序后，将排序结果的字符串形式作为 containsKey() 的参数，查看 map 中是否有该 key ，如果没有的话，则作为新的 key 加入；否则的话则 get 到 key 对应的列表，加入当前字符串，因为当前字符串通过排序后与 key 的表现形式一致，是 key 对应的异构词
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
//做排序的目的是为了统一异位词的顺序，借此判断当前字符串是否是某一 key 的异构，如果是的话，加入 key 对应的列表中，进行分组
Arrays.sort(chars);
String key = new String(chars);
//如果排序后的字符串不存在于 map 中，则不破坏原本的结构将当前的字符串 str 加入到列表中
if(!map.containsKey(key)){
ArrayList<String> list = new ArrayList<>();
list.add(str);
map.put(key, list);
}else{
//如果排序后的字符串已经存在于map中了，说明当前字符串是已存在字符串的异构
map.get(key).add(str);
}
}
return new ArrayList<>(map.values());
}
}
Leetcode 447 回旋镖的数量
这题的题目可能有些抽象，其实大概意思就是给你 N 个点，求出这 N 个点能组成多少个 ( i, j, k ) 列表( 每个元素为一个点 )，使得点 i 到 j == 点 i 到 k 的距离，这样一个列表称为回旋镖
在理解题意之后，其实这个题就没有这么难了。可以很容易的想到，我们可以通过遍历第 i 个点之外的所有点，来找到 i 与所有点的距离并记录这个距离出现的次数，如果这个次数大于等于 2 的话，就说明回旋镖数量 >= 1
比如说，距离 i 点为 3 的点有 N 个，那么基于与 i 距离为 3 的回旋镖的数量就是 N*( N-1 )。其它距离同理
因此，可以很容易的看出映射关系应该是 距离:该距离出现的次数
class Solution {
public int numberOfBoomerangs(int[][] points) {
int result = 0;
for (int i = 0; i < points.length; i++) {
Map<Integer, Integer> map = new HashMap<>();
for (int j = 0; j < points.length; j++) {
if( i!=j ){
int des = (points[i][0]-points[j][0])*
(points[i][0]-points[j][0])+
(points[i][1]-points[j][1])*
(points[i][1]-points[j][1]);
map.put(des, map.getOrDefault(des, 0)+1);
}
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() >= 2){
result += entry.getValue()*(entry.getValue()-1);
}
}
}
return result;
}
}
Leetcode 219 存在重复元素 II
这道题也可以使用滑动窗口来解决，但是不同于前面所说的滑动窗口，这里并不需要知道左右两个边界而只需要知道范围内是否有相同的值，且滑动窗口的大小是固定的，所以我们可以通过一个 set 来滑动窗口模拟
题意简单的来理解，就是说：如果在 k 个元素中存在相同的元素，那么就返回 true
如果理解了题意，那么过程就很简单了
- 对 nums[] 进行循环，如果当前元素在 set 中已经存在了，说明大小为 k 的范围内已经存在了这个元素，返回 true
- 如果不存在这个元素，则将其加入 set 中
- 再加入新的元素 (扩大窗口) 后判断当前 set 大小是否大于了 k，如果大于则从 set 中删除最左边的元素，维持窗口大小
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<>();
//维持窗口 set 的大小 <= k
for (int i = 0; i < nums.length; i++) {
//只要在窗口范围内存在重复元素，就返回 true
if(set.contains(nums[i])){
return true;
}
//如果不存在，则添加到 set 中
set.add(nums[i]);
//如果已经存在了 k+1 个元素，则移除最左边的元素
//保持窗口大小 <= k
if(set.size() > k){
set.remove(nums[i-k]);
}
}
return false;
}
}
Leetcode 217 存在重复元素
这个问题的思路还用说吗？一句话就完事儿了
class Solution {
public boolean containsDuplicate(int[] nums) {
return nums.length != Arrays.stream(nums).boxed().collect(Collectors.toSet()).size();
}
}
Leetcode 220 存在重复元素 III
这个题目与 219 题很类似，区别在于多了一条限制条件
仔细品味一下这个限制条件
| nums[i] - nums[j] | <= t
--> nums[i]-nums[j] <= t && nums[i]-nums[j] >= -t
--> nums[i] <= t+nums[j] && nums[i] >= nums[j] - t
所以其实我们需要在滑动窗口中找到一个数能满足上述条件即可
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
//返回 set 中大于等于(最接近) (long)nums[i] - (long)t 的值
//如果这个值还小于等于 (long)nums[i] + (long)t)
//那么就返回 true
Long tar = set.ceiling((long)nums[i] - (long)t);
if( tar != null && tar <= ((long)nums[i] + (long)t)){
return true;
}
set.add((long)nums[i]);
if(set.size() > k){
set.remove((long)nums[i-k]);
}
}
return false;
}
}
Leetcode 5603 确定两个字符串是否接近
这个题比较考验找规律
- 如果两个字符串中出现的字符不相同，一定不相似
- 如果两个字符串中所有字符的次数不完全一致，一定不相似
( 比如：a:1 b:2 c:3 和 a:1 b:3 c:3 一定是 false )
基于上面两个原则，我们可以通过 TreeSet 来实现对两个字符串中字符出现次数的排序，然后判断是否完全一致
class Solution {
public boolean closeStrings(String word1, String word2) {
Map<Character, Integer> map1 = new HashMap<>();
Map<Character, Integer> map2 = new HashMap<>();
Set<Object> set1 = new TreeSet<>();
Set<Object> set2 = new TreeSet<>();
for (char c : word1.toCharArray()) {
set1.add(c);
map1.put(c, map1.getOrDefault(c, 0)+1);
}
for (char c : word2.toCharArray()) {
set2.add(c);
map2.put(c, map2.getOrDefault(c, 0)+1);
}
//判断字符是否完全一致
if (!set1.equals(set2)) return false;
set1.clear();
set2.clear();
for (Map.Entry<Character, Integer> entry : map1.entrySet()) {
set1.add(entry.getValue());
}
for (Map.Entry<Character, Integer> entry : map2.entrySet()) {
set2.add(entry.getValue());
}
//判断字符出现的次数是否完全一致 ( 不用管对应的字符是否一致，因为最终都能通过转换得到 )
if(!set1.equals(set2)) return false;
return true;
}
}
Leetcode 299 猜数字
题目比较长，但是题意总结下来有以下两点
- 两个字符串中，有多少个相同索引下相同的字符，就有多少个 bulls
- 两个字符串中，假设有 secret 中有 n 个字符 ‘c’，guess 中有 m 个字符 ‘c’，且索引都不同，那么就认为有 n>m ? m:n 个 cows ( 猜多了也只有 n 个，猜少了那么就是猜的 m 个 )
有了上面的思路，代码就不难写了
class Solution {
public String getHint(String secret, String guess) {
//使用长度为 10 的数组，存储 0~9 数字
int[] nums = new int[10];
int cows = 0, bulles = 0;
for (int i = 0; i < secret.length(); i++) {
//字符相同，则公牛+1
if(secret.charAt(i) == guess.charAt(i)){
bulles++;
}
}
//创建两个 hashMap，统计各自的词频
HashMap<Character, Integer> scMap = new HashMap<>();
HashMap<Character, Integer> gsMap = new HashMap<>();
//不同位置上的字母才进行统计
for (int i = 0; i < secret.length(); i++) {
char sc = secret.charAt(i);
char gs = guess.charAt(i);
if(sc != gs){
scMap.put(sc, scMap.getOrDefault(sc, 0)+1);
gsMap.put(gs, gsMap.getOrDefault(gs, 0)+1);
}
}
// 对 gsMap / scMap 进行遍历，
// 两个 map 中各自找到对应字符的出现次数，如果没有出现则为 0
for (Map.Entry<Character, Integer> entry : gsMap.entrySet()) {
int cow1 = scMap.getOrDefault(entry.getKey(), 0);
int cow2 = gsMap.getOrDefault(entry.getKey(), 0);
//然后选择较小的那一个出现次数加到 cows 上
cows += Math.min(cow1, cow2);
}
return bulles + "A" + cows + "B";
}
}
若有收获，就点个赞吧
0 人点赞
