leetcode Question: Majority Element

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

Analysis:


This a simple question that hashmap (dict) is all we need.
Construct a hashmap that the key is each element in the num, the value is the occurrence of num.
Check the value while constructing the map can get the result.

Code(C++):

class Solution {
public:
    int majorityElement(vector<int> &num) {
        map<int,int> mp;
        for (int i=0;i<num.size();i++){
            if (mp.find(num[i]) == mp.end()){
                mp[num[i]] = 1;
            }else{
                mp[num[i]] += 1;
            }
            if (mp[num[i]] > num.size()/2){
                return num[i];
            }
        }
    }
};

Code(Python):

class Solution:
    # @param num, a list of integers
    # @return an integer
    def majorityElement(self, num):
        dict = {}
        for n in num:
            dict[n] = dict.get(n,0) +1
            if dict[n] > len(num)/2:
                return n


leetcode Question: Fraction to Recurring Decimal

Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,


  • Given numerator = 1, denominator = 2, return "0.5".
  • Given numerator = 2, denominator = 1, return "2".
  • Given numerator = 2, denominator = 3, return "0.(6)".

Analysis:

This problem needs a little bit of thinking, but it's not difficult to handle. The key idea is not about programming, but the procedure of division.

For example, lets do 4/7, a table can be easily computed as follows:

dividend   divisor   quotient  remainder
     4               7            0               4
-----------------------------------------------
    40              7            5               5
    50              7            7               1
    10              7            1               3
    30              7            4               2
    20              7            2               6
    60              7            8               4
    40              7            5               5  

From the table we can see that, the quotient are the result:   0. (571428).
Why the computation stops?  Because the remainder occurred in previous steps.
How to get the new dividend?  10 times the remainder in previous round.

I think it is now pretty clear how to do the programming part.

Note that
(1) We need to handle the negative number(s).
(2) The remainders is better to save in a list (array, vector), but not a string.

Python code below is more clear and easy to understand the procedure of this algorithm.

Code(C++):

class Solution {
public:
    string num2str(long a){
        if (a<0){a = -a;}
        ostringstream os;
        os << a;
        return os.str();
    }
    
    
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0 || denominator == 0){
            return "0";
        }
        bool pos=true;
        if ((numerator<0 && denominator>0)||(numerator>0 && denominator<0)){
            pos = false;
        }
        
        long numer = abs(numerator);
        long denom = abs(denominator);
        
        int l = -1;
        vector<string> res;
        int maxlen = 1000;
        vector<string> mod;
        
        while (mod.size()<maxlen){
            res.push_back(num2str(numer / denom));
            long m = numer % denom;
            if (m == 0){
                break;
            }
            
            for (int i=0;i<mod.size();i++){
                if (mod[i] == num2str(m)){
                    l = i;
                    break;
                }
            }
   
            if (l == -1){
                mod.push_back(num2str(m));
                numer = m * 10;
            }else{
                break;
            }
        }
        
        
        string r = "";
        
        if (res.size()==1){
            r = res[0];
        }else{
            r=res[0]+".";
            for (int i=1;i<res.size();i++){
                if (i == l+1){
                    r += "(";
                }
                r += res[i];
            }
            if (l != -1){
                r += ")";
            }
        }
        
        
        if (pos) {
            return r;
        }else{
            return "-"+r;
        }
    }
};

Code(Python):

class Solution:
    # @return a string
    def fractionToDecimal(self, numerator, denominator):
        if numerator * denominator < 0:
            pos = False
        else:
            pos = True
        numerator = abs(numerator)
        denominator = abs(denominator)
        
        maxlen=1000
        mod = []
        if numerator == 0 or denominator == 0:
            return "0"
        res = []
        l = -1
        while len(mod) < maxlen:
            res.append(numerator/denominator)
            m = numerator % denominator
            if m == 0:
                break
            if m in mod:
                l = mod.index(m)
                break
            else:
                mod.append(m)
                numerator = m * 10
        
        if len(res) == 1:
            s = str(res[0])
        else:
            s = str(res[0]) + "."
            if l == -1:
                s = s + "".join([str(n) for n in res[1::]] )
            else:
                s = s+ "".join([str(n) for n in res[1:l+1]]) + "(" + "".join([str(n) for n in res[l+1::]]) + ")"
        if pos:
            return s
        else:
            return "-"+s
        


leetcode Question: Largest Number

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.

Analysis:


The key to this question is  ---- Don't think it too complicated.
No recursion, no DP, no complicated sorting is needed.

