/**
 * 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) {
        if (headA == NULL || headB == NULL) return NULL;
        int lengthA = 0;
        int lengthB = 0;
        ListNode* traverseA = headA;
        ListNode* traverseB = headB;
        while(traverseA != NULL) {
            traverseA = traverseA->next;
            lengthA += 1;
        }
        while(traverseB != NULL) {
            traverseB = traverseB->next;
            lengthB += 1;
        }
        if (lengthA > lengthB) {
            int gap = lengthA - lengthB;
            while(gap > 0) {
                headA = headA->next;
                gap -= 1;
            }
        }else {
            int gap = lengthB - lengthA;
            while(gap > 0) {
                headB = headB->next;
                gap -= 1;
            }
        }
        while(headA != NULL && headB != NULL && headA != headB) {
            headA = headA->next;
            headB = headB->next;
        }
        return headA;
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int count = 0;
        int start = 0;
        int pre = nums[0];
        int index = start;
        while(count < nums.size()) {
            count += 1;
            int nextIndex = (index + k) % nums.size();
            int temp = nums[nextIndex];
            nums[nextIndex] = pre;
            pre = temp;
            index = nextIndex;
            if (index == start) {start += 1; index += 1; pre = nums[index];}
            cout << index << endl;
        }
    }
};

class Solution {
public:
    Solution(vector<int> nums) {
        current = nums;
        origin = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return origin;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        vector<int> ret;
        int size = this->origin.size();
        while(size > 0) {
            int randomIndex = rand() % size;
            ret.push_back(current[randomIndex]);
            swap(current, randomIndex, size - 1);
            size -= 1;
        }
        return ret;
    }
    
    void swap(vector<int>& vec, int left, int right) {
        int temp = vec[left];
        vec[left] = vec[right];
        vec[right] = temp;
    }
private:
    vector<int> origin;
    vector<int> current;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * vector<int> param_1 = obj.reset();
 * vector<int> param_2 = obj.shuffle();
 */

class Solution {
public:
    int calculate(string s) {
        int ret = 0;
        bool shallow = true;
        this->calculateFromIndex(s, 0, ret, shallow);
        return ret;
    }
    
    int calculateFromIndex(string& s, int index, int& ret, bool shallow) {
        int number = 0;
        while(index < s.size()) {
            while(index < s.size() && s[index] == ' ') index += 1;
            if (index == s.size()) return -1;
            
            if (s[index] >= '0' && s[index] <= '9')
                index = this->extractNumber(s, index, ret);
            else {
                //Check the operator's priority
                char currentOp = s[index];
                index += 1;
                while(s[index] == ' ') index += 1;
                int numberIndex = index;
                index = this->extractNumber(s, index, number);
                while(index < s.size() && s[index] == ' ') index += 1;
                if (index >= s.size()) {
                    ret = this->operate(ret, number, currentOp);
                    return index;
                }
                char nextOp = s[index];
                int sign = this->check(currentOp, nextOp);
                int nested = 0;
                switch (sign) {
                    case -1:
                        index = this->calculateFromIndex(s, numberIndex, nested, false);
                        ret = this->operate(ret, nested, currentOp);
                        break;
                    case 1:
                        ret = this->operate(ret, number, currentOp);
                        break;
                    case 0:
                        ret = this->operate(ret, number, currentOp);
                        if (shallow)
                            break;
                        else
                            return index;
                }   
            } 
        }
        return -1;
    }
    
    int operate (int left, int right, char op) {
        if (op == '+') return left + right;
        if (op == '-') return left - right;
        if (op == '*') return left * right;
        if (op == '/') return left / right;
    }
    
    int check(char left, char right) {
        if ( ( (left == '-' || left == '+') && (right == '+' || right == '-') ) || \
            ( (left == '*' || left == '/') && (right == '*' || right == '/') ) )
            return 1;
        
        if ( (left == '-' || left == '+') && (right == '/' || right == '*') )
            return -1;
            
        if ( (left == '*' || left == '/') && (right == '+' || right == '-') )
            return 0;
    }
    
    int extractNumber(string& s, int index, int& number) {
        number = 0;
        while (s[index] >= '0' && s[index] <= '9' && index < s.size()) {
            number = number * 10 + (s[index] - '0');
            index += 1;
        }
        return index;
    }
    
};

