Reverse a singly linked list.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Subscribe to see which companies asked this question. Continue reading →

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?

Write a bash script to calculate the frequency of each word in a text file words.txt.

For simplicity sake, you may assume:

• words.txt contains only lowercase characters and space ' ' characters.

• Each word must consist of lowercase characters only.

• Words are separated by one or more whitespace characters.

Continue reading →

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

这题看起来不难，但居然做了我两个小时。其中还是有很多值得注意一下的地方的。

def convertToTitle2(n):
    ret = ""
    while(n):
        ret = chr( (n-1)%26 + 65 ) + ret
        n = (n-1)/26 #核心
    return ret

先贴一下最后AC的代码。我之前用了很长的代码去判断字符进位的情况，但效果都不理想。

Given an integer, write a function to determine if it is a power of three.

class Solution(object):
    def isPowerOfThree(self, n):
        #while (n and (n % 3 == 0)):
            #n = n / 3
        #return n == 1
        
        
        #return (n > 0 and 1162261467 % n == 0)
        
        return (n > 0 and int(math.log10(n) / math.log10(3)) - math.log10(n) / math.log10(3) == 0)

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root)
    {
        if(root == NULL)
            return 0;  
        int res = 1;  
        int l = maxDepth(root->left);  
        int r = maxDepth(root->right);  
        return l > r? l + 1:r+ 1;  
    }
};

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

class Solution {
public:
    bool containsDuplicate(vector<int>& nums)
    {
        if(nums.empty())
            return false;
            
        set<int> s;
        vector<int>::iterator itr = nums.begin();
        
        while(itr != nums.end())
        {
            if(s.count(*itr) == 1)
                return true;
            s.insert(*itr);
            itr++;
        }
        return false;
    }
};

Given an integer, write a function to determine if it is a power of two.

class Solution(object):
    def isPowerOfTwo(self, n):
        while (n and (n % 2 == 0)):
            n = n / 2
            
        return n == 1
        
        #Certainly,you can also use the following method
        #return (n and (n&(n-1))) == 0

Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.
Note that 1 is typically treated as an ugly number.

class Solution(object):
    def isUgly(self, number):
        if number == 1:
            return True
        if number == 0:
            return False
        
        while(number % 2 == 0):
            number /= 2
        while(number % 3 == 0):
            number /= 3
        while(number % 5 == 0):
            number /= 5
    
        return number == 1

Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number.

class Solution(object):
    def min_three(self, a, b, c):
        minNum = min(a,b)
        return min(minNum,c)
    def nthUglyNumber(self, n):
        ugly = [1]
        factor2 = 2
        factor3 = 3
        factor5 = 5
        index2 = index3 = index5 = 0
        for i in range(1,n):
            minNum = min(factor2, factor3, factor5)
            ugly.append(minNum)
            if(factor2 == minNum):
                factor2 = 2 * ugly[index2+1]
                index2 += 1
            if(factor3 == minNum):
                factor3 = 3 * ugly[index3+1]
                index3 += 1
            if(factor5 == minNum):
                factor5 = 5 * ugly[index5+1]
                index5 += 1
        return ugly[n-1]