LeetCode 刷题第一阶段Longest Common Prefix & Implement Trie

前缀, 词频问题一般有两种解法，一种暴力枚举一种 trie 。出于学习考虑 此次用 trie 解决。而且就我所知的面试题中今年trie出现频率非常高。PS。虽然我神奇地听说过考察用DP解决这个问题的三哥面试官。。。如果有观众知道怎么用DP解， 还望赐教。

The next figure shows a trie with the words “tree”, “trie”, “algo”, “assoc”, “all”, and “also.”

Note that every vertex of the tree does not store entire prefixes or entire words. The idea is that the program should remember the word that represents each vertex while lower in the tree. ( from topcoder)

典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。

Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

使用范围

     既然学Trie树，我们肯定要知道这玩意是用来干嘛的。

     第一：词频统计。

            可能有人要说了，词频统计简单啊，一个hash或者一个堆就可以打完收工，但问题来了，如果内存有限呢？还能这么

             玩吗？所以这里我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。

     第二: 前缀匹配

            就拿上面的图来说吧，如果我想获取所有以"a"开头的字符串，从图中可以很明显的看到是：and,as,at，如果不用trie树，

            你该怎么做呢？很显然朴素的做法时间复杂度为O(N²) ，那么用Trie树就不一样了，它可以做到h，h为你检索单词的长度。

===========================================================

Leetcode：

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

=========================================================

思路不难，但是边界问题太多。。。本人之前写出了一个Bug硬是没有找出来。。。后来大神帮忙看才找出来。。我把isWord标在了正确值的上面一个好像，同时查找的时候也查的是上一个。所以出现了95%的test 能过。。不过代码还可以优化。。。待我回头再来。。。
=========================================================
Code:





欢迎指正

LeetCode 刷题第一阶段 Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

=================================================================

2个loop check.  easy.  更好的解法可参考trie. 时间复杂度更低但是code实现起来太麻烦。。此处不用。

CODE:

LeetCode 刷题第一阶段 Integer to Roman

Given an integer, convert it to a roman numeral.
==============================================

Key point:
建个二维数组来存数。


