liuyubobobo_查找问题
查找问题
总结：其对查找问题的范围相对宽泛，很多找出、找到等等的问题均认为是查找问题，而查找问题常用的两种数据结构就是set 和 map。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-547PlI2V-1570278837489)(http://note.youdao.com/noteshare?id=51bc2549d98fe0d9833e185b09575668&sub=A998BFB2DF9C46D1B2160E9573362E36)]
-
各种不同的实现都有其特殊性能，没有一种是最好的，只有针对不同应用场景才有最佳最适合的，哈希表的方式虽然插入、查找、删除等操作均为O(1)级别的，但是由于其存储元素是按某种方式做散列，不会按元素值大小顺序保存，也就是说哈希表的方式不会保存数据的顺序，而二分搜索树和顺序数组的实现方式会保存元素值的大小顺序信息，这在解决某些问题时会十分方便。比如说查找第k大，第k小的元素，查找比某一个值小的最大元素，查找比某一个值大的最小元素，查找最大、最小元素，等等操作时，二分搜索树和顺序数组会有着比哈希表好很多的性能，因为其本身就是按照顺序存储的，对于上面的查找问题解决起来十分方便。
1. 349 两个数组的交集
- 方法：哈希表set，题目要求找出两个数组的交集，并将交集元素输出并保持唯一，可以考虑将一个数组中的所有元素都放入一个set中，然后遍历另外一个数组，看元素是否在set中，如果在则找到一个交集元素，由于题目要求输出交集所有元素是唯一的，因此将找到的交集元素放入set中，set只用于查找有无而不管查找其数量。利用HashSet 操作时间复杂度是O(1)，因此整体时间复杂度是O(m + n)，空间复杂度是O(n)。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> hashSet = new HashSet<>();
for(int x : nums1)
hashSet.add(x);
HashSet<Integer> resultSet = new HashSet<>();
for(int x : nums2){
if(hashSet.contains(x))
resultSet.add(x);
}
int[] result = new int[resultSet.size()];
int i = 0;
for(int x : resultSet){
result[i++] = x;
}
return result;
}
}
2. 350 两个数组的交集II
- 方法：哈希表map，题目要求找出两个数组的交集，而且不用保证唯一性，和上一题相比，这里去掉了唯一性要求，这就使得只是查找是否交集不够用了，还需要查找两个数组某个重复元素的数量，考虑使用HashMap查找有无交集，并通过键值对保存交集元素数量，由于HashMap时间复杂度是O(1)，因此整体时间复杂度是O(m + n)，空间复杂度是O(n)。
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for(int x : nums1)
hashMap.put(x, hashMap.containsKey(x) ? hashMap.get(x) + 1 : 1);
List<Integer> resultList = new ArrayList<>();
for(int x : nums2){
if(hashMap.containsKey(x) && hashMap.get(x) > 0){
resultList.add(x);
hashMap.put(x, hashMap.get(x) - 1);
}
}
int[] result = new int[resultList.size()];
int i = 0;
for(int x : resultList)
result[i++] = x;
return result;
}
}
3. 242 有效的字母异位词
- 字母异位词：即字母种类和数量相同，但是排列方式不一定相同。
- 方法：哈希表map，用map查找s中的字母及其数量，然后遍历t这个字符串，并将map中查找到对应的字母数量减1，如果map中最后无任何字母，则说明是字母异位词，O(m + n)，空间复杂度O(m)。
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length())
return false;
char[] sChars = s.toCharArray();
char[] tChars = t.toCharArray();
HashMap<Character, Integer> hashMap = new HashMap<>();
for(char x : sChars)
hashMap.put(x, hashMap.containsKey(x) ? hashMap.get(x) + 1 : 1);
for(char x : tChars){
if(!hashMap.containsKey(x))
return false;
else if(hashMap.get(x) == 1)
hashMap.remove(x);
else
hashMap.put(x, hashMap.get(x) - 1);
}
return hashMap.size() == 0;
}
}
4. 202 快乐数
- 如何将一个正整数按各位上的数进行拆解求平方和，将该整数对10取余得到个位，然后将该整数除以10，继续取余，不断得到个位上的数直到除以10后整数为0…
- 找循环点问题，可以考虑用双指针，快慢指针，慢指针走一步，快指针走两步，如果有环(有循环点则就是有环)，快指针一定能追上慢指针。
- 此题就是找循环点，题目已经说明一定有环，只不过这个环可能是1->1,也可能是其他的大环循环，如果循环点是1则为快乐数，如果循环点不是1则不是快乐数。
- 方法一：可以考虑用set记录遍历过的和值，如果当前和值在set中则说明找到了循环点，则判断这个点是否为1即可，是1则为快乐数，不是1则不是快乐数。这样的问题是空间开销会比较大，如果计算过程中经过了很多次拆解计算，那么set会很大。时间复杂度O(n)，空间复杂度O(n)。
class Solution {
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>();
while(!set.contains(1)){
if (set.contains(n))
return false;
else set.add(n);
n = getSumByBit(n);
}
return true;
}
private int getSumByBit(int n){
int bit;
int sum = 0;
while(n != 0){
bit = n % 10;
sum += bit * bit;
n = n / 10;
}
return sum;
}
}
- 方法二：可以考虑用快慢指针，双指针，题目已经保证是有环的，既然是找环的循环点，那么如果有环，则快指针一定能追上慢指针。如果快指针追上了慢指针，则这时有两种情况，一是这个点就是1；二是这个点不是1而是一个大环中的某个点，此时一定没有1；因此当快指针追上慢指针的时候，只需要判断当前这个点是否为1即可判断是否为快乐数。时间复杂度O(n)，空间复杂度O(1)。
class Solution {
public boolean isHappy(int n) {
int slow = n;
int fast = getSumByBit(n);
while (slow != fast){
slow = getSumByBit(slow);
fast = getSumByBit(fast);
fast = getSumByBit(fast);
}
return slow == 1;
}
private int getSumByBit(int n){
int bit;
int sum = 0;
while(n != 0){
bit = n % 10;
sum += bit * bit;
n = n / 10;
}
return sum;
}
}
5. 290 单词规律
- <mark>错误</mark>方法：哈希表set，题目要求判断给定字符串是否符合给定的模式，两两遍历模式字符串的字符，查看对应给定字符串中这两个单词是否和模式规则相同，即模式中这两个字母相同，则这两个单词也应该相同；反之，模式中这两个字母不同，则这两个单词也应该不同。将模式转为字符数组进行遍历，关键在于如何判断两个单词是否相同，考虑通过set进行查找判断，把第一个单词放入set中，然后判断第二个单词是否已经在set中。时间复杂度O(n)，空间复杂度O(1)。
这个方法的问题在于只考虑相邻两个之间的相同不同关系，而给出的模式实际上是包括所有元素在内的关系
比如说 pattern = "abba", str = "dog cat cat fish" 结果应该是false，但是按照上面的方***返回true。
- 方法：哈希表map，仔细思考模式的关键在于对于模式中同一个字母，其应该对应到字符串中的同一个单词，并且反之，字符串中的同一个单词应该对应模式中的同一个字母。按照这个思路，首先遍历一遍模式字符串，并使用map中键为模式中的字母，value为给定字符串中对应的单词，如果相同的模式字符串中的字母对应到了不同的字符串中的单词，则不符合规律；如果所有相同的字母均对应到了相同的单词，则返过来遍历字符串中的所有单词，单词为key，模式字符串中的字母为value，按照上面的思路遍历。时间复杂度为O(n)，空间复杂度为O(n)。
class Solution {
public boolean wordPattern(String pattern, String str) {
char[] patternChars = pattern.toCharArray();
String[] strs = str.split("\\s+");
if ( patternChars.length != strs.length)
return false;
if (patternChars.length == 1)
return true;
// 遍历模式字符串中的所有字母
HashMap<Character, String> map = new HashMap<>();
for(int i = 0; i < patternChars.length; i++){
if(!map.containsKey(patternChars[i]))
map.put(patternChars[i], strs[i]);
else if(!map.get(patternChars[i]).equals(strs[i]))
return false;
}
// 遍历单词字符串中的所有单词
HashMap<String, Character> hashMap = new HashMap<>();
for(int i = 0; i < strs.length; i++){
if(!hashMap.containsKey(strs[i]))
hashMap.put(strs[i], patternChars[i]);
else if(!hashMap.get(strs[i]).equals(patternChars[i]))
return false;
}
return true;
}
}
6. 205 同构字符串
- 方法：哈希表map，这个题目类似于上一题，两个字符串是否同构，按照上一题，就是一个字符串当做模式，另外一个字符串去判断是否符合这个模式，这两个题目是一个意思。时间复杂度O(n)，空间复杂度O(n)。
class Solution {
public boolean isIsomorphic(String s, String t) {
if(s.length() != t.length())
return false;
HashMap<Character, Character> hashMap = new HashMap<>();
for(int i = 0; i < s.length(); i++){
if(!hashMap.containsKey(s.charAt(i)))
hashMap.put(s.charAt(i), t.charAt(i));
else if(!hashMap.get(s.charAt(i)).equals(t.charAt(i)))
return false;
}
hashMap.clear();
for(int i = 0; i < t.length(); i++){
if(!hashMap.containsKey(t.charAt(i)))
hashMap.put(t.charAt(i), s.charAt(i));
else if(!hashMap.get(t.charAt(i)).equals(s.charAt(i)))
return false;
}
return true;
}
}
7. 451 根据字符出现频率排序
- 字符区分大小写。
- 输出答案中，相同字符排在一起。
- 方法一：哈希表map + 桶排序，通过map去查找每一个字母的频次，然后对字母的频次进行排序，这里采用桶排序的方式，创建一个桶，按照字母的频次将字母放入其对应的桶中，字母的频次对应桶数组的索引，然后遍历桶，得到从高频到低频的顺序输出字母。时间复杂度O(n)，空间复杂读为O(n)。
class Solution {
public String frequencySort(String s) {
if(s.length() <= 1)
return s;
Map<Character, Integer> map = new HashMap<>();
int maxFrequence = 0;
for(int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
map.put(ch, map.containsKey(ch) ? map.get(ch) + 1 : 1);
maxFrequence = Math.max(maxFrequence, map.get(ch));
}
ArrayList<Character>[] buckets = new ArrayList[maxFrequence + 1];
for(Character key : map.keySet()){
int frequence = map.get(key);
if(buckets[frequence] == null)
buckets[frequence] = new ArrayList<Character>();
for(int i = 0; i < frequence; i++)
buckets[frequence].add(key);
}
StringBuilder sb = new StringBuilder();
for(int i = buckets.length - 1; i > 0 ; i--){
if(buckets[i] != null)
for(Character x : buckets[i])
sb.append(x);
}
return sb.toString();
}
}
- 方法二：数组 + 普通排序，字符作为数组索引，频率为数组索引对应的值，然后对数组排序，便得到字母的频率顺序，但是需要注意在排序之前保存数组索引和其频次的对应关系，否则在排序之后字母和其对应的频次对应关系被打乱。时间复杂度O(nlogn)，空间复杂度O(1)。虽然时间复杂度比方法一高，但实际上数组访问速度是远快于其桶中对象的。因此实际执行时间比方法一短。
class Solution {
public String frequencySort(String s) {
int[] hash = new int[256];
for(int i = 0; i < s.length(); i++){
hash[s.charAt(i)]++;
}
int[] hashSearch = hash.clone();
Arrays.sort(hash);
StringBuilder sb = new StringBuilder();
for(int i = hash.length - 1; i >= 0; i--){
int frequence = hash[i];
for(int j = 0; j < hashSearch.length; j++){
if(hashSearch[j] == frequence){
while(hashSearch[j] > 0){
sb.append((char)j);
hashSearch[j]--;
}
}
}
}
return sb.toString();
}
}
8. 1 两数之和
- 方法一：暴力解法，时间复杂度O(n^2)。暴力遍历所有数组中数的两两组合。
class Solution {
public int[] twoSum(int[] nums, int target) {
for(int i = 0; i < nums.length; i++)
for(int j = i + 1; j < nums.length; j++)
if(nums[i] + nums[j] == target)
return new int[]{i, j};
return new int[]{-1, -1};
}
}
- 方法二：排序，二分搜索；为防止排序后原来数组中数字和索引的对应关系信息丢失，首先复制数组，然后排序，通过二分查找target - nums[i]完成。时间复杂度O(nlogn)，空间复杂度O(n)。
这个方法在实现的时候有很多细节，比如给的数组中的数只要正整数吗？二分查找查找不到的时候返回什么值，该值可能会作为正确答案返回吗？
- 方法三：双指针，指针对撞，首先将数组排序（但是要注意题目要求返回元素在原数组中的索引，如果直接排序会丢失在原数组中位置的信息，如何处理能够使得排序后仍然得到位置信息？），然后利用对撞指针解决，时间复杂度O(nlogn)。
- 将原数组复制一份，用于查找数值在原数组中的位置索引。
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] numsSearch = nums.clone();
int[] result = new int[2];
Arrays.sort(nums);
int left = 0, right = nums.length - 1;
boolean isValied1 = true, isValied2 = true;
while(left < right){
if(nums[left] + nums[right] == target){
for(int i = 0; i < numsSearch.length; i++){
if(isValied1 && numsSearch[i] == nums[left]){
result[0] = i;
isValied1 = false;
}else if(isValied2 && numsSearch[i] == nums[right]){
result[1] = i;
isValied2 = false;
}
}
return result;
}
else if(nums[left] + nums[right] < target)
left++;
else
right--;
}
return result;
}
}
- 方法四：使用hash表实现的map，遍历一遍数组，对于当前遍历的元素x，查找target - x 是否在map中，如果在则找到两个数的和为target，如果不在且当前x也不在map中则将其放入map中，如果x已经在map中则无需重复放入，map中的key为数组值，value为其索引，思考一下为何重复的无需继续放入？时间复杂度O(n)。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashMap = new HashMap<>();
int[] result = new int[2];
for(int i = 0; i < nums.length; i++){
int x = target - nums[i];
if(hashMap.containsKey(x)){
result[0] = i;
result[1] = hashMap.get(x);
return result;
}
if(!hashMap.containsKey(nums[i]))
hashMap.put(nums[i], i);
}
return result;
}
}
9. 15 三数之和
- 方法一：暴力方法，三层循环，遍历所有可能的三个数的组合，然后判断和是否为零，需要注意题目要求不要有重复，利用哈希表set来去重，因此在判断和为零后，还需要判断是否该三数的解已经出现过，重复时不要重复放入结果中返回，时间复杂度O(n^3)，空间复杂度O(1)。
// 代码省略
- 方法二：排序 + 双指针、指针对撞，参考两数之和中最佳的算法是双指针、指针对撞，这里的三数之和可以变为两数之和的问题，首先对数组进行排序，然后遍历数组中的值，对于当前遍历的数组中的值 x， target = 0 - x， 对target在数组当前元素后面的元素中进行两数之和的查找，找到两个数的和为target，找到两个数的和为target的算法采用双指针指针对撞，此时找两个数为target的时间复杂度是O(n)，而对每一个数组中的元素都需要进行O(n)的查找，因此整体的时间复杂度是O(n^2)，这个问题中要求返回的是三数之和的三个数，而不是两数之和那个题中两个数的索引，而且要求返回的结果中不能有重复的三数元组，考虑通过HashSet进行去重。空间复杂度是O(1)。这里我们采用另外一种去重的方式，可以在遍历时进行几种情况的判断，从而去重。
- 首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面子数组的两端，数字分别为 nums[L]和nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集，不满足则对后面子数组中的数继续进行指针碰撞的查找，下面是一些需要判断的可以跳过的重复条件
- 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
- 如果 nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
- 当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
- 当 sum == 0 时，nums[R] == nums[R-1] 则会导致结果重复，应该跳过，R–
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if(nums.length < 3)
return new ArrayList<List<Integer>>();
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
if(nums[i] > 0)
break;
if(i > 0 && nums[i] == nums[i - 1])
continue;
int left = i + 1, right = nums.length - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum == 0){
ArrayList<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
result.add(temp);
while(left < right && nums[left] == nums[left + 1])
left++;
while(left < right && nums[right] == nums[right - 1])
right--;
left++;
right--;
}
else if(sum < 0)
left++;
else
right--;
}
}
return result;
}
}
- 方法三：哈希表set，遍历一遍数组，对于当前的数组值x，target = 0 - x，在当前数组值后面的所有元素组成的子数组中查找两数之和为target，查找两数之和时利用set，因为不同于两数之和的查找，两数之和需要返回数组的索引，因此需要key为值value为索引，这里只需要返回数组值，set即可，时间复杂度O(n2)，空间复杂度O(n2)。
// 这个方法行不通，原因在于题目要求返回的结果是无重复的，但是上面的方法中每次都会在当前遍历的数组值后面所有元素构成的子数组中进行一个全新的两数之查找，会出现重复。
10. 18 四数之和
-
题目要求返回所有满足要求的四元组
-
题目要求没有重复的四元组
-
暴力方法，时间复杂度O(n^4)。
- 方法一：两两组合得到所有和值，和值中继续两两组合得四数之和。
// 方法存在一定的问题需要解决，首先两两组合得到的和值中，有的和值是由相同的一个元素得到的，因此可能从和值中两两组合实际上是原数组中三个数之和。
// 其次需要考虑去重的问题。
- 方法二：排序 + 双指针、对撞指针；类似于三数之和的方法，可以先对数组进行排序，然后固定两个数，并对后面的所有元素组成的子数组进行双指针对撞，整体时间复杂度O(n^3)，空间复杂度O(1)。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
if(nums.length < 4)
return new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
if(i > 0 && nums[i] == nums[i - 1])
continue;
for(int j = i + 1; j < nums.length; j++){
if(j > i + 1 && nums[j] == nums[j - 1])
continue;
int left = j + 1, right = nums.length - 1;
while(left < right){
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if(sum == target){
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[left]);
temp.add(nums[right]);
result.add(temp);
while(left < right && nums[left] == nums[left + 1])
left++;
while(left < right && nums[right] == nums[right - 1])
right--;
left++;
right--;
} else if(sum < target)
left++;
else
right--;
}
}
}
return result;
}
}
11. 16 最接近的三数之和
- 方法：排序 + 指针对撞，类似于三数之和，只不过这里是找一个和值与target最接近，整体时间复杂度O(n^2)，空间复杂度O(1)。
- 不同于三数之和，很多剪枝无法减去，三数之和中很多条件下不再需要继续遍历，但是这里不能剪。
class Solution {
public int threeSumClosest(int[] nums, int target) {
int result = 0;
int distance = Integer.MAX_VALUE;
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
int left = i + 1, right = nums.length - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum == target){
result = sum;
distance = 0;
return result;
}else if(sum < target){
result = target - sum < distance ? sum : result;
distance = target - sum < distance ? target - sum : distance;
left++;
}else{
result = sum - target < distance ? sum : result;
distance = sum - target < distance ? sum - target : distance;
right--;
}
}
}
return result;
}
}
12. 454
- 看视频，讲解的很清楚，尤其是学习其分析问题的思路
- 对于查找的问题，首先弄明白我们需要查找什么，很多题目需要查找什么不是很明显，需要我们自己去构造。
- 方法：哈希表，四数之和拆解为两数之和，例如将cd两两求和放入查找表中，利用map记录两数之和的结果，key为两数之和的值，value为两数之和为该值的数量，然后另外两个数组ab两两求和取反，并在map中查找该值是否存在。时间复杂度是O(n2),空间复杂度是O(n2)。
class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
Map<Integer, Integer> map = new HashMap<>();
int result = 0;
for(int i = 0; i < A.length; i++){
for(int j = 0; j < B.length; j++){
int sum = A[i] + B[j];
if(map.containsKey(sum))
map.put(sum, map.get(sum) + 1);
else
map.put(sum, 1);
}
}
for(int i = 0; i < C.length; i++){
for(int j = 0; j < D.length; j++){
int sum = - (C[i] + D[j]);
if(map.containsKey(sum))
result += map.get(sum);
}
}
return result;
}
}
13. 49 字母异位词分组
- 方法一：哈希表map，遍历数组中的所有字符串，对于当前的字符串，判断其是否与前面遍历过的字符串中的字符串有异位词关系，如果有放入其异位词组的map中，保存异位词组，key为异位词组的第一个单词，value为剩余单词组成的list。
- 超出时间限制。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for(String str : strs){
boolean flag = true;
for(String key : map.keySet()){
if(isValied(key, str)){
List tempList = map.get(key);
tempList.add(str);
map.put(key, tempList);
flag = false;
}
}
if(flag){
List<String> list = new ArrayList<>();
map.put(str, list);
}
}
List<List<String>> result = new ArrayList<>();
for(String str : map.keySet()){
List<String> temp = new ArrayList<>();
temp.add(str);
for(String string : map.get(str)){
temp.add(string);
}
result.add(temp);
}
return result;
}
private boolean isValied(String str1, String str2){
if(str1.length() != str2.length())
return false;
int[] hash = new int[26];
for(int i = 0; i < str1.length(); i++){
hash[str1.charAt(i) - 'a']++;
}
for(int i = 0; i < str2.length(); i++){
hash[str2.charAt(i) - 'a']--;
if(hash[str2.charAt(i) - 'a'] < 0)
return false;
}
return true;
}
}
方法二： 排序+哈希表，题目本质是将具有相同类型的字符串映射到相同的集合中，这里相同类型的定义是字母异位词即相同类型，而字母异位词的特点是如果字符排序后，这些字母异位词会变成相同的单词。哈希表的key为排序后的字母异位词对应的单词，value为该组对应的字母异位词。主要是利用map的containsKey的常数时间复杂度的特性来简化。
- 其实还可以用数组统计每个单词中各个字母的数量，然后将其映射为一个字符串 例如 abc 就是 1#1#1 abb 就是1#2，这样就可以将映射后的带#的字符串当做key，类似于排序后的字母异位词对应的单词，之所以不直接用统计字母数量的数组当做key是因为数组对象无法利用containsKey。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for(String str : strs){
char[] chars = str.toCharArray();
Arrays.sort(chars);
String afterSort = new String(chars);
if(map.containsKey(afterSort)){
List<String> tempList = map.get(afterSort);
tempList.add(str);
map.put(afterSort, tempList);
}else{
List<String> tempList = new ArrayList<>();
tempList.add(str);
map.put(afterSort, tempList);
}
}
List<List<String>> result = new ArrayList<>();
for(List<String> value : map.values()){
result.add(value);
}
return result;
}
}
- 算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。
- 算术基本定理的内容由两部分构成：
- 分解的存在性：
- 分解的唯一性:即若不考虑排列的顺序，正整数分解为素数乘积的方式是唯一的
- 方法三：质数分解唯一性，由于字母异位词具有相同类型及其数量的字母，因此其每个字母映射到唯一一个质数后所得到的积和这一组字母异位词是一一对应的，因此可以利用这个，我们把每个字符串都映射到一个正数上。
用一个数组存储质数 prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103}。
然后每个字符串的字符减去 ’ a ’ ，然后取到 prime 中对应的质数。把它们累乘。
例如 abc ，就对应 ‘a’ - ‘a’， ‘b’ - ‘a’， ‘c’ - ‘a’，即 0, 1, 2，也就是对应素数 2 3 5，然后相乘 2 * 3 * 5 = 30，就把 “abc” 映射到了 30。而30与"abc"这一组字母异位词是一一对应的，原因就是算数基本定理。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
Map<Long, List<String>> map = new HashMap<>();
for(String str : strs){
long key = 1;
for(int i = 0; i < str.length(); i++){
key *= prime[str.charAt(i) - 'a'];
}
if(map.containsKey(key)){
List<String> tempList = map.get(key);
tempList.add(str);
map.put(key, tempList);
}else{
List<String> tempList = new ArrayList<>();
tempList.add(str);
map.put(key, tempList);
}
}
return new ArrayList<List<String>>((map.values()));
}
}
14. 447 回旋镖的数量
- 看视频讲解的很清楚
- 注意点坐标的范围
- 注意点坐标的表示，整数？浮点数？会不会在计算过程中出现浮点数误差，会不会在计算过程中出现整形数范围越界
- 方法一：O(n^3)的算法很容易想出来，三层循环遍历，但是通过题目条件直到数据规模是500，500的三次方的时间复杂度是不行的，最差也应该是平方级别的算法才能接受。
- 方法二：哈希表，优化方法一可以得到一个平法级别的算法，双层循环，外层循环遍历所有点，对当前点作为中心点i，然后遍历后续所有点，计算其与当前中心点的距离dis，利用map统计，key为距离dis平方，value为该距离的点数量；遍历该map中的所有key，对于该key中心点，则有其value * （value -1）个元组。
- 由于计算距离时需要开根号，可能会导致出现精读丢失，考虑使用距离的平方，因为距离平方相同，距离也相同。时间复杂度O(n2)，空间复杂度O(n2)。
class Solution {
public int numberOfBoomerangs(int[][] points) {
List<Map<Integer, Integer>> hash = new ArrayList<>();
for(int i = 0; i < points.length; i++){
Map<Integer, Integer> map = new HashMap<>();
for(int j = 0; j < points.length; j++){
int dis = (points[i][0] - points[j][0]) * ((points[i][0] - points[j][0]));
dis += (points[i][1] - points[j][1]) * ((points[i][1] - points[j][1]));
if(map.containsKey(dis))
map.put(dis, map.get(dis) + 1);
else
map.put(dis, 1);
}
hash.add(map);
}
int result = 0;
for(Map<Integer, Integer> map : hash){
for(Integer value : map.values()){
result += value * (value - 1);
}
}
return result;
}
}
15. 149 直线上最多的点数
- 很容易想到一个暴力的立方算法，三层循环遍历所有的点，在一条直线上的进行统计。
- 方法：优化暴力算法，利用哈希表map，首先花费平方时间复杂度遍历所有点，并对当前点计算其余点与其两两组合的点对组成直线斜率和同一个点组成直线具有相同斜率的点是在同一条直线上的，map中key为斜率，value为到某个点为该斜率的点的数量，则数量最大的就是题目要求的最多的点数的直线。
- 点数组中可能会有多个点在同一个位置上。
- 求斜率时精读丢失及分母为零的问题？尝试用double，BigDecimal 均无法结局精度问题，在求斜率时由于会出现小数，会导致精度丢失，本来两个斜率有细微的差别，但由于精度问题计算出的斜率却相等。既然除法无法避免精度问题，那么如何避免出现小数的除法？我们考虑计算出除数和被除数的最大公约数，然后除数和被除数分别除以这个最大公约数，得到两个int值，然后将这两个值保存在int[] 中并作为map的key，这样本来用斜率当做key，改为int[]作为key。
- 新的问题，如何高效的求出最大公约数？
class Solution {
public int maxPoints(int[][] points) {
if(points.length == 0)
return 0;
int result = 0;
for(int i = 0; i < points.length; i++){
Map<String, Integer> map = new HashMap<>();
int repeat = 0;
int localResult = 1;
for(int j = i + 1; j < points.length; j++){
if(points[i][0] == points[j][0] && points[i][1] == points[j][1]){
repeat++;
continue;
}
int[] temp = new int[2];
if(points[i][0] == points[j][0]){
temp[0] = points[i][0];
temp[1] = Integer.MAX_VALUE;
}
else if(points[i][1] == points[j][1]){
temp[0] = Integer.MAX_VALUE;
temp[1] = points[i][1];
}
else{
int gcd = gcdfunc((points[i][1] - points[j][1]), (points[i][0] - points[j][0]));
if(gcd != 0){
temp[0] = (points[i][0] - points[j][0]) / gcd;
temp[1] = (points[i][1] - points[j][1]) / gcd;
}else{
temp[0] = (points[i][0] - points[j][0]);
temp[1] = (points[i][1] - points[j][1]);
}
}
StringBuilder sb = new StringBuilder();
sb.append(temp[0]);
sb.append(temp[1]);
String tempStr = sb.toString();
if(map.containsKey(tempStr)){
map.put(tempStr, map.get(tempStr) + 1);
localResult = Math.max(localResult, map.get(tempStr));
}
else{
map.put(tempStr, 2);
localResult = Math.max(localResult, map.get(tempStr));
}
}
localResult += repeat;
result = Math.max(result, localResult);
}
return result;
}
// 求两个数的最大公约数
private int gcdfunc(int a, int b) {
if (b == 0)
return a;
else
return gcdfunc(b, a % b);
}
}
- 总结该题：虽然这个题目的思路比较容易相出来，但是存在很多细小的问题，首先是给出的测试用例中有重复的点，而且在同一位置的不同点认为是在同一直线上的不同多个点；其次就是最大的问题，求斜率时精度丢失的问题，通过转化求斜率为求最大公约数，并将被除数 除数均除以最大公约数后的值组成数组，整体作为map的key；最后一个问题是，当map的key是数组时，相同内容值的不同数组会被map认为是不同的对象，这是因为虽然内容相同，但是仍然是不同的对象，map会对对象的地址做哈希，这样内容相同的不同数组对象会被hash到不同的位置存储，因此会被认为是不同的，要解决这个问题，可以将数组内容转化为字符串，由于字符串在java中是字符串常量池中存储，这样相同内容的字符串会使字符串常量池中的同一个对象，因此不会出现数组中的问题。
- 求最大公约数的方法的时间复杂度是O(logn)，因此整体的时间复杂度是O(nnlogn)，空间复杂度是O(n)。
17. 219 存在重复元素II
- 方法：滑动窗口 + 哈希表map，维持一个滑动窗口使得窗口中的元素个数为k个（k个元素最大距离是k-1）窗口长度固定，当一个新的元素从右边进入窗口时，此时窗口长度为k+1，最大长度为k，满足题目要求的最大长度限制条件，在这个窗口中查找是否有两个元素值相等，如果相等则满足题目要求返回true。为了提高查找两个元素值相等操作，将窗口中的元素放入set中，当前新进入元素只需要判断是否set中存在该值即可判断是否有相同的值。时间复杂度O(n)，空间复杂度O(k)k为题目要求的最大长度范围。
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<>();
for(int i = 0; i < nums.length; i++){
if(set.contains(nums[i]))
return true;
set.add(nums[i]);
// 保持窗口中最多有k个元素，这样遍历下一个nums中的值即可组成k+1个元素，最大长度就是k
if(set.size() == k + 1)
set.remove(nums[i - k]);
}
return false;
}
}
18. 217
- 方法：set查找，时间复杂度O(n)，空间复杂度O(n)。
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num : nums){
if(set.contains(num))
return true;
set.add(num);
}
return false;
}
}
19. 220 存在重复元素III
- 暴力解法，遍历所有两两组合的值，判断是否满足题目的两个要求，时间复杂度是O(n^2)，空间复杂度是O(1)。
- 方法：滑动窗口 + 有序查找表，类似于 “存在重复元素II”，依然可以采用滑动窗口来保证两个索引的差值不会超过k，这个题目的关键是如何快速在窗口范围内查找一个值使得该值与当前加入滑动窗口的新值的和不超过t，考虑使用具有顺序存储结构的有序查找表来解决，java中TreeSet和 TreeMap具有此种结构。两个值的差值的绝对值小于等于t，假设两个值是v 和 x，也就是x在[v-t, v+t]这样的区间中，对于此题而言当前遍历的值为v，则需要在查找表中查找一个元素x，使其在区间[v-t, v+t]中，利TreeSet中的方法floor，floor(x)会返回查找表中小于等于x的最大的元素，如果不存在会返回null，而且这个操作是O(n)时间复杂度。在此题中，当前遍历的值为v，则floor(v + t)找到小于等于v + t的最大的值x，然后判断该值x是否大于等于v - t，如果满足则说明x在区间[v-t, v+t]中。时间复杂度O(n)，空间复杂度O(k)。
- 注意：由于会进行v + t的操作，测试用例中的值可能会整数溢出，因此通过long类型来计算，此题的测试用例范围，long不会溢出。
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Long> treeSet = new TreeSet<>();
for(int i = 0; i < nums.length; i++){
Long floor = treeSet.floor((long)nums[i] + t);
if(floor != null && floor >= (long)nums[i] - t)
return true;
treeSet.add((long)nums[i]);
if(treeSet.size() == k + 1)
treeSet.remove((long)nums[i - k]);
}
return false;
}
}
阿里云二面54人在聊
投递蔚来等公司10个岗位 >