public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        return combine(1,n+1,k);
    }
   
    public ArrayList<ArrayList<Integer>> combine(int low,int upper, int k) {
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>> ();
        if(k==1) {
            for(int i=low;i<upper;i++){
                ArrayList<Integer>r=new ArrayList<Integer>();
                r.add(i);
                result.add(r);
            }            
            return result;
        }
        for(int i=low;i<upper;i++){
            ArrayList<ArrayList<Integer>>r=combine(i+1,upper,k-1);
            for(ArrayList<Integer> a:r){
                a.add(0,i);
            }
            result.addAll(r);
        }
        return result;
    }
}

Using linked list:

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        // if need to be unique, sort it first
        // Arrays.sort(num);
        LinkedList<Integer>l=new LinkedList<Integer>();
        for(int i:num){
            l.add(i);
        }
        return permute(l);
    }
   
    public ArrayList<ArrayList<Integer>> permute(LinkedList<Integer>l) {
        ArrayList<ArrayList<Integer>>result=new ArrayList<ArrayList<Integer>>();
       
        if(l.size()==0)return result;
        if(l.size()==1){
            ArrayList<Integer> n=new ArrayList<Integer>();
            n.add(l.get(0));
            result.add(n);
            return result;
        }
        for(int i=0;i<l.size();i++){
            // create a new array without i
            int current=l.get(i);
            // if need to be unique, add following line:
            // if(i>0&&current==l.get(i-1))continue;
            l.remove(i);
           
            ArrayList<ArrayList<Integer>>tresult=permute(l);
           
            for(ArrayList<Integer>rr:tresult){
                rr.add(0,current);
            }
            result.addAll(tresult);
            l.add(i,current);
        }
        return result;
    }
}

Just use array:
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>>result=new ArrayList<ArrayList<Integer>>();
       
        if(num.length==0)return result;
        if(num.length==1){
            ArrayList<Integer> n=new ArrayList<Integer>();
            n.add(num[0]);
            result.add(n);
            return result;
        }
        for(int i=0;i<num.length;i++){
            // create a new array without i
            int[]newnum=new int[num.length-1];
            int j=0;
            while(j<newnum.length){
                newnum[j]=num[j<i?j:j+1];
                j++;
            }
            ArrayList<ArrayList<Integer>>tresult=permute(newnum);
           
            for(ArrayList<Integer>rr:tresult){
                rr.add(0,num[i]);
            }
            result.addAll(tresult);
        }
        return result;
    }

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length()!=s3.length())return false;
        boolean[][]c=new boolean[s1.length()+1][s2.length()+1];
        c[0][0]=true;
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i)==s3.charAt(i))
                c[i+1][0]=true;
            else break;
        }
        for(int i=0;i<s2.length();i++){
            if(s2.charAt(i)==s3.charAt(i))
                c[0][i+1]=true;
            else break;
        }
        for(int i=1;i<s1.length()+1;i++){
            for(int j=1;j<s2.length()+1;j++){
                char c3=s3.charAt(i+j-1);
                if(s1.charAt(i-1)==c3){
                    c[i][j]=c[i-1][j];
                }
                if(s2.charAt(j-1)==c3){
                    c[i][j]=c[i][j-1]||c[i][j];
                }
            }
        }
        return c[s1.length()][s2.length()];
    }
}

    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;
    }

思路：从最后一个开始，找到第一个能到最后的，再往前找第一个能到新的位置的，直到第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;
    }
}

用找第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));
        }
    }
}