My life

Month: April 2013

  • Leetcode: Container With Most Water

    public class Solution {
        public int maxArea(int[] height) {
            int i=0,j=height.length-1;
            int result=0;
            while(i<j){
                if(result<Math.min(height[i],height[j])*(j-i)){
                    result=Math.min(height[i],height[j])*(j-i);
                }
                if(height[i]<height[j])i++;else j--;
            }
            return result;
        }
    }

  • Leetcode: First Missing Positive

    public class Solution {
        public int firstMissingPositive(int[] A) {
            for(int i=0;i<A.length;i++){
                while(A[i]-1>=0&&A[i]<=A.length&&A[A[i]-1]!=A[i]){
                    int t=A[i];
                    int temp=A[t-1];
                    A[t-1]=A[i];
                    A[i]=temp;
                }
            }
            int i=0;
            for(i=0;i<A.length;i++){
                if(i+1!=A[i])break;
            }
            return i+1;
        }
    }

  • Leetcode: Jump Game

        public boolean canJump(int[] A) {
            int i=A.length-1;
            while(i>0){
                int j=0;
                boolean hasNext=false;    
                for(j=0;j<i;j++){
                    if(A[j]+j>=i){
                        i=j;
                        hasNext=true;
                        break;
                    }
                }
                if(!hasNext)return false;
            }
            return true;
        }

  • Leetcode: Jump Game II

    思路：从最后一个开始，找到第一个能到最后的，再往前找第一个能到新的位置的，直到第0位：
    public class Solution {
        public int jump(int[] A) {
            int i=A.length-1;
            int step=0;
            while(i>0){
                for(int j=0;j<i;j++){
                    if(A[j]+j>=i){
                        step++;
                        i=j;
                        break;
                    }
                }
            }
            return step;
        }
    }

  • Leetcode: Median of Two Sorted Arrays

    用找第k个最小元素的方法求：

    public class Solution {
        public double findMedianSortedArrays(int A[], int B[]) {
            int l = A.length + B.length;
            if (l % 2 == 0) {
                return (find(A, 0, A.length, B, 0, B.length, l / 2) + find(A, 0, A.length, B, 0, B.length, l / 2 - 1)) / 2.0;
            } else {
                return find(A, 0, A.length, B, 0, B.length, l / 2);
            }
        }

            // k = 0 means the first element
        public int find(int A[], int as, int ae, int B[], int bs, int be, int k) {
            if (as >= ae)
                return B[bs + k];
            if (bs >= be)
                return A[as + k];

            int am = (as + ae) / 2;
            int bm = (bs + be) / 2;

                    //number of half elements including the middle elements
            int h = am - as + bm - bs + 2;
            if (A[am] < B[bm]) {
                if (h > k + 1)
                    return find(A, as, ae, B, bs, bm, k);
                else
                    return find(A, am + 1, ae, B, bs, be, k - (am - as + 1));
            } else {
                if (h > k + 1)
                    return find(A, as, am, B, bs, be, k);
                else
                    return find(A, as, ae, B, bm + 1, be, k - (bm - bs + 1));
            }
        }
    }