Let's look at the question in this way:
(1) All the numbers are used. (No need to choose)
(2) Order of the numbers is important. (May use sorting algorithm)
(3) How to determine the order of  like 30 and 3?   3>30? 3< 30?

So it is natural to think that sorting is all we need. If I can get the sorted list of numbers, the last step is just concatenate them and output as a string.

Sort can be done by calling library functions (e.g., c++ sort(a.begin(), a.end(), _comp), python sorted(a, comp)), where we need to define the compare function.  Note that in c++,  _comp in sort function need to be static.  

How to define the compare function?
1. Consider two int, a and b.  e.g., 34 and 3.
2. Actually, what we need to compare is not 34 and 3, but  3 43 and 3 34. 
3. If 343 > 334, then 34 should have higher order than 3, and vice versa.


In my code, the int are converted into string in case of long length. In c++, stringstream is a good way to do so.

Note:
(1) In c++, comp function must be static and it returns true and false.
(2) In python, comp function must return positive , 0 and negative numbers to represent greater, equal and smaller.  (see note 8 in here)
(3) In sort function, ascending order is the default. So in my code I change the order in comp function so that the output is descending order.
(4) String compare, either in C++ or Python, is comparing each char from the start. And if the compared string is shorter, it will return "smaller"




Code(C++):

class Solution {
public:
    static bool _comp(int a, int b){
        ostringstream ss;
        ss << a;
        string sa = ss.str();
        ss.clear();
        ss << b;
        string sb = ss.str();
        ss.clear();
        
        sa = sa + sb;
        sb = sb + sa;
        
        if (sa.compare(sb) >=0){
            return true;
        }else{
            return false;
        }
    }

    string num2str(int i){
        ostringstream ss;
        ss << i;
        return ss.str();
    }
    
    string largestNumber(vector<int> &num) {
        
        string res="";
        
        sort(num.begin(),num.end(), _comp);
        
        if (num[0]==0){return "0";}
        
        for(int i=0;i<num.size();i++){
            res = res+ num2str(num[i]);
        }
        
        return res;
    }
};

Code(Python):

class Solution:
    # @param num, a list of integers
    # @return a string
    def largestNumber(self, num):
        def my_cmp(x,y):
            sx = str(x)
            sy = str(y)
            sx = sx + sy
            sy = sy + sx
            if sx > sy:
                return -1
            if sx == sy:
                return 0
            if sx < sy:
                return 1
           
        num = sorted(num, cmp=my_cmp)
        
        if num[0] == 0:
            return "0"
        else:
            return "".join([str(n) for n in num])
        
        

leetcode Question: Binary Search Tree Iterator

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.

Analysis

So this problem is a little tricky if you do not familar with recursion and stack. I had an answer using recursion until recently I tried to solve this problem again by using a stack. The advantage of using a stack is making the solution pretty neat and clean. However, the disadvantage now becomes of how could we get the idea of such solution.

Firstly, let's review the basic concept of binary search tree. In short, the binary search tree is an binary tree with order, by traverse the whole tree, you will get the nodes in order. The traversal is defined how you search the tree, here in BST, we could just use the pre-order traversal. The figure below illustrates a BST and its traversal procedure.

For this specific problem, note that, the starting node for the iterator may NOT be the root node! Yes, although it is initialized from the root node, actually the starting node should be the node with smallest value (it's possible the smallest node is the root.) So what is the smallest node in the BST, it is the left-most node.

Secondly, I draw the firgure to show how the preorder traversal is done in recursion way. Specifically, in each recursion, we have 3 steps, (1) search the left node, (2)print the value, and (3) search the right node. In the figure, I show the current value and all 3 steps in blue color, this is what actually is stored in the function stack. The green arrow is our function call each time, while the organe arrow is the recursion. The red arrow and number is getting the node value.

From the figure we can see that, the whole procedue acts like the following way:

  1. keep searching the left node.
  2. if there is no left node OR the left node has already been visited, we do the following steps:
    1. pop/print the current node
    2. keep searching the right node

If we tried to simulate the function stack using a regular stack, we could see from the figure that, green arrow acts like the push to stack operation, and red arrow acts like the pop operation. The property of stack itself servers the orange arrow.

Notice that, now the top element of stack is alway the smallest node. Every time we pop the top node, at the same time we push the right child and all its left children. Because for each node, the next node in its preorder traversal will be only two cases:

  1. The left-most node of its right child (if current node has right child)
  2. It current node doese have right child. Then search up to its parent, until the parent node has right child. The left-most node of that right child is the next node we want.

The above two steps becomes quite easy if we are using a stack. The first step in stack is just pushing nodes into stack, while the second step could be viewed as the following steps in stack:

  1. If current node has right child, we keep pushing the left child of that node (include the right child itself).
  2. If there is no right child, we do nothing. The top node in the stack is what we want. Why? because once we visited the node, we pop it form the stack, so all the previous nodes are no longer existed in the stack.

In this way, we could design the iterator very easily, as the following code:

Code (C++):

/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
st = stack<TreeNode*>();
push_left_node(st, root);
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !st.empty();
}
/** @return the next smallest number */
int next() {
TreeNode* tmp = st.top();
st.pop();
push_left_node(st, tmp->right);
return tmp->val;
}
private:
stack<TreeNode*> st;
void push_left_node(stack<TreeNode*>& st, TreeNode* root){
while (root != NULL){
st.push(root);
root = root->left;
}
}
};
/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

