LeetCode: Excel Sheet Column Title

Question:

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

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

Thoughts:

Covert decimal number to 26th numeral system number.

Key point need to consider:

• If given number is a a multiple of 26, then
  • modResult = modResult + 1
  • quotient = quotient – 1

public class Solution {
    public String convertToTitle(int n) {
        //remove edge case
        if (n < 1) {
            return "";
        }
        
        //use a string buffer to build final result
        StringBuffer sb = new StringBuffer();
        while (n != 0) {
            int digit = n % 26;
            n = n / 26;
            
            //key point need to consider
            if (digit == 0) {
                digit = 26;
                n -= 1;
            }
            
            digit -= 1;
            char c = (char) (digit + 'A');
            sb.append(c);
        }
        
        //because StringBuffer is built in reverse order
        //so reverse it to correct order
        sb.reverse();
        return new String(sb);
    }
}

Climbing Staris

Question:

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Thoughts:

This problem is solving a Fibonacci Sequence, find the n-th element value in a Fibonacci sequence.

Recursion is prohibited in this question, it does not meet the time limit.

Running Time: O(n)

public class Solution {
    public int climbStairs(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        
        int a = 1;
        int b = 2;
        int c = 0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        
        return c;
    }
}

Leetcode: Evaluate Reverse Polish Notation

Question:

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Thoughts:

A stack is needed to record operands and sub-results of the reverse polish notation

Scan the given postfix expression from left to right
for each symbol
 {
  if operand then
    push onto stack
  if operator then
   {
    operand1=pop stack
    operand2=pop stack
    compute operand1 operator operand2
    push result onto stack
   }
 }
return top of stack as result

If the question asks to evaluate a polish notation(prefix notation), do the same process as the post-fix expression, but scan the expression from right to left.

public class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens.length <= 0) {
            return 0;
        }
        
        LinkedList<String> stack = new LinkedList<String>();
        String operators = "+-*/";
        for (String s : tokens) {
            if (!operators.contains(s)) {
                stack.push(s);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                
                if (s.equals("+")) stack.push(new Integer(num1 + num2).toString());
                else if (s.equals("-")) stack.push(new Integer(num2 - num1).toString());
                else if (s.equals("*")) stack.push(new Integer(num1 * num2).toString());
                else if (s.equals("/")) stack.push(new Integer(num2 / num1).toString());
            }
        }
        
        return Integer.parseInt(stack.pop());
    }
}

LeetCode: Factorial Trailing Zeroes

Question:

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Reference:

http://blog.csdn.net/chenlei0630/article/details/42271019

http://bookshadow.com/weblog/2014/12/30/leetcode-factorial-trailing-zeroes/

Thoughts:

感谢 在线疯狂 博主的解释，此题只需要计算 n 中包含多少个5就可以了。

public class Solution {
    public int trailingZeroes(int n) {
        int num = 0;
        while (n > 0) {
            n = n / 5;
            num += n;
        }
        return num;
    }
}

Leetcode: Excel Sheet Column Number

Question:

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

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Thoughts:

这道题就是计算 二十六进制转十进制的问题，题目很简单，轻松搞定。

public class Solution {
    public int titleToNumber(String s) {
        int num = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            int d = c - 'A' + 1;
            int j = s.length() - 1 - i;
            while (j > 0) {
                d *= 26;
                j--;
            }
            num += d;
        }
        
        return num;
    }
}

LeetCode: Add Binary

Question:

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Difficulty: ★★

Key Word: iteration

LeetCode: Integer to Roman

Question:

Given an integer, convert it to a roman numeral.

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

LeetCode: Roman To Integer

Question:

Given a roman numeral, convert it to an integer.

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

LeetCode: Palindrome Number

Question:

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

LeetCode: String to Integer (atoi)

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.