===================================================================
CODE:
public class Solution {
    public String intToRoman(int num) {
        String ret = "";
        String [][] table = { {"","I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
        {"","X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
            {"","C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
            {"","M", "MM", "MMM"}};
        int [] n = {1,10,100,1000};
        int index = 3;
        
        while(index >= 0){
           int rem = num % n[index];
           int dif = num / n[index];
           ret += table[index][dif];
           num = rem ;
           index --;
        }
        
        return ret;
    }
    

}

LeetCode 刷题第一阶段 Roman to Integer

Given a roman numeral, convert it to an integer.

================================================================================
做题须知:

【罗马数字】

1~9: {"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

10~90: {"X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};

100~900: {"C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};

1000~3000: {"M", "MM", "MMM"}.

Which means:

I -> 1

V -> 5

X -> 10

L -> 50

C -> 100

D -> 500

M -> 1000

规律: 左减右加。 设一个指针，每次判断它的前一个是不是比它小， 小就从结果里减去。

=======================================================================

Code:

public class Solution {

    public int romanToInt(String s) {

        char [] t = s.toCharArray();

        int cur = 1;

        int res = toNum(t[0]);

        while(cur < s.length()){

            // minus

            if(toNum(t[cur - 1]) < toNum(t[cur])){

                res += toNum(t[cur]) - 2*toNum(t[cur - 1]); 

            } else{

                // plus

                res += toNum(t[cur]) ; 

            }

            cur ++;

        }

        

        return res;

    }

    

    public int toNum(char c){

        switch(c){

            case 'I' : return 1;

            case 'V' : return 5;

            case 'X' : return 10;

            case 'L' : return 50;

            case 'C' : return 100;

            case 'D' : return 500;

            case 'M' : return 1000;

        }

        return 0;

    }

}

LeetCode 刷题第一阶段 Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

======================================================

Just create a reverse int and compare them. Pay attention that if the input is negative it will always return false.

Code:
public class Solution {
    public boolean isPalindrome(int x) {
        boolean ret = true;
        if(x < 0) return false;
        int rev = 0;
        int n = x;
        while(n != 0){
            int temp = n % 10;
            rev = rev * 10 + temp;
            n = n / 10;
        }
        
        if(rev != x) ret = false;
        
        return ret;
    }

}

面试中需要问清楚的 clarifying question

1. Array:

(1) Sorted or not?

(2) How many elements?

(3) Element type? Int, float, double?

(4) What's the range of those numbers? Positive or negative?

(5) Contain duplicates or not?

2. Binary tree:

(1) Binary search tree or normal binary tree? Or normal tree?

(2) Balanced or not?

(3) Complete or not?

(4) Has parent pointer or not?

3. Linked list:

(1) Singly or doubly linked list?

(2) Has duplicated nodal value or not?

4. String:

(1) Need to remove white spaces? Tab and newline?

(2) Only has digits? English letters? Upper or lower case?

5. Graph:

(1) How many nodes and edges?

(2) Directed or undirected?

(3) Edges have weights? If so, what's the range?

(4) Has loops? Negative sum loops?

6. Return value:
(1) What should my method return?
(2) If there are multiple solutions to the problem, which one should be returned?
(3) If it should return multiple values, do you have any preference on what to return?
(4) What should I do/return if the input is invalid / does not match the constraints?

LeetCode 刷题第一阶段 String to Integer

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

=================================================================================

Mainly consider special cases:

1. string null or "" (length = 0)

2. contains non-digit element(s): 符号位 （sign）和数位, return the int before

3. exceed int value range (check overflow). If exceed INT_MAX we return INT_MAX, if exceed INT_MIN we return INT_MIN.
4. white space

The function we would use : Integer.parseInt(String s) , we will use it to convert the string. But we have to check all conditions to avoid assertion or exception. 

Checking the first two condition is easy, we must figure out the third one.

P.S.  convert result to "long" or double will be a faster way but normally this is not a good solution so we try to avoid it. 

Attention:

 For input ”+1“ should return "1", "+-1" should return 0.

 For input "  35ab7876" should return "35"
================================================================

Code:

public class Solution {
    public int myAtoi(String str) {
        int ret = 0;
        int index = 0;
        boolean negative = false;
       if(str != null){
          // wipe out whitespace
          str = str.trim();
          if(str.length()>0){ 
          // check sign 
          char sign = str.charAt(0);
          if(sign == '+' || sign == '-'){
              if(str.length() == 1 ) return 0;
              if(sign == '-') negative = true;
              str = str.substring(1);
          }
        //check digits
        while(index < str.length()){
            if(str.charAt(index) - '0' > 9 || str.charAt(index) - '0' < 0){
                str = str.substring(0,index);
                if(str.length() == 0 ) return 0;
            } 
            index ++;
        }
        // check overflow
        if(str.length()>10){
            if(negative) return Integer.MIN_VALUE;
            if(!negative) return Integer.MAX_VALUE;
        }else if(str.length() == 10){
            if(negative && 
                str.compareTo("2147483648")>0) return Integer.MIN_VALUE;
            if(!negative  &&
                str.compareTo(Integer.toString(Integer.MAX_VALUE))>0) return Integer.MAX_VALUE;
        }
        if(negative) {
            str = "-" + str ;
        }
        ret = Integer.parseInt(str);
    }
    }
        return ret;
    }
}
=======================================
时间复杂度  n
空间复杂度 1

LeetCode 刷题第一阶段 ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

第一个考虑的问题是如果 nRows 比 input长度还小怎么办 (极端情况是负数)。保险起见还是先check condition.
总体思路的话， 我用了两个Int 当指针。 一个指示正常规律的跳跃一个指示zigzag。 设置了一个常数代表跳跃变量。 注意的问题是当跳跃变量等于0时容易死循环。。。
CODE:
public class Solution {
    public String convert(String s, int numRows) {
        String ret = "" ;
        int len = s.length() ;
        int c = 2 * numRows - 2 ; 
        
        if(c != 0 && 0 < numRows && numRows < len){
            
        for(int i = 0; i < numRows ; i++){
            ret += s.charAt(i);
            int index = i + c ;
            int zig =  c - i ;
            while(index < len || zig < len){
            if(i != 0 && i != (numRows -1)){
                ret += s.charAt(zig);
            }
            if(index < len) ret += s.charAt(index);
            zig += c ;
            index += c ;
            }
        }
        
        } else{
            ret = s;
        }
        
        return ret;
    }

}

LeetCode 刷题第一阶段 Inverse Integer

之前混乱地刷了一些 LeetCode 的题目， 经大神提点，现今决定进入系统刷题。第一阶段是 自主快速刷完所有easy难度的题。之后的阶段求最优解加上进阶medium, hard。


2016. 3. 19
inverse integer:

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

consideration:

思路比较简单直接，但是博主考虑到restore x 的问题， 然而网上大家都没有考虑相应问题， 题目也没有要求restore 故此处不管。 具体面试的时候可以问考官。

***** 但是要考虑overflow 问题。

The input can be in int range but the output might overflow , for example, if you input (INT_MAX-1)， the output will be out of range.

Till now, two solutions for it.

1. Change return answer to long type

2. set upper bound and lower bound to detect 

talk is cheap, show the code :

public class Solution {

    public int reverse(int x) {

        int res = 0;

        while(x != 0){

            int lastD = x % 10 ;

            int upBound = (Integer.MAX_VALUE - lastD) / 10 ;

            int loBound = (Integer.MIN_VALUE - lastD) / 10 ;

            

            if (x>0 && res > upBound) return 0;

            if (x<0 && res < loBound) return 0;

            x = x / 10 ;

            res = res * 10 + lastD ; 

        }

      

        return res;

    }

}

btw 这题也可以用recursion 做 就不写了这次。 因为overflow问题 耽误时间较长希望下次改进。