HashSet(HashMap)

Substring with Concatenation of all words

• 不能算 hard,但是需要思路清晰，写出clean code也有点难度

• words长度相同 words里每一个单词都需要用到且只能用一次

• 要求找到由words里的word组成的substring的index

• 两个hashmap

  • 先对words建立wordToCount

  • 然后取sub = s.substring(i, i + n * wordLen) 实现并调用boolean isConcat(String sub, Map wordToCount, int wordLen)

public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0 || words[0].length() == 0) return res;
        Map<String, Integer> wordToCnt = new HashMap<>();
        for (String word : words) {
            wordToCnt.put(word, wordToCnt.getOrDefault(word, 0) + 1);
        }
        int N = words.length;
        int wordLen = words[0].length();
        for (int i = 0; i < s.length() - N * wordLen + 1; i++) {
            String sub = s.substring(i, i + N * wordLen);
            if (isConcat(sub, wordToCnt, wordLen)) {
                res.add(i);
            }
        }
        return res;
    }
    private boolean isConcat(String str, Map<String, Integer> wordToCnt, int wordLen) {
        Map<String, Integer> visitedMap = new HashMap<>();
        for (int i = 0; i < str.length(); i += wordLen) {
            String word = str.substring(i, i + wordLen);
            visitedMap.put(word, visitedMap.getOrDefault(word, 0) + 1);
            if (!wordToCnt.containsKey(word) || visitedMap.get(word) > wordToCnt.get(word)) {
                return false;
            }
        }
        return true;
    }

Happy Number

• Easy题

• 每一位的平方和一直分解，最后是1的话就是happy number

• 用Set to check duplicate

public boolean isHappy(int n) {
        Set<Integer> visited = new HashSet<>();
        visited.add(n);
        while (n > 1) {
            int sum = calculate(n);
            if (visited.contains(sum)) return false;
            visited.add(sum);
            n = sum;
        }
        return n == 1;
    }
    private int calculate(int n) {
        int sum = 0;
        while (n > 0) {
            int mod = n % 10;
            sum = sum + mod*mod;
            n /= 10;
        }
        return sum;
    }