［LeetCode］Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,

If n = 4 and k = 2, a solution is:

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


解题思路：
                1. 求n个数中的k个数的组合，如果此组合含有n,则就是求n-1的k-1个组合，不含有n，就是n-1的k。即 combine(n, k) = combine(n-1, k -1) + combine(n-1, k);
                2. 要注意的就是n-1,k-1可能返回nil, 那么这时就要初始化n。
       

public List> combine(int n, int k) {
         List> res = new ArrayList>();
         
         if( n < k || k == 0) return res;
         
         res = combine(n-1, k-1);
         
         for(int i = 0; i < res.size(); i++){
             List tmp = res.get(i);
             tmp.add(n);
         }
         
         if(res.size() == 0){
             List tmp = new ArrayList();
             tmp.add(n);
             res.add(tmp);
         }
         
         res.addAll(combine(n-1, k));
         
         return res;
    }

[LeetCode] Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.



解题思路：
1. recursion method, check the height of the left sub tree and right sub tree. 
2. Keep track the height of every node, then we iterate the whole tree only one time.

Java Code:
     

 public boolean isBalanced(TreeNode root) {
        
        return getHeight(root) != -1;
    }
    
    public int getHeight(TreeNode root){
        if(root == null) return 0;
        
        int leftheight = 0, rightheight = 0;
        
        if(root.left != null) leftheight = getHeight(root.left);
        if(root.right != null) rightheight = getHeight(root.right);
        if(leftheight == -1 || rightheight == -1 || Math.abs(leftheight - rightheight) > 1) return -1;
        
        int height = leftheight > rightheight? leftheight +1 : rightheight + 1;
        
        return height;
    }

[LeetCode] Binary Tree PostOrder

Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?

解题思路：
1. recursion 最直接的做法
2. non-recursion, 借助stack.
   2.1 find the leftmost node, for every step, push node.right, node into stack
  2.2  pop up one node if current node is null, if the popped one node has its right node at the top of the stack, then pop up its right child node, push itself into the stack. repeat the 2.1

和inorder类似，区别为在push node, node.right的顺序不一样。要确保node的right child 不会重复visit,就先push node.right, 再存入node. 这样每次就可以对比当前的node的right child是不是为stack top。

Java Code:

recursion solution:

 public List postorderTraversal(TreeNode root) {
         List res = new ArrayList();
        
         postorderT(res, root);
         return res;
    }
     public void postorderT(List res, TreeNode root) {
            if(root == null) return;
            if(root.left != null) postorderT(res, root.left);
            if(root.right != null) postorderT(res, root.right);
            res.add(root.val);
    }

non-recursion solution:

public List postorderTraversal(TreeNode root) {
         List res = new ArrayList();
         Stack tmp = new Stack();
         TreeNode p = root;
         
         while(!tmp.isEmpty() || p != null ){
             while(p != null){
                 if(p.right != null) tmp.add(p.right);
                  tmp.add(p);
                
                 p = p.left;
             }
             
            p = tmp.pop();
            
            if(p.right != null && !tmp.isEmpty() &&p.right == tmp.peek()){
               TreeNode tmp0 = tmp.pop();
               tmp.add(p);
               p = p.right;
            }else{
                res.add(p.val);
                p = null;
            }
         }
         
         return res;
    }

Binary Tree Zigzag Level Order Traversal

Question:

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
] 

Java Code:

  public static ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root)
    {
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>> ();
        ArrayList<TreeNode> tmpQ = new ArrayList<TreeNode> ();
        
        int i = 0;
        
        if(root != null)
            tmpQ.add(root);
    
        while ( !tmpQ.isEmpty() )
        {
            ArrayList<Integer> tmpresult = new ArrayList<Integer> ();
            int length = tmpQ.size();
            int count = 0;
            
            for (int z = 0; z < length; z++)
                tmpresult.add(tmpQ.get(z).val);
            
            while( count < length)
            {
                TreeNode tmp = tmpQ.get(length - 1 - count);
                tmpQ.remove(length-1-count);
                
                count++;
                
               if (i%2 == 0)
                {
                   if(tmp.right != null)
                       tmpQ.add(tmp.right);
                   if(tmp.left != null)
                       tmpQ.add(tmp.left);
                }
               else 
               {
                   if(tmp.left != null)
                       tmpQ.add(tmp.left);
                   if(tmp.right != null)
                       tmpQ.add(tmp.right);   
               }
             
            }
            
            results.add(tmpresult);
            i++;
        
        }
    
        return results;
    
    }

