企业官网建设流程全解析

系列文章目录

前言

关于哈希的基础知识的学习 请点开！！！！
哈希有拉链法和开放寻址法
这俩方法有模板
还有字符串哈希
模板都是用的数组 简便快捷了一点

对于数之和的那种 同一个数组就用双指针 不同数组 还是哈希法比较好 哈希加上动态数组那种
Set和arrayList转换成数组
a.stream().mapToInt(x->x).toArray();

一、 242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

classSolution{publicbooleanisAnagram(Strings,Stringt){int[]r=newint[26];for(charc:s.toCharArray())r[c-'a']++;for(charc:t.toCharArray())r[c-'a']--;for(inti:r)if(i!=0)returnfalse;returntrue;}}

int[]record=newint[26];for(inti=0;i<s.length();i++){record[s.charAt(i)-'a']++;}for(inti=0;i<t.length();i++){record[t.charAt(i)-'a']--;}for(intcount:record){if(count!=0){returnfalse;}}returntrue;

classSolution{publicbooleanisAnagram(Strings,Stringt){Map<Character,Integer>maps=newHashMap<Character,Integer>();Map<Character,Integer>mapt=newHashMap<Character,Integer>();for(inti=0;i<s.length();i++){charc=s.charAt(i);maps.put(c,maps.getOrDefault​(c,0)+1);}for(inti=0;i<t.length();i++){charc=t.charAt(i);mapt.put(c,mapt.getOrDefault​(c,0)+1);}returnmaps.equals(mapt);}}

变形1383.赎金信

classSolution{publicbooleancanConstruct(Strings,Stringt){int[]r=newint[26];for(charc:t.toCharArray())r[c-'a']++;for(chark:s.toCharArray()){r[k-'a']--;if(r[k-'a']<0)returnfalse;}returntrue;}}

49.字母异位词分组

438.找到字符串中所有字母异位词

双指针算法 滑动窗口

