Object Oriented JavaScript–Class Method

Recently I am implementing 3D rendering in JavaScript. Professor Saty Raghavachary gave me a very good introduction of JavaScript class/methods, which helped me get much better understanding of JavaScript’s power and flexibility.

There are four ways to declare a method of a class

    1. As a member of the class declared inside constructor:
      see example

      function Vector(x,y,z){
         this.x = x;
         this.y = y;
         this.z = z;
         //don't do it this way
         //this.normalize = function(){...};
      }
      

      The downside is every instance of the class would create its normalize method, which is unnecessary and redundant. This is a bad choice, don’t do it this way. Only include data/variables in constructor.

    2. As a class level static method:
      see example (assume we already have Vector class)

      Vector.unit = function(){ return new Vector(1,0,0) }
      

      This will create a static method, which is object independent.

    3. As a prototype method:
      see example (assume we already have Vector class)

      Vector.protoype.normalize= function(){ ... };
      

      By calling prototype, the method is attached to a prototype, and every instance of the Vector class has a pointer to the same prototype, thus can call this method from there. This is the right way to do it, since we only need one copy of the method. One magic thing about prototype is its method can be added even after some instances are declared, and still usable to that instance, see example:

      var obj = new Vector(1,0,0);
      Vector.prototype.addMethod = function(){...};
      obj.addMethod();
      

      Another even more incredible thing is other class can also add the same method by pointing to it. Say we have another class Normal, we can assign Normal.prototype.normalize = Vector.prototype.normalize, to point to normalize method of Vector. By doing this, we can actually mix&match classes/methods, and break class inheritance restrictions.

    4. As a private method only owned by one instance:
      See example:

      var a = Vector(0,0,1);
      a.aMethod = function(){...};
      a.aMethod();
      

      In this case, the aMethod is a private method owned only by a, so it can only be called by a, not by other instances. Also can use delete(a.aMethod) to remove the method after done with it.

Leetcode–Roman to Integer

The Problem:

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Notes:

  1. First need to know about Roman numbers: I – 1, V – 5, X – 10, L – 50, C – 100, D – 500, M – 1000. For special representation of 4 and 9, it’s simpler to just hard code the rules and insert to the above list. Then only need to check if number > (1000,900,…), if so append a symbol accordingly.
  2. Be careful about checking the range in the match function.

Java Solution

public class Solution {
    public int romanToInt(String s) {
        //I - 1, V - 5, X - 10, L - 50, C - 100, D - 500, M - 1000.
        //only need to check if greater than 10-9-5-4-1
        String[] sym = {"M","CM", "D","CD", "C", "XC", "L", "XL", "X", "IX", "V","IV" ,"I"};
        int[] scale = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        int result = 0;
        int i = 0; 
        int j = 0;
        while( i < s.length()){
            if(match(s, i, sym[j])){
                result += scale[j];
                i+= sym[j].length();
            }
            else{
                j++;
            }
        }
        return result;
    }    
    private boolean match(String a, int id, String b){
        int l = b.length();
        if(a.length()-id < l)return false;
        return b.equals(a.substring(id,id+l));
    }
}

Leetcode–Integer to Roman

The Problem:

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Notes:

  1. First need to know about Roman numbers: I – 1, V – 5, X – 10, L – 50, C – 100, D – 500, M – 1000. For special representation of 4 and 9, it’s simpler to just hard code the rules and insert to the above list. Then only need to check if number > (1000,900,…), if so append a symbol accordingly.

Java Solution

public class Solution {
    public String intToRoman(int num) {
        StringBuffer sb = new StringBuffer();
        //I - 1, V - 5, X - 10, L - 50, C - 100, D - 500, M - 1000.
        //only need to check if greater than 10-9-5-4-1
        String[] sym = {"M","CM", "D","CD", "C", "XC", "L", "XL", "X", "IX", "V","IV" ,"I"};
        int[] scale = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        int i = 0;
        while(i < sym.length){
            if(num >= scale[i]){
                sb.append(sym[i]);
                num -= scale[i];
            }
            else{
                i++;
            }
        }
        return sb.toString();
    }
}

Leetcode–Sum Root to Leaf Numbers

The Problem:

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Notes:

  1. This is a basic tree traversal problem. The key is to only add to final output at leaf nodes.

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int sum = 0;
    public int sumNumbers(TreeNode root) {
        if(root==null)
            return 0;
        sumPath(root, 0);
        return sum;
    }
    
    public void sumPath(TreeNode root, int pass){
        if(root.left==null && root.right==null){
            // leaf node, add to final result
            sum+= 10 * pass + root.val;
        }
        else {
            if(root.left!= null){
                 sumPath(root.left, 10 * pass + root.val);
            }
             if(root.right!= null){
                 sumPath(root.right, 10 * pass + root.val);
            }
        }
    }
}