[LeetCode] Anagrams

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

解题思路：
        寻找回文构词，就是需要建立一个hash函数，使得为anagrams的词都映射到相同的hash key。
      1. 最直接的方法，就是对每个str进行排序，然后比较它们是否相等
      2. 这里我用的是countandsay的方法，就是统计出每个字母出现的次数，然后用字母的次数和字母组合成一个key。
     3. 这个题可以转化为，如何找出2个str为anagrams. 我们可以为每个字母分配一个不同的prime，最后把所有的prime相乘。如果最后的数相等，则为anangrams.

Notice : 这里hash函数的value存的为第一次出现此key的str在数组里的index. 如果出现了此词的anangrams，则将此index. 改为-1。

Java Code:

   

  public List anagrams(String[] strs) {
       List res = new ArrayList ();
       HashMap tmp = new HashMap();

       for(int i = 0; i < strs.length; i++){     
           String key = getKey(strs[i]);
           
           if(tmp.containsKey(key)){
                if(tmp.get(key) != -1){
                   res.add(strs[tmp.get(key)]);
                   tmp.put(key, -1);
               }
               res.add(strs[i]);
              
           }else{
               tmp.put(key, i);
           }
       }
       
       return res;
    }
    
    public String getKey(String str){
        int[] count = new int[26];
        String res = "";
        
        for(int i = 0; i < str.length(); i++){
            count[str.charAt(i) - 'a']++;
        }
        
        for(int i = 0; i < 26; i++){
            if(count[i] > 0){
                res += count[i] + String.valueOf(Character.toChars(i+'a')) ;
            }
        }
        
        return res;
    }

[LeetCode] Add Two Numbers

Question:

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解题思路： 一道实现题

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
           ListNode p1 = l1;
           ListNode p2 = l2;
           ListNode head = new ListNode(0);
           ListNode p = head;
           
           int add = 0;
           
           while(p1 != null || p2 != null || add > 0){
               int add1 = 0, add2 = 0;
               
               if(p1 != null){
                  add1 = p1.val;
                  p1 = p1.next;
               } 
               
               if(p2 != null){
                   add2 = p2.val;
                   p2 = p2.next;
               } 
               
                int val = (add1 + add2 + add)%10;
                add = (add1 + add2 + add)/10;
                
                ListNode l = new ListNode(val);
                p.next = l;
                p = p.next;
           }
           
           return head.next;
    }

[LeetCode] Add Binary

Question:

Given two binary strings, return their sum (also a binary string). 
For example,
a = "11"
b = "1"
Return "100".  

Java Code:

 
 public String addBinary(String a, String b) {
     String res = "";
          int aLen = a.length();
          int bLen = b.length();
          int add = 0, add1 = 0, add2 = 0;
          
          int i = 1;
          
          while( i <= aLen || i <= bLen || add > 0){
              add1 = i <= aLen ? a.charAt(aLen - i) - '0' : 0;
              add2 = i <= bLen? b.charAt(bLen - i) - '0' : 0;
              
              res = (add1+add2+add)%2 + res;
              add = (add1 + add2 + add)/2;
              i++;
          }
          
          return res;
       }

[LeetCode] 4Sum

Question:

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Thoughts : similar with the 3Sum

Java Code:

