Subsets, Subsets II, Missing Ranges

Posted on 2015-02-26   |   In 刷题   |  

Subsets

Given a set of distinct integers, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Non-recursive Solution

Just keep adding current number to the result collection..
Pay attention to the use of add and addAll

i=0 | [[], [1]]
i=1 | [[2], [1,2]]
i=2 | [[3], [1,3], [2,3], [1,2,3]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        Arrays.sort(S);
        ArrayList<Integer> subset=new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> subsets=new ArrayList<ArrayList<Integer>> ();
        //add empty set
        subsets.add(new ArrayList<Integer>());
        //add set from layers 
        for(int i=0;i<S.length;i++){
             ArrayList<ArrayList<Integer>> subsetsfori=new ArrayList<ArrayList<Integer>>();
            for(ArrayList<Integer> prev: subsets){
                ArrayList<Integer> tmp= new ArrayList<Integer>();
                tmp.addAll(prev);
                tmp.add(S[i]);
                subsetsfori.add(tmp);
        }
        subsets.addAll(subsetsfori);
    }
    return subsets;
}

Recursive Solution

Similar to DFS, i refers to start position of a subset

i=0 | [[], [1], [1,2], [1,2,3]]
i=1 | [[2], [2,3]]
i=2 | [[3]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        Arrays.sort(S);
        ArrayList<Integer> subset=new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> subsets=new ArrayList<ArrayList<Integer>> ();
        subsets.add(new ArrayList<Integer>());
        subset_helper(subsets, subset, 0, S);
    return subsets;
}
    private  void subset_helper(ArrayList<ArrayList<Integer>> subsets, ArrayList<Integer> subset, int start, int[] s){
        for(int i=start;i<s.length;i++){
            subset.add(s[i]);
            //add new arraylist subset here
            subsets.add(new ArrayList<Integer>(subset));
            subset_helper(subsets, subset, i+1, s);
            subset.remove(subset.size()-1);
        }
    }

Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:

1
2
3
4
5
6
7
8
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Only difference is the added while loop.
If completed current layer, and found the next element is the same then skip.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
          Arrays.sort(num);
        ArrayList<Integer> subset=new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> subsets=new ArrayList<ArrayList<Integer>> ();
        subsets.add(new ArrayList<Integer>());
        subset_helper(subsets, subset, 0, num);
    return subsets;
    }
    
  private  void subset_helper(ArrayList<ArrayList<Integer>> subsets, ArrayList<Integer> subset, int start, int[] s){
  for(int i=start;i<s.length;i++){
      subset.add(s[i]);
      //add new arraylist subset here
      subsets.add(new ArrayList<Integer>(subset));
      subset_helper(subsets, subset, i+1, s);
      subset.remove(subset.size()-1);
      while(i < s.length-1 && s[i]==s[i+1]) 
      {i++;}
  }
}

Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return [“2”, “4->49”, “51->74”, “76->99”].

Main idea: output accrodingly when two elements differ>=2, pay attention to edge cases.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public ArrayList<String> findmissingRanges(int[] num, int lower, int upper){
    ArrayList<String> res=new ArrayList<String>();
   
      if(num.length==0){
        if(lower!=upper) res.add(lower+"->"+upper);
        else res.add(lower+"");
        return res;
      }
      if(lower<num[0]){
        if(num[0]-lower>1) res.add(lower+"->"+(num[0]-1));
        else res.add(lower+"");
      }
      
      for(int i = 0;i<num.length-1;i++){
        if(num[i+1]-num[i]>2) res.add((num[i]+1)+"->"+(num[i+1]-1)+"");
        else if(num[i+1]-num[i]==2) res.add(num[i]+1+"");
        else continue;
      }
      
      if(num[num.length-1]<upper){
        if(upper-num[num.length-1]>1) res.add(num[num.length-1]+1+"->"+upper);
        else res.add(""+upper);
      }
      return res;
  }

More Concise:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<String> findMissingRanges(int[] vals, int start, int end) {
       List<String> ranges = new ArrayList<String>();
       int prev = start - 1;
       for (int i=0; i<=vals.length; i++) {
           int curr = (i==vals.length) ? end + 1 : vals[i];
           if ( curr-prev>=2 ) {
               ranges.add(getRange(prev+1, curr-1));
           }
           prev = curr;
       }
       return ranges;
   }
   private String getRange(int from, int to) {
       return (from==to) ? String.valueOf(from) : from + "->" +to;
   }
#Recursion #Array

Remove Nth Node From End of List, Merge Two Sorted Lists, Merge K Sorted Lists

Posted on 2015-02-26   |   In 刷题   |  

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Solution

Honestly I don’t know how my first solution got accepted, basically I just count the size of list and then remove that element in the second pass.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode removeNthFromEnd(ListNode head, int n) {
           ListNode cur=head;
           int i=0;
           while(cur!=null){cur=cur.next;i++;}
           System.out.println(i);
           ListNode cur2=head;
            
           if(n==i){head=head.next;}
            
           for(int j=0;j<i-n-1;j++){
               
               System.out.println(j);
               cur2=cur2.next;
           }
           if (cur2.next == null) {
               return null;
           }
           else cur2.next=cur2.next.next;
           
           return head;      
       }

