LeetCode 26-30

26. Remove Duplicates from Sorted Array

分析:

给一个已排序好的数组，把重复的元素都删掉保留一个，然后返回新的数组的长度。要求不能使用额外的空间。
使用双指针，i从0开始，j从1开始，如果nums[j] != nums[i]， 那么i+1，且把nums[j]赋值到现在的nums[i]上去。 最后返回的答案应为i+1。

Java：

    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }

27. Remove Element

分析：

使用双指针，只要nums[i] != val，就赋值到nums[res++]上去。

Java：

    public int removeElement(int[] nums, int val) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[res++] = nums[i];
            } 
        }
        return res;
    }

28. Implement strStr()

分析：

正常应该使用kmp算法，但是这里直接使用substring就行了。

Java:

class Solution {
    public int strStr(String haystack, String needle) {
        if ("".equals(needle)) {
            return 0;
        }
        int len = needle.length();
        for (int i = 0; i < haystack.length() - len + 1; i++) {
            if (needle.equals(haystack.substring(i, i + len))) {
                return i;
            }
        }
        return -1;
    }
}

29. Divide Two Integers

分析：

要求实现两个数相除，不能使用乘法除法取模，可以不断相减，计算可以相减多少次，但是耗时太大，待优化。

Java：

    public static int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        int a = Math.abs(dividend), b = Math.abs(divisor);
        int res = 0;
        while (a - b >= 0) {
            res++;
            a = a - b;
        }
        return (dividend > 0) == (divisor > 0) ? res : -res;
    }

30. Substring with Concatenation of All Words

分析：

给了一个字符串s，和一个字符串数组words，words中每个字符串的长度都相同，可以求出这个words数组的总长度为wordsLen，要求找到字符串中所有的起始下标i，使得s.subString(i,i+wordsLen) 这个子串包含words中所有字符串，不需要考虑字符串的串联顺序。

先遍历整个words数组，把每个单词出现的次数记录在map中，再遍历s，截取所有符合长度的子串，然后一个一个判断，判断这个子串是否和words数组匹配，如果匹配，则将起始索引i加入到结果中。
注意Integer在-128~127之间可以用==比较，超过这个范围必须用equals()比较。

Java：

class Solution {
    Map<String, Integer> map;

    public Solution() {
        this.map = new HashMap<>();
    }

    public boolean judge(String str, String[] words) {
        Map<String, Integer> tempMap = new HashMap<>();
        int wordLen = words[0].length();
        for (int i = 0; i < words.length; i++) {
            String split = str.substring(i * wordLen, i * wordLen + wordLen);
            if (tempMap.containsKey(split)) {
                tempMap.put(split, tempMap.get(split) + 1);
            } else {
                tempMap.put(split, 1);
            }
        }
        for (String key : tempMap.keySet()) {
            if (!tempMap.get(key).equals(map.getOrDefault(key, -1))) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> findSubstring(String s, String[] words) {
        if (words.length == 0) {
            return null;
        }
        List<Integer> res = new ArrayList<>();

        for (String str : words) {
            if (map.containsKey(str)) {
                map.put(str, map.get(str) + 1);
            } else {
                map.put(str, 1);
            }
        }
        int wordsLen = words.length * words[0].length();
        for (int i = 0; i < s.length() - wordsLen + 1; i++) {
            if (judge(s.substring(i, i + wordsLen), words) == true) {
                res.add(i);
            }
        }
        return res;
    }
}