欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

代码随想录刷题攻略哈希表笔记

时间:2023-07-31
代码随想录 刷题攻略 哈希表 笔记

代码随想录 刷题攻略 笔记1.关于哈希表,你该了解这些!2.哈希表:可以拿数组当哈希表来用,但哈希值不要太大

242.有效的字母异位词 3.哈希表:查找常用字符

1002、查找常用字符 4.哈希表:哈希值太大了,还是得用set

349、两个数组的交集小结 5.哈希表:用set来判断快乐数

202、快乐数小结 6.哈希表:map等候多时了

1、两数之和 7.哈希表:其实需要哈希的地方都能找到map的身影

第454题.四数相加II 8.哈希表:这道题目我做过?

383、赎金信 9.哈希表:解决了两数之和,那么能解决三数之和么?

第15题、三数之和 10.双指针法:一样的道理,能解决四数之和

第18题、四数之和小结

核心代码 11.哈希表:总结篇!(每逢总结必经典) 代码随想录 刷题攻略 笔记

代码随想录 刷题攻略
代码随想录 刷题攻略 笔记

1.关于哈希表,你该了解这些!

讲义地址

2.哈希表:可以拿数组当哈希表来用,但哈希值不要太大

讲义地址

242.有效的字母异位词

leetcode地址

输入字符有限且比较小,使用数组比hashmap快。

class Solution { public boolean isAnagram(String s, String t) { int sLen = s.length(); int tLen = t.length(); if(sLen != tLen){ return false; } char temp = 0; Map map = new HashMap<>(); for (int i = 0; i < sLen; i++) { temp = s.charAt(i); map.put(temp, map.getOrDefault(temp,0) + 1); } for (int i = 0; i < tLen; i++) { temp = t.charAt(i); if(!map.containsKey(temp)){ return false; } map.put(temp, map.get(temp) - 1); if(map.get(temp) < 0){ return false; } } return true; }}

3.哈希表:查找常用字符

讲义地址

1002、查找常用字符

leetcode地址

