299. Bulls and Cows

一开始我用的是HashSet保存两个字符串中出现过的数字但是没有匹配上的，但是出现了下面的情况，所以用的是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

动态规划
运用动态规划法，当循环到当前元素i时，判断此元素与前面的元素m的大小关系，如果比前面的元素大，那么该位置的LIS长度为max(dp[i],dp[j]+1)。
同时还需要一个元素保存当前最大的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;
    }
}

动态规划结合二分查找
思路是先建立一个空的dp数组，然后开始遍历原数组，对于每一个遍历到的数字，我们用二分查找法在dp数组找第一个不小于它的数字，如果这个数字不存在，那么直接在dp数组后面加上遍历到的数字，如果存在，则将这个数字更新为当前遍历到的数字，最后返回dp数字的长度即可，注意的是，跟上面的方法一样，特别注意的是dp数组的值可能不是一个真实的LIS（每个位置的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;
    }
}