面试编程题 hash篇

面试编程题 hash篇

Posted by julyerr on February 13, 2018

Two-Sum

解题思路
和为定值,只有一个解;使用hash,map.put(sum-num[i],i),然后判断是否存在num[i]的key;存在即可返回,注意不能是本身.
实现代码

public int[] twoSum(int[] nums, int target) {
//        check validation
    if (nums == null || nums.length < 1) {
        return nums;
    }
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(target - nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        Integer v = map.get(nums[i]);
//            can't be itself
        if (v != null && v != i) {
            return new int[]{i , v};
        }
    }
    return null;
}

完整代码


Duplicate系列

Contains Duplicate

解题思路
使用hash判断是否已经存在相同元素即可
实现代码

public boolean containsDuplicate(int[] nums) {
//         check validation
    if(nums == null || nums.length < 2){
        return false;
    }
    Map<Integer,Integer> map = new HashMap<>();
    for(int i = 0;i < nums.length;i++){
        if(map.get(nums[i])!=null){
            return true;
        }
        map.put(nums[i],0);
    }
    return false;
}

Contains Duplicate II

解题思路
使用hash记录出现情况,对于出现多次的元素判断下标之差是否小于等于k

实现代码

public boolean containsNearbyDuplicate(int[] nums, int k) {
//  check validation
    if (nums == null || nums.length < 2) {
        return false;
    }
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.get(nums[i]) != null && (i - map.get(nums[i])) <= k) {
            return true;
        }
        map.put(nums[i], i);
    }
    return false;
}

Contains duplicate III使用treeSet题解


Valid Anagram

解题思路 先一遍将char的次数统计出来,后一次遍历的时候次数减少1,最后一遍的时候判断是否全为0.
实现代码

public boolean isAnagram(String s, String t) {
    if (s == null || t == null || s.length() != t.length()) {
        return false;
    }

    Map<Character, Integer> map = new HashMap<>();
//        第一次遍历的时候统计次数
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        int times = 0;
        if (map.get(c) != null) {
            times = map.get(c);
        }
        map.put(c, times);
    }

//        第二次遍历的时候次数--,并判断
    for (int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        if (map.get(c) == null) {
            return false;
        }
        int times = map.get(c);
        if (times == 0) {
            return false;
        }
        map.put(c, --times);
    }

//        最后一遍判断0
    for (Integer integer :
            map.values()) {
        if (integer != 0) {
            return false;
        }
    }
    return true;
}

参考资料