Longest SubString Without Repeating Characters LeetCode

开始我用的int [] 来存index，发现不行，因为我不知道具体里面有多少个字符。看了下大牛答案，用的是Hashmap非常好用啊。 要想写的快，方法得对。

public int lengthOfLongestSubstring(String s) {
        if (s==null || s.length() == 0) return 0;
     
        Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
        int start = 0;
        int end = 0;
        int len = s.length();
        int result = 0;
     
        while (end < len) {
            Integer c = new Integer(s.charAt(end));
            if (!hm.containsKey(c)){
                hm.put(c, end);
            } else {
                int diff = end - start;
                if (diff > result) result = diff;
                Integer index = hm.get(c);
                start = Math.max(start, index + 1);
                hm.put(c,end);
            }
            end++;
        }
        return (result > (end - start)) ? result : (end - start);
    }

Wow. I was on the right track. For two passes solution, using a boolean array.

public int lengthOfLongestSubstring(String s) {
        boolean[] exist = new boolean [256];
        int i=0, maxLen = 0;
        for (int j=0; j<s.length(); j++) {
            while (exist[s.charAt(j)]) {
                exist[s.charAt(i)] = false;
                i++;
            }
            exist[s.charAt(j)] = true;
            maxLen = Math.max(j-i+1, maxLen);
        }
        return maxLen;
    }

For one pass solution, using a integer array.

Median of Two Sorted Array LeetCode

这个题也可以是findKthElement from two sorted Array。 思路很简单就是不停的把A，B两个Array分别切成两段。这样比较中间值，把小值得小的部分和大数的大的部分（估计只有我自己懂）去掉。最后终止条件为三种，1. A的size为0,2，B的size为0， 3 Kth为0.
当Kth为0的时候，意味着两边都有一个元素，kth为0，我们就选两个剩余元素小的那个。

难点：实现过程中，下标一定要注意。

public double findMedianSortedArrays(int A[], int B[]) {
        int lenA = A.length;
        int lenB = B.length;
        int total = lenA + lenB;
       
        if (total % 2 != 0) {
            return ((double)findKthElement(A, B, total/2, 0, lenA - 1, 0, lenB - 1));
        } else {
            return (findKthElement(A, B, total/2 - 1, 0, lenA - 1, 0, lenB - 1) +
                    findKthElement(A, B, total/2, 0, lenA - 1, 0, lenB - 1)) /2;
        }
    }
   
    private double findKthElement(int[] A, int[] B, int kth, int startA, int endA, int startB, int endB){
        int sizeA = endA - startA + 1;
        int sizeB = endB - startB + 1;
       
        if (sizeA == 0) return B[startB + kth];
        if (sizeB == 0) return A[startA + kth];
        if (kth == 0) return A[startA] > B[startB] ? B[startB] : A[startA];
       
        //Binary Search
        int midA = sizeA * kth /(sizeA + sizeB);
        int midB = kth - midA - 1;
       
        //Match to the original index
        midA += startA;
        midB += startB;
       
        if (A[midA] < B[midB]) {
            kth -= midA - startA + 1;
            endB = midB;
            startA = midA + 1;
        } else {
            kth -= midB - startB + 1;
            endA = midA;
            startB = midB + 1;
        }
        return findKthElement(A, B, kth, startA, endA, startB, endB);
    }

Restore IP Addresses LeetCode

这个题，在我写了无数次的DFS之后，还是卡住了，这个题容易出现bug的地方很多。