One pass solution using two pointers: one fake pointer to move n steps from the beginning, then move both pointers until list ends.

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode removeNthFromEnd(ListNode head, int n) {
     
         ListNode cur=head;
         ListNode p=head;
         
         for(int i=0;i<n;i++){cur=cur.next;}
         //deal with removing head cases
         if(cur==null) head=head.next;
         //made a mistake here, forgot to move cur with p...
         else {while(cur.next!=null){p=p.next;cur=cur.next;}
         p.next=p.next.next;}
         return head;
    }

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution

Note: Algorithm is trivial, however I always forget to copy head to last therefore lost the final head during the iteration…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode h=new ListNode(0);
        ListNode l=h;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                l.next=l1;
                l1=l1.next;     
            }
            else{
                l.next=l2;
                l2=l2.next;
            }
            l=l.next;
        }
        //attach the rest of one list
        if (l1==null) l.next=l2;
        else l.next=l1;
        return h.next;
    }

Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Solution

First Solution is Divide and Conquer, by calling the above method and reconstruct. The recursion is T(k) = 2T(k/2)+O(n*k)=O(nklogk).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode mergeKLists(List<ListNode> lists) {
         
         int n=lists.size();
         if(n==0) return null;
         //main function call
         else return mergeKlist(lists,0,n-1);
         
     }
     
     public ListNode mergeKlist(List<ListNode> lists, int l, int r){
         
         if(l<r){
             int m=(l+r)/2;
             //divide the lists by 2 until its size reaches 1, then merge them from bottom to top
             return mergeTwoLists(mergeKlist(lists,l,m),mergeKlist(lists,m+1,r));
         }
         
         return lists.get(l);
       }

Or, instead of dividing into two parts, we can use ArrayDeque Class. (Similar to brute force solution, merges two list each time, whose complexity is n(2+3+…k)=O(nk^2))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode mergeKLists(List<ListNode> lists) {
    
      if(lists == null || lists.isEmpty()) return null;
      ArrayDeque<ListNode> q = new ArrayDeque<ListNode>();
      for(ListNode n : lists) {
          if (n != null) q.offer(n);
      }
      while(q.size() > 1) {
          ListNode a = q.poll();
          ListNode b = q.poll();
          q.offer(mergeTwoLists(a, b));
      }
      
      return q.poll();
 }

Second Solution is PQ. We can add the heads of all lists into the queue. And we can poll out the smallest one. If the next node of this smallest node is not null, we can add the next node to the queue. Until we empty the PQ, we get the sorted lists. The complexity is also O(nklogk).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public ListNode mergeKLists(List<ListNode> lists) {
         if(lists == null || lists.isEmpty()) return null;
         PriorityQueue<ListNode> heap=new PriorityQueue<>(lists.size(), new Comparator<ListNode>(){
            public int compare(ListNode a, ListNode b){
                if(a==null) return 1;
                if(b==null) return -1;
                return a.val - b.val;
            }
            });
        for(int i=0; i<lists.size(); i++){
            if(lists.get(i) != null){
                heap.add(lists.get(i));
            }
        }
        ListNode h=new ListNode(0);
        ListNode l=h;
        while(!heap.isEmpty()){
            ListNode head=heap.poll();
            l.next=head;
            l=head;
            if(head.next != null){
                heap.add(head.next);
            }
        }
        return h.next;
}
#LinkedList

First Missing Positive, Sort Colors

Posted on 2015-02-26   |   In 刷题   |  

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.

Solution

First solution I thought of is simply sort the array, then find the fist missing positive by comparing each positive element with index. However, even though this passed the OJ, it’s still O(logn) time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int firstMissingPositive(int A[]) {
    int n= A.length;
    int i=0;
    int index=0;
    
    if(n==0) return 1;
    Arrays.sort(A);
    while(i<n && A[i]<=0) i++;
    for(;i<n;i++){
        if(i>0&&A[i]==A[i-1]) continue;
        else if(A[i]-index!=1) return index+1;
        else index=A[i];
    }
    return index+1;  
}

Second solution sorts every number corresponding with index, index i holds number i+1, if i+1 is not in the array then we return the smallest mismatch. The runtime is O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int firstMissingPositive(int A[]) {
    int n= A.length;
    int i=0;
    int tmp=0;
    
    while(i<n){
        if(A[i]>0 && A[i]<n && A[i]!=A[A[i]-1])
        {
            tmp=A[A[i]-1];
            A[A[i]-1]=A[i];
            A[i]=tmp;
        }
        else i++;
    }
    
    for(i=0;i<n;i++){
        if(A[i]!=i+1) return i+1;
    }
    return n+1;
}

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library’s sort function for this problem.

Solution

First solution is counting sort, two pass algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
public void sortColors(int[] A) {     
      int n=A.length;
      int[] B=new int[3];
      for (int i=0;i<n;i++){
        B[A[i]]++;
      }
      int p=0;
      for(int j=0;j<B.length;j++){
          for (int k=0;k<B[j];k++)
              A[p++]=j;
      }          
    }

