LeetCode 179: Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.

public class Solution {
    public String largestNumber(int[] num) {
        // Adopt modified LSD (Least-Significant-Digits) algorithm
        // MSD algorithm is not suitable here
        // However, LSD requires identical length of every element (String format)
        // Suppose that the longest length of element is 4, we append any element by itself until the length is 4*2:
        // "123" ---> "123"+"123"+"12" ---> "12312312"
        // We can define a "charAt()" function to implement that without actually append the string.
        int n = num.length;
        int R = 10; // Only 10 digits: 0, 1, 2, ..., 9
        int len = 0; // Max length of elements
        String[] a = new String[n];
        String[] aux = new String[n];
        
        // Convert 'num' to 'a'
        for (int i = 0; i < n; i++)
        {
            a[i] = String.valueOf(num[i]);
            
            if (len < a[i].length())
                len = a[i].length();
        }
        
        // Original num: [3, 30, 34, 5, 9]
        // Result: [30, 3, 34, 5, 9]
        for (int d = len*2-1; d >= 0; d--)
        {
            int[] count = new int[R+1];
            
            // Compute frequency counts
            for (int i = 0; i < n; i++)
                count[charAt(a[i], d)+1]++;
                
            // Transform counts to indices
            for (int r = 0; r < R; r++)
                count[r+1] += count[r];
                
            // Distribute the data
            for (int i = 0; i < n; i++)
                aux[count[charAt(a[i], d)]++] = a[i];
                
            // Copy back
            for (int i = 0; i < n; i++)
                a[i] = aux[i];
        }
        
        String result = "";
        
        for (int i = n-1; i >= 0; i--)
            result += a[i];
        
        // Note: Maybe exist special case: "0000"    
        if (result.length()>1 && result.charAt(0)=='0')
            result = "0";

        return result;
    }
    
    private int charAt(String s, int d)
    {
        d = d%s.length();
        
        return s.charAt(d)-'0';
    }
}

Interesting Post About Query Parser

• Paper:

The Magic and Wonder of Query Parsing – Search Technologies

More info:Sometimes it is necessary to apply a custom filter to an existing SQL query (to perform search … query, you should first create … parser will work faster if we …

URL: http://www.searchtechnologies.com/search-query-parsing

• Tool:

OpenNLP

The Apache OpenNLP library is a machine learning based toolkit for the processing of natural language text.
It supports the most common NLP tasks, such as tokenization, sentence segmentation, part-of-speech tagging, named entity extraction, chunking, parsing, and coreference resolution. These tasks are usually required to build more advanced text processing services. OpenNLP also includes maximum entropy and perceptron based machine learning.

• My understandings:

1. Different users speak different query languages; different kinds of search engines should have different documents or regulations.

2. Not only a string of simple tokens, how can we understand some operations or special signs, such as "+/-", "NOT", "OR", and so on?

3. How can you set up the relationships between "chair" and "chairs", between "mouse" and "mice", and so on?

4. Spell checker should put before query parser, which can remove some dirty data.

5. Relevancy ranking: Documents which contain search terms in the title or abstract may be considered to be more relevant; Query parsers can boost documents which contain all of the terms close together (proximity weighting) or boost documents from friendly web sites while reducing documents from un-friendly sites.

Jazzy-based Spell Checker

Jazzy is a set of APIs that allow you to add spell checking functionality to Java Applications easily.

For a misspelled word, Jazzy can provide with some corrected words for selection.

Additional task is to judge which word is better. We have two schemes to do that: 1. Edit distance; 2. Input frequency or context. Context information is based on Jazzy dictionary. However, for some specific search engine, common dictionary is not enough. For example, we should add some merchant brand names into the dictionary for Amazon's search engine.

There are still two problems here:

1. How do we customize our own dictionary? How do we confirm the validity of the data source for building the dictionary?
2. How do you balance the results of edit distance and context?

LeetCode 174: Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

Notes:

• The knight's health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        // DP problem
        // Let minHP[i][j] denotes the least HP when the knight reached dungeon[i][j].
        // Note: This question should consider backward induction.
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] minHP = new int[m][n];
    
        // Note: Supposed only one cube that imorisoned princess.
        minHP[m-1][n-1] = (dungeon[m-1][n-1] > 0) ? 1 : (1 - dungeon[m-1][n-1]);
    
        // 1. In the last column, from up to bottom.
        for(int i = m-2; i >= 0; i--)
        {
            int down = minHP[i+1][n-1] - dungeon[i][n-1];
            minHP[i][n-1]  = down > 0 ? down : 1;
        }
    
        // 2. In the last row, from left to right.
        for (int j = n-2; j >= 0; j--)
        {
            int right = minHP[m-1][j+1] - dungeon[m-1][j];
            minHP[m-1][j]  = right > 0 ? right : 1;
        }
    
        // 3. In other areas, from up to bottom and from left to right.
        for(int i = m-2; i >= 0; i--)
        {
            for(int j = n-2; j >= 0; j--)
            {
                int down = (minHP[i+1][j]-dungeon[i][j] > 0) ? minHP[i+1][j]-dungeon[i][j] : 1;
                int right = (minHP[i][j+1]-dungeon[i][j] > 0) ? minHP[i][j+1]-dungeon[i][j] : 1;
                
                minHP[i][j] = Math.min(down, right);
            }
        }
        
        return minHP[0][0];
    }
}

LeetCode 173: Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class BSTIterator {
    // Adopt inorder traversal
    Queue<TreeNode> queue;
    
    public BSTIterator(TreeNode root) {
        queue = new LinkedList<>();
        inorder(root);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if (!queue.isEmpty())
            return true;
        else
            return false;
    }

    /** @return the next smallest number */
    public int next() {
        return queue.remove().val;
    }
    
    private void inorder(TreeNode root)
    {
        if (root == null)
            return;
            
        inorder(root.left);
        queue.add(root);
        inorder(root.right);
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

LeetCode 172: Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.

public class Solution {
    public int trailingZeroes(int n) {
        // http://en.wikipedia.org/wiki/Trailing_zero
        
        // Non-negative number doesn't have factorial.
        // The factorial of 0 is 1.
        if (n <= 0)
            return 0;
        
        // Find k so that pow(5, k+1) > n.
        // Add 0.1 to n in case pow(5, k+1) = n.
        int k = (int)Math.ceil(Math.log(n+0.1)/Math.log(5.0)-1);
        
        if (k < 1)
            return 0;
        
        // The number of trailing zeros
        int ntz = 0;
        
        for (int i = 1; i <= k; i++)
            ntz += n/Math.pow(5, i);
        
        return ntz;
    }
}

LeetCode 171: Excel Sheet Column Number

Related to question Excel Sheet Column Title
Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

public class Solution {
    public int titleToNumber(String s) {
        // BAC -> 2*26*26+1*26+3
        // Note: Character.getNumericValue(ch) is used for convert number (e.g, '3' -> 3)
        // (int) is used to get ASCII code (e.g., 'A' -> 65; '3' -> 51)
        int n = s.length();
        int result = 0;
        int nA = 'A';
        
        for (int i = n-1; i >= 0; i--)
            result += Math.pow(26, n-i-1)*(s.charAt(i)-nA+1);
            
        return result;
    }
}