public List> fourSum(int[] num, int target) {
           Arrays.sort(num);
           List> res = new ArrayList>();
           
           for(int i = 0; i < num.length - 3; i++){
               for(int j = i+1; j < num.length - 2; j++){
                   int start = j+1, end = num.length - 1;
                   
                   while(start < end){
                       int total = num[i] + num[j] + num[start] + num[end];
                       
                       if(total == target){
                           List tmp = new ArrayList();
                           tmp.add(num[i]);
                           tmp.add(num[j]);
                           tmp.add(num[start]);
                           tmp.add(num[end]);
                           
                           res.add(tmp);
                       }
                       
                       if(total >= target){
                           end--;
                           while(end > start && num[end] == num[end+1]) end--;
                       }
                       
                        if(total <= target){
                           start++;
                           while(end > start && num[start] == num[start-1]) start++;
                       }
                   }
                   
                   while(j < num.length -2 && num[j] == num[j+1]) j++;
               }
               
               while(i < num.length - 3 && num[i] == num[i+1]) i++;
           }
           
           return res;
    }

[LeetCode] 3Sum closest

Question:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

解题思路：
              与3Sum一样

Java code:

public int threeSumClosest(int[] num, int target) {
        Arrays.sort(num);
        int closestNum = Integer.MAX_VALUE;
        
        for(int i = 0; i < num.length - 2; i++){
            int j = i+1;
            int t = num.length - 1;
            
            while(j < t){
            int total = num[i] + num[j] + num[t] - target;
            
            if(total == 0){
                return target;
            }
            
            closestNum = Math.abs(total) < Math.abs(closestNum) ? total : closestNum;
            
            if(total > 0){
                t--;
                
                while(j < t && num[t] == num[t+1]) t--;
            }else{
                j++;
                
                while(j < t && num[j] == num[j-1]) j++;
            }
          }
          
          while(i < num.length - 2 && num[i] == num[i+1]) i++;
        }
        
        
        return closestNum + target;
        
    }

[LeetCode] 3 sum

Question:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

解题思路：2个pointer，前后扫描。注意移动的时候，要移到下一个不同的数。

Java Code:

public List> threeSum(int[] num) {
        Arrays.sort(num);
        List> res = new ArrayList>();
        
        for(int i = 0; i < num.length - 2;){
            int s = i+1;
            int e = num.length - 1;
            
            while(s < e){
                int total = num[i]+num[s]+num[e];
                if(total == 0){
                    List tmp = new ArrayList();
                    tmp.add(num[i]);
                    tmp.add(num[s]);
                    tmp.add(num[e]);
                    res.add(tmp);
                }
                
                if(total >= 0){
                    e--;
                    while(e > s && num[e+1] == num[e]) e--;
                }
                
                if(total <= 0){
                   s++;
                   while(e > s && num[s] == num[s-1]) s++;
                }
            }
            
            i++;
            while(i < num.length-2 && num[i] == num[i-1]) i++;
        }
        
        return res;
}

[LeetCode] Minimum depth of Binary Tree

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

解题思路：典型的BSF. 用一个Queue就好了

Java code:

public int minDepth(TreeNode root) {
        Queue tmp = new LinkedList ();      
        if(root == null) return 0;   
        
        tmp.add(root);
        int minDepth = 0;
        
        while(!tmp.isEmpty()){
            int count = tmp.size();
            minDepth++;
            
            for(int i = 0; i < count; i++){
               TreeNode t = tmp.poll();
               
               if(t.left == null && t.right == null){
                   return minDepth;
               }else{
                   if(t.left != null) tmp.add(t.left);
                   if(t.right != null) tmp.add(t.right);           
               }
            }
            
        }
        return minDepth; 
    }

Multiply Strings

Visit this to view the content of this question.

Java code:

  public static String multiple(String num1, String num2)
    {
     String result = "";
    
     if (num1.isEmpty() || num2.isEmpty())
         return result;
     if ( num1.compareTo("0") == 0 || num2.compareTo("0") == 0)
         return "0";
    
     int tmp = 0, add = 0;
     int j;
    
     for (int i = 0; i < num1.length() + num2.length() - 1; i++)
     {
       if ( i >= num1.length() )
           j = num1.length() -1;
       else j = i;
          
       while ( (i - j) < num2.length() && j >= 0)
       {
           System.out.println(i + " " + j);
          
        tmp += Integer.parseInt(num2.substring(num2.length() -1 -i+j, num2.length() -i+j)) * Integer.parseInt(num1.substring(num1.length() - 1 - j, num1.length()- j));
        System.out.println(tmp);
        j--;
       }
      
       result =  (tmp + add)%10 + result;
       add = (tmp+add)/10;
       tmp = 0;
      
     }
     if (add != 0)
         result = add + result;
   
    
     return result;
    
    }

