Leetcode HashMap总结

题目列表

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%。

Leetcode HashMap总结