Code (Python):

# Definition for a binary tree node
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
self.st = []
self.push_left(root)
def hasNext(self):
"""
:rtype: bool
"""
return len(self.st)!=0
def next(self):
"""
:rtype: int
"""
tmp = self.st.pop(0)
self.push_left(tmp.right)
return tmp.val
def push_left(self, root):
while root:
self.st.insert(0, root)
root = root.left
# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())

leetcode Question: Compare Version Numbers

 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.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.
Here is an example of version numbers ordering:
0.1 < 1.1 < 1.2 < 13.37

Analysis:

This question is to test the skills of string to int and int to string convention.
In C++, parsing string (e.g., parse string according to ' , ') as well as int to string operation can be done using the stringstream.  In python, it is much easier since we have int() and str() methods to do so.

The idea of this problem could be considered to compare two list of numbers that are separated by '.' Note that when comparing list with different length, if they are the same for the 1st part, if the longer list have all 0s in its tail, then those two lists are the same. E.g.,    1.0.000.0 and 1, two lists generated are [1,0,0,0], and [1]. And it is necessary to check "all" digits instead of checking only the "next" digits because if there exists one digit that is not 0, the two numbers are not equal.  




Code(C++):

class Solution {
public:
    int compareVersion(string version1, string version2) {
        istringstream st1(version1);
        istringstream st2(version2);
        string token;
        vector<int> d1;
        vector<int> d2;
        while (getline(st1,token,'.')){
            stringstream os1;
            os1.str(token);
            int tmp;
            os1 >> tmp;
            d1.push_back(tmp);
        }
        while (getline(st2,token,'.')){
            stringstream os2;
            os2<<token;
            int tmp;
            os2 >> tmp;
            d2.push_back(tmp);
        }
        
        int n1 = d1.size();
        int n2 = d2.size();
        
        for (int i=0;i<min(n1,n2);i++){
            if (d1[i]>d2[i]){ return 1;}
            if (d1[i]<d2[i]){ return -1;}
        }
        
        if (n1<n2){
            for (int i=n1;i<n2;i++){
                if (d2[i]!=0){return -1;}
            }
            return 0;
        }
        if (n1>n2){
            for (int i=n2;i<n1;i++){
                if (d1[i]!=0){return 1;}
            }
            return 0;
        }
        if (n1==n2){return 0;}
    }
};

Code(Python):

class Solution:
    # @param version1, a string
    # @param version2, a string
    # @return an integer
    def compareVersion(self, version1, version2):
        l1 = version1.split('.')
        l2 = version2.split('.')
        for i in range(min(len(l1),len(l2))):
            if int(l1[i]) > int(l2[i]):
                return 1
            if int(l1[i]) < int(l2[i]):
                return -1
                
        if len(l1)<len(l2):
            if all( int(n)==0 for n in l2[len(l1)::]):
                return 0
            else:
                return -1
            
        if len(l1)>len(l2):
            if all( int(n) == 0 for n in l1[len(l2)::]):
                return 0
            else:
                return 1
                
        if len(l2) == len(l2):
            return 0

leetcode Question: Repeated DNA Sequences

Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example,
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Analysis:

This problem is straightforward (no need to think about KMP algorithm), only dictionary (hashmap) can pass the OJ.
Since there are many restrictions in this problem, it becomes much easier. E.g., only four chars are occurred in the sequence (A,T,C,and G), only length-10 substr is needed.
So the algorithm goes as follows:
1. Search from the start of the string, get every substr with length 10.
2. Construct and look up a hashmap, add 1 to the value.
3. After the whole search, check every entry in the hashmap, if the value is greater than 1, output.