Second Solution is one pass three way partition, using three pointers: pr for the first not red, pb for first not blue and i for current.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void sortColors(int[] A) {
       
       int n=A.length;
       int pr=0,pb=n-1,i=0;
       while(pr<n&&A[pr]==0) pr++;
       while(pb>0&&A[pb]==2) pb--;
       i=pr;
       while(i<=pb){
           
           if(A[i]==0) {swap(A,i,pr); pr++;}
           if(A[i]==2) {swap(A,i,pb); pb--;}
           else i++;
       }
         
     }
   
   void swap(int[] A,int a, int b){
       int tmp=A[a];
       A[a]=A[b];
       A[b]=tmp;
   }
#Sort #Array

Merge Sorted Array, Merge Intervals, Insert Interval

Posted on 2015-02-26   |   In 刷题   |  

Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Two Pointer Solution:

Unlike merge sort, we need to merge these two arrays in place. So start from the end (A[m+n-1]), we compare each pointer. Until one of the pointers reached 0, copy the rest of B to A.

1
2
3
4
5
6
7
8
public void merge(int A[], int m, int B[], int n) {
        int cur=m+n;
        while(m>0 && n>0){
             if(A[m-1]<B[n-1]){A[--cur]=B[--n];}
             else {A[--cur]=A[--m];}
        }
        while(n>0){A[--cur]=B[--n];}
    }

Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Correct Solution

