[LeetCode] 11. Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

1. Two pointer scan with greedy.

public class Solution {
    public int maxArea(int[] height) {
        int len = height.length;
        if(0 == len)
            return 0;

        int res = -1;
            
        int i = 0;
        int j = len-1;
        
        while(i < j){
            int hI = height[i];
            int hJ = height[j];
            
            int water = Math.min(hI, hJ)*(j - i);
            if(water > res){
                res = water;
            }
            
            if(hI < hJ){
                i++;
            }else{
                j--;
            }
        }
        
        return res;
    }
}

[LeetCode] 7. Reverse Integer My

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

1. Special handling of overflow.

public class Solution {
    public int reverse(int x) {
        if (0 == x)
            return 0;
        boolean n = false;
        if (x < 0){
            x = x * -1;
            n = true;
        }
        int of = Integer.MAX_VALUE / 10;
        
        int res = 0;
        while(x > 0){
            if(res <= of){
                res *= 10;
                if(Integer.MAX_VALUE - res > x % 10){
                    res += x % 10;
                }
                x /= 10;
            }
            else{
                return 0;
            }
        }
        return n?res*-1:res;
        
    }
}

[LeetCode] 9. Palindrome Number

1. Wrong code. 1000021 --> true. Once 1000000 and 1 is subtract, only 2 left.
Should get the number of digits first.

public class Solution {
    public boolean isPalindrome(int x) {
        
        if(0 == x)
            return true;
        
        if(x < 0)
            return false;
        
        while(x >= 10){    
            int r = x % 10;
        
            int l = x;
            int s = 1;
            while(l >= 10){
                l /= 10;
                s *= 10;
            }
            s *= l;
            
            if(l != r)
                return false;
            
            x -= s;
            x /= 10;
        }
        
        return true;
        
    }
}

[LeetCode] 10. Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

1. DP, code is not elegant enough. Will improve later. Judge the way the code end is an issue, at the boader charAt will not work.

public class Solution {
    
    public int isMatchAux(String s, String p, int indexS, int indexP, int[][] dp){
        int lenS = s.length();
        int lenP = p.length();
        
        if(lenS < indexS || lenP < indexP){
            return -1;
        }
        
        if(0 != dp[indexS][indexP]){
            return dp[indexS][indexP];
        }
        
        if(lenS == indexS && lenP == indexP){
            dp[indexS][indexP] = 1;
            return dp[indexS][indexP];
        }else if(lenS == indexS && indexP < lenP -1 && '*' == p.charAt(indexP + 1)){
            dp[indexS][indexP] = isMatchAux(s, p, indexS, indexP + 2, dp);
            return dp[indexS][indexP];
        }else if(lenS == indexS || lenP == indexP){
            dp[indexS][indexP] = -1;
            return dp[indexS][indexP];
        }
        
        
        char cs = s.charAt(indexS);
        char cp = p.charAt(indexP);
        
        if(0 == dp[indexS][indexP]){
            
            boolean ret = false;
            
            if(indexP < lenP -1 && '*' == p.charAt(indexP + 1) ){
                ret = ret || isMatchAux(s, p, indexS, indexP + 2, dp) == 1;
                if('.' == cp || cs == cp){
                    ret = ret || isMatchAux(s, p, indexS + 1, indexP, dp) == 1;
                    ret = ret || isMatchAux(s, p, indexS + 1, indexP+2, dp) == 1;
                }
            }else if('.' == cp || cs == cp){
                ret = isMatchAux(s, p, indexS + 1, indexP + 1, dp) == 1;
            }
            
            dp[indexS][indexP] = ret ? 1: -1;
        
        }
        
        return dp[indexS][indexP];
    }
    
    public boolean isMatch(String s, String p) {
        int lens = s.length();
        int lenp = p.length();
        
        int[][] dp = new int[lens+1][lenp+1];
        
        return isMatchAux(s, p, 0, 0, dp) == 1? true: false;
    }
}

[leetcode] 8. String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

1.  Very boring problem. Not sure possible inputs before coding.
https://github.com/csehao/LeetCode/blob/master/Java/StringtoInteger.java