Note that in the C++ OJ, when using string as the map key, the will cause an memory exceeded error. So, I map the string to long int, which is used as the key. Results are mapped back to string and output.


Code(C++):

class Solution {
public:
    long str2long(string s){
        long res = 0;
        for (int i=0;i<10;i++){
            if (s[i] == 'A'){res = res*10 + 1;}
            if (s[i] == 'T'){res = res*10 + 2;}
            if (s[i] == 'C'){res = res*10 + 3;}
            if (s[i] == 'G'){res = res*10 + 4;}
        }
        return res;
    }
    string long2str(long s){
        string res = "";
        for (int i=0;i<10;i++){
            int d = s%10;
            if (d == 1) {res= "A" + res;}
            if (d == 2) {res= "T" + res;}
            if (d == 3) {res= "C" + res;}
            if (d == 4) {res= "G" + res;}
            s = s /10;
        }
        return res;
    }
    vector<string> findRepeatedDnaSequences(string s) {
        int n = s.size();
        map<long, int> d;
        vector<string> res;
        for (int i=0;i<n-9;i++){
            string sub = s.substr(i,10);
            long idx = str2long(sub);
            if (d.find(idx) == d.end()){
                d[idx] = 0;
            }else{
                d[idx] = d[idx] + 1;
            }
        }
        for (auto it= d.begin();it!=d.end();it++){
            if (it->second >= 1){
                res.push_back(long2str(it->first));
            }
        }
        return res;
        
    }
};

Code(Python):

class Solution:
    # @param s, a string
    # @return a list of strings
    def findRepeatedDnaSequences(self, s):
        n = len(s)
        d = {}
        res = []
        for i in range(n):
            substr = s[i:i+10]
            d[substr] = d.get(substr,0) + 1
        for key, val in d.items():
            if val > 1:
                res.append(key)
        return res
        


leetcode Question: Rotate Array

Rotate Array

Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Hint:
Could you do it in-place with O(1) extra space?

Analysis:

1st solution is to use a temp array.  Space O(n).

e.g. nums = [ 1 2 3 4 5 ], k=2
temp = [4 5 1 2 3]
num = temp


2nd solution is to rotate one position each time and do it k times. Space O(1), but it will exceed the time limit.
e.g. nums = [1 2 3 4 5], k=2
1st iteration:
      nums = [1 1 2 3 4] temp = 5, then nums = [5 1 2 3 4]
2nd iteration:
      nums = [5 5 1 2 3] temp = 4, nums = [4 5 1 2 3]



3rd solution is to rotate k steps once for an element. Space O(1).
e.g. nums = [1 2 3 4 5 6], k=2
1st iteration: starts from nums[i=0], keep rotate nums[i+k] until meet the start position
      nums = [5 2 1 4 3 6]
2nd iteration: starts from nums[i=1]
      nums = [5 6 1 2 3 4]

How to determine the number of iterations?
Use the gcd (greatest common divisor) between n and k. Because we need to find how many "circles" are there in the sequence, one circle is like counting each element nums[i] + k + k + k... and back to nums[i]. If the gcd is 1, which means only one circle will cover all the elements in the sequence, so only 1 iteration is needed.If the gcd is 2, there are 2 circles, so 2 iterations are needed.






Code(C++):

class Solution {
public:
    int gcd(int a, int b){
        if (b==0){
            return a;
        }else{
            return gcd(b, a%b);
        }
    }
    
    void rotate(int nums[], int n, int k) {
        int i,j,tmp,pre;
        k = k%n;
        for (int i=0;i<gcd(n,k);i++){
            pre = nums[i];
            j=i;
            while ((j+k)%n != i){
                tmp = nums[(j+k)%n];
                nums[(j+k)%n] = pre;
                pre = tmp;
                j = (j+k)%n;
            }
            nums[(j+k)%n] = pre;
        }
        
    }
};


Code(Python):

class Solution:
    # @param nums, a list of integer
    # @param k, num of steps
    # @return nothing, please modify the nums list in-place.
    def rotate(self, nums, k):
        
        def gcd(a,b):
            if b==0:
                return a
            else:
                return gcd(b, a%b)
        
        n = len(nums)
        for i in range(gcd(n,k)):
            pre = nums[i]
            j = i
            while (j+k)%n != i:
                nums[(j+k)%n], pre = pre, nums[(j+k)%n]
                j = (j+k)%n
            nums[(j+k)%n] = pre