Leetcode–Subsets

The Problem:

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:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Notes:

  1. Sort the input list first, and then add each next element to all existing list in result. Remember to add an empty set first.

Java Solution

public class Solution {
    public List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        result.add(new ArrayList<Integer>());
        if(S.length==0){
            return result;
        }
        Arrays.sort(S);
        for(int i = 0; i < S.length; i++){
            int len = result.size();
            for(int j = 0; j < len; j++){
                ArrayList<Integer> addlist =  new ArrayList<Integer>(result.get(j));
                addlist.add(S[i]);
                result.add(addlist);
            }
        }
        return result;
    }
}

Leetcode–Anagrams

The Problem:

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Notes:

  1. The key is to sort each string, and use sorted string as the signature to group anagrams.
  2. Use a hashMap to record the list of each group. We can also directly add the anagrams to result list (with some mark to tell if a key in the map has no anagram) since we don’t need to return the result by groups

Java Solution

public class Solution {
    public List<String> anagrams(String[] strs) {
        List<String> result = new ArrayList<String>();
        if(strs.length==0) return result;
        Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for(int i = 0; i < strs.length; i++){
            char[] arr = strs[i].toCharArray();
            Arrays.sort(arr);
            String newstr = new String(arr);
            if(!map.containsKey(newstr)){
                map.put(newstr, new ArrayList<String>());
            }
            map.get(newstr).add(strs[i]);
        }
        for(ArrayList<String> list : map.values()){
            if(list.size()>=2){
                for(String s : list)
                    result.add(s);
            }
        }
        return result;
    }
}

Leetcode–Generate Parentheses

The Problem:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

 

Notes:

  1. I tried to derived the list of n from list of n-1, then found it’s not that easy! Try a different approach which is much simpler: Add a ‘(‘ if number of left not reach n, and add a ‘)’ if left more than right.

Java Solution

public class Solution {
    List<String> result;
    public List<String> generateParenthesis(int n) {
        result = new ArrayList<String>();
        if(n==0)
            return result;
        gp(1, 1, n, "(");
        return result;
    }
    public void gp(int left, int lSubR, int n, String str){
        if(left==n && lSubR==0){// a valid string
            result.add(str);
        }
        else if(left==n){
            gp(left, lSubR-1, n, str+")");
        }
        else if(left < n){
            gp(left+1, lSubR+1, n, str+"(");
            if(lSubR > 0){
                gp(left, lSubR-1, n, str+")");
            }
        }    
    }
    
}

Leetcode–Word Ladder

The Problem:

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Notes:

  1. At first I was considering using recursion, which results in a “DFS” structure, and need to keep track of min steps, because it may already traverse down too far in one recursion then reach the end, yet in other branches may only need much fewer steps. This is an indication that we should use “BFS” instead.
  2. When using BFS, we need 3 things:
    1. a queue to hold “next start”
    2. a set to record the strings already visited, to avoid trapped in a loop
    3. since we need to return the steps, it needs to pair with the string in queue. So I used a wrapper class.

Java Solution I-DFS

public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        if(start.equals(end)) return 1;
        char[] arr = start.toCharArray();
        int min = Integer.MAX_VALUE;
        for(int i = 0; i <start.length(); i++){
            char temp = arr[i];
            for(char ch = 'a'; ch <='z'; ch++){
                if(ch != temp){
                    arr[i] = ch;
                    String nxt = new String(arr);
                    if(end.equals(nxt))
                        return 2;
                    else if(dict.contains(nxt)){
                        dict.remove(nxt);
                        min = Math.min(min, 1+ ladderLength(nxt, end, dict));
                        dict.add(nxt);
                    }
                }
            }
            arr[i] = temp;
        }
        return min==Integer.MAX_VALUE ? 0:min;
    }
}

Java Solution II-BFS

public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        if(start.equals(end)) return 1;
        Queue<WrapStr> q = new LinkedList<WrapStr>();
        Set<String> visited = new HashSet<String>();
        q.add(new WrapStr(start, 1));
        visited.add(start);
        while(!q.isEmpty()){
            WrapStr wp = q.poll();
            char[] arr = wp.str.toCharArray();
            for(int i = 0; i <arr.length; i++){
                char temp = arr[i];
                for(char ch = 'a'; ch <='z'; ch++){
                    if(ch != temp){
                        arr[i] = ch;
                        String nxt = new String(arr);
                        if(end.equals(nxt))
                            return wp.steps+1;
                        else if(!visited.contains(nxt) && dict.contains(nxt)){
                            q.add(new WrapStr(nxt, wp.steps+1));
                            visited.add(nxt);
                        }
                    }
                }
                arr[i] = temp;
            }
        }
        return 0;        
    }
}
class WrapStr{
    public String str;
    public int steps;
    public WrapStr(String s, int l){
        str = s;
        steps = l;
    }
}