28. Implement strStr()

28. Implement strStr()

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.equals("")) return 0;
        if (haystack.equals("")) return -1;
        for (int i = 0; i < haystack.length();){
            int temp = i;
            int neadleIndex= 0;
            while(i < haystack.length() && 
                  neadleIndex < needle.length() &&
                  haystack.charAt(i) ==needle.charAt(neadleIndex)){
                neadleIndex++;
                i++;
                }
                if(neadleIndex-1 == needle.length() -1) return temp;
            else {
                i = temp+1 ;
            }
            }
        
        return -1;
    }
}

13. Roman to Integer

13. Roman to Integer

class Solution {
    public int romanToInt(String s) {
        int out = 0;
        for (int i = 0; i <s>= 0 &amp;&amp; s.charAt(i-1) == 'I'){
                    out -= 1;
                    out += 4;
                }else out += 5;
            }
             //3
            else if (s.charAt(i) == 'X'){
                if ((i-1) &gt;= 0 &amp;&amp; s.charAt(i-1) == 'I'){
                    out -= 1;
                    out += 9;
                }else out += 10;
            }
             //4
            else if (s.charAt(i) == 'L'){
                if ((i-1) &gt;= 0 &amp;&amp; s.charAt(i-1) == 'X'){
                    out -= 10;
                    out += 40;
                }else out += 50;
            }
             //5
            else if (s.charAt(i) == 'C'){
                if ((i-1) &gt;= 0 &amp;&amp; s.charAt(i-1) == 'X'){
                    out -= 10;
                    out += 90;
                }else out += 100;
            }
             //6
            else if (s.charAt(i) == 'D'){
                if ((i-1) &gt;= 0 &amp;&amp; s.charAt(i-1) == 'C'){
                    out -= 100;
                    out += 400;
                }else out += 500;
            }
             //7
            else if (s.charAt(i) == 'M'){
                if ((i-1) &gt;= 0 &amp;&amp; s.charAt(i-1) == 'C'){
                    out -= 100;
                    out += 900;
                }else out += 1000;
            }
        }
        return out;
    }
}

637. Average of Levels in Binary Tree

637. Average of Levels in Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List averageOfLevels(TreeNode root) {
       List out = new ArrayList();
        Queue q = new LinkedList();
        q.add(root);
        
        while(! q.isEmpty()){
            int len = q.size();
            Double sum = 0.0;
            for (int i = 0; i < len; i++){
               TreeNode c = q.remove();
                if (c != null){
               sum += c.val; 
                if(c.left !=null)q.add(c.left);
                if(c.right != null)q.add(c.right);
                }

            }
                          out.add(sum/len);

        }
      return out;  
    }
}

868. Binary Gap

868. Binary Gap

class Solution {
    public int binaryGap(int N) {
        String binary = Integer.toBinaryString(N);
        int first = 0;
        while (first < binary.length() && binary.charAt(first) != '1'){
            first ++;}
        if (first == binary.length()) return 0;
        int diff = Integer.MIN_VALUE;
        int current = first;
        for (int i = first+1; i  diff){
                    diff = i - current;
                }
                current = i;
            }
        }
        if (diff == Integer.MIN_VALUE) return 0;
        return diff;
    }
}

884. Uncommon Words from Two Sentences

884. Uncommon Words from Two Sentences

class Solution {
    public String[] uncommonFromSentences(String A, String B) {
                List outputList = new ArrayList();  
String[] As = A.split(" ");
String[] Bs = B.split(" ");
        Map s = new HashMap();
        for (int i = 0; i < As.length; i++){
            if(s.get(As[i]) == null) s.put(As[i],1);
            else s.put(As[i],s.get(As[i])+1);
        }
        for (int i = 0; i < Bs.length; i++){
            if(s.get(Bs[i]) == null) s.put(Bs[i],1);
            else s.put(Bs[i],s.get(Bs[i])+1);
        }
        
        for (String a: s.keySet()){
            if ( s.get (a) == 1) outputList.add(a);
        }
        
        return outputList.toArray(new String[outputList.size()]);
    }
}