public class Solution {
    public int myAtoi(String str) {
        int len = str.length();
        int res = 0;
        boolean pn = true;
        boolean hasValue = false;
        boolean pnvalid = false;
        
        int md10 = Integer.MAX_VALUE/10;
        int md10tail = Integer.MAX_VALUE - md10;
        // It is necessary to Integer.MIN_VALUE as well. Omitted here.

        int nmd10 = Integer.MAX_VALUE/10;
        
        for(int i = 0; i < len; ++i){
            Character c = str.charAt(i);
            if('+' == c){
                if(pnvalid == true)
                    return 0;
                pn = true;
                pnvalid = true;
            }else if('-' == c){
                if(pnvalid == true)
                    return 0;
                pn = false;
                pnvalid = true;
            }else if(Character.isDigit(c)){
                
                if(res > md10){
                    return pn?Integer.MAX_VALUE:Integer.MIN_VALUE;    
                }
                res*= 10;
                int value = (int)(Character.getNumericValue(c));
                if(Integer.MAX_VALUE - value < res)
                    return pn?Integer.MAX_VALUE:Integer.MIN_VALUE;
                res+= value;
                hasValue = true;
            }else if(c == ' '){
                if(false == hasValue && pnvalid == false)
                    continue;
                    
                if(hasValue || pnvalid == true){
                    return pn?res:-1*res; 
                }
                
            }else{
                if(hasValue){
                    return pn?res:-1*res;
                }
                else{
                    return 0;
                }
            }
        }
        
        return pn?res:-1*res;
        
    }
}

It is necessary to test the mod behavior under positive and negative values.

[LeetCode] 6. ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".



1. Element manipulation.
 Special boarder condition on first row and last row
 Special boarder condition on 1 row.
 Alternative increment, see initial increment to the second step first, will be changed to step 1.
 Better way is to setup index,

public class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();
        
        StringBuilder sb = new StringBuilder();
        if(0 == len)
            return sb.toString();
        
        if(1 == numRows){
            return s;
        }
        
        for(int j = 0; j < numRows; ++j){
            
            int d1 = 2*(numRows - 1 - j);
            int d2 = 2*j;
            
            if(0 == d1){
                for(int i = j; i < len; i += d2){
                    sb.append(s.charAt(i));
                }
            }
            else if(0 == d2){
                for(int i = j; i < len; i += d1){
                    sb.append(s.charAt(i));
                }
            }
            else{
                int d = d2;
                for(int i = j; i < len; i += d){
                    sb.append(s.charAt(i));
                    if(d == d1)
                        d = d2;
                    else
                        d = d1;
                }
            }
            
        }
        
        return sb.toString();
        
    }
}

2. The following code works as well, the condition of the last row matches with middle rows, special handling of the first row, first element is OK.

public class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();
        
        StringBuilder sb = new StringBuilder();
        if(0 == len)
            return sb.toString();
        
        sb.append(s.charAt(0));
        
        if(1 == numRows){
            return s;
        }
        
        for(int j = 0; j < numRows; ++j){
            int d1 = 2*(numRows - 1 - j);
            int d2 = 2*j;
            
            int d = d2;
            
            for(int i = j; i < len; i += d){
                if(0 != d){
                    sb.append(s.charAt(i));
                }
                if(d == d1)
                    d = d2;
                else
                    d = d1;
            }
        }
        
        return sb.toString();
        
    }
}

3. A more efficient code It turns out, set up a variable to judge the past increment value seems to be the leanest code. Might not be the most efficient one. It is similar to set a prehead in list manipulation. From somewhere before the list, from somewhere before the array.

public class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();
        
        StringBuilder sb = new StringBuilder();
        if(0 == len)
            return sb.toString();
        
        if(1 == numRows){
            return s;
        }
        
        for(int j = 0; j < numRows; ++j){
            
            int d1 = 2*(numRows - 1 - j);
            int d2 = 2*j;

            int[] inc = new int[2];
            inc[0] = d1;
            inc[1] = d2;
                
            int index = 0;
            int add = -1;
            for(int i = j; i < len; i += inc[index++%2]){
                if(0 != add)
                    sb.append(s.charAt(i));
                add = inc[index%2];
            }
        }
        
        return sb.toString();
        
    }
}

