173. Binary Search Tree Iterator ---M

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

• BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
• boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
• int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

 

Example 1:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

 

Constraints:

• The number of nodes in the tree is in the range [1, 105].
• 0 <= Node.val <= 106
• At most 105 calls will be made to hasNext, and next.

 

Follow up:

• Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?

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) {
        while(root){
            S.push(root);
            root = root->left;
        }
    }
    
    int next() {
        auto res = S.top();
        S.pop();
        auto runner = res->right;
        while(runner){
            S.push(runner);
            runner = runner->left;
        }
        return res->val;
    }
    
    bool hasNext() {
        return not S.empty();
    }
private:
    stack<TreeNode*> S;
};
/**
 * 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:

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

• intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
• listA - The first linked list.
• listB - The second linked list.
• skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
• skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

 

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

 

Constraints:

• The number of nodes of listA is in the m.
• The number of nodes of listB is in the n.
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• intersectVal is 0 if listA and listB do not intersect.
• intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

 

Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?

A:

Sol 1:  Hash Set

/**

* 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) {

unordered_set<ListNode*> S;

ListNode* tail = headA;

while (tail) {

S.insert(tail);

tail = tail->next;

}

tail = headB;

while (tail) {

if (S.find(tail) != S.end()) {

return tail;

}

tail = tail->next;

}

return nullptr;

}

};

Sol 2:   先找到相同长度的位置。再逐一对比。

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