class Solution { public List commonChars(String[] words) { int[] minfreq = new int[26]; Arrays.fill(minfreq, Integer.MAX_VALUE); // 用一个26位的数组记录字母在这么多个词中的最低频率 for (String word : words) { int[] freq = new int[26]; int length = word.length(); for (int i = 0; i < length; ++i) { char ch = word.charAt(i); ++freq[ch - 'a']; } for (int i = 0; i < 26; ++i) { minfreq[i] = Math.min(minfreq[i], freq[i]); } } // 打印26个字母的最低频率 List ans = new ArrayList(); for (int i = 0; i < 26; ++i) { for (int j = 0; j < minfreq[i]; ++j) { ans.add(String.valueOf((char) (i + 'a'))); } } return ans; }}

4.哈希表:哈希值太大了,还是得用set

讲义地址

349、两个数组的交集

leetcode地址

class Solution { public int[] intersection(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int length1 = nums1.length; int length2 = nums2.length; int[] temp = new int[length1 > length2 ? length2 : length1]; int index0 = 0; int index1 = 0; int index2 = 0; while (index1 < length1 && index2 < length2) { int num1 = nums1[index1]; int num2 = nums2[index2]; if (num1 < num2) { index1++; } else if (num1 > num2) { index2++; } else { if (index0 == 0 || num1 != temp[index0 - 1]) { temp[index0] = num1; index0++; } index1++; index2++; } } return Arrays.copyOfRange(temp, 0, index0); }}

小结

先排序+集合比map要快。

使用双指针

关键:

if (index0 == 0 || num1 != temp[index0 - 1]) { temp[index0] = num1; index0++; }

5.哈希表:用set来判断快乐数

讲义地址

202、快乐数

leetcode地址

class Solution { public int getNext(int n) { int totalSum = 0; while (n > 0) { int d = n % 10; n = n / 10; totalSum += d * d; } return totalSum; } public boolean isHappy(int n) { int slowRunner = n; int fastRunner = getNext(n); while (fastRunner != 1 && slowRunner != fastRunner) { slowRunner = getNext(slowRunner); fastRunner = getNext(getNext(fastRunner)); } return fastRunner == 1; }}

小结

使用快慢指针判断是否有环,这比使用set更节省空间。

6.哈希表:map等候多时了

讲义地址

1、两数之和

leetcode地址

class Solution { public int[] twoSum(int[] nums, int target) { Map hashtable = new HashMap(); for (int i = 0; i < nums.length; ++i) { if (hashtable.containsKey(target - nums[i])) { return new int[]{hashtable.get(target - nums[i]), i}; } hashtable.put(nums[i], i); } return new int[0]; }}

7.哈希表:其实需要哈希的地方都能找到map的身影

讲义地址

第454题.四数相加II

leetcode地址

class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { HashMap hashMap = new HashMap<>(); for (int i = 0; i < nums1.length; i++) { for (int j = 0; j < nums2.length; j++) { hashMap.put(nums1[i] + nums2[j], hashMap.getOrDefault( nums1[i] + nums2[j], 0) + 1); } } int res = 0; for (int i = 0; i < nums3.length; i++) { for (int j = 0; j < nums4.length; j++) { if (hashMap.containsKey(-nums3[i] - nums4[j])) { res += hashMap.get(-nums3[i] - nums4[j]); } } } return res; }}

8.哈希表:这道题目我做过?

讲义地址

383、赎金信

leetcode地址

class Solution { public boolean canConstruct(String ransomNote, String magazine) { if (ransomNote.length() > magazine.length()) { return false; } HashMap map = new HashMap<>(); for (int i = 0; i < magazine.length(); i++) { char temp = magazine.charAt(i); map.put(temp, map.getOrDefault(temp,0)+1); } for (int i = 0; i < ransomNote.length(); i++) { char temp = ransomNote.charAt(i); if (map.containsKey(temp)){ map.put(temp,map.get(temp)-1); if (map.get(temp) ==0){ map.remove(temp); } }else { return false; } } return true; }}


如果使用数组来计数,而不是使用hashmap,效率会更高。

9.哈希表:解决了两数之和,那么能解决三数之和么?

讲义地址

第15题、三数之和

leetcode地址

class Solution { public List> threeSum(int[] nums) {// 总时间复杂度:O(n^2) List> res = new ArrayList<>(); if (nums == null || nums.length < 3) return res; Arrays.sort(nums); for (int i = 0; i < nums.length - 2; i++) { // target必须大于0 if (nums[i] > 0) break; // 去重 if (i > 0 && nums[i] == nums[i - 1]) continue; int left = i + 1; int right = nums.length - 1; int target = -nums[i]; while (left < right) { if (nums[left] + nums[right] == target) { res.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right]))); left++; right--; // 去重 while (left < right && nums[left] == nums[left - 1]) left++; // 去重 while (left < right && nums[right] == nums[right + 1]) right--; } else if (nums[left] + nums[right] < target) { left++; } else { right--; } } } return res; }}

10.双指针法:一样的道理,能解决四数之和

讲义地址

第18题、四数之和

leetcode地址

class Solution { public List> fourSum(int[] nums, int target) { List> res = new ArrayList<>(); if (nums == null || nums.length < 4) return res; Arrays.sort(nums); for (int i = 0; i < nums.length - 3; i++) {// if (nums[i] > target) break; if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i+1; j < nums.length - 2; j++) {// if (nums[j] > target - nums[i]) break; if (j>i+1 && nums[j] == nums[j-1]) continue; int left = j + 1; int right = nums.length - 1; int newTarget = target-nums[i]-nums[j]; while (left < right) { if (nums[left] + nums[right] == newTarget) { res.add(new ArrayList<>(Arrays.asList(nums[i],nums[j], nums[left], nums[right]))); left++; right--; while (left < right && nums[left] == nums[left - 1]) left++; while (left < right && nums[right] == nums[right + 1]) right--; } else if (nums[left] + nums[right] < newTarget) { left++; } else { right--; } } } } return res; }}

小结

这题与上一题解法一样

核心代码

就是上一题的代码

11.哈希表:总结篇!(每逢总结必经典)

讲义地址

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。