Minimum Window Substring

Visit this to view the content of this question.

Java code:
  public static String minWindow (String S, String T)
    {
     if ( S.length() < T.length() || T.isEmpty())
         return "";
   
     int min = 0;
     int start = 0;
     int end = 0;
   
     HashMap<String, Queue<Integer>> window = new  HashMap<String, Queue<Integer>>();
     ArrayList<Integer> index = new ArrayList<Integer> ();
   
     ArrayList<String> tmpT = new ArrayList<String> ();
   
     for (int j = 0; j < T.length(); j++)
     {
        tmpT.add(T.substring(j, j+1));
     }
   
     for (int i = 0; i < S.length(); i++)
     {
       if (T.contains( S.substring(i, i+1)))
       {
           if (tmpT.contains(S.substring(i, i+1)))
           {
               Queue<Integer> tmp = window.get(S.substring(i, i+1));
             
               if (tmp == null)
               {
                tmp = new LinkedList<Integer> ();
               }
             
               tmp.add(i);
               window.put(S.substring(i, i+1), tmp );
               tmpT.remove(S.substring(i,i+1));
             
               index.add(i);
             
               if (tmpT.isEmpty())
               {
                min = index.get( index.size() - 1)- index.get(0);
                start = index.get(0);
                end = index.get( index.size() - 1 );
               }
           }
           else
           {
               Queue<Integer> tmp = window.get(S.substring(i, i+1));
               tmp.add(i);
               index.remove( index.indexOf(tmp.poll()));
               index.add(i);
               window.put(S.substring(i, i+1), tmp);
           }
         
           /**
            * update the min widow.
            */
         
           if (tmpT.isEmpty())
           {
            if ( min > index.get( index.size() - 1)- index.get(0) )
               {
                start = index.get(0);
                end = index.get(index.size() - 1);
                min = index.get( index.size() - 1)- index.get(0);
               }
           }
       }
     
     }
  
     if( !tmpT.isEmpty() )
         return "";
   
    else return S.substring(start, end+1);
   
    }

[LeetCode] Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

 解体思路：
       1. 数组A[0..j]的最大和来自于子数组A[0..j-1]或者来自于A[i..j]
       2. 对于A[i..j]的最大数，是 A[i..j-1]+A[j] or A[j]
       3. 使用divide-conquer 解法：A[0..n]的最大值来自于3个地方：左边子数组A[0..j]， 右边子数组 A[j+1..n]的最大值，或者跨越这两个数组之间的最大值，也就是一定包含A[j],A[j+1]的最大值。
     
     

public int maxSubArray(int[] A) {
        if(A.length == 0) return 0;
        int maxSum = A[0];
        int sum = A[0];
        
        for(int i = 1; i < A.length; i++){
           sum = A[i] > sum + A[i] ? A[i] : sum + A[i];
           maxSum = Math.max(maxSum, sum);
        }
     
        return maxSum;
    }

divide-conquer的解法

public int maxSubArray(int[] A) {
        if (A.length == 0) return 0;
        
        return maxSubarray(A, 0, A.length - 1);
    }

    public int maxSubarray(int[] A, int start, int end) {
        int mid = (start + end) / 2;
        int leftMax = Integer.MIN_VALUE;
        int rightMax = Integer.MIN_VALUE;
        int crossMax = Integer.MIN_VALUE;
        int maxSum = 0;
        
        if(start == end) return A[start];
        
        if (mid >= start) {
            leftMax = maxSubarray(A, start, mid);
        }

        if (mid < end) {
            rightMax = maxSubarray(A, mid + 1, end);
        }


        if (mid >= start && mid < end) {
            int sum = A[mid];
            crossMax = A[mid];
            
            for (int j = mid - 1; j >= start; j--) {
                sum += A[j];
                crossMax = Math.max(sum, crossMax);
            }

            crossMax+= A[mid+1];
            sum = crossMax;
            
            for (int i = mid + 2; i <= end; i++) {
                sum += A[i];
                crossMax = Math.max(sum, crossMax);
            }
        }
        
        maxSum = Math.max(leftMax,rightMax);
        maxSum = Math.max(maxSum, crossMax);
        
        return maxSum;
    }

