题目列表
1. 205 同构字符串
2. 217 存在重复元素
3. 219 存在重复元素||
4. 242 有效的字母异位词
5. 290 单词规律
205 同构字符串
题目大意
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
示例1：
输入: s = "egg", t = "add"
输出: true
示例2：
输入: s = "foo", t = "bar"
输出: false
思路
两种方法，第一种用HashMap映射。第二种用indexOf方法，定位字符出现的位置。下面详细来看。
方法一：HashMap
代码一
private boolean sym(String s,String t) {
HashMap <Character,Character> map = new HashMap<>();
if(s.length()!=t.length()) return false;
for(int i=0;i<s.length();i++)
{
if(!map.containsKey(s.charAt(i))) //不包含该键值对
map.put(s.charAt(i),t.charAt(i));
else if(map.get(s.charAt(i))!=t.charAt(i))
return false;
else
continue;
}
return true;
}
public boolean isIsomorphic(String s, String t) {
return sym(s,t) && sym(t,s);
}
运行时间26ms,击败31.82%。这个版本进行了两轮映射，可优化为一轮映射。
优化版本二
public boolean isIsomorphic(String s,String t) {
HashMap <Character,Character> map = new HashMap<>();
if(s.length()!=t.length()) return false;
for(int i=0;i<s.length();i++)
{
if(map.containsKey(s.charAt(i))) {
if(map.get(s.charAt(i))!=t.charAt(i)) return false;
}else if(map.containsValue(t.charAt(i))) return false;
else
map.put(s.charAt(i),t.charAt(i));
}
return true;
}
运行时间24ms,击败39.64%。
方法二：寻找字符出现位置
public boolean isIsomorphic(String s, String t) {
if(s.length()!=t.length()) return false;
for(int i=0;i<s.length();i++)
if(s.indexOf(s.charAt(i))!=t.indexOf(t.charAt(i))) return false;
return true;
}
运行时间12ms,击败76.47%。
217 存在重复元素
题目大意
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
示例1：
输入: [1,2,3,1]
输出: true
示例2：
输入: [1,2,3,4]
输出: false
方法一：HashSet
代码一
当检查到有重复元素，马上返回结果，否则一直加入到set中。
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for(int i=0;i<nums.length;i++)
if(set.contains(nums[i])) return true;
else set.add(nums[i]);
return false;
}
代码二：HashSet去重
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for(int i=0;i<nums.length;i++)
set.add(nums[i]);
return nums.length==set.size()?false:true;
}
运行时间24ms,击败50.06%。
方法二：排序
public boolean containsDuplicate(int[] nums) {
if(nums.length==0) return false;
Arrays.sort(nums); //排序
for(int i=1;i<nums.length;i++)
if(nums[i]==nums[i-1]) return true;
return false;
}
运行时间10ms,击败84.65%。
219 存在重复元素||
题目大意
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。
示例1：
输入: nums = [1,2,3,1], k = 3
输出: true
示例2：
输入: nums = [1,0,1,1], k = 1
输出: true
方法一：HashMap
利用HashMap存储元素和相应的下标。
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++)
{
if(!map.containsKey(nums[i]))
map.put(nums[i],i);
else if(Math.abs(map.get(nums[i])-i)<=k)
return true;
else
map.put(nums[i],i);
}
return false;
}
运行时间28ms,击败33.98%。
方法二：HashSet动态维护k个数
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashSet<Integer> set = new HashSet<>();
for(int i=0;i<nums.length;i++)
{
if(set.contains(nums[i])) return true;
set.add(nums[i]);
if(set.size()>k)
set.remove(nums[i-k]);
}
return false;
}
运行时间30ms,击败28.97%。
242有效的字母异位词
题目大意
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例1：
输入: s = "anagram", t = "nagaram"
输出: true
示例2：
输入: s = "rat", t = "car"
输出: false
说明：
你可以假设字符串只包含小写字母。
进阶：
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
方法一：数组
利用数组计数，统计字母出现的次数，统计完后遍历数组，判断是否有字母次数没有被抵消。
public boolean isAnagram(String s, String t) {
if(s.length()!=t.length()) return false;
int[] res = new int[26];
for(int i=0;i<s.length();i++){
res[s.charAt(i)-'a']++;
res[t.charAt(i)-'a']--;
}
for(int count:res)
if(count!=0) return false;
return true;
}
运行时间14ms,击败36.67%。
方法二：排序
对两个字符串分别进行排序，然后判断这两个字符串是否相等。
public boolean isAnagram(String s, String t) {
if(s.length()!=t.length()) return false;
char[] arrs = s.toCharArray();
char[] arrt = t.toCharArray();
Arrays.sort(arrs);
Arrays.sort(arrt);
return Arrays.equals(arrs,arrt);
}
运行时间9ms,击败70.34%。
方法三：HashMap
可以处理Unicode的情况。
public boolean isAnagram(String s, String t) {
if(s.length()!=t.length()) return false;
HashMap<Character,Integer> map = new HashMap<>();
for(char ch: s.toCharArray())
map.put(ch,map.getOrDefault(ch,0)+1);
for(char ch: t.toCharArray()) {
Integer count = map.get(ch); //这里可以为null
if(count==null)
return false;
else if(count>1)
map.put(ch,count-1);
else
map.remove(ch);
}
return map.isEmpty();
}
运行时间38ms,击败23.86%。
290 单词规律
题目大意
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例1：
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
示例2：
输入:pattern = "abba", str = "dog cat cat fish"
输出: false
代码
直接利用HashMap，注意除了判断Key是否存在，还需要判断Value。
public boolean wordPattern(String pattern, String str) {
if(pattern.length()==0 && str.length()==0) return true;
String[] arr = str.split("\\s+");
if(pattern.length()!=arr.length) return false;
HashMap<Character,String> map = new HashMap<>();
for(int i=0;i<pattern.length();i++)
{
if(map.containsKey(pattern.charAt(i)))
{
if(!map.get(pattern.charAt(i)).equals(arr[i])) return false;
}
else{
if(map.containsValue(arr[i])) return false;
map.put(pattern.charAt(i),arr[i]);
}
}
return true;
}
运行时间7ms,击败6.75%。