[LeetCode] 5. Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

1. DP, O(N^2) complexity.

https://github.com/csehao/LeetCode/blob/master/Java/LongestPalindrome.java

public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        
        StringBuilder sb = new StringBuilder();
        if(0 == len)
            return sb.toString();
            
        boolean[][] dp = new boolean[1001][1001];
        
        int l = 0;
        int u = 1;
        
        for(int i = 0; i < len; ++i){
            dp[i][i+1] = true;
        }
        
        for(int i = 0; i < len-1; ++i){
            if(s.charAt(i) == s.charAt(i+1)){
                dp[i][i+2] = true;
                l = i;
                u = i+2;
                
            }
            else{
                dp[i][i+2] = false;
            }
        }

        for(int d = 3; d <= len; ++d){
            for(int i = 0; i<=len-d; ++i){
                if(s.charAt(i) == s.charAt(i+d-1)){
                    dp[i][i+d] = dp[i+1][i+d-1];
                    if(dp[i][i+d] == true){
                        l = i;
                        u = i+d;
                    }
                }
                else{
                    dp[i][i+d] = false;
                }
            }
        }
        
        return s.substring(l, u);
        
    }
}

[LeetCode] 4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Solution 1: 
Implement find the kth smallest, then find the median based on that.

Note when n is even, the subroutine findKth were called twice. It can be optimized by a function that returns both kth and k+1th. Small revision at lines that returns without recursive calls will do.

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int n = len1 + len2;
        // n == 4
        if( 0 == n % 2){
            return (findKth(nums1, nums2, 0, 0, n/2) + findKth(nums1, nums2, 0, 0, n/2 + 1) ) / 2.0;
        }
        // n == 5
        if( 1 == n % 2){
            return findKth(nums1, nums2, 0, 0, n/2+1);
        }
        
        return 0.0;
    }
    
    public int findKth(int[] nums1, int[] nums2, int index1, int index2, int k){
    
        // if k == 4
        // if k == 5

        int len1 = nums1.length - index1;
        int len2 = nums2.length - index2;
        
        if(len1 + len2 < k){
            return Integer.MIN_VALUE;
        }
        
        if(0 == len1)
            return nums2[index2 + k - 1];
        
        if(0 == len2)
            return nums1[index1 + k - 1];
        
        if(1 == k){
            return Math.min(nums1[index1], nums2[index2]);
        }
        
        // error code
        //if(2 == k)
        //   return Math.max(nums1[index1], nums2[index2]);

        // { 0 1 }

        // { 2 3 }

        // compare 0 and 2 is not correct, answer is 1
        
        // if 2 == k, kd2 = 1; 3 == k, kd2 = 1;
        
        int kd2 = k/2;
        if(len1 < kd2){
            return findKth(nums1, nums2, index1, index2 + kd2, k-kd2);
        }
        if(len2 < kd2){
            return findKth(nums1, nums2, index1 + kd2, index2, k-kd2);
        }
        
        int m1 = nums1[index1 + kd2 -1];
        int m2 = nums2[index2 + kd2 -1];
        
        // k = 4 kd2 = 2
        // k = 5 kd2 = 2
        if(m1 == m2){
            if(0 == k % 2)
                return m1;
            else
                {
                    return findKth(nums1, nums2, index1, index2 + kd2, k-kd2);
                }
        }
        
        if(m1 < m2)
            return findKth(nums1, nums2, index1 + kd2, index2, k-kd2);
        
        if(m1 > m2)
            return findKth(nums1, nums2, index1, index2 + kd2, k-kd2);
        
        return Integer.MIN_VALUE;
    }
    
    
}

[LeetCode] 3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if(0 == len)
            return 0;
        
        int l = 0;

        int resLen = -1;
        HashMap m = new HashMap();
        
        for(int i = 0; i < len; ++i){
            if(m.containsKey(s.charAt(i))){
                int lnew = m.get(s.charAt(i))+1;
                while(l < lnew){
                    m.remove(s.charAt(l++));
                }
                
            }
            m.put(s.charAt(i), i);
            resLen = Math.max(resLen, i - l +1);
        }
        
        return resLen;
    }
}

