ftalm

Wednesday, December 2, 2015

[leetcode] happy number

public class Solution {
 private int getNext(int n){
  int sum = 0;
  while (n > 0){
   int digit = n%10;
   sum += (digit*digit);
   n/=10;
  }
  return sum;
 }

    public boolean isHappy(int n) {
     if (n <= 0) return false;
   HashSet<Integer> lookup = new HashSet<Integer>();  
   while (n > 1){
    if (lookup.contains(n)){
     return false;
    }
    lookup.add(n);
    n = getNext(n);
   }
   return true;
    }
}

Tuesday, December 1, 2015

[leetcode]Shortest Word Distance II

public class WordDistance {
    HashMap<String, List<Integer>> lookup = new HashMap<String, List<Integer>>();
    public WordDistance(String[] words) {
        for (int i = 0; i < words.length; i++){
            if (!lookup.containsKey(words[i])){
                lookup.put(words[i], new ArrayList<Integer>());
            }
            lookup.get(words[i]).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> list1 = lookup.get(word1);
        List<Integer> list2 = lookup.get(word2);
        int min = Integer.MAX_VALUE;
        for (int i = 0, j = 0; i < list1.size() && j < list2.size();){
            min = Math.min(min, Math.abs(list1.get(i)-list2.get(j)));
            if (list1.get(i) < list2.get(j)) i++;
            else j++;
        }
        return min;
    }
}

[leetcode] Valid Anagram

public class Solution {
    public boolean isAnagram(String s, String t) {
     if (s.length() != t.length()) return false;
   HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();
   for (int i = 0; i < s.length(); i++){
    int count = 1;
    char current = s.charAt(i);
    if (lookup.containsKey(current)){
     count = lookup.get(current)+1;
    }
    lookup.put(current, count);
   }
   for (int i = 0; i < t.length(); i++){
    char current = t.charAt(i);
    if (!lookup.containsKey(current)) return false;
    int count = lookup.get(current)-1;
    if (count == 0) lookup.remove(current);
    else lookup.put(current, count);
   }

   return lookup.size()==0;
    }
}

[leetcode]Sparse Matrix Multiplication

加了个0 row col才过不知道有没有更快的方法

public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
     if (A.length == 0 || B.length == 0 || A[0].length != B.length) return null;
     int result[][] = new int[A.length][B[0].length];
     HashSet<Integer> zeroRow = new HashSet<Integer>();
     HashSet<Integer> zeroCol = new HashSet<Integer>();

     for (int i = 0; i < A.length; i++){
      for (int j = 0; j < B[0].length; j++){
       if (!(zeroRow.contains(i) || zeroCol.contains(j))){
           int sum = 0;
           boolean rowZero = false;
           boolean colZero = false;
        for (int k = 0; k < A[i].length; k++){
         sum += A[i][k]*B[k][j];
         rowZero = rowZero & A[i][k] == 0;
         colZero = colZero & B[k][j] == 0;
        }
        result[i][j] = sum;
           if (rowZero) zeroRow.add(i);
           if (colZero) zeroCol.add(j);
       }
      }
     }

     return result;
    }
}

[leetcode]Single Number

public class Solution {
    public int singleNumber(int[] nums) {
        int result = nums[0];
        for (int i = 1; i < nums.length; i++){
         result ^= nums[i];
        }
        return result;
    }
}

[leetcode]Palindrome Permutation

public class Solution {
    public boolean canPermutePalindrome(String s) {
        HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++){
         char key = s.charAt(i);
         int count = 1;
         if (lookup.containsKey(key)){
          count = lookup.get(key)-1;
         }
         if (count == 0){
          lookup.remove(key); 
         }else{
          lookup.put(key, count);
         }
        }
        return lookup.size() <= 1;
    }
}

[leetcode] Simplify Path

public class Solution {
    public String simplifyPath(String path) {
     Stack<String> stack = new Stack<String>();
   String temp = "";
   path = path+"/";
   for (int i = 0; i < path.length(); i++){
    char current = path.charAt(i);
    if (current == ' ') continue;
    if (current == '/'){
     if (temp.equals("..")){
      if (!stack.isEmpty()){
       stack.pop();
      }
     }else if(!temp.equals(".") && !temp.equals("")){
      stack.push(temp);
     }
     temp = "";
    }else{
     temp += current;
    }
   } 
   if (stack.isEmpty()) return "/";
   String result = "";
   while (!stack.isEmpty()){
    result = "/"+stack.pop()+result;
   }

   return result;
    }
}