[LeetCode] Plus One

Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.

注意：数字不可以以0开头，所以我们要考虑最后进位的问题。如果超过原来的数组长度，得重新分配一个数组

Java code:

public int[] plusOne(int[] digits) {
        int add = 1;
        int len = digits.length;
        
        for(int i = len - 1; add > 0 && i >= 0; i--){
            digits[i] = (digits[i] + add)%10;
            add = (digits[i] + add)/10;
        }
        
        if( add > 0 ){
            
            int[] result = new int[len + 1];
            result[0] = add;
            
            for(int i = 1; i <= len; i++){
                result[i] = digits[i-1];
            }
            return result;
        }
       
        return digits;
    }

[LeetCode] Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
解题思路： 典型的DP
        1. S(i)->T(j) = S(i-1)->T(j-1) if s(i) == t(j)
        2. if s(i) != t(j), 有三个选择，2.1 插入 S(i)->T(j-1) = S(i) ->T(j) 2.2 删除，S(i-1, j) ->S(i, j)   2.3. 替换 S(i-1)->T(j-1) = S(i) -> T(j)

public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        
        int[][] minDis = new int[len1+1][len2+1];
        
        for(int i = 0; i <= len1; i++){
            for(int j = 0; j <= len2; j++){
                if(i == 0){
                    minDis[i][j] = j;
                }else if( j == 0){
                    minDis[i][j] = i;
                }else{
                    if(word1.charAt(i-1) == word2.charAt(j-1)){
                        minDis[i][j] = minDis[i-1][j-1]; 
                    }else{
                        int min = Math.min(minDis[i-1][j-1], minDis[i][j-1]);
                        min = Math.min(min, minDis[i-1][j]);
                        
                        minDis[i][j] = min + 1;
                    }
                }
            }
        }
        
        return minDis[len1][len2];
    }

[LeetCode]First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.

解题思路：
  1. 长度为n的数组应该包含的正整数是1-n. 而数组的index为0-n-1。 所以我们可以将数为i的数移到i-1的位置上。这样，第一个A[i-1] != i的数，就是我们要找的first missing positive

注意：当我们移动数i到i-1的位置上时，要考虑到i必须在1-n之间，并且i-1位置原有的数不为i

public int firstMissingPositive(int[] A) {
       for(int i = 0 ; i < A.length; i++){
           while(A[i] > 0 && A[i] <= A.length && A[A[i] - 1] != A[i]){
               int tmp = A[A[i]-1];
               A[A[i]-1] = A[i]; 
               A[i] = tmp;
           }
       }
       
       int i = 1;
       while (i <= A.length && A[i-1] == i){
           i++;
       }
       
       return i;
    }

Double Square Problem

A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 3² + 1². Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 32 + 12 (we don’t count 1² + 3² as being different). On the other hand, 25 can be written as 5² + 0² or as 4² + 3².
Input
You should first read an integer N, the number of test cases. The next N lines will contain N values of X.
Constraints
0 = X = 2147483647
1 = N = 100
Output
For each value of X, you should output the number of ways to write X as the sum of two squares.

Solutions:
We use the bruce force method to solve this problem

Palindrom Number

See this to view the content of this question.
 
Java Code:


   public  static boolean isPalindrome(int x)
    {
      if ( x < 0 )
         return false;
     
      int count = (int) Math.floor( Math.log10(x)) + 1;
     
      if (count < 2)
          return true;
    
      int tmp = (int) Math.pow(10, count -1);
      int start = 10;
     
      while ( count > 1)
      {
         if ( x%start != x/tmp)
             return false;
        
         x =( x - (x/tmp * tmp) - (x%start *(start/10)) ) /10;
        
         tmp = tmp/100;
        
         count -= 2;
        
      }
     
    return true;
   
    }