At first sort the Intervals, then I thought of three basic cases:

  • cur.end > next.end (&& cur.end > next.start)
  • cur.end < next.end && cur.end > next.start
  • cur.end < next.end && cur.end < next.start

    • we can leave the third case alone, and only the first two cases need to be merged: if(cur.end > next.start) we set cur.end to the max out of two ends.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
      
      public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
      //sort according to start using inline comparator
      Collections.sort(intervals, new Comparator<Interval>(){
        public int compare(Interval a, Interval b) {
          return a.start-b.start;
        }
      });
      //compare and add to result
      ArrayList<Interval> res=new ArrayList<Interval>();
      for(int i=0;i<intervals.size();i++){
        Interval cur=intervals.get(i);
        //imagine cur to eat all overlapped intervals
        while(i<intervals.size()-1 && cur.end>=intervals.get(i+1).start){
          cur.end=Math.max(cur.end, intervals.get(i+1).end);
          i++;
        }
        res.add(cur);
      }
      return res;
    }

    Insert Interval

    Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
    You may assume that the intervals were initially sorted according to their start times.
    Example 1:
    Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
    Example 2:
    Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
    This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

    Solution(while loop)

    Still three cases:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
            int i=0; Interval cur=null;
            if(intervals.size()==0) {intervals.add(newInterval); return intervals;}
            
            while(i<intervals.size()){
              cur=intervals.get(i);
              //nonoverlap, newInterval is behind current, continue
              if(cur.end<newInterval.start) {i++;continue;}
              //nonoverlap, newInterval is before current, jump out of loop
              else if(cur.start>newInterval.end) break;
              //overlap, update newInterval and remove current
              else {
                newInterval.start=Math.min(newInterval.start, cur.start);
                newInterval.end=Math.max(newInterval.end, cur.end);
                intervals.remove(i);
              }
            }
            intervals.add(i, newInterval);
             return intervals;
            }

    Solution(For each loop)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
           ArrayList<Interval> res = new ArrayList<Interval>();
    //for each interval in list, add to res
           for(Interval interval: intervals){
               if(interval.end < newInterval.start){
                   res.add(interval);
               }
               else if(interval.start > newInterval.end){
                   res.add(newInterval);
                   newInterval = interval;        
               }
               else {
                   newInterval.start=Math.min(interval.start, newInterval.start);
                   newInterval.end=Math.max(newInterval.end, interval.end);
               }
           }
           res.add(newInterval); 
           return res;

    Solution(ListIterator)

    ListIterator:

  • hasNext(), next(), add(), hasPrevious(), previous(),remove(), set(), nextIndex(), previousIndex()

    • Iterator:

  • hasNext(), next(), remove()
    • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
      
      public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
      Interval cur=null;
      if(intervals.size()==0) {intervals.add(newInterval); return intervals;}
      ListIterator<Interval> it=intervals.listIterator();
      while(it.hasNext()){
        cur=it.next();
        //nonoverlap, newInterval is before current, jump out of loop
        if(newInterval.end<cur.start) {it.previous();it.add(newInterval);return intervals;}
        //nonoverlap, newInterval is after current, continue
        else if(newInterval.start>cur.end) continue;
        //overlap, update newInterval, remove current
        else {
          newInterval.start=Math.min(newInterval.start, cur.start);
          newInterval.end=Math.max(newInterval.end, cur.end);
          it.remove();
        }
      }
      //if new eats the last, add new to intervals
      intervals.add(newInterval);
      return intervals;
    }
    #Sort #Array

    Best Time to Buy and Sell Stock, Best Time to Buy and Sell Stock II, Best Time to Buy and Sell Stock III

    Posted on 2015-02-26   |   In 刷题   |  

    Best Time to Buy and Sell Stock

    Say you have an array for which the ith element is the price of a given stock on day i.
    If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

    Brute Force Solution

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public int maxProfit(int[] prices) {
        int maxp=0, low=Integer.MAX_VALUE;
        for(int i=0;i<prices.length;i++){
                if(prices[i]<low) low=prices[i];
                if(prices[i]-low>maxp)
                maxp=prices[i]-low;
        }
        return maxp;
    }

    DP Solution

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public int maxProfit(int[] prices) {
            int maxp=0, tmp=0;
            if (prices == null || prices.length <2) { return 0;}
            int[] t=new int[prices.length-1];
            for(int i=0;i<prices.length-1;i++){
                    t[i]=prices[i+1]-prices[i];
            }
            for(int i=0;i<t.length;i++){
                tmp+=t[i];
                    if(tmp>maxp) maxp=tmp;
                    if(tmp<0) tmp=0;
            }
            return maxp;
        }

    Best Time to Buy and Sell Stock II

    Greedy Solution: trasaction once there exist profit.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public int maxProfit(int[] prices) {
          if(prices.length == 0) return 0;
          int ans = 0;
          for(int i=1; i<prices.length; i++){
              if(prices[i] > prices[i-1])
                ans += prices[i]-prices[i-1];
          }
          return ans;
        }

    DP Solution

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public int maxProfit(int[] prices) {
            int maxp=0, tmp=0,curmax=0;
            if (prices == null || prices.length <2) { return 0;}
            int[] t=new int[prices.length-1];
            for(int i=0;i<prices.length-1;i++){
                    t[i]=prices[i+1]-prices[i];
            }
            for(int i=0;i<t.length;i++){
              if(t[i]>0) maxp+=t[i];
            }
            return maxp;
        }

    Best Time to Buy and Sell Stock III

    Say you have an array for which the ith element is the price of a given stock on day i.
    Design an algorithm to find the maximum profit. You may complete at most two transactions.
    Note:
    You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

    DP Solution

    First thought: we can cut the array in half in n ways, and get the max profit from both sides using solution in the first question. This will be O(n^2), too LTE…
    Using DP to store the max profit from both sides? just scan twice from both directions and update the max profit array for [0…i] and [i…n-1]. Return the max value when a[i]+b[i] is max.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    public class Solution {
        public int maxProfit(int[] prices) {
            if(prices==null||prices.length<2) return 0;
            int n=prices.length, maxsofar=0, low=0,high=0;
            //curmax[i] shows max profit from [0..i]
            int[] curmax=new int[n];
            curmax[0]=0;low=prices[0];
            for(int i=1;i<n;i++){
                if(prices[i]<low) low=prices[i];
                if(prices[i]-low>maxsofar) maxsofar=prices[i]-low;
                curmax[i]=maxsofar;
            }
            //backmax[i] shows max profits from [i...n-1]
            int[] backmax=new int[n];maxsofar=0;
            backmax[n-1]=0; high=prices[n-1];
            for(i=n-2;i>=0;i--){
                if(high<prices[i]) high=prices[i];
                if(high-prices[i]>maxsofar) maxsofar=high-prices[i];
                backmax[i]=maxsofar;
            }
            maxsofar=0;
            for(i=0;i<n;i++){
                if(backmax[i]+curmax[i]>maxsofar) maxsofar = backmax[i]+curmax[i];
            }
            return maxsofar;
        }
    }

    General DP Solution

    Two cases select max as f[k][i]

  • transact on i: p[i]-p[j]+f[k-1][j] or write as p[i]-max(f[k-1][j]-p[j]) j belongs to [0,i-1]

  • no transaction on i: t[k][i-1]
    • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length<2) return 0;
        int n=prices.length, maxsofar=0, K=2;
        int[][] f=new int[K+1][n];
         for (int kk = 1; kk <= K; kk++) {
                int tmpMax = f[kk-1][0] - prices[0];
                for (int ii = 1; ii < n; ii++) {
                    f[kk][ii] = Math.max(f[kk][ii-1], prices[ii] + tmpMax);
                    tmpMax = Math.max(tmpMax, f[kk-1][ii] - prices[ii]);
                    maxsofar = Math.max(f[kk][ii], maxsofar);
                }
            }
        
        return maxsofar;
    }
    #Sort #Array #DP

    Container With Most Water, Trapping Rain Water

    Posted on 2015-02-26   |   In 刷题   |  

    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.

    Solution

    Two Pointers l and r:

  • start from two ends, keep updating maxsofar area
  • changing rule: if left’<’right then we know moving right makes no change(width decreases and min board is still left), so we need to move left pointer, vise versa
    • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    public int maxArea(int[] height) {
         if(height==null) return -1;
         int curmax=-1, maxsofar=-1, l=0,r=height.length-1;
         while(l<r){
          curmax=(r-l)*Math.min(height[l],height[r]);
          if(curmax>maxsofar){
            maxsofar=curmax;
          }
          if(height[l]<height[r]){
            //move r-- would never increase area with same l
            int tmp=height[l];
            while(l<r && height[l]<=tmp)
            l++;
          }
          else{
            int tmp=height[r];
            while(l<r && height[r]<=tmp)
            r--;
          }
         }
         
         return maxsofar;
         
     }

    Trapping Rain Water

    Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
    For example,
    Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
    eg

    Crazy Smart Solution

    left[i] to store the largest to the left of i; right[i] to store the largest to the right of i. The min of these two, subtracted by A[i], determines how much water A[i] can hold
    remember to add up volume from 1 to n-2, since two sides cannot hold water.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public int trap(int[] A) {
          if (A == null || A.length == 0) {  
              return 0;  
          }  
          int i, n=A.length,vol=0,max=0,left[]=new int[n],right[]=new int[n];
          //left to right
          for(i=1, max=A[0], left[0]=A[0]; i<n;i++ ){
              if(A[i]>max) {max=A[i]; left[i]=A[i];}
              else left[i]=max;
          }
          //right to left
          for(i = n-2, max=A[n-1],right[n-1]=A[n-1];i>=0;i--){
              if(A[i]>max){max=A[i]; right[i]=max;}
              else right[i]=max;
          }
          for(i =1;i<n-1;i++){
              int tmp= 1 * (Math.min(left[i],right[i])-A[i]);
              if(tmp!=0) vol+=tmp;
          }
          return vol;
      }
    #Sort #Array

    Valid Palindrome, Palindrome Number, Scramble String, Reverse Binary, Interleaving String

    Posted on 2015-02-26   |   In 刷题   |  

    Valid Palindrome

    Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
    For example,
    “A man, a plan, a canal: Panama” is a palindrome.
    “race a car” is not a palindrome.
    Note:
    Have you consider that the string might be empty? This is a good question to ask during an interview.
    For the purpose of this problem, we define empty string as valid palindrome.

  • Only count numeric and alphabetical, ignore cases
  • Empty String count as palindrome
    • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public boolean isPalindrome(String s) {
               if(s==null||s.length()==0) return true;
               s=s.toUpperCase();
               int l=0, r=s.length()-1;
               while(l<r){
                   Character tmpl=s.charAt(l), tmpr=s.charAt(r);
                   if(!(tmpl>='0'&& tmpl<='9'||tmpl>='A'&&tmpl<='Z')) {l++; continue;}
                   else if(!(tmpr>='0'&& tmpr<='9'||tmpr>='A'&&tmpr<='Z')) {r--;continue;}
                   
                   else{
                       if(tmpl.equals(tmpr)){l++;r--;}
                       else return false;
                   }          
               }
               return true;
           }

    Palindrome Number

    Determine whether an integer is a palindrome. Do this without extra space.
    Could negative integers be palindromes? (ie, -1)
    If you are thinking of converting the integer to string, note the restriction of using extra space.
    You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?
    There is a more generic way of solving this problem.

    Solution

    refer my solution to reverse integer.

  • reverse the number. If the number is the same as its reversed, then it must be a palindrome.
  • negative integers as non-palindromes.

    • Even thought this passed OJ, didn’t deal with overflow issues.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public boolean isPalindrome(int x) {
         int res=0,orig=x;
         if(x<0) return false;
         while(x!=0){
             res=res*10+x%10;
             x=x/10;
         } 
         return res==orig ? true:false;
         
     }

    Another Solution

    First, compare the first and last digit. If they are not the same, it must not be a palindrome. If they are the same, chop off one digit from both ends and continue until you have no digits left, which you conclude that it must be a palindrome.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public boolean isPalindrome2(int x) {
              if (x < 0) return false;
              int div = 1;
              while (x / div >= 10) {
                div *= 10;
              }        
              while (x != 0) {
                int l = x / div;
                int r = x % 10;
                if (l != r) return false;
                x = (x % div) / 10;
                div /= 100;
              }
              return true;
            }

    Scramble String

    Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
    Below is one possible representation of s1 = “great”:

    1
    2
    3
    4
    5
    6
    7
        great
       /    \
      gr    eat
     / \    /  \
    g   r  e   at
               / \
              a   t

    To scramble the string, we may choose any non-leaf node and swap its two children.
    For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

    1
    2
    3
    4
    5
    6
    7
        rgeat
       /    \
      rg    eat
     / \    /  \
    r   g  e   at
               / \
              a   t

    We say that “rgeat” is a scrambled string of “great”.
    Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.

    1
    2
    3
    4
    5
    6
    7
        rgtae
       /    \
      rg    tae
     / \    /  \
    r   g  ta  e
           / \
          t   a

    We say that “rgtae” is a scrambled string of “great”.
    Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

    Iterative Solution

    If string s1 and s2 are scramble strings, there must be a point(i) that breaks s1 to two parts s11, s12, and a point(l-i) that breaks s2 to two parts, s21, s22, and isScramble(s11, s21) && isScramble(s12, s22) is true, or isScramble(s11, s22) && isScramble(s12, s21) is true.

    Cases to consider to avoid LTE:

  • If the lengths of two strings are different, they can’t be scramble.
  • If the characters in two strings are different, they can’t be scramble either.
    • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    public boolean isScramble(String s1, String s2) {
           //check length
           if(s1.length()!=s2.length()) return false;
           int i=0;int L = s1.length();
           if(s1.equals(s2)) return true;
       
             // check letters
             int[] count=new int[26];
             for(;i<L;i++){
               count[s1.charAt(i)-'a']++;
               count[s2.charAt(i)-'a']--;
             }
             for(i=0;i<26;i++){
               if(count[i]!=0) return false;
             }
      
           //check scramble, starting from 1
           for(i=1;i<L;i++){
             String s11=s1.substring(0, i);
             String s12=s1.substring(i);
             String s21=s2.substring(0,i);
             String s22=s2.substring(i);
             if(isScramble(s11,s21)&&isScramble(s12,s22)) return true;
             else {
               s21=s2.substring(0,L-i);
               s22=s2.substring(L-i);
               if(isScramble(s11,s22)&&isScramble(s12,s21)) return true;
             }
           }return false;
         }

    DP Solution

  • t[i][j][len]=1 means that two substrings of length k, one starts from i of string s1, another one starts from j of string s2, are scramble
  • we are looking for t[0][0][L]
  • given a len, we can cut the substring in len-1 ways, if one of them proves to be scramble then t[i][j][k]=true
  • Changing Rule: t[i][j][k] && t[i+k][j+k][Len-k] || t[i][j+Len-k][k] && t[i+k][j][Len-k]
  • Time is O(n^4), space is O(n^3).
    • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    public boolean isScramble(String s1, String s2) {
         if(s1.length()!=s2.length()) return false;
         if(s1.equals(s2)) return true;
         int L=s1.length();
         boolean [][][] t=new boolean[L][L][L+1];
         //init base value
         for(int i=0;i<L;i++){
             for(int j=0;j<L;j++){
                 t[i][j][1] = s1.charAt(i)==s2.charAt(j);
             }
         }
         //calculate the whole table
         for(int len=2;len<=L;len++){
             for(int i=0;i<L-len+1;i++){
                 for(int j=0;j<L-len+1;j++){
                     for(int k=1;k<len;k++){
                       //等号左右两边只要有一个是1就行了
                        t[i][j][len] |= (t[i][j][k] &&  t[i+k][j+k][len-k] || t[i][j+len-k][k] && t[i+k][j][len-k]) ;
                         
                         }
                     }
                 }
             }
        //return the last value
        return t[0][0][L];
        }

    Reverse Binary

    1) 1010->0101 1111->0000

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public String ReverseBinary2(int d){
        int n=Integer.toBinaryString(d).length();
        String res="";
        System.out.println(" d "+d);
        while(d!=0){
             int tmp = 1-d & 0x01;
             System.out.println(" d "+Integer.toBinaryString(d) +" tmp "+tmp);
             res=tmp+res;
             d >>= 1;
             System.out.println(" d: "+d+ " b "+Integer.toBinaryString(d));
        }
        System.out.println(res);
        return res;
      }

    2) 1100->0011 1111->1111

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public String ReverseBinary(int d){
        int n=Integer.toBinaryString(d).length();
        StringBuffer sb=new StringBuffer();
        System.out.println(" d "+d);
        while(d!=0){
             sb.append(d ^ 0x01);
             System.out.println(" d "+d+" sb "+sb+ " "+0x01);
             d >>= 1;
             System.out.println(" d: "+d+ " b "+Integer.toBinaryString(d));
        }
        String s=sb.toString();
        System.out.println(" s: "+s);
        String res=Integer.valueOf(s, 2).toString();
        return res;
      }

    Interleaving String

    Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
    For example,
    Given:
    s1 = “aabcc”,
    s2 = “dbbca”,
    When s3 = “aadbbcbcac”, return true.
    When s3 = “aadbbbaccc”, return false.

    Recursive Solution

    Three pointers, four cases:

  • char at p3 equals to both p2, p1. either result could be true
  • char at p3 only equals to p2, increment these two pointers. If one of p1, p2 reached its length, just compare the rest substring
  • vice versa
  • char at p3 equals to none, break and return false

    • This solution is LTE, as expected…

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public boolean isInterleave(String s1, String s2, String s3) {
         if(s1.length()+s2.length()!=s3.length()) return false;
         return rec(s1,0,s2,0,s3,0); 
         }
       
       private boolean rec(String s1, int p1, String s2, int p2, String s3, int p3){
           if(p3==s3.length()) return true;  
         if(p2==s2.length()) return s1.substring(p1).equals(s3.substring(p3));
         if(p1==s1.length()) return s2.substring(p2).equals(s3.substring(p3));
         if(s3.charAt(p3)==s1.charAt(p1) && s3.charAt(p3)==s2.charAt(p2))
           return rec(s1,p1+1,s2,p2,s3,p3+1) || rec(s1,p1,s2,p2+1,s3,p3+1);
         else if(s3.charAt(p3)==s1.charAt(p1))
           return rec(s1,p1+1,s2,p2,s3,p3+1);
         else if(s3.charAt(p3)==s2.charAt(p2))
           return rec(s1,p1,s2,p2+1,s3,p3+1);
         else return false;
       }

    DP Solution

    特么才一辈子都凑不粗来好么…

  • t[i][j] shows whether using the first i and j elements of s1, s2 can form the first i+j elements of s3.
  • Initialization: for t[s1+1][s2+1], the first column and row are set by comparing chars to target string, and the previous tuple.
  • Changing Rule: depends on top and left tuple. Set to true if current char in s1 equals to corresponding char in s3, and previous tuple is true.
  • Target: t[s1][s2]
    • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public boolean isInterleave(String s1, String s2, String s3) {
         if(s1.length()+s2.length()!=s3.length()) return false;
         boolean[][] t=new boolean[s1.length()+1][s2.length()+1];
         t[0][0]=true;
         for(int i=1;i<s1.length()+1;i++){
           t[i][0]= s1.charAt(i-1)==s3.charAt(i-1) && t[i-1][0];
         }
         for(int i=1;i<s2.length()+1;i++){
           t[0][i]= s2.charAt(i-1)==s3.charAt(i-1) && t[0][i-1];
         } 
         //deduct the whole table 
         for(int i=1; i<s1.length()+1;i++){
           for(int j=1;j<s2.length()+1;j++){
             t[i][j]= (t[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1)) || (t[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1));
           }
         }
         
         return t[s1.length()][s2.length()]; 
         }
    #String #Recursion #DP

    Multiply Strings, Implement strStr(), Reverse Words in a String, String to Integer (atoi)

    Posted on 2015-02-26   |   In 刷题   |  

    Multiply Strings

    Multiply Strings
    Given two numbers represented as strings, return multiplication of the numbers as a string.
    Note: The numbers can be arbitrarily large and are non-negative.

    First Solution

  • reverse two input strings, so index and digits are the same
  • create a tmp int[] to store the additions of two digits multiply results
  • add up the array, while inserting into a stringbuilder
  • delete zeros in the beginning
    • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
     
     public String multiply(String num1, String num2) {
     num1=new StringBuilder(num1).reverse().toString();
     num2=new StringBuilder(num2).reverse().toString();
     int[] tmp= new int[num1.length()+num2.length()];
     StringBuilder res=new StringBuilder();
     for(int i = 0; i< num1.length();i++){
       for(int j = 0; j<num2.length();j++){
         tmp[i+j]+=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
       }
     }
     
     for(int i=0;i<tmp.length;i++){
       int carries=0, num=0;
       num=tmp[i]%10;
       carries=tmp[i]/10;
       res.insert(0, num);
       if(i!=tmp.length-1){tmp[i+1]+=carries;}
     }
     
     while(res.length()>1&&res.charAt(0)=='0'){res.deleteCharAt(0);}
     return res.toString();
    }

    Second Solution

    Do it reversly, same process:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
      
      public String multiply(String num1, String num2) {
      int[] tmp= new int[num1.length()+num2.length()];
      StringBuilder res=new StringBuilder();
      int j=0,i,num,carries=0;
      for( i = num1.length()-1; i>=0 ;i--){
          carries=0; num=0;
        for( j = num2.length()-1; j>=0;j--){        
          num=(num1.charAt(i)-'0')*(num2.charAt(j)-'0')+tmp[i+j+1]+carries;
          tmp[i+j+1]=num%10;
          carries=num/10;
        }
        tmp[i+j+1]=carries;
      }
      i=0;
      while(i<tmp.length-1&&tmp[i]==0){i++;}
      while(i<tmp.length){res.append(tmp[i++]);}
      return res.toString();
    }

    Implement strStr()

    Implement strStr().
    Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
    Update (2014-11-02):
    The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button to reset your code definition.

    Naive Solution

    Two pointers:

  • i: from 0 to n-m, check each substring(i,i+m) equals to needle
  • j: from i to m+i-1, break if non-equal character found

  • If j=m+i after some round, then we found a substring(i, i+m) matches the needle.
    • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public int strStr(String haystack, String needle) 
      {  
        int n = haystack.length();  
        int m = needle.length(); 
        //if haystack empty but needle not
        if (n==0 && m!=0) return -1;
        //special case 
        else if(n==0||m==0) return 0;
        else{
          for (int i = 0; i < n - m+1; i++)  
          {   int j=i;
            for (; j < m+i; j++)  
            {  
              if (needle.charAt(j-i) != haystack.charAt(j)) break;  
            }  
            if (j == m+i) return  i;
          }  
          return -1;  }
      }

    More Consice:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public int strStr(String haystack, String needle) {
           if(haystack == null || needle == null) {
               return 0;
           }
           int i, j;
           for(i = 0; i < haystack.length() - needle.length() + 1; i++) {
               for(j = 0; j < needle.length(); j++) {
                   if(haystack.charAt(i + j) != needle.charAt(j)) {
                       break;
                   }
               }
               if(j == needle.length()) {
                   return i;
               }
           }
           return -1;
       }

    KMP is another solution.

    Reverse Words in a String

    Given an input string, reverse the string word by word.
    For example,
    Given s = “the sky is blue”,
    return “blue is sky the”.
    Clarification:
    What constitutes a word?
    A sequence of non-space characters constitutes a word.
    Could the input string contain leading or trailing spaces?
    Yes. However, your reversed string should not contain leading or trailing spaces.
    How about multiple spaces between two words?
    Reduce them to a single space in the reversed string.

    Correct Solution:

    First, split words into array by spaces. Then from last element in array, append to stringBuilder if not space, add one space after that element in the new string. At last, get the substring from 0 to sb.length()-1 to delete the ending space.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public String reverseWords(String s) {
      if(s==null||s.length()==0) return "";
      String[] words=s.split(" ");
      int n=words.length;
      StringBuilder sb=new StringBuilder();
      for(int i=n-1; i>=0;i--){
        if(!words[i].equals("")){
          sb.append(words[i]).append(" ");}
      } return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
    }

    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.

    Naive Sulotion

  • Case 1: general case, given string is a valid input, convert to int directly
  • Case 2: input string is null or all blank, return 0;
  • Case 3: sign of number(+/-, default as +)
  • Case 4: overflow
    • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public int atoi(String str){
        if(str==null) return 0;
        //remove spaces at beginning and end
        str=str.trim();
        int n=str.length(),i=0;
        //use long to store result
        long res=0;
        if(n==0) return 0;
        int sign = 1;
        if(str.charAt(i)=='+') {sign=1;i++;}
        else if(str.charAt(i)=='-') {sign=-1;i++;}
        for(;i<n;i++){
          char tmp=str.charAt(i);
          if(tmp>'9'||tmp<'0'||tmp==' ') break;
          res=res*10+(tmp-'0');
          if(res>Integer.MAX_VALUE) return sign==1 ? Integer.MAX_VALUE: Integer.MIN_VALUE;
        }
        return (int)res*sign;
      }

    An alternative solution

    without using long, is to use the following during loop:

  • Integer.MAX_VALUE/10 < res;

    • res*10 will become bigger than MAX

  • Integer.MAX_VALUE/10 == res && Integer.MAX_VALUE%10 <(str.charAt(i) - ‘0’)

    • compare last digit when res*10=MAX

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public int atoi(String str){
        if(str==null) return 0;
        str=str.trim();
        int n=str.length(),i=0;
        int res=0;
        if(n==0) return 0;
        int sign = 1;
        if(str.charAt(i)=='+') {sign=1;i++;}
        else if(str.charAt(i)=='-') {sign=-1;i++;}
        for(;i<n;i++){
          char tmp=str.charAt(i);
          if(tmp>'9'||tmp<'0'||tmp==' ') break;
          if(Integer.MAX_VALUE/10 < res || (Integer.MAX_VALUE/10 == res && Integer.MAX_VALUE%10 <(str.charAt(i) - '0')))
          return sign==1 ? Integer.MAX_VALUE: Integer.MIN_VALUE;    
          res=res*10+(tmp-'0');
        }
        return (int)res*sign;
      }
    #Sort #Array #Math

    Add Binary, Add Two Numbers

    Posted on 2015-02-26   |   In 刷题   |  

    Add Binary

    Given two binary strings, return their sum (also a binary string).
    For example,
    a = “11”
    b = “1”
    Return “100”.

    Solution

    Note:Int can be converted to String for manipulation, however, converting String to Int might cause overflow errors.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
        public String addBinary(String a, String b) {
    		
    		if(a==null|a.length()==0)
    			return b;
    		if(b==null|b.length()==0)
    			return a;
    //switch a,b if a is shorter than b 
            if(a.length() < b.length()){
                String temp = a;
                a = b;
                b = temp;
            }
            
            int m = a.length()-1;
            int n = b.length()-1;
            int res = 0;
            String rst = "";
            
    //Add from last digit
            while(n >= 0){
                int sum = (int)(a.charAt(m) - '0') + (int)(b.charAt(n) - '0') + res;
                rst = String.valueOf(sum % 2) + rst;
                res = sum / 2;
                m --;
                n --;
            }
    //Add the longer digits        
            
            while(m >= 0){
                int sum = (int)(a.charAt(m) - '0') + res;
                rst = String.valueOf(sum % 2) + rst;
                res = sum / 2;
                m --;
            }       
            
    //Don't forget the highest digit 
            if (res == 1)
                rst = "1" + rst;
            return rst;
        }

    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

    Solution

    We don’t have to compare the length of two lists an match digits since we are given reversed order. So just add each pair and the rest, pay attention to the last carries.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            
            if(l1==null && l2==null) return null;
            ListNode head=new ListNode(0);
            ListNode cur=head;
            int carries=0;
            while(l1!=null&&l2!=null){
                int sum=l1.val+l2.val+carries;
                carries=sum/10;
                ListNode n=new ListNode(sum%10);
                cur.next=n;
                
                l1=l1.next;
                l2=l2.next;
                cur=cur.next; 
            }
            
            while(l1!=null){
                int sum=carries+l1.val;
                cur.next=new ListNode(sum%10);
                carries=sum/10;
                cur=cur.next;
                l1=l1.next;
            }
            
            while(l2!=null){
                int sum=carries+l2.val;
                cur.next=new ListNode(sum%10);
                carries=sum/10;
                cur=cur.next;
                l2=l2.next;
            }
            
            if(carries!=0){
                cur.next=new ListNode(carries%10);
            }
            
            return head.next;
               }
    #Array #LinkedList

    東京喰種, 寄生兽

    Posted on 2015-02-24   |   In 追剧   |