299. Bulls and Cows

一開始我用的是HashSet保存兩個(gè)字符串中出現(xiàn)過的數(shù)字但是沒有匹配上的秩仆，但是出現(xiàn)了下面的情況，所以用的是HashMap：

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int cows = 0;
        char[] chars1 = secret.toCharArray();
        char[] chars2 = guess.toCharArray();
        Map<Character,Integer> map1 = new HashMap<Character,Integer>();
        Map<Character,Integer> map2 = new HashMap<Character,Integer>();
        for(int i = 0;i<chars1.length;i++){
            if(chars1[i] == chars2[I]){
                bulls++;
            }
            else{
                if(map1.containsKey(chars1[I]))
                    map1.put(chars1[i],map1.get(chars1[i])+1);
                else
                    map1.put(chars1[i],1);
                if(map2.containsKey(chars2[I]))
                    map2.put(chars2[i],map2.get(chars2[i])+1);
                else
                    map2.put(chars2[i],1);
            }
        }
        for(char chr:map1.keySet())
            if(map2.containsKey(chr)){
                cows += Math.min(map1.get(chr),map2.get(chr));
            }
                
        return bulls +"A" + cows + "B";
    }
}

300. Longest Increasing Subsequence

image.png

動(dòng)態(tài)規(guī)劃
運(yùn)用動(dòng)態(tài)規(guī)劃法祟偷，當(dāng)循環(huán)到當(dāng)前元素i時(shí)，判斷此元素與前面的元素m的大小關(guān)系撬统，如果比前面的元素大两曼，那么該位置的LIS長度為max(dp[i],dp[j]+1)。
同時(shí)還需要一個(gè)元素保存當(dāng)前最大的LIS斧散。

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums==null || nums.length==0)
            return 0;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int res = 1;
        for(int i =1;i<nums.length;i++){
            int temp = 1;
            for(int j=0;j<i;j++){
                if(nums[i] > nums[j]){
                    temp = Math.max(dp[j]+1,temp);
                }                    
            }
            dp[i] = temp;
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

動(dòng)態(tài)規(guī)劃結(jié)合二分查找
思路是先建立一個(gè)空的dp數(shù)組岳颇，然后開始遍歷原數(shù)組，對(duì)于每一個(gè)遍歷到的數(shù)字颅湘，我們用二分查找法在dp數(shù)組找第一個(gè)不小于它的數(shù)字，如果這個(gè)數(shù)字不存在栗精，那么直接在dp數(shù)組后面加上遍歷到的數(shù)字闯参，如果存在，則將這個(gè)數(shù)字更新為當(dāng)前遍歷到的數(shù)字悲立，最后返回dp數(shù)字的長度即可鹿寨，注意的是，跟上面的方法一樣薪夕，特別注意的是dp數(shù)組的值可能不是一個(gè)真實(shí)的LIS（每個(gè)位置的LIS是從0到插入的index)脚草。參見代碼如下：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }
}