[LeetCode] Longest Valid Parenthese

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

解题思路：
用两个stack，一个用来装不match的括号符号，另一个装此符号的index。最后得到的stack就是将隔断match符号的位置。相隔的两个index相减就得到了这两个符号的中间的有效括号长度。 


Java Code:

public int longestValidParentheses(String s) {
       Stack index = new Stack();
       Stack parenth = new Stack();
       int maxLen = 0;
       
       for(int i = 0; i < s.length(); i++){
           if(!index.isEmpty() && parenth.peek() == '(' && s.charAt(i) == ')'){
               parenth.pop();
               index.pop();
           }else{
               parenth.add(s.charAt(i));
               index.add(i);
           }
       }
       
       int curr = s.length();
       while(!index.isEmpty()){
           maxLen = maxLen > curr - 1 - index.peek()? maxLen : curr - 1 - index.peek();
           curr = index.pop();
       }
       
       if(curr > 0){
           maxLen = maxLen > curr? maxLen : curr;
       }
       
        return maxLen; 
    }

Largest Rectangle in Histogram

See this to view question.

Java Code:

 public static int largestHistArea(int[] height)
    {
      Stack<Integer> heights = new Stack<Integer> ();
      Stack<Integer> indexes = new Stack<Integer> ();
      int largestSize = 0;
     
      for (int i = 0; i < height.length; i++)
      {
       if (heights.isEmpty() || height[i] > heights.peek())
       {
         heights.push(height[i]);
         indexes.push(i);
       }
      
       else  if ( height[i] < heights.peek() )
        {
         int lastIndex  = 0;
         while ( !heights.isEmpty() && height[i] < heights.peek())
         { 
             lastIndex = indexes.pop();
            int tmpsize = heights.pop() * (i-lastIndex);
          
            if (tmpsize > largestSize)
               largestSize = tmpsize;   
         }
         heights.push(height[i]);
         indexes.push(lastIndex);
       }
       
      }
     
      while ( !heights.isEmpty() )
         {
           int tmpsize = heights.pop() * (height.length - indexes.pop());
          
           if (tmpsize > largestSize)
               largestSize = tmpsize;   
         }
     
      return largestSize;
   
    }

[LeetCode] Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)


Java Code:

 public int jump(int[] A) {
        if(A.length < 2) return 0;
        
        int start = 0, end = 0, step = 0, max = 0;
        
        while(end < A.length){
            step++;
            for(int i = start; i <= end; i++){
                if(A[i] + i >= A.length - 1) return step;
                
                max = max > A[i] + i? max : i + A[i];
            }
           
            start = end + 1;
            end = max;
            
        }
        
        return step;
    }

[LeetCode] Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

Java Code:

public boolean canJump(int[] A) {
        if(A.length < 1) return true;
        
        int endIndex = 0;
        
        for(int i = 0; i <= endIndex; i++){
            if(i+A[i] >= A.length - 1) return true;
            
           endIndex = i+A[i] > endIndex? i +  A[i] : endIndex;
        }
        
        return false;
    }

[LeetCode] Integer to Roman

Given an integer, convert it to a roman numeral.

Java Code:

public String intToRoman(int num) {
       HashMap intRomanMap = new HashMap();
       intRomanMap.put(1000, "M");
       intRomanMap.put(900, "CM");
       intRomanMap.put(500, "D");
       intRomanMap.put(400, "CD");
       intRomanMap.put(100, "C");
       intRomanMap.put(90, "XC");
       intRomanMap.put(50, "L");
       intRomanMap.put(40, "XL");
       intRomanMap.put(10, "X");
       intRomanMap.put(9, "IX");
       intRomanMap.put(5, "V");
       intRomanMap.put(4, "IV");
       intRomanMap.put(1, "I");
       
       
       String result = "";
       int[] ints = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
       
       for(int i = 0; num > 0 && i < ints.length; i ++){
           int remainder = num/ints[i];
           num = num%ints[i];
           
           for(int j = 0; j < remainder; j++){
               result += intRomanMap.get(ints[i]);
           }         
       }
       
       return result;
       
    }