比如终止条件有三种要想到，太长太短或者是正好找到。
第二个问题是，当一个字段开头为0的时候，直接跳到下一个字段。
第三个问题是，在储存的时候，会在后面多加一个点要去掉，并且存之前判断是否有重复。
public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> result = new ArrayList<String>();
        if (s==null || s.length() < 4) return result;
        String ip = "";
        generate(s, 0, 0, result, ip);
        return result;
    }
 
    public void generate(String s, int start, int depth, ArrayList<String> result, String ip){
        int MAX_DEPTH = 4;
        // there are three conditions to stop the DFS
        // too long
        if (s.length() - start > (MAX_DEPTH - depth) * 3) return ;
        // too short
        if (s.length() - start < MAX_DEPTH - depth) return;
        //found one possible solution
        if (depth == 4){
            //remove the "."
            ip = ip.substring(0, ip.length() - 1);
            if (!result.contains(ip)) result.add(ip);
            return;
        }
        //update every depth
        int num = 0;
        for (int i = start; i < Math.min(start + 3, s.length()); i++){
            num = num*10 + (s.charAt(i) - '0');
         
            if (num <=255){
                generate(s, i+1, depth+1, result, ip + num + ".");
            }
            //if this depth start with 0, then we go to the next depth
            if (num == 0) break;
        }
    }

Previous solution is not clear since we did not make it as specific as possible.
DFS is key function
isValid is checking each small string is valid or not.

public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        if (s.length() < 4 || s.length() > 12) return result;
        dfs(result, "" ,s ,0);
        return result;
    }
   
    private void dfs(List<String> result, String currString, String s, int count) {
        if (count == 3 && isValid(s)) {
            result.add(currString+s);
            return;
        }
        for (int i=1; i<4 && i <s.length();i++) {
            String tempString = s.substring(0,i);
            if (isValid(tempString)) {
                dfs(result, currString+tempString+".", s.substring(i), count+1);
            }
        }
    }
   
    private boolean isValid(String s) {
        if (s.charAt(0) == '0') return s.length() == 1;
        int value = Integer.parseInt(s);
        return value>=0 && value<=255;
    }

Remove Duplicates from Sorted Array II LeetCode

水题 需要一个counter来记录出现了几次。
update the count first and the count will be condition to store the value.

public int removeDuplicates(int[] A) {
        if (A.length < 3) return A.length;
        int index = 1;
        int count = 1;
        for (int i = 1; i < A.length; i++){
     
            if (A[i] == A[i-1]){
                count++;
            } else {
                count = 1;
            }
         
            if (count <= 2){
                A[index] = A[i];
                index++;
            }
        }
        return index;
    }

Remove Duplicate from Sorted Array LeetCode

简单题，发现对Array掌握的还不错啊。

public int removeDuplicates(int[] A) {
        int index = 0;
        for (int i = 0; i < A.length; i++){
           
            if (i== 0 || (i >0 && A[i] != A[i - 1])) {
                A[index] = A[i];
                index++;
            } else {
                continue;
            }
        }
        return index;
    }

Letter Combinations LeetCode

鉴于我对DFS的练习实在太少了，突击练了一下。
发现难道是不难，一定要把终止条件，写的很清楚。

public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> result = new ArrayList<String>();
        //Stop
        if (null == digits || digits.length() == 0){
            result.add("");
            return result;
        }
        String[] map = {"abc","def","ghi","jkl","mno","pqrs", "tuv", "wxyz"};
        for (String str : letterCombinations(digits.substring(1))) {
            for (char c : map[digits.charAt(0) - '0' - 2].toCharArray()){
                result.add(c + str);
            }
        }
        return result;
    }

Reverse Integer LeetCode

这个题三个地方需要注意，正负，开始为0，以及Overflow.
一般做过atoi，都知道会有正负和overflow，开头为0，我直接写出来的程序已经误打误撞解决了。

Overflow有几种处理方式，第一是throw exception， 第二个是判断边界条件，可以写的很严格，也可以用MAX_VALUE/10.

public int reverse(int x) {
        //正负问题
       boolean negative = x < 0 ? true: false;
       int result = 0;
       int temp = Math.abs(x);
       int rightDigit = 0;
     
       //0开头的问题已经解决了
       while (temp != 0) {
           rightDigit = temp % 10;
           result = result * 10 + rightDigit;
           temp = temp/10;
       }
     
       if (result > Integer.MAX_VALUE) {
           return Integer.MAX_VALUE;
       }
       return negative == true ? result*(-1) : result;
    }