strStr KMP solution Java

KMP :
prefix array to find prefix and suffix.
use for - while loop .

class Solution {
    /**
     * Returns a index to the first occurrence of target in source,
     * or -1  if target is not part of source.
     * @param source string to be scanned.
     * @param target string containing the sequence of characters to match.
     */
    public int strStr(String source, String target) {
        if(source==null || target==null)
            return -1;
        if(target.length()==0)
            return 0;
        int[] prefix= new int[target.length()];
        int k=0;
        for(int i=1;i<target.length();i++){
            while(k>1 && target.charAt(k)!= target.charAt(i))
                k=prefix[k-1];
            if(target.charAt(i)==target.charAt(k))
                k++;
            prefix[i]=k;
        }
        k=0;
        for(int i=0;i<source.length();i++){
             while( k>1 && source.charAt(i)!= target.charAt(k))
                k=prefix[k-1];
            if(target.charAt(k) ==source.charAt(i))
                k++;
            if(k== target.length())
                return i-k+1;
        }
        return -1;
    }
}

lintcode @54 String to Integer(atoi) Java

1. trim string.
2. loop until . other character.
    judge if bigger than Integer.MAX_VALUE or smaller than Integer.MIN_VALUE

public class Solution {
    /**
     * @param str: A string
     * @return An integer
     */
    public int atoi(String str) {
        if(str==null)
            return 0;
        str=str.trim();
        int i=0;
        boolean neg=false;
        if(str.length()==0)
            return 0;
        if(str.charAt(0)=='-')
        {
            neg=true;
            i++;
        }else if(str.charAt(0)=='+')
            i++;
        int res=0;
        while(i<str.length()){
            char c= str.charAt(i);
            if(c=='.'){
                if(i-1<0 || str.charAt(i-1)>'9'|| str.charAt(i-1)<'0')
                    return 0;
                break;
            }else if( c>'9'|| c<'0')
                break;
            if(!neg && res>(Integer.MAX_VALUE -  c-'0')/10)
                return Integer.MAX_VALUE;
            else if(neg && res > (Integer.MIN_VALUE +  c-'0')/10 *-1 )
                return Integer.MIN_VALUE;
            else{
                res= res*10+ c-'0';
            }
            i++;
        }
        return neg? -res:res;
    }
}

lintcode@ 171 Anagrams Java

use isanagram method, same algorithm test if two strings are anagrams, then check whole string list.

public class Solution {
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    public List<String> anagrams(String[] strs) {
        List<String> res= new ArrayList<>();
        if(strs==null)
            return res;
        boolean flag= false;
        HashSet<Integer> tested= new HashSet<>();
        for(int i=0;i<strs.length;i++){
            flag=false;
            for(int j=i+1;j<strs.length;j++){
                if(tested.contains(i))
                    break;
                if(isanagram (strs[i], strs[j]))
                   {
                    res.add(strs[j]);
                    flag=true;
                    tested.add(j);
                   }
                }
            // added anagrams into the return
            if(flag){
                res.add(strs[i]);
            }
        }
        return res;
    }
   
    private boolean isanagram(String s1, String s2){
        if(s1==null || s2== null || s1.length()!=s2.length())
            return false;
        int[] mp= new int[256];
        for(int i=0;i<s1.length();i++){
            mp[s1.charAt(i)]++;
            mp[s2.charAt(i)]--;
        }
        for(int i=0;i<256;i++)
            if(mp[i]!=0)
                return false;
        return true;
    }
}

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

Leetcode @merge k sorted lists python

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

Hidden:
lists contain 0~k ListNode, the maximum number in each ListNode queue is n.
return one ListNode,which is the head of the long list.
corner case: [{}], [{},{}]

Analysis:
There are two ways to solve this problem. One use recursive call, the essence is the same as merge sort.
we treat 0,1....n-1 as merge sort. use mid as the dividing point. The time is T (K) = T( K/2) +O( nK), so T= O(nKlogK)

Another way is to use min heap as size K, and each time pop the min , insert the next one in the list. The time is O(nKlogK)
Code for recursive: 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param a list of ListNode
    # @return a ListNode
    
    def mergeKLists(self, lists):
        if not lists:
            return None
        else:
            return self.mergeList(lists, 0, len(lists)-1)
        
    def mergeList(self, lists, left, right):
        # return a node with merged two lists
        if left<right:
            mid= (left+right)//2
            return self.merge(self.mergeList(lists, left, mid), self.mergeList(lists, mid+1, right))
        else:
            return lists[left]
    
    def merge(self, node1, node2):
        dummy =ListNode(0)
        pointer=dummy
        while node1!=None and node2!=None:
            if node1.val>node2.val:
                pointer.next=node2
                node2=node2.next
            else: pointer.next=node1; node1=node1.next
            pointer=pointer.next
        if node1==None:
            pointer.next=node2
        if node2==None:
            pointer.next=node1
        return dummy.next

Code for Min heap:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param a list of ListNode
    # @return a ListNode
    
    def mergeKLists(self, lists):
        #   this method use a min heap
        heap =[]
        for node in lists:
            if node:
                heap.append((node.val,node))
        heapq.heapify(heap);head=ListNode(0);curr=head
        while heap:
            pop=heapq.heappop(heap)
            curr.next=pop[1]
            curr=curr.next
            if pop[1].next: heapq.heappush(heap,(pop[1].next.val,pop[1].next))
        return head.next