四川手机响应式网站建设设计,上海工商注册查询网,科技网站有哪些,新媒体 网站建设 管理规范一、字母异位词-判断两个参数内容出现的次数是否相等 滑动窗口、数组排序、计数法、哈希表 1. 242【有效的字母异位词】
题目#xff1a; 给定两个字符串 s 和 t #xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。 注意#xff1a;若 s 和 t 中每个字符出现的次数都…一、字母异位词-判断两个参数内容出现的次数是否相等 滑动窗口、数组排序、计数法、哈希表 1. 242【有效的字母异位词】
题目 给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。 注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词。代码 方法一哈希表法
class Solution {public boolean isAnagram(String s, String t) {//s和t中每个字符出现的次数都相同也就是说s和t的长度肯定相同if(s.length() ! t.length()){return false;}HashMapCharacter,Integer map new HashMap();for (int i 0; i s.length(); i) {map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)1);map.put(t.charAt(i),map.getOrDefault(t.charAt(i),0)-1);}//若t与s有不同的字符或相同字符的个数不同则map中必有value0的数for (Integer value : map.values()) {if(value 0){return false;}}return true;}
}方法二排序法
class Solution {public boolean isAnagram(String s, String t) {if (s.length() ! t.length()) {return false;}//s和t中每个字符出现的次数都相同,则其转换为字符数组并排序后两数组相等char[] str1 s.toCharArray();char[] str2 t.toCharArray();Arrays.sort(str1);Arrays.sort(str2);return Arrays.equals(str1, str2);}
}2. 383【赎金信】
题目 给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以返回 true 否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。代码
class Solution {public boolean canConstruct(String ransomNote, String magazine) {HashMapCharacter,Integer map new HashMap();//先遍历magazine统计可用字符及其个数for (int i 0; i magazine.length(); i) {char ch magazine.charAt(i);map.put(ch,map.getOrDefault(ch,0)1);}for (int i 0; i ransomNote.length(); i) {char ch ransomNote.charAt(i);map.put(ch,map.getOrDefault(ch,0)-1);if(map.get(ch) 0){return false;}}return true;}
}3. 49【字母异位词分组】
题目 给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]代码 方法一排序法
class Solution {public ListListString groupAnagrams(String[] strs) {//将字符串数组中的每个字符串转换成字符数组并排序以排序后字符数组组成的字符串为key具有相同字母的字符串组成的list为value。HashMapString,ListString map new HashMap();for (String s: strs) {char[] charArr s.toCharArray();Arrays.sort(charArr);String str String.valueOf(charArr);ListString list map.getOrDefault(str,new ArrayList());list.add(s);map.put(str,list);}ListListString ansList new ArrayList(map.values());return ansList;}
}方法一排序法
class Solution {public ListListString groupAnagrams(String[] strs) {//将字符串数组中的每个字符串转换成字符数组并排序以排序后字符数组组成的字符串为key具有相同字母的字符串组成的list为value。HashMapString,ListString map new HashMap();for (String s: strs) {char[] charArr s.toCharArray();Arrays.sort(charArr);String str String.valueOf(charArr);ListString list map.getOrDefault(str,new ArrayList());list.add(s);map.put(str,list);}ListListString ansList new ArrayList(map.values());return ansList;}
}4. 438【找到字符串中所有字母异位词】
题目 给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串包括相同的字符串。代码 方法一排序法
class Solution {public ListInteger findAnagrams(String s, String p) {//首先考虑长度关系if(s.length() p.length()){return new ArrayListInteger();}//排序法char[] charArr p.toCharArray();Arrays.sort(charArr);String tmp String.valueOf(charArr);int j 0;ListInteger list new ArrayList();for (int i 0; i s.length(); i) {if(i-j1 p.length()){String str s.substring(j,i1);char[] c str.toCharArray();Arrays.sort(c);str String.valueOf(c);if(str.equals(tmp)){list.add(j);}j;}}return list;}
}方法二计数法
class Solution {public ListInteger findAnagrams(String s, String p) {if(s.length() p.length()){return new ArrayList();}ListInteger list new ArrayList();//记录p中每个字符的个数int[] pCount new int[26];//记录s中每个字符的个数int[] sCount new int[26];for (int i 0; i p.length(); i) {pCount[p.charAt(i)-a];}int j 0;for (int i 0; i s.length(); i) {sCount[s.charAt(i)-a];if(i-j1 p.length()){if(Arrays.equals(pCount,sCount)){list.add(j);}sCount[s.charAt(j)-a]--;j;}}return list;}
}二、数组的交集
1. 349【两个数组的交集】
题目 给定两个数组 nums1 和 nums2 返回它们的交集 。输出结果中的每个元素一定是唯一 的。我们可以不考虑输出结果的顺序 。代码
class Solution {public int[] intersection(int[] nums1, int[] nums2) {//题目中交集的意思是nums1与nums2共有的数结果是不可重复的、无序的因此可以使用HashSet存储SetInteger set1 new HashSet();SetInteger set2 new HashSet();SetInteger set3 new HashSet();for (int i 0; i nums1.length; i) {set1.add(nums1[i]);}for (int i 0; i nums2.length; i) {set2.add(nums2[i]);}for(Integer i : set1){if(set2.contains(i)){set3.add(i);}}int[] ans new int[set3.size()];int index 0;for(int i:set3){ans[index] i;}return ans;}
}2. 350【两个数组的交集 II】
题目 给你两个整数数组 nums1 和 nums2 请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数应与元素在两个数组中都出现的次数一致如果出现次数不一致则考虑取较小值。可以不考虑输出结果的顺序。代码
class Solution {public int[] intersect(int[] nums1, int[] nums2) {//与上一题相比本题结果是可重复的、无序的考虑使用HashMap存储//key为交集中的元素value为key出现的次数int[] ans new int[nums1.length];int index 0;HashMapInteger,Integer map new HashMap();for (int i 0; i nums1.length; i) {map.put(nums1[i],map.getOrDefault(nums1[i],0)1);}for (int i 0; i nums2.length; i) {if(map.containsKey(nums2[i]) map.get(nums2[i])0){ans[index] nums2[i];map.put(nums2[i], map.get(nums2[i])-1);}}return Arrays.copyOfRange(ans,0,index);}
}三、快乐数
1. 202【快乐数】
题目 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为 对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。如果 n 是 快乐数 就返回 true 不是则返回 false 。 代码
class Solution {public boolean isHappy(int n) {//无限循环也就是说平方和会重复出现考虑使用HashSetHashSetInteger set new HashSet();while (true){int sum 0;while (n0){sum (n % 10) * (n % 10);n / 10;}if(sum 1){return true;}if(set.contains(sum)){return false;}set.add(sum);n sum;}}
}四、数相加
1. 1【两数之和】
题目 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。代码
class Solution {public int[] twoSum(int[] nums, int target) {//本题需要返回数组下标返回的元素不可重复因此考虑使用HashMap存储//key存储元素value存储元素对应下标//注意nums数组可重复可能有两个相同的数相加等于targetHashMapInteger,Integer map new HashMap();for (int i 0; i nums.length; i) {if(map.containsKey(target-nums[i])){return new int[]{map.get(target-nums[i]),i};}map.put(nums[i],i);}return new int[2];}
}2. 454【四数相加II】
题目 给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足 0 i, j, k, l nnums1[i] nums2[j] nums3[k] nums4[l] 0 代码
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {//因为题目只要求返回相加等于0的个数因此可以只记录和数与该和数出现的次数即可//以和数为key出现次数为valueint ans 0;HashMapInteger,Integer map new HashMap();for (int i 0; i nums1.length; i) {for (int j 0; j nums2.length; j) {int key nums1[i]nums2[j];map.put(key,map.getOrDefault(key,0)1);}}for (int i 0; i nums3.length; i) {for (int j 0; j nums4.length; j) {int key 0 - nums3[i] - nums4[j];if(map.containsKey(key)){ans map.get(key);}}}return ans;}
}
