宠物网站素材,辽宁专业模板网站建设公司,设计公司调研报告,数字营销专业学什么目录
242.有效的字母异位词 49.字母异位词分组 202.快乐数 219.存在重复元素Ⅱ 383.赎金信 205.同构字符串
290.单词规律 242.有效的字母异位词 题意#xff1a; 给定两个字符串 s 和 t #xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。 注意#xff1a;若 s 和…目录
242.有效的字母异位词 49.字母异位词分组 202.快乐数 219.存在重复元素Ⅱ 383.赎金信 205.同构字符串
290.单词规律 242.有效的字母异位词 题意 给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。 注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词 【输入样例】 sanagram,tnagaram 【输出样例】true 解题思路 比较简单定义一个数组来记录两个字符串中的字母出现次数 数组alphaNum初始化为0一个字符串负责对其一个对齐-- 如果是字母异位词最后alphaNum的值肯定还是全0 class Solution {public boolean isAnagram(String s, String t) {//s和t都是小写字母,每个字符出现次数相同当两个字符长度不一样时也不行if(s.length() ! t.length()){return false;}int[] alphaNum new int[26];for(int i0;is.length();i){alphaNum[s.charAt(i) - a];}for(int i 0;it.length();i){--alphaNum[t.charAt(i) - a];if(alphaNum[t.charAt(i) - a] 0){return false;}}return true;}
} 时间 击败了82.24% 内存 击败了71.71% 49.字母异位词分组 题意 给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 【输入样例】 strs[eat,tea,tan,ate,nat,bat] 【输出样例】[[eat,tea,ate],[tan,nat],[bat]] 解题思路 排序哈希 拿到一个字符串str对其进行排序如“eat排序完是”aet“之后将aet作为key存到map中 使用map.getOrDefault(key,new Array()); 如果map中存在此key会将key对应的value(本题是list)返回了如果没有此key证明是第一次遇到new一个list class Solution {public ListListString groupAnagrams(String[] strs) {//方法一排序哈希MapString,ListString map new HashMapString,ListString();for(String str: strs){char[] array str.toCharArray();Arrays.sort(array);String key new String(array);ListString list map.getOrDefault(key,new ArrayListString());list.add(str);map.put(key,list);}return new ArrayListListString(map.values());//把map转成对应格式}
} 时间 击败了99.24% 内存 击败了40.02% class Solution {public ListListString groupAnagrams(String[] strs) {//方法二计数哈希/**拿到一个字符串str按上一题的思路统计出现的次数和字母作为key如eat为a1e1t1用计数统计来替换掉数组排序之后是一样的操作使用map.getOrDefault(key,new Array());如果map中存在此key会将key对应的value(本题是list)返回了如果没有此key证明是第一次遇到new一个list*/MapString,ListString map new HashMapString,ListString();for(String str: strs){int[] count new int[26];for(int i0;istr.length();i){count[str.charAt(i)-a];}//合成keyStringBuffer key new StringBuffer();for(int i0;i26;i){if(count[i]!0){key.append((char)(ia));//字母key.append(count[i]);//次数}}String strKey key.toString();ListString list map.getOrDefault(strKey,new ArrayListString());list.add(str);map.put(strKey,list);}return new ArrayListListString(map.values());//把map转成对应格式}
} 202.快乐数 题意 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为 对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true 不是则返回 false 。 【输入样例】n19 【输出样例】true 解题思路 哈希集合 不断计算n的各位数平方之和并且将每次计算到的数存到set中如果在n不等于1的情况下发现当前计算出来的n已经存在set中证明陷入了死循环 class Solution {private int getNext(int n) {int totalSum 0;while (n 0) {int d n % 10;n n / 10;totalSum d * d;}return totalSum;}public boolean isHappy(int n) {SetInteger seen new HashSet();while (n ! 1 !seen.contains(n)) {seen.add(n);n getNext(n);}return n 1;}
} 时间 击败了85.70% 内存 击败了81.73% 219.存在重复元素Ⅱ 题意 给你一个整数数组 nums 和一个整数 k 判断数组中是否存在两个 不同的索引 i 和 j 满足 nums[i] nums[j] 且 abs(i - j) k 。如果存在返回 true 否则返回 false 。 【输入样例】nums[1,2,3,1],k3 【输出样例】true 解题思路 nums[i]作为keyi作为value当找到nums[j] nums[i]时计算i和j的差距如果不符合k的要求修改nums[i]的value为j因为数组遍历指针一直在往后走。 class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {MapInteger,Integer map new HashMapInteger,Integer();int temp;for(int i0;inums.length;i){temp nums[i];if(map.containsKey(temp) (i - map.get(temp) k)){return true;}map.put(temp,i);}return false;}
} 时间 击败了85.19% 内存 击败了47.36% 383.赎金信 题意 给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以返回 true 否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。 提示 1 ransomNote.length, magazine.length 105ransomNote 和 magazine 由小写英文字母组成 【输入样例】ransomNotea, magazine b 【输出样例】false 解题思路 直接统计magazine中每个字符用到的次数能不能大于等于randomNote中每个字符用到的次数。 class Solution {public boolean canConstruct(String ransomNote, String magazine) {if(magazine.length() ransomNote.length()){return false;}int[] num new int[26];for(int i0;imagazine.length();i){num[magazine.charAt(i) - a];}for(int i0;iransomNote.length();i){--num[ransomNote.charAt(i) - a];if(num[ransomNote.charAt(i) - a] 0){return false;}}return true;}
} 时间 击败了99.33% 内存 击败了98.96% 205.同构字符串 题意 给定两个字符串 s 和 t 判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t 那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符同时不改变字符的顺序。不同字符不能映射到同一个字符上相同字符只能映射到同一个字符上字符可以映射到自己本身。 提示 1 s.length 5 * 104t.length s.lengths 和 t 由任意有效的 ASCII 字符组成 【输入样例】segg,tadd 【输出样例】true 解题思路 s.charAt(i)是keyt.charAt(i)是value必须一致。 class Solution {public boolean isIsomorphic(String s, String t) {if(snull){return true;}MapCharacter,Character map new HashMapCharacter,Character();for(int i0;is.length();i){char key s.charAt(i);if(!map.containsKey(key)){//如果这个key和value都不存在的话那就直接添加keyvalue//key不存在但是已经有value了也不行if(map.containsValue(t.charAt(i))){return false;}map.put(key,t.charAt(i));}else{if(t.charAt(i) ! map.get(key)){return false;}}}return true;}
} 时间 击败了58.80% 内存 击败了76.72% 290.单词规律 题意 给定一种规律 pattern 和一个字符串 s 判断 s 是否遵循相同的规律。 这里的 遵循 指完全匹配例如 pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。 提示 1 pattern.length 300pattern 只包含小写英文字母1 s.length 3000s 只包含小写英文字母和 s 不包含 任何前导或尾随对空格s 中每个单词都被 单个空格 分隔 【输入样例】patternabba, sdog cat cat dog 【输出样例】true 解题思路 与205.同构字符串类似只不过value从Character变成了String。 class Solution {public boolean wordPattern(String pattern, String s) {if(s null){return true;}MapCharacter,String map new HashMapCharacter,String();String[] str s.split( );//根据空格提取单词if(pattern.length() ! str.length){return false;}for(int i0;ipattern.length();i){char key pattern.charAt(i);if(map.containsKey(key) !(str[i].equals(map.get(key)))){return false;}if(!map.containsKey(key) map.containsValue(str[i])){return false;}map.put(key,str[i]);}return true;}
} 时间 击败了55.43% 内存 击败了61.55%
