福建省建设工程信息网站,vs2010做网站,网站备案幕布多少钱,公司企业发展建议当我们遇到了要快速判断一个元素是否出现集合里的时候#xff0c;就要考虑哈希法
242、有效地字母异位词
给定两个字符串 s 和 t #xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。
注意#xff1a;若 s 和 t 中每个字符出现的次数都相同#xff0c;则称 s 和 t…当我们遇到了要快速判断一个元素是否出现集合里的时候就要考虑哈希法
242、有效地字母异位词
给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。
注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词。
示例 1:
输入: s anagram, t nagaram
输出: true示例 2:
输入: s rat, t car
输出: false数组也是哈希表用数组来记录
class Solution {public boolean isAnagram(String s, String t) {//打表记录的方式int[] record new int[26];for(int i0;is.length();i) //统计各个字母出现的次数//注意数组是length属性String是length()方法{record[s.charAt(i)-a];}for(int i0;it.length();i) {record[t.charAt(i)-a]--; //可以用两个表 也可以用一个表相减看是否为0}for(int i0;irecord.length;i) //注意这里要变量所有字母{if(record[i]!0) return false;}return true;}
}383、赎金信
给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以返回 true 否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1
输入ransomNote a, magazine b
输出false示例 2
输入ransomNote aa, magazine ab
输出false示例 3
输入ransomNote aa, magazine aab
输出true即magazine里的每个字符的个数要大于等于ransomNote的每个字符的个数因此相减后要小于等于0也可以用两个数组
class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] record new int [26];for(int i0;iransomNote.length();i){record[ransomNote.charAt(i)-a];}for(int i0;imagazine.length();i){record[magazine.charAt(i)-a]--;}for(int i0;irecord.length;i){if(record[i]0) return false;}return true;}
}#49、字母异位词分组
给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs [eat, tea, tan, ate, nat, bat]
输出: [[bat],[nat,tan],[ate,eat,tea]]示例 2:
输入: strs []
输出: [[]]示例 3:
输入: strs [a]
输出: [[a]]因为字符异位词他们每个字母排序后都是相同的因此可以把这个排序后的字符串当做键
根据字母异位词排序之后是是相等的来使用map进行分组
class Solution {public ListListString groupAnagrams(String[] strs) {//想到使用map来进行每个排列有一个键把相同的放到一个键值对当中//因为字符异位词他们每个字母排序后都是相同的因此可以把这个排序后//的字符串当做键MapString,ListString map new HashMapString,ListString();for(String str:strs){char[] arraystr.toCharArray();Arrays.sort(array);String keynew String(array); //数组可以直接构造字符串ListString list map.getOrDefault(key,new ArrayListString());list.add(str);map.put(key,list);}return new ArrayListListString(map.values());}
}438、 找到字符串中所有字母异位词
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串包括相同的字符串。
示例 1:
输入: s cbaebabacd, p abc
输出: [0,6]
解释:
起始索引等于 0 的子串是 cba, 它是 abc 的异位词。
起始索引等于 6 的子串是 bac, 它是 abc 的异位词。示例 2:
输入: s abab, p ab
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 ab, 它是 ab 的异位词。
起始索引等于 1 的子串是 ba, 它是 ab 的异位词。
起始索引等于 2 的子串是 ab, 它是 ab 的异位词。封装一个判断字母异位词的方法然后利用双指针判断长度等于p的长度的子串与p是否是字母异位词
class Solution {public ListInteger findAnagrams(String s, String p) {int lenss.length();int lenpp.length();ListInteger ans new ArrayList();for(int l0,rlenp;rlens;l,r){//注意这里的subString不包括rif(isAnagram(s.substring(l,r),p))ans.add(l);}return ans;}//判断是否为字母异位词public boolean isAnagram(String s, String t) {//打表记录的方式int[] record new int[26];for(int i0;is.length();i) //统计各个字母出现的次数//注意数组是length属性String是length()方法{record[s.charAt(i)-a];}for(int i0;it.length();i) {record[t.charAt(i)-a]--; //可以用两个表 也可以用一个表相减看是否为0}for(int i0;irecord.length;i) //注意这里要变量所有字母{if(record[i]!0) return false;}return true;}
}350、两个数组的交集二
给你两个整数数组 nums1 和 nums2 请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数应与元素在两个数组中都出现的次数一致如果出现次数不一致则考虑取较小值。可以不考虑输出结果的顺序。
示例 1
输入nums1 [1,2,2,1], nums2 [2,2]
输出[2,2]示例 2:
输入nums1 [4,9,5], nums2 [9,4,9,8,4]
输出[4,9]用数组作为哈希表
class Solution {public int[] intersect(int[] nums1, int[] nums2) {int[] record1 new int[1002];int[] record2 new int[1002];ListInteger result new ArrayList();for(int i0;inums1.length;i){record1[nums1[i]];}for(int i0;inums2.length;i){record2[nums2[i]];}for(int i0;irecord1.length;i){if(record1[i]0 record2[i]0){//只需要添加这一行即添加次数最小的个数for(int j0;j(record1[i]record2[i]?record1[i]:record2[i]);j)result.add(i);}}int[] ansnew int[result.size()];for(int i0;iresult.size();i){ans[i]result.get(i); //get(i)是取第i个位置的元素}return ans;}
}202、快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true 不是则返回 false 。
示例 1
输入n 19
输出true
解释
1² 9² 82
8² 2² 68
6² 8² 100
1² 0² 0² 1因为可能会循环所以应该用set记录出现过的sum如果sum没有出现过加入set中如果出现过说明循环则结束循环。
class Solution {public boolean isHappy(int n) {SetInteger setnew HashSet();while(n!1) //一直while直到1为止{int sum0;while(n0){int tn%10;sumt*t;nn/10;}nsum;if(!set.contains(sum)) set.add(sum);else return false;}return true;}
}也可以用字符串的方式实现求平方和
class Solution {public boolean isHappy(int n) {SetInteger set new HashSet();//用来记录sum出现的次数while(n!1){int sum0;String sString.valueOf(n);for(int i0;is.length();i){char cs.charAt(i);int tc-0;sumt*t;}nsum;if(!set.contains(sum)) set.add(sum);else return false;}return true;}
}1、两数之和
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1
输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2
输入nums [3,2,4], target 6
输出[1,2]示例 3
输入nums [3,3], target 6
输出[0,1]当我们需要查询一个元素是否出现过或者一个元素是否在集合里的时候就要第一时间想到哈希法。
本题我们不仅要知道元素有没有遍历过还要知道这个元素对应的下标需要使用 key value结构来存放key来存元素value来存下标那么使用map正合适
一个存一个找。
如果是返回的是数值不是下标还可以使用双指针法。
class Solution {public int[] twoSum(int[] nums, int target) {MapInteger,Integer map new HashMap();int[] result new int[2];for(int i0;inums.length;i){map.put(nums[i],i);}for(int i0;inums.length;i){Integer valuemap.get(target-nums[i]);if(value !null value!i) //注意这里要判空并且要不相等//这里要先判断是否为空防止空指针{result[0]i;result[1]value;return result;}}return result;}
}454、四数相加二
给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足
0 i, j, k, l nnums1[i] nums2[j] nums3[k] nums4[l] 0
示例 1
输入nums1 [1,2], nums2 [-2,-1], nums3 [-1,2], nums4 [0,2]
输出2
解释
两个元组如下
1. (0, 0, 0, 1) - nums1[0] nums2[0] nums3[0] nums4[1] 1 (-2) (-1) 2 0
2. (1, 1, 0, 0) - nums1[1] nums2[1] nums3[0] nums4[0] 2 (-1) (-1) 0 0示例 2
输入nums1 [0], nums2 [0], nums3 [0], nums4 [0]
输出1直接四重循环复杂度太高可以考虑二重循环用一个map把两数之和存储起来key是两数之和value是个数。
两数之和存另外两数之和找。
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {//直接暴力会四重循环会超时所以使用map记录一下MapInteger,Integer map new HashMap();int count0;for(int i:nums1) //使用增强for循环{for(int j:nums2){int value map.getOrDefault(ij,0);map.put(ij,value1);}}for(int i:nums3){for(int j:nums4){count map.getOrDefault(0-i-j,0);}}return count;}
}#15、三数之和
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。
示例 1
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。示例 2
输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。示例 3
输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。哈希解法去重比较麻烦容易超时所以使用双指针的方法。
拿这个nums数组来举例首先将数组排序然后有一层for循环i从下标0的地方开始同时定一个下标left 定义在i1的位置上定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a b c 0我们这里相当于 a nums[i]b nums[left]c nums[right]。
接下来如何移动left 和right呢 如果nums[i] nums[left] nums[right] 0 就说明 此时三数之和大了因为数组是排序后了所以right下标就应该向左移动这样才能让三数之和小一些。
如果 nums[i] nums[left] nums[right] 0 说明 此时 三数之和小了left 就向右移动才能让三数之和大一些直到left与right相遇为止。
时间复杂度O(n^2)。
两数之和 就不能使用双指针法因为两数之和要求返回的是索引下标 而双指针法一定要排序一旦排序之后原数组的索引就被改变了。
如果两数之和要求返回的是数值的话就可以使用双指针法了。
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayListListInteger();Arrays.sort(nums); //先排序//找出a b c 0// a nums[i], b nums[left], c nums[right]for(int i0;inums.length;i){//排序之后第一个元素大于0则和一定不会为0if(nums[i]0) //也相当于剪枝return result;//去重aif(i0 nums[i]nums[i-1])continue;int sum0;int lefti1;int rightnums.length-1;while(rightleft){sumnums[i]nums[left]nums[right];if(sum0)right--;else if(sum0)left;//相加为0else{ //等于0 的话先去重再减result.add(Arrays.asList(nums[i],nums[left],nums[right]));// 去重逻辑应该放在找到一个三元组之后对b 和 c去重while(rightleft nums[right]nums[right-1]) right--;while(rightleft nums[left]nums[left1]) left;right--;left;}}}return result;}
}18、四数之和
给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d na、b、c 和 d互不相同nums[a] nums[b] nums[c] nums[d] target
你可以按 任意顺序 返回答案 。
示例 1
输入nums [1,0,-1,0,-2,2], target 0
输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2
输入nums [2,2,2,2,2], target 8
输出[[2,2,2,2]]提示
1 nums.length 200-109 nums[i] 109-109 target 109
四数之和和三数之和是一个思路都是使用双指针法, 基本解法就是在三数之和的基础上再套一层for循环。
但是有一些细节需要注意例如 不要判断nums[k] target 就返回了三数之和 可以通过 nums[i] 0 就返回了因为 0 已经是确定的数了四数之和这道题目 target是任意值。比如数组是[-4, -3, -2, -1]target是-10不能因为-4 -10而跳过。但是我们依旧可以去做剪枝逻辑变成
nums[i]0 nums[i]target
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger result new ArrayList();Arrays.sort(nums);for(int i0;inums.length;i){//剪枝if(nums[i]0 nums[i]target)return result;//对nums[i]去重if(i0 nums[i-1]nums[i])continue;for(int ji1;jnums.length;j){//对nums[j]去重if(ji1 nums[j-1]nums[j])continue;int leftj1;int rightnums.length-1;while(rightleft){//nums的范围是int的范围直接加会溢出long sum(long) nums[i]nums[j]nums[left]nums[right];if(sumtarget)right--;else if(sumtarget)left;else{result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));// 对nums[left]和nums[right]去重while(rightleft nums[right]nums[right-1]) right--;while(rightleft nums[left]nums[left1]) left;left;right--;}}}}return result;}
}#128、最长连续序列
给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1
输入nums [100,4,200,1,3,2]
输出4
解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2
输入nums [0,3,7,2,5,8,4,6,0,1]
输出9class Solution {public int longestConsecutive(int[] nums) {//使用哈希表然后进行遍历只有找到初始值的时候才会进入while开始计数//总的复杂度还是OnSetInteger set new HashSet();for(int num:nums){set.add(num);}int result0; //存储最大的长度for(int num:set){if(set.contains(num-1)) //说明不是初始值continue;else{//说明前面没有元素int curNumnum;int ans0; //存储每次的长度while(set.contains(curNum)){curNum;ans;}resultMath.max(result,ans);}}return result;}
}560、和为 K 的子数组
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1
输入nums [1,1,1], k 2
输出2示例 2
输入nums [1,2,3], k 3
输出2使用前缀和哈希表
两个位置对应的前缀和相减就是两个位置之间的和。
所以使用map保存着遍历的前缀和然后判断sum-k对应的前缀和的个数。
class Solution {public int subarraySum(int[] nums, int k) {//前缀和哈希表//存储前缀和以及对应的个数//为什么前缀和可以相等因为数据有正有负MapInteger,Integer map new HashMap();map.put(0,1); //前缀和为0的个数只有一个int sum0; //计算前缀和int count0; //计算结果个数for(int num:nums){sumnum;//先获得sum-k前缀和的个数再把前缀和sum放入map中//因为当k0时先放入sum前缀和再获得个数会多一个个数if(map.containsKey(sum-k))countmap.get(sum-k);map.put(sum,map.getOrDefault(sum,0)1);}return count;}
}
