本篇是哈希表啦。
242. 有效的字母异位词
思路分析：
其实这个题比较简单，（我踏马一开始想复杂了，竟然想用HashMap），看了题解才发现有一个更加精妙的做法，就是用一个数组来装字符串中每个字母出现的个数，因为题目说了都是小写字母，所以我们只需要申请一个26大小的数组空间（数组也是哈希表的一种），然后下标用s[i]-'a’来表示（注意这里只能减a，因为减其他的值肯定就小于（为负值了，比如a-z就小于0了）我们的数组下标了呀）。因为a到z的ASCII码在内存是连续的，那么我用字符串中的每一位字符去减同一个值，得到的值肯定都是唯一的，那么我们就将它存入数组中（具体存在了哪里不用管）将该位置的元素值+1即可。然后我们再对字符串t做一次相同的 *** 作，只不过这次是减法，但是经历过这次 *** 作以后，如果两个字符串中的字符出现出现都一样多，那么一加一减肯定都是正好为0的，此时返回true，但是只要有一个位置不为0，那么就返回false。
非常的精妙。
class Solution {
public boolean isAnagram(String s, String t) {
int[] record = new int[26];//26个字母（只包括小写嘛）
for(char c : s.toCharArray()){
record[c - 'a'] += 1;
}
for(char c : t.toCharArray()){
record[c - 'a'] -= 1;
}
for(int i=0;i
383. 赎金信
题目描述：
思路分析：
其实大体上和上一题的思路是差不多的，但是这回的题目不能直接照抄上面的代码，因为如果照抄上面的代码会因为masazine中存在其他字符而导致无法通过最后的判断record元素值是否为来返回false和true。但其实也不复杂，我们只需要再需要一个HashSet来存一下ransomNote中的元素，然后在后面比对时进行判断即可，代码如下：
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
//还是用之前的老方法，不过这里需要加个HashSet来帮忙判断
HashSet set = new HashSet<>();
int[] record = new int[26];
for(char c : ransomNote.toCharArray()){
record[c - 'a'] += 1;
set.add(c);//存入该字符
}
for(char c : magazine.toCharArray()){
if(set.contains(c)){ //如果存在该字符才进行自减 *** 作，否则其他字符存在也会自减，那么record中的某一元素就肯定不为0了
record[c - 'a'] -= 1;
if(record[c -'a'] == 0){//自减完成后如果当前元素值为0，说明该字符已经满足题目条件了
//是可以由masazine中的字符构成的
set.remove(c); //那么我们移除掉这个字符，避免后续判断而它还存在
}
}
}
for(int c : record){
if(c != 0) return false;
}
return true;
}
}
49. 字母异位词分组
题目描述：
思路分析：
一开始没啥思路，囿于了前面两题的解题思路，妈的。
看了题解之后发现还蛮简单的，其实我们可以用一个HashMap来进行记录，map的key值为一个该组字母异位词的标志字符串，而怎么拿到这个标志字符串我们可以通过排序的方式来拿到，比如nat和tan是一组字母异位词，那么我们只要将其中任意的字符串比如nat进行排序得到ant，不难发现tan排序过后也是ant，我们只需要将排序过后的字符串作为key键存入map中，然后将所有符合这个排序规则的字符串都存入map中的value就可以了。
代码如下：
class Solution {
public List> groupAnagrams(String[] strs) {
//先拿到一个HashMap
HashMap> map = new HashMap<>();
//循环取出strs中的每一个字符串来进行规则匹配
for(String str : strs){
//要想对字符进行排序，那么要先将其转化为字符数组
char[] arr = str.toCharArray();
//对数组进行排序
Arrays.sort(arr);
//排序完成后又转化为字符串，因为下面要存进map中了
String s = String.valueOf(arr);
//判断是否已经出现在map中的key键了
if(!map.containsKey(s)){
//如果不存在，那么字符串s就该作为key键存入
//并让它的value值实例化一个ArrayList
map.put(s,new ArrayList<>());
}
//如果存在，那么就往该key键所对应的value中的list追加字符串即可
//下面这段的连写可以简要分析一下
//map.get(Key)返回的是该key所对应的value
//而本题中key所对应的value是一个ArrayList集合
//所以是返回的该List集合再用的.add()方法添加的字符串
map.get(s).add(str);
}
return new ArrayList<>(map.values());
}
}
438. 找到字符串中所有字母异位词
题目描述：
思路：
都在代码注释里了，总体思路其实就是暴力破解，和上面那道题差不多思路。
但是效率很低，最好还是用高级点的滑动窗口做法。
class Solution {
public List findAnagrams(String s, String p) {
//和上题同样的思路，排序比较
//先将p字符串排序拿到标志异位串
char[] pChar = p.toCharArray();
Arrays.sort(pChar);
//创建结果数组
List resultList = new ArrayList<>();
//从s字符串的第一个值开始逐一往后截取p字符串长度的字符数组与标志串进行比较
for (int i = 0; i <= s.length() - p.length(); i++) {//防止数组越界
//用substring从s字符串中截取子串
char[] iPlusChar = s.substring(i, i + p.length()).toCharArray();
//对截取的子串排序
Arrays.sort(iPlusChar);
//比较是否相等，相等则返回该字符的起始下标
if (String.valueOf(pChar).equals(String.valueOf(iPlusChar))) {
resultList.add(i);
}
}
return resultList;
}
}
滑动窗口做法：
（下回做）
349. 两个数组的交集
思路分析：
这题没啥思路啊，就暴力就可以，代码中有详细注释。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
//这就直接暴力哈希就可以解决啦
//创建结果集合
List list = new ArrayList<>();
//创建HashSet，set集合因为其中不允许有重复值因此很好用
HashSet set = new HashSet<>();
//将nums1中所有值（不允许重复的）放入set中
for(int n : nums1){
set.add(n);
}
//一一取出nums2中的值，判断其是否在set中存在
for(int n : nums2){
//如果存在那说明是并集的一部分，往结果集合中添加
if(set.contains(n)){
list.add(n);
//然后移除该值，因为下次还要判断
set.remove(n);
}
}
//最后将List集合转为题目需要的int类型数组
int[] arr = new int[list.size()];
int i = 0;
for(int n : list){
arr[i] = n;
i++;
}
return arr;
}
}
350.两个数组的交集 II
题目描述：
思路描述：
题目意思是说由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
那么用哈希表法如下：
首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
//创建结果集合
List list = new ArrayList<>();
//用哈希表，key存值，value存对应出现的次数
HashMap map = new HashMap<>();
//往map中存值（用哪个数组都行，不过用小数组的空间会消耗较少）
for(int n : nums1){
//如果key键为n的key存在则返回对应的value值，不然创建对应为n的key键，value值默认设置为0
int cnt = map.getOrDefault(n,0);
cnt++;//n出现一次，则对应的value数目+1
map.put(n,cnt);//更新map中n键对应的value值
}
//遍历nums2，看是否在map中有对应key值
for(int n : nums2){
int cnt = map.getOrDefault(n,0);
//如果返回value值大于0，说明该n为交集部分
if(cnt > 0){
list.add(n);//存进结果数组中
cnt--;//出现次数减1
map.put(n,cnt);//更新value值
}
}
//list转化为int数组
int[] arr = new int[list.size()];
int i = 0;
for(int n : list){
arr[i] = n;
i++;
}
return arr;
}
}
202. 快乐数
题目描述：
思路分析：
这个题得用到数学里面的一点东西
我也不会证明，反正记结论就是了
1、最终会得到 11。
2、最终会进入循环，出现重复值而永远到不了1。
3、值会越来越大，最后接近无穷大（但这种不可能发生，最终都会处于243范围内，所以不需要考虑）
综上所述的话代码就比较好写了：
class Solution {
public boolean isHappy(int n) {
//创建HashSet集合来存入每一次求得的值
HashSet set = new HashSet<>();
//循环检查每一个数是否于set中出现
while(n != 1 && !set.contains(n)){
set.add(n); //如果没有存过，那么添加该次结果
//去取下一个值
n = getNextNum(n);
}
//跳出循环时有两种情况
//要么n==1，要么n!=1而set集合中已经出现重复（说明循环永远无法变到1）
return n == 1;
}
//getNextNum方法用来取下一次值
private int getNextNum(int n){
int res = 0; //返回结果
//循环取n每一位上的平方和
while(n > 0){
int temp = n % 10;
res = res + temp*temp;
n = n / 10;
}
return res;
}
}
1. 两数之和
题目描述
思路描述：
…妈的，我是直接暴力解的。
不过还有一种思路是用哈希表map，key键存数组元素，key对应的value值存其对应下标，因为哈希表底层的实现很复杂，所以查询效率很高，复杂度会比暴力低很多（其实也不是很多，也就还行）。
暴力破解：
class Solution {
public int[] twoSum(int[] nums, int target) {
//快慢指针
int slow = 0;//慢指针
int fast = 1;//快指针
//创建结果数组
int[] res = new int[2];
while(true){
//满足条件返回答案
if(nums[slow] + nums[fast] == target){
res[0] = slow;
res[1] = fast;
return res;
}
//判断fast是否来到数组边界
//如果到了边界，那么刷新slow和fast
//slow++
//fast=slow+1
//就是暴力破解...
if(fast == nums.length-1){
slow++;
fast = slow + 1;
}else{
fast++;
}
}
}
}
哈希表法：
class Solution {
public int[] twoSum(int[] nums, int target) {
//创建结果数组
int[] res = new int[2];
//创建哈希Map
HashMap map = new HashMap<>();
for(int i=0;i
454. 四数相加 ||
题目描述：
思路：
暴力会超时，但用哈希说实话也就是勉强过掉，效率也不见得高，我看的是代码随想录中的题解答案。
代码如下：
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
//创建返回结果res
int res = 0;
//创建HashMap
HashMap map = new HashMap<>();
//遍历nums1和nums2，将其元素之和作为key、出现次数作为value存入map中
for(int n : nums1){
for(int m: nums2){
int temp = n + m;//求两数之和
if(map.containsKey(temp)){ //如果存在该和，将其出现次数+1
map.put(temp,map.get(temp)+1);
}else{//如果不存在，那么将其初始出现次数置为1
map.put(temp,1);
}
}
}
//遍历nums3和nums4，求其二者元素之和与0的差值
//然后在map中查找该差值是否存在，存在即将其value值累加给res
for(int n : nums3){
for(int m : nums4){
int temp =0 - n - m;
if(map.containsKey(temp)){ //存在该key值
res += map.get(temp);//得到该key值对应的value值给res累加
}
}
}
return res;
}
}
15. 三数之和
思路：
三指针法，具体可看卡尔大佬的思路分析：
代码如下：
class Solution {
public List> threeSum(int[] nums) {
List> list = new ArrayList<>();
//对数组进行排序
Arrays.sort(nums);
//fou循环用三指针法
for(int i = 0;i < nums.length;i++){ //i就是最左边的指针
//排序之后如果第一个元素已经大于0，那么无论如何也不可能有三元组之和为0
//但是这道判断其实省略也能AC，加一个只不过是可以让判断更少一些，耗时更少
if(nums[i] > 0) return list;
//数组去重逻辑
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
//定义left指针，right指针
int left = i + 1;
int right = nums.length - 1;
//对中间数组进行 *** 作，即left与right之间的数组
while(right > left){
//条件符合，添加进list结果集合中
if(nums[i] + nums[left] + nums[right] == 0){
List li = new ArrayList<>();
li.add(nums[i]);
li.add(nums[left]);
li.add(nums[right]);
list.add(li);
//对中间数组去重（因为返回结果中不能有重复值）
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
//指针移动
right--;
left++;
}else if(nums[i] + nums[left] + nums[right] > 0){
//说明三数之和大了，那么right指针向左移动
right--;
}else {//说明三数之和小了，那么left指针向右移动
left++;
}
}
}
return list;
}
}
18. 四数之和
题目描述：
思路描述：
大体上和之前的三数之和那道题目思路差不多，只不过这道是四数之和，那么我们只要再多加一道循环即可。
代码如下：
class Solution {
public List> fourSum(int[] nums, int target) {
//大题思路和三数之和差不多
List> list = new ArrayList<>();
//排序
Arrays.sort(nums);
//四指针循环判断
for(int i=0; i 0 && nums[i] == nums[i - 1]) continue;
for(int j=i+1; j i+1 && nums[j] == nums[j - 1]) continue;
//就是对left和right指针进行循环查找
int left = j + 1;
int right = nums.length - 1;
while(right > left){
//如果找到符合条件的，加入结果数组
if(nums[i] + nums[j] + nums[left] + nums[right] == target){
List li = new ArrayList<>();
li.add(nums[i]);
li.add(nums[j]);
li.add(nums[left]);
li.add(nums[right]);
list.add(li);
//指针收缩之前，进行去重判断
while(right > left && nums[right] == nums[right - 1]) right--;
while(right > left && nums[left] == nums[left + 1]) left++;
//双指针收缩后移
right--;
left++;
}else if(nums[i] + nums[j] + nums[left] + nums[right] > target){
right--;
}else{
left++;
}
}
}
}
return list;
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）