/* 滑动窗口算法框架 */voidslidingWindow(string s,string t){unordered_map<char,int>need,window;for(charc:t)need[c]++;intleft=0,right=0;intvalid=0;while(right<s.size()){// c 是将移入窗口的字符charc=s[right];// 右移窗口right++;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/printf("window: [%d, %d)\n",left,right);/********************/// 判断左侧窗口是否要收缩while(window needs shrink){// d 是将移出窗口的字符chard=s[left];// 左移窗口left++;// 进行窗口内数据的一系列更新...}}}

利用模板的话

classSolution{publicList<Integer>findAnagrams(Strings,Stringp){List<Integer>res=newArrayList<>();//此map为pMapMap<Character,Integer>map=newHashMap<>();for(charc:p.toCharArray()){map.put(c,map.getOrDefault(c,0)+1);}intneedToMatch=map.size();intr=0,l=0;while(r<s.length()){if(map.containsKey(s.charAt(r))){map.put(s.charAt(r),map.get(s.charAt(r))-1);//count 1--> 0if(map.get(s.charAt(r))==0){needToMatch--;}}//when length exceedswhile(r-l+1>p.length()){if(map.containsKey(s.charAt(l))){if(map.get(s.charAt(l))==0)needToMatch++;map.put(s.charAt(l),map.get(s.charAt(l))+1);}l++;}//以上操作恢复到p.length() 长度//如果此时 needToMatch正好为0，也就意味着 没有再需要匹配的字符了(并且匹配过的字符都已经count相等)//那么这一段 就是个anagramif(needToMatch==0){res.add(l);}r++;}returnres;}}

双指针算法是包含滑动窗口算法的 所以要是滑动窗口的话 还是指的是双指针算法

• 先统计 p 中每个字母出现多少次，以及有多少种不同字母。
• 在 s 上套一个和 p 一样长的滑动窗口。
• 窗口内字母计数完全匹配 p → 就是异位词，记录窗口起点。

classSolution{publicList<Integer>findAnagrams(Strings,Stringp){int[]hash=newint[26];for(charc:p.toCharArray())hash[c-'a']++;intt=0;//统计 p 里有多少种不同字符for(inti=0;i<26;i++){if(hash[i]!=0)t++;}List<Integer>res=newArrayList<>();char[]a=s.toCharArray();//i和j为窗口 kind 为种类for(inti=0,j=0,kind=0;i<s.length();i++){if(--hash[a[i]-'a']==0)kind++;while(i-j+1>p.length()){//收缩窗口//if==0说明删之前a[j]满足要求if(hash[a[j]-'a']==0)kind--;//删除操作：1、把这个字符的需求加回去//2、j++ 左指针右移，窗口缩小hash[a[j++]-'a']++;}if(kind==t)res.add(j);}returnres;}}

二、 349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

//将结果集合转为数组-法一returnresSet.stream().mapToInt(x->x).toArray();//将结果集合转为数组-法二int[]resArr=newint[resSet.size()];intindex=0;for(inti:resSet1){resArr[index++]=i;}returnresArr;

classSolution{publicint[]intersection(int[]nums1,int[]nums2){Sets=newHashSet();for(inti:nums1)s.add(i);ArrayList<Integer>a=newArrayList<>();for(inti:nums2){if(s.contains(i))a.add(i);s.remove(i);}int[]res=newint[a.size()];for(inti=0;i<res.length;i++){res[i]=a.get(i);}returnres;}}

变形350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

a.stream().mapToInt(Integer::intValue).toArray();

classSolution{publicint[]intersect(int[]nums1,int[]nums2){HashMap<Integer,Integer>map=newHashMap<>();for(inti:nums1)map.put(i,map.getOrDefault(i,0)+1);ArrayList<Integer>a=newArrayList<>();for(inti:nums2){if(map.containsKey(i)&&map.get(i)>=1){a.add(i);map.put(i,map.get(i)-1);}}//return a.stream().mapToInt(Integer::intValue).toArray();returna.stream().mapToInt(x->x).toArray();}}

三、快乐数

不加set的话 直接超时
可以将判断快乐数过程中的所有点看成一个单链表，可能存在环，即该问题就变成了单链表是否存在环的问题

1、fast 指针从原点每次走2步， slow 指针从原点每次走1步
2、两个指针从起点开始走，只要有环，最终两个指针都会相遇，或者没有环，最后走到1，也会不停的在1位置循环，也会相遇，因此两个指针最后一定会相遇
(1)、当相遇的点的值是1，则表示不存在环
(2)、当相遇的点的值不是1，则表示存在环

classSolution{publicbooleanisHappy(intn){// HashSet<Integer> set = new HashSet<>();// while(n != 1 && !set.contains(n)){// set.add(n);// n = get(n);// }// return n==1 ;intfast=get(n),slow=n;while(fast!=slow){fast=get(get(fast));slow=get(slow);}returnfast==1;}publicintget(intx){intres=0;while(x>0){res+=(x%10)*(x%10);x/=10;}returnres;}}

两数之和(梦开始的地方)

454. 四数相加 II

classSolution{publicintfourSumCount(int[]nums1,int[]nums2,int[]nums3,int[]nums4){HashMap<Integer,Integer>map=newHashMap<>();for(inta:nums1)for(intb:nums2)map.put(a+b,map.getOrDefault(a+b,0)+1);intres=0;for(intc:nums3)for(intd:nums4){intsum=(c+d)*(-1);if(map.containsKey(sum))res+=map.get(sum);}returnres;}}

LeetCode 15. 三数之和-java

leetcode 18. 四数之和-java

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

classSolution{publicList<List<Integer>>fourSum(int[]nums,inttarget){List<List<Integer>>ans=newArrayList<List<Integer>>();Arrays.sort(nums);intn=nums.length;for(inti=0;i<n;i++){if(i>0&&nums[i]==nums[i-1])continue;//去重for(intj=i+1;j<n;j++){if(j>i+1&&nums[j]==nums[j-1])continue;//双指针for(intk=j+1,u=n-1;k<u;k++){if(k>j+1&&nums[k]==nums[k-1])continue;while(k<u-1&&(long)nums[i]+nums[j]+nums[k]+nums[u-1]>=target)u--;if((long)nums[i]+nums[j]+nums[k]+nums[u]==target){ans.add(Arrays.asList(nums[i],nums[j],nums[k],nums[u]));}}}}returnans;}}