enum Type{
    INT,
    ADD,
    SUB,
    MUL,
    DIV
};
class Solution {
public:
    Type checkType(char ch) {
        if (ch >= '0' && ch <= '9') return INT;
        if (ch == '*') return MUL;
        if (ch == '/') return DIV;
        if (ch == '+') return ADD;
        if (ch == '-') return SUB;
    }
    int calculate(string s) {
        stack<int> numberSt;
        int index = 0;
        int ret = 0;
        while(index < s.size()) {
            while(index < s.size() && s[index] == ' ') index += 1;
            if (index == s.size()) return ret;
            Type type = this->checkType(s[index]);
            if (type != INT) index += 1;
            int nextNumber = this->extractNumber(s, index);
            int top;
            switch(type) {
                case INT:
                    numberSt.push(nextNumber);
                    break;
                case MUL:
                    top = numberSt.top();
                    numberSt.pop();
                    numberSt.push(top * nextNumber);
                    break;
                case DIV:
                    top = numberSt.top();
                    numberSt.pop();
                    numberSt.push(top / nextNumber);
                    break;
                case ADD:
                    numberSt.push(nextNumber);
                    break;
                case SUB:
                    numberSt.push(-nextNumber);
                    break;
            }
        }
        while(numberSt.size() >= 2) {
            int right = numberSt.top();
            numberSt.pop();
            int left = numberSt.top();
            numberSt.pop();
            numberSt.push(left + right);
        }
        return numberSt.top();
    }
    
    int extractNumber(string& s, int& index) {
        while(index < s.size() && s[index] == ' ') index += 1;
        int ret = 0;
        while (index < s.size() 
               && s[index] <= '9'
               && s[index] >= '0') {
            ret  = ret * 10 + (s[index] - '0');
            index += 1;
        }
        while(index < s.size() && s[index] == ' ') index += 1;
        return ret;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) return false;
        ListNode* before = head;
        ListNode* after = head;
        while (after != NULL) {
            before = before->next;
            after = after->next;
            if (after == NULL) return false;
            after = after->next;
            if (before == after) return true;
        }
        return false;
    }
};

/**
 * 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:
    void flatten(TreeNode* root) {
        if (root == NULL) return;
        this->transform(root);
    }
    TreeNode* transform(TreeNode* root) {
        TreeNode* temp = root->right;
        TreeNode* current = root;
        if (root->left != NULL) {
            root->right = root->left;
            current = this->transform(root->left);
            current->left = NULL;
            root->left = NULL;
            current->right = temp;
        }
        if (temp == NULL) return current;
        current = this->transform(temp);
        return current;
    }
};

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if (triangle.size() == 0) return 0;
        int index = 1;
        while (index < triangle.size()) {
            triangle[index][0] += triangle[index - 1][0];
            for (int i = 1; i < triangle[index].size() - 1; i++) {
                triangle[index][i] += min(triangle[index - 1][i - 1], triangle[index - 1][i]);
            }
            triangle[index][triangle[index].size() - 1] += triangle[index - 1][triangle[index - 1].size() - 1];
            index += 1;
        }
        
        int ret = INT_MAX;
        for (int i = 0; i < triangle[triangle.size() - 1].size(); i++)
            if (triangle[triangle.size() - 1][i] < ret) 
                ret = triangle[triangle.size() - 1][i];
        
        return ret;
    }
};

class Solution {
public:
    bool checkPair(char& left, char& right) {
        return (left == '{' && right == '}') || \
            (left == '[' && right == ']') || (left == '(' && right == ')');
    }
    bool checkLeft(char& item) {
        return (item == '[') || (item == '{') || (item == '(');
    }
    bool isValid(string s) {
        if (s.size() == 0) return true;
        if (s.size() % 2 || !this->checkLeft(s[0])) return false;
        int index = 1;
        stack<char> st;
        st.push(s[0]);
        while(index < s.size()) {
            if ( this->checkLeft(s[index]) ) st.push(s[index]);
            else {
                if (!this->checkPair(st.top(), s[index]) ) return false;
                st.pop();
            }
            index += 1;
        }
        return st.empty();
    }
};

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret(1, vector<int>());
        vector<int> currentSet;
        this->getSubset(ret, nums, currentSet, 0, nums.size() );
        return ret;
    }
    
    void getSubset(vector<vector<int>>& ret, vector<int>& nums, vector<int>& currentSet, int index, int size) {
        if (index >= size) return;
        for (int i = index; i < size; i++) {
            currentSet.push_back(nums[i]);
            vector<int> newSet(currentSet);
            ret.push_back(newSet);
            this->getSubset(ret, nums, currentSet, i + 1, size);
            currentSet.pop_back();
        }
        return;
    }
};