leetcode228 @summary ranges

Analysis:
Recursive call until pointer to the end of the array.
Time complexity: O(n).

public class Solution {
    private final String CONSTLINK = "->";
    public List<String> summaryRanges(int[] nums) {
        List<String> res= new ArrayList<>();
        if(nums.length==0)
            return res;
        StringBuilder sb=new StringBuilder();
        sb.append(nums[0]);
        getRange(nums, 0, 0, sb, res);
        return res;
    }
 
    private void getRange(int[] nums, int start, int pointer,  StringBuilder tmp, List< String > res){
        if(pointer >= nums.length)
            return;
        if(pointer == nums.length -1){
            if( start == pointer)
                res.add(tmp.toString());
              else{
                  tmp.append(CONSTLINK);
                  tmp.append( nums[pointer]);
                  res.add(tmp.toString());
              }
              return;
        }
        else {
            if( pointer +1 < nums.length && nums[pointer +1] == nums[ pointer] +1)
                getRange( nums, start, pointer +1, tmp, res );
            else{
             
              if( start == pointer)
                res.add(tmp.toString());
              else{
                  tmp.append(CONSTLINK);
                  tmp.append( nums[pointer]);
                  res.add(tmp.toString());
              }
                StringBuilder sb= new StringBuilder();
                sb.append(nums[pointer+1]);
                getRange(nums, pointer+1, pointer+1, sb, res);
            }    
        }
    }
}

lintcode @401 Kth Smallest Number in sorted matrix Java

Use a  minheap to keep a size of min( row, col , k) heap. row search or column search  k times.

public class Solution {
    /**
     * @param matrix: a matrix of integers
     * @param k: an integer
     * @return: the kth smallest number in the matrix
     */
    public int kthSmallest(int[][] matrix, int k) {
 
        PriorityQueue<cell> pq= new PriorityQueue< cell>();
        cell res=new cell(0, 0, matrix[0][0]);

        if(matrix.length > matrix[0].length) {
            //serach by col
            for(int i=0;i< Math.min (matrix[0].length, k); i++)
             pq.offer(new cell(0, i, matrix[0][i]));
     
            while(k-- >0){
                res= pq. poll();
         
            if (res.x+1<matrix.length)
            pq.offer(new cell(res.x+1, res.y, matrix[res.x+1][res.y]));
            }
        }
        else {
            // height is smaller
            for(int i=0;i< Math.min(matrix.length, k); i++)
                pq.offer(new cell(i, 0, matrix[i][0]));
           
             while(k -- >=0){
                 res= pq. poll();
         
                if (res.y+1<matrix[0].length)
                pq.offer(new cell(res.x, res.y+1, matrix[res.x][res.y+1]));
            }
        }
        return res.d;
    }
   
    private class cell implements Comparable<cell>{
        public final int x;
        public final int y;
        public final  int d;
       
        public cell(int x, int y, int d){
            this.x=x;
            this.y=y;
            this.d=d;
        }
       
        public int compareTo(cell that){
            return d-that.d;
        }
       
    }
}

Leetcode @Rectangle Area 223

Find the left down corner and right up corner of shared area .



public class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int ac = (D-B)*(C-A);
        int eg = (H-F)*(G-E);
        int share1x = Math.max(A, E);
        int share1y= Math.max(B, F);
        int share2x = Math.min(C, G);
        int share2y= Math.min(D, H);
     
        return ac+eg-(share2y-share1y)*(share2x-share1x);
    }
}