173. Binary Search Tree Iterator ---M

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.

 

Example:

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

 

Note:

• next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
• You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

A:

就是简单的用stack来记录当前的path.
思想跟iterative in-order traversal类似。   但这里，多了一个性质，就是该树是BST (但是题目里面没有用到)。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        TreeNode* ptr = root;
        while(ptr){
            myStack.push(ptr);
            ptr= ptr->left;
        }
    }
    
    /** @return the next smallest number */
    int next() {
        auto res = myStack.top();
        myStack.pop();
        TreeNode * ptr = res->right;
        while(ptr){
            myStack.push(ptr);
            ptr= ptr->left;
        }
        return res->val;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return not myStack.empty();
    }
private:
    stack<TreeNode*> myStack;
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

Mistakes:
1：  恩，错误是  致命的。

        TreeNode* ptr = root;
        while(ptr){
            myStack.push(ptr);
            ptr= ptr->left;
        }

   我写成了 

        TreeNode* ptr = root;
        while(ptr){
            myStack.push(ptr);

            if(ptr->left)
                ptr= ptr->left;
        }

造成了死循环

Factorial Trailing Zeroes

Q:

Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.

 A:

public class Solution {
    public int trailingZeroes(int n) {
        return n<5?0:(n/5+ trailingZeroes(n/5));
    }
}

 Mistakes:
 1:  开始想错了。不是 先找5 的个数，再找 10 的倍数。  这样是不对的。
   要找的是 5 的倍数， 25的倍数。 和5^k  的倍数

171. Excel Sheet Column Number

Q:
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 

A:

public class Solution {
    public int titleToNumber(String s) {
        if(s.length()==0)
            return 0;
        return (1+ s.charAt(s.length()-1)-'A') + titleToNumber(s.substring(0,s.length()-1))*26;
    }
}

Mistakes:

Majority Element

Q:
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.

A:
就是每次dump两个不同的数字。

public class Solution {
    public int majorityElement(int[] num) {
        int a = num[0], aCount = 1; // first let b point to a value NOT a
        for(int i = 1;i<num.length;i++){
            if(num[i]==a){
                aCount++;
            }else{ // if these two are not equal
                aCount--;
                if(aCount==0){
                    i++;
                    a=num[i]; // because it must exist, so num[i] is within range
                    aCount=1;
                }
            }
        }
        return a;
    }
}

用两个地址，记录不同的位置

public class Solution {
    public int majorityElement(int[] nums) {
        int i1= 0;
        for(int i2=0; i2 < nums.length;i2++){
            if(nums[i2] != nums[i1]){
                int val = nums[i1];
                i1++;
                // i1 till not equal
                while(i1<= i2 && nums[i1] != val){
                    i1++;
                }
            }
        }
        return nums[i1];
    }
}

Mistakes：

168. Excel Sheet Column Title

Q:
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 

A:

public class Solution {
    public String convertToTitle(int n) {
        String result = "";
        while(n>0){
            int value = n % 26;
            if(value ==0){
                value = 26;
            }
            result = (char)('A'+value-1)+result;
            n = (n-value) / 26;
        }
        return result;
    }
}

Mistakes:
1: 应该是 (n+1)%26.  而非 n%26+1       自己想想为什么
2：  n%26 + 'A' 的结果是个int
      ‘A’ + n%26   的结果是????? 也TMD是int
3：  简单的拍脑门是不行的。
      肯定会出错，  例如 input == 26的时候，
不能简单的做除法。而应该是先减法，减去刚刚用过的部分，（为什么？因为我们前面不是简单的 求模运算，还对模==0的情况，做了特别处理  ！！！！！！！！！

public class Solution {
    public String convertToTitle(int n) {
        if(n<=26){
            return ""+(char)('A'+n-1);
        }else{
            return convertToTitle( (n-1)/26 ) + convertToTitle( (n-1) %26 +1 );
        }
    }
}
 

166. Fraction to Recurring Decimal -M !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

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.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 2, denominator = 3
Output: "0.(6)"

A:
思路很简单，就是挨个 乘呗。每次都乘以10

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {        
        long a = numerator;
        long b = denominator;
        if( b == 0)
            throw std::invalid_argument( "demoninator cannot be zero");
        string sign = "";
        if(  (a < 0 and b >0 ) || (a > 0 and b < 0))
            sign = "-";
        a = abs(a);
        b = abs(b);
        string res = sign + to_string(a /b);
        
        long rem = a % b;
        if(rem ==0)
            return res;
        else
            return res+"." + helper(rem, b);
    }
private:
    string helper(long a, long b)
    {    
        unordered_map<long, int> M; // value to index
        vector<char> res;
        int index = 0;
        while(a != 0 && M.find(a) == M.end())
        {
            M[a]=index++;
            char v = '0'+(a*10 / b);
            res.push_back(v);
            a = a*10 % b;
        }
        if(a!=0) // we found loop
        {
            res.insert(res.begin() + M[a], '(');
            res.push_back(')');
        }
        string ss(res.begin(), res.end());
        return ss;
    }
};

