Daily Temperatures

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Solution:
This quiz is a classical application of the stack data structure. Here we can store indexes of each element which is waiting a bigger element in a stack, and calculate the difference between the current index and stored indexes when the current element is bigger than previous elements. The while loop part is really elegant and tricky, in which judging whether the stack is empty and comparing elements.

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        ans = [0] * len(T)

        stk = list()

        for c_index, value in enumerate(T):
            while stk and T[stk[-1]] < value:
                p_index = stk.pop()
                ans[p_index] = c_index - p_index
            stk.append(c_index)

        return ans

Compare Version Numbers

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences. Continue reading

Word Frequency

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

Excel Sheet Column Title

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的代码。我之前用了很长的代码去判断字符进位的情况,但效果都不理想。

Power of Three

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)

Maximum Depth of Binary Tree

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;  
    }
};

Contains Duplicate

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;
    }
};

Power of two

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