【LeetCode-经典面试150题-day10】

目录

242.有效的字母异位词

 49.字母异位词分组

 202.快乐数

 219.存在重复元素Ⅱ

 383.赎金信

 205.同构字符串

290.单词规律 

---

 

242.有效的字母异位词

题意：

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

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

【输入样例】

s="anagram",t="nagaram"

【输出样例】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 i=0;i<s.length();++i){++alphaNum[s.charAt(i) - 'a'];}for(int i = 0;i<t.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 List<List<String>> groupAnagrams(String[] strs) {//方法一：排序+哈希Map<String,List<String>> map = new HashMap<String,List<String>>();for(String str: strs){char[] array = str.toCharArray();Arrays.sort(array);String key = new String(array);List<String> list = map.getOrDefault(key,new ArrayList<String>());list.add(str);map.put(key,list);}return new ArrayList<List<String>>(map.values());//把map转成对应格式}
}

时间： 击败了99.24%

内存： 击败了40.02%

class Solution {public List<List<String>> groupAnagrams(String[] strs) {//方法二：计数+哈希/**拿到一个字符串str，按上一题的思路统计出现的次数和字母作为key：如eat为a1e1t1用计数统计来替换掉数组排序之后是一样的操作使用map.getOrDefault(key,new Array<>());如果map中存在此key，会将key对应的value(本题是list)返回了，如果没有此key，证明是第一次遇到，new一个list*/Map<String,List<String>> map = new HashMap<String,List<String>>();for(String str: strs){int[] count = new int[26];for(int i=0;i<str.length();++i){++count[str.charAt(i)-'a'];}//合成keyStringBuffer key = new StringBuffer();for(int i=0;i<26;++i){if(count[i]!=0){key.append((char)(i+'a'));//字母key.append(count[i]);//次数}}String strKey = key.toString();List<String> list = map.getOrDefault(strKey,new ArrayList<String>());list.add(str);map.put(strKey,list);}return new ArrayList<List<String>>(map.values());//把map转成对应格式}
}

 202.快乐数

题意：

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

【输入样例】n=19

【输出样例】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) {Set<Integer> 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],k=3

【输出样例】true

解题思路：

nums[i]作为key，i作为value，当找到nums[j] == nums[i]时，计算i和j的差距，如果不符合k的要求，修改nums[i]的value为j，因为数组遍历，指针一直在往后走。

class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<Integer,Integer>();int temp;for(int i=0;i<nums.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 <= 105
• ransomNote 和 magazine 由小写英文字母组成

【输入样例】ransomNote="a", 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 i=0;i<magazine.length();++i){++num[magazine.charAt(i) - 'a'];}for(int i=0;i<ransomNote.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 * 104
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

【输入样例】s="egg",t="add"

【输出样例】true

解题思路：

s.charAt(i)是key，t.charAt(i)是value，必须一致。

class Solution {public boolean isIsomorphic(String s, String t) {if(s==null){return true;}Map<Character,Character> map = new HashMap<Character,Character>();for(int i=0;i<s.length();++i){char key = s.charAt(i);if(!map.containsKey(key)){//如果这个key和value都不存在的话，那就直接添加key，value//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 <= 300
• pattern 只包含小写英文字母
• 1 <= s.length <= 3000
• s 只包含小写英文字母和 ' '
• s 不包含 任何前导或尾随对空格
• s 中每个单词都被 单个空格 分隔

【输入样例】pattern="abba", s="dog cat cat dog"

【输出样例】true

解题思路：

与205.同构字符串类似，只不过value从Character变成了String。

class Solution {public boolean wordPattern(String pattern, String s) {if(s == null){return true;}Map<Character,String> map = new HashMap<Character,String>();String[] str = s.split(" ");//根据空格提取单词if(pattern.length() != str.length){return false;}for(int i=0;i<pattern.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%