Mistakes:
1： 不能简单的，假设a / b的整数结果就可以处理符号问题。
  如果是   -7 / 12 整数位是0 ，没有负号。  因此要单独处理

2: 考虑到负数的范围更大，因此考虑都转换成负数 
Line 7: Char 22: runtime error: signed integer overflow: -1 * -2147483648 cannot be represented in type 'int' (solution.cpp)

long b = abs(denominator);   这样也是不对的。 因为会默认先转成int 类型的正数。
Line 10: Char 21: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself (solution.cpp)

3: 别傻了， 老老实实转换成 double类型， 别非想着用int， 否则 *10之后，可能会溢出的

160. Intersection of Two Linked Lists (easy)

Q:

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory. 

A:
就是先找到相同长度的位置。再逐一对比。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int n1 = getLength(headA);
        int n2 = getLength(headB);        
        if(n1-n2>0){
            for(int i =0;i<n1-n2;++i){
                headA = headA->next;
            }
        }else{
            for(int i =0;i<n2-n1;++i){
                headB = headB->next;
            }
        }
        while(headA != headB){
            headA = headA->next;
            headB = headB->next;
        }
        return headA;
    }
private:
    int getLength(ListNode *head){
        int res = 0;
        while(head){
            head=head->next;
            res++;
        }
        return res;
    }
};

********************round 2 ********two pointer *****

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA = headA;
        ListNode *curB = headB;
        if (!headA || !headB) 
            return NULL;
        while (curA != curB)
        {
            curA = curA? curA->next:headB;
            curB = curB? curB->next:headA;
        }
        return curA;
    }
};

Two Pointers

• Maintain two pointers $pA$ and $pB$ initialized at the head of A and B, respectively. Then let them both traverse through the lists, one node at a time.
• When $pA$ reaches the end of a list, then redirect it to the head of B (yes, B, that's right.); similarly when $pB$ reaches the end of a list, redirect it the head of A.
• If at any point $pA$ meets $pB$, then $pA$/$pB$ is the intersection node.
• To see why the above trick would work, consider the following two lists: A = {1,3,5,7,9,11} and B = {2,4,9,11}, which are intersected at node '9'. Since B.length (=4) < A.length (=6), $pB$ would reach the end of the merged list first, because $pB$ traverses exactly 2 nodes less than $pA$ does. By redirecting $pB$ to head A, and $pA$ to head B, we now ask $pB$ to travel exactly 2 more nodes than $pA$ would. So in the second iteration, they are guaranteed to reach the intersection node at the same time.
• If two lists have intersection, then their last nodes must be the same one. So when $pA$/$pB$ reaches the end of a list, record the last element of A/B respectively. If the two last elements are not the same one, then the two lists have no intersections.

Complexity Analysis

• Time complexity : $O(m+n)$.
• Space complexity : $O(1)$.

Mistakes:

        while(head){

这里 一开始写成了   !head   

Compare Version Numbers

Q:
Compare two version numbers version1 and version1.
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

A:
思路就是一个个取出来比较。

public class Solution {
    public int compareVersion(String version1, String version2) {
        version1=version1.trim();
        version2 = version2.trim();
        if(version1.length()==0)
            return version2.length()==0?0:(isZero(version2)?0:-1);
        if(version2.length()==0)
            return version1.length()==0?0:(isZero(version1)?0:1);
        
        int i1 = version1.indexOf('.'), i2 = version2.indexOf('.');
        int n1,n2;
        
        if(i1 == -1){
            n1 = Integer.parseInt(version1);
            version1 = "";
        }else{
            n1 = Integer.parseInt(version1.substring(0,i1));
            version1 = version1.substring(i1+1);
        }
        
        if(i2 == -1){
            n2 = Integer.parseInt(version2);
            version2 = "";
        }else{
            n2 = Integer.parseInt(version2.substring(0,i2));
            version2 = version2.substring(i2+1);
        }
        return n1==n2?compareVersion(version1,version2):(n1>n2?1:-1);
    }
    public boolean isZero(String str){
        if(str.length()==0)
            return true;
            
        char ch = str.charAt(0);
        if(ch =='0' || ch=='.')
            return isZero(str.substring(1));
        else
            return false;
    }
}

Mistakes:
没考虑这种情况：
1：   1.0   和  1
2：   1.000.00 和 1

-----------第二遍-----犯了同样的错误-----------------

public class Solution {
    public int compareVersion(String version1, String version2) {
        List<Integer> l1 = new LinkedList<>(), l2 = new LinkedList<>();
        for(String ss: version1.split("\\.")) 
            l1.add(Integer.parseInt(ss));
        for(String ss : version2.split("\\."))
            l2.add(Integer.parseInt(ss));
        int m = l1.size(), n = l2.size();
        for(int i =0;i< Math.max(m,n);i++){
            int a =i>=m?0:l1.get(i), b = i>=n?0:l2.get(i);
            if(a>b)
                return 1;
            else if(a<b)
                return -1;
        }
        return 0;
    }
}