給自己的目標(biāo)：[LeetCode](https://leetcode.com/ "Online Judge Platform") 上每日一題

在做題的過(guò)程中記錄下解題的思路或者重要的代碼碎片以便后來(lái)翻閱。
項(xiàng)目源碼：github上的Leetcode

26. Remove Duplicates from Sorted Array

題目：給出一組有序的數(shù)組，移除重復(fù)的數(shù)字后，輸出不重復(fù)數(shù)字的個(gè)數(shù)。不允許分配新的空間來(lái)存儲(chǔ)數(shù)組。

Given input array nums = [1,1,2]
output:length = 2,nums = [1,2]

直接將重復(fù)的數(shù)字用之后不重復(fù)的數(shù)字覆蓋過(guò)去，這樣輸出的數(shù)組就能夠不存在重復(fù)的數(shù)字了。

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

27. Remove Element

題目：給出一組有序的數(shù)組和一個(gè)給定的值，從數(shù)組中移除給定的數(shù)字后，輸出數(shù)組長(zhǎng)度。不允許分配新的空間來(lái)存儲(chǔ)數(shù)組

Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

解題與 # 26 思路一樣，同樣是碰到指定的值后使用后面的值來(lái)進(jìn)行覆蓋。

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

28. Implement strStr()

題目：給出兩個(gè)字符串，求子串在父串的的位置，若不匹配返回-1.

之前以為 indexOf() nm 的時(shí)間復(fù)雜度會(huì)導(dǎo)致TLE，便想先看看KMP的算法或者Sunday算法來(lái)縮減復(fù)雜度，后來(lái)試了一下發(fā)現(xiàn)nm的時(shí)間復(fù)雜度能夠直接AC.

public class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

29. Divide Two Integers

題目：給出兩個(gè)數(shù)進(jìn)行相除，要求程序不能使用乘法，除法和求模的運(yùn)算。數(shù)值溢出使用最大值。

剛開(kāi)始直接使用減法來(lái)求值，最后導(dǎo)致 TLE . 換一種思路，任何一個(gè)整數(shù)可以表示成以2的冪為底的一組基的線性組合，即num=a_02^0+a_12^1+a_2*22+...+a_n*2^n。時(shí)間復(fù)雜度為 O(logn).

63/4 = 15;
63 = 32+16+8+4+3 = 4*2^3+4*2^2+4*2^1+4*2^0+3=(8+4+2+1)*4+3 = 63

注意正負(fù)數(shù)和數(shù)值的溢出。

public class Solution {
    public int divide(int dividend, int divisor) {
        int sign = 1;
        if (dividend < 0) sign = -sign;
        if (divisor < 0) sign = -sign;
        long temp = Math.abs((long) dividend);
        long temp2 = Math.abs((long) divisor);
        long c = 1;
        while (temp > temp2) {
            temp2 = temp2 << 1;
            c = c << 1;
        }
        long res = 0;
        while (temp >= Math.abs((long) divisor)) {
            while (temp >= temp2) {
                temp -= temp2;
                res += c;
            }
            temp2 = temp2 >> 1;
            c = c >> 1;
        }
        if (sign > 0) {
            if (res > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }
            return (int) res;
        } else return -(int) res;
    }
}

30. Substring with Concatenation of All Words TLE

題目：給定一個(gè)字符串S和一個(gè)字符串?dāng)?shù)組L，L中的字符串長(zhǎng)度都相等，找出S中所有的子串恰好包含L中所有字符各一次，返回子串的起始位置。

s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].

使用map將數(shù)組中的字符串記錄下來(lái)，從字符串截取字符來(lái)進(jìn)行匹配。但是在最后的 case 中會(huì)出現(xiàn) TLE.在網(wǎng)上找到的資料是說(shuō)可以使用 slide window 的算法來(lái)實(shí)現(xiàn)，等待以后來(lái)學(xué)習(xí)。

/**
* 這是 TLE 的代碼
 *  */
public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s.length() == 0 || words.length == 0) {
            return res;
        }
        Map<String, Integer> map = new HashMap<>();
        for (String str : words) {
            map.put(str, map.containsKey(str) ? map.get(str) + 1 : 1);
        }
        int len = words[0].length();
        for (int i = 0; i <= s.length() - len * words.length; i++) {
            HashMap<String, Integer> tempMap = new HashMap<>(map);
            int temp = i;
            int count = 0;
            String tempStr = s.substring(temp, temp + len);
            while (tempMap.containsKey(tempStr) && tempMap.get(tempStr) > 0) {
                tempMap.put(tempStr, tempMap.get(tempStr) - 1);
                temp = temp + len;
                count++;
                if (temp + len <= s.length()) {
                    tempStr = s.substring(temp, temp + len);
                } else {
                    break;
                }
            }
            if (count == words.length) {
                res.add(i);
            }
        }
        return res;
    }
}