不知道什么时候用Hash表,学完后,我得到了答案 —> 判断一个元素是否出现 , 就要考虑哈希法

242.有效的字母异位词

怎么硕呢?
虽然我想到了可以用表去存每个字母的个数,所以一开始,我用了这种算法,
我将其锐评为: 傻子方法:用两个表
思路就是::建两个表,然后遍历对比

public boolean isAnagram1(String s, String t) {
        // 傻子方法:用两个表
        int[] sHashCount = new int[26], tHashCount = new int[26];
        if (s == null || t == null) {
            return false;
        }
        if (s.length() != t.length()) {
            return false;
        }

        for (int i = 0; i < s.length(); i++) {
            char charS = s.charAt(i);
            char charT = t.charAt(i);
            sHashCount[charS - 'a']++;
            tHashCount[charT - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (sHashCount[i] != tHashCount[i]) {
                return false;
            }
        }
        return true;
    }

然后看答案之后,我发现可以只用一个表:
思路:第一个串遍历时, 我的Hash表用 ‘ + ‘,第二个串用 ‘ – ‘, 然后看是否全是0

/**
     * 聪明人用的方法
     */
public boolean isAnagram(String s, String t) {
        int[] hashCount = new int[26];
        for (int i = 0; i < s.length(); i++) {
            hashCount[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            hashCount[t.charAt(i) - 'a']--;
        }
        for (int i : hashCount) {
            if (i == 0) {
                return false;
            }
        }
        return true;
    }

349. 两个数组的交集

public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        for (int i : nums1) {
            set1.add(i);
        }
        for (int i : nums2) {
            if (set1.contains(i)) {
                set2.add(i);
            }
        }
//        Object[] array = set2.toArray();
//        int[] answer = new int[set2.size()];
//        for (int i = 0; i < set2.size(); i++) {
//            answer[i] = (int) array[i];
//        }

        return set2.stream().mapToInt(x -> x).toArray();
    }

202. 快乐数

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> hashSet = new HashSet<>();
        while (n != 1 && !hashSet.contains(n)) {
            hashSet.add(n);
            n = get(n);
        }
        return n==1;
    }

    public int get(int n) {
        int sum = 0;
        int tmp;
        while (n != 0) {
            tmp = n % 10;
            sum += tmp * tmp;
            n = n / 10;
        }
        return sum;
    }
}

1. 两数之和

public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        if(nums == null || nums.length==0){
            return answer;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (map.containsKey(need)) {
                answer[0] = map.get(need);
                answer[1] = i;
                break;
            }
            map.put(nums[i], i);
        }
        return answer;
    }

原文地址:http://www.cnblogs.com/Chain-Tian/p/16931063.html

发表评论

您的电子邮箱地址不会被公开。