[LeetCode] 2. Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

It is always fun to manipulate linklist.

Iterates, add one by one.

All methods can be optimized with early stop condition (when one linklist reaches null and 0 == carry). 

1. Iterates till end of one linklist, use the second loop to do the rest job.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode preHead = new ListNode(-1);
        ListNode x = preHead;
        
        while(null != l1 && null != l2){
            carry += l1.val+l2.val;
            preHead.next = new ListNode(carry % 10);
            carry /= 10;
            preHead = preHead.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        
        ListNode head = null == l1 ? l2 : l1;
        while( null != head){
            carry += head.val;
            preHead.next = new ListNode(carry % 10);
            carry /= 10;
            preHead = preHead.next;
            head = head.next;
        }
        
        if(0 != carry)
            preHead.next = new ListNode(carry);
            
        return x.next;
    }
}

2. Use one loop, add 0 if link list reaches end.

.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(null == l1)
            return l2;
        if(null == l2)
            return l1;
        
        int carry = 0;
        ListNode pre = new ListNode(0);
        ListNode res = pre;
        while(0 != carry || l1 != null || l2 != null){
            carry += (null == l1 ? 0 : l1.val) + (null == l2 ? 0 : l2.val);
            pre.next = new ListNode(carry % 10);
            carry /= 10;
            pre = pre.next;
            l1 = null == l1 ? l1 : l1.next;
            l2 = null == l2 ? l2 : l2.next;
        }

        return res.next;
        
    }
}

3. Variants, like implement += operation, add value based on l1.

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode res = l1;
        
        ListNode pl1 = new ListNode(0);
        pl1.next = l1;
        while(0 != carry || null != pl1.next || null != l2){
            if(null == pl1.next)
                pl1.next = new ListNode(0);
            carry += pl1.next.val + (null == l2? 0: l2.val);
            
            pl1.next.val = carry % 10;
            carry /= 10;
            pl1 = pl1.next;
            l2 = (null == l2? null : l2.next);
        }
        return l1;
    }
}

[LeetCode] 1. Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Method 1: Hash Map.
Time: O(n)
Space: O(n)

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        int[] res = new int[2];
        
        if(0 == len)
            return res;
            
        Map m= new HashMap();
        for(int i = 0; i < len; ++i){
            if(m.containsKey(target - nums[i])){
               res[0] = m.get(target - nums[i])+1;
               res[1] = i+1;
            }
             m.put(nums[i], i);
        }
        return res;
    }
}

Method 2: Sort, then use two pointers.

Time: O(nlogn)
Space: O(n), we need new objects to keep the index. Or we don't keep the index, but scan the array twice.

import java.util.*;

class pair{
    public int index;
    public int val;
    pair(int index, int val){
        this.index = index;
        this.val = val;
    }
}

public class TwoSum{
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        int[] res = new int[2];
        if(0 == len)
            return res;
            
        pair[] pArr = new pair[len];
        for(int i = 0; i < len; ++i){
            pArr[i] = new pair(i, nums[i]);
        }
        Arrays.sort(pArr, new Comparator()
                {
                public int compare(pair A, pair B){
                    return A.val - B.val;
                    }
                }
        );

        int i = 0;
        int j = len -1;
        while(i < j){
            if (pArr[i].val + pArr[j].val == target){
                res[0] = Math.min(pArr[i].index+1, pArr[j].index+1);
                res[1] = Math.max(pArr[i].index+1, pArr[j].index+1);
                return res;
            }
            else if ( pArr[i].val + pArr[j].val < target){
                ++i;
            }
            else{
                --j;
            }
        }
        return res;
    }

    public static void main(String[] args){
        TwoSum t = new TwoSum();
        int[] nums = new int[]{3, 2, 4};
        System.out.println(Arrays.toString(t.twoSum(nums, 6)));
    }
}