homework01

//leetcode 26 easy
//leetcode 去重
//code


      
class Solution {
public:
// we use two pointer to iterate all elements in the vector
// if it is  the same number, move the second pointer to next, kep first still
// if two numbers do not matched, the place the second num in front the first num, increment the first and second

    int removeDuplicates(vector<int>& nums) {
        
        int len = nums.size();
        
        if(len == 0) return 0; //if empty return 0
        //first pointer
        int first = 0;
        //second pointer
        int last = 1;
        //interate all 
        while(last != len){
            if(nums[first] == nums[last]) ++last; // add sec pter
            else { nums[first+1] = nums[last]; ++first; ++last;  // add sec pter }


        }

        ++first; // because first only represent the index num ; add one 


        return first;

    }
    
    
    
 

///Time Complexity: O(n)
///Space Complexity: O(1)

//==========================================================分割线======================================================================


//leetcode 88 easy
 //合并有序数组
//code


//iterate backwards
//change each elements via compare each end points

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        
        int nums = m + n - 1;
        int num1 = m - 1;
        int num2 = n - 1;
        //if nums2 or all are empty return
        if(nums<0 || n == 0) return ;
        // if only nums1 is empty return nums2
        if(m == 0) {nums1 = nums2; return ;}
        
        //iterate all nums1 from behind
        for(int i = nums; i>=0;i--){
            if(nums1[num1] >= nums2[num2]){
                nums1[i] = nums1[num1];
                num1--;
            }
            else{
                nums1[i] = nums2[num2];
                num2--;
            }
            //either nums1 or nums2 's element are used, we break
            if(num1 == -1 || num2 == -1) break;
            
        }
        
        // if( num2 are longer, copy all remaining numbers in nums2 into nums2's begining 
        if(num1 == -1 && num2 != -1){
            for(int i = 0; i <= num2; i++) nums1[i] = nums2[i];
        } 
        
        
        
    }
};

///Time Complexity: O(n)
///Space Complexity: O(1)

//==========================================================分割线======================================================================
//leetcode 206 medium 反转链表
//leetcode 链接： https://leetcode-cn.com/problems/reverse-linked-list/
//code
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* dummyhead = new ListNode(0,head);
        ListNode* prehead = dummyhead;
        if(head == nullptr)  return head;
        while(head != nullptr){
             dummyhead->next = head->next;
            if(prehead == dummyhead) head->next = nullptr;
            else head->next = prehead;
            prehead = head;
            head = dummyhead->next;
            
            
            
        }
        
        return prehead;
        
    }
};
///Time Complexity: O(n)
///Space Complexity: O(1)


//===============================================分割线=======================================================================================
//leetcode 641 medium  双端队列
//leetcode 链接： https://leetcode.com/problems/design-circular-deque/
//code

class MyCircularDeque {
public:
    /** Initialize your data structure here. Set the size of the deque to be k. */
    int* deque;
    int front = 0;
    int rear = 0;
    int size = 0;
    int cap = 0;
    MyCircularDeque(int k) {
        cap = k;
        deque = new int[k];
    }
    
    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    bool insertFront(int value) {
        if(cap && !isFull()){
        if(!isEmpty()) {
            front = (front == 0) ? cap - 1 : front - 1;
        }
        deque[front] = value;
        size++;
            return true;
        }
        
        return false;
    }
    
    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    bool insertLast(int value) {
        if(cap && !isFull()){
        if(!isEmpty()) {
            rear = (rear == cap-1) ? 0 : rear + 1;
        }
        deque[rear] = value;
        size++;
            return true;
        }
        
        return false;
        
    }
    
    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    bool deleteFront() {
     
        if(!isEmpty()){
            --size;
            if(size == 0){ front = 0; rear=0;}
            else {
                front = (front == cap-1)? 0 : front + 1;
            }
            return true;
        }
        return false;
    }
    
    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    bool deleteLast() {
         if(!isEmpty()){
            --size;
            if(size == 0){ front = 0; rear=0; }
            else {
                rear = (rear == 0)? cap - 1 : rear - 1;
            }
            return true;
        }
        return false;
    }
    
    /** Get the front item from the deque. */
    int getFront() {
        if(isEmpty()) return -1;
        return deque[front];
    }
    
    /** Get the last item from the deque. */
    int getRear() {
        if(isEmpty()) return -1;
        return deque[rear];
        
    }
    
    /** Checks whether the circular deque is empty or not. */
    bool isEmpty() {
        
        return size == 0;
    }
    
    /** Checks whether the circular deque is full or not. */
    bool isFull() {
        
        
        return size == cap;
        
    }
};


//===============================================分割线=======================================================================================
//leetcode 641 medium
//leetcode 链接： https://leetcode.com/problems/design-circular-deque/
//code
class MyCircularDeque {
public:
    /** Initialize your data structure here. Set the size of the deque to be k. */
    int* deque;
    int front = 0;
    int rear = 0;
    int size = 0;
    int cap = 0;
    MyCircularDeque(int k) {
        cap = k;
        deque = new int[k];
    }
    
    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    bool insertFront(int value) {
        if(cap && !isFull()){
        if(!isEmpty()) {
            front = (front == 0) ? cap - 1 : front - 1;
        }
        deque[front] = value;
        size++;
            return true;
        }
        
        return false;
    }
    
    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    bool insertLast(int value) {
        if(cap && !isFull()){
        if(!isEmpty()) {
            rear = (rear == cap-1) ? 0 : rear + 1;
        }
        deque[rear] = value;
        size++;
            return true;
        }
        
        return false;
        
    }
    
    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    bool deleteFront() {
     
        if(!isEmpty()){
            --size;
            if(size == 0){ front = 0; rear=0;}
            else {
                front = (front == cap-1)? 0 : front + 1;
            }
            return true;
        }
        return false;
    }
    
    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    bool deleteLast() {
         if(!isEmpty()){
            --size;
            if(size == 0){ front = 0; rear=0; }
            else {
                rear = (rear == 0)? cap - 1 : rear - 1;
            }
            return true;
        }
        return false;
    }
    
    /** Get the front item from the deque. */
    int getFront() {
        if(isEmpty()) return -1;
        return deque[front];
    }
    
    /** Get the last item from the deque. */
    int getRear() {
        if(isEmpty()) return -1;
        return deque[rear];
        
    }
    
    /** Checks whether the circular deque is empty or not. */
    bool isEmpty() {
        
        return size == 0;
    }
    
    /** Checks whether the circular deque is full or not. */
    bool isFull() {
        
        
        return size == cap;
        
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */
//===============================================分割线=======================================================================================
//leetcode 25 hard
//leetcode 链接： https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
//code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        
        ListNode* dummy = new ListNode(0,head);
        ListNode* end = dummy;
        ListNode* prehead = nullptr;
        ListNode* Res;
       while(end != nullptr){
           
           end = get_end_node(end,k);
           if(end == nullptr) break;
           if(prehead == nullptr) Res = end;
           head =  reverseList(prehead, head, end);
           prehead = dummy->next;
           dummy->next = head;
           end = dummy;
          // dummy = reverseList(prehead, dummy,end);
           //if(prehead == nullptr) head = end;
          // if(end != nullptr) end->val = 0;
           //break;
           
       }
        return Res;
        
    }
   ListNode* reverseList(ListNode* last_Group_tail, ListNode* head, ListNode* end) {
       
       ListNode* next_group_head = end->next;
       ListNode* backward_node = end->next; 
       ListNode* forward_node = head;
       while(forward_node != next_group_head){
           
           head = forward_node->next;
           forward_node->next = backward_node;
           backward_node = forward_node;
           forward_node = head;
           
       }
       if(last_Group_tail != nullptr) {  last_Group_tail->next = end; }
     
       
        return next_group_head;
        
        
    }
    
    ListNode* get_end_node(ListNode* node,int k){
        
        for(int i=0; i<k; i++){
            node = node->next;
            if(node == nullptr) return nullptr;
        }
        
        return node;
        
    }
};


 //===============================================分割线=======================================================================================
//leetcode 150 medium
//leetcode 链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
//code

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        int i = 0;
        stack<int> numbers;
        string operands[4] = {"+","-","*","/"};
        int res;
        for(string token : tokens){
            
            int a = 0;
            int b = 0;
            
           
            if(!numbers.empty() && (token[0] > '9' || token[0] < '0') && token.size() == 1 ){
                if(!token.compare(operands[0])){
                   a = numbers.top();
                    numbers.pop();
                    b = numbers.top();
                    numbers.pop();
                   //cout << a+b;
                    numbers.push(a+b);
                    
                }
                else if(!token.compare(operands[1])){
                     a = numbers.top();
                    numbers.pop();
                    b = numbers.top();
                    numbers.pop();
                   
                    numbers.push(b-a);
                    
                } else if(!token.compare(operands[2])){
                    a = numbers.top();
                    numbers.pop();
                    b = numbers.top();
                    numbers.pop();
                    numbers.push(a*b);
                    
                } else if(!token.compare(operands[3])){
                     a = numbers.top();
                    numbers.pop();
                    b = numbers.top();
                    numbers.pop();
                   
                   // a = b/a;
                    numbers.push(b/a);
                   
                    
                }
                
            }
             else {
                
                i = stoi(token);
                numbers.push(i);
                 cout << i << " ";
            }
            
            
        }
        return numbers.top() ;
        
    }
};
 //===============================================分割线=======================================================================================
//leetcode 21 easy
//leetcode 链接：https://leetcode.com/problems/merge-two-sorted-lists/
//code


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        while(l1!=nullptr && l2!=nullptr){
            if(l1->val > l2->val) {
                
                tail->next = l2;
                l2 = l2->next;
            }
            else{
                
                tail->next = l1;
                l1 = l1->next;
            }
            tail = tail->next;
        }
        
        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};
 //===============================================分割线=======================================================================================
//leetcode 53 easy
//leetcode 链接：https://leetcode.com/problems/maximum-subarray/
//code
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
         int res = INT_MIN, curSum = 0;
        for (int num : nums) {
            curSum = max(curSum + num, num);
            res = max(res, curSum);
        }
        return res;
     
    }
};
//===============================================分割线=======================================================================================
//leetcode 304 medium Range Sum Query 2D - Immutable
//leetcode 链接：https://leetcode.com/problems/range-sum-query-2d-immutable/
//code
class NumMatrix {
private:
    vector<vector<int>> mymatrix;
public:
    
    NumMatrix(vector<vector<int>>& matrix) {
        int total = 0;
        
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[i].size();j++){
                if(i == 0 && j == 0) continue;
                if(i == 0 && j) matrix[0][j] += matrix[0][j-1];
                if(i && j == 0) matrix[i][0] += matrix[i-1][0];
                if(i && j) matrix[i][j] = matrix[i][j] + matrix[i-1][j] +  matrix[i][j-1] - matrix[i-1][j-1];
                
            }
        }
        mymatrix = matrix;
        
        
    }
  
    
    int sumRegion(int row1, int col1, int row2, int col2) {
       
        if(row1==0 && col1==0)  return mymatrix[row2][col2];
        if(row1 == 0 && col1)  return mymatrix[row2][col2] - mymatrix[row2][col1-1];
        if(row1 && col1 == 0)  return mymatrix[row2][col2] - mymatrix[row1-1][col2];
        
        return mymatrix[row2][col2] - mymatrix[row2][col1-1] - mymatrix[row1-1][col2] + mymatrix[row1-1][col1-1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */
 
 //===============================================分割线=======================================================================================
//leetcode 1109. Corporate Flight BookingsMedium
//leetcode 链接：https://leetcode.com/problems/corporate-flight-bookings/
//code
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> ans(n);
        
        for(int i =0; i < bookings.size(); i++){
                if(bookings[i][0] == 1) ans[0] += bookings[i][2];
                else ans[bookings[i][0] - 1] += bookings[i][2];
                
                if( bookings[i][1] == n) { continue; }
                else { ans[bookings[i][1] ] -= bookings[i][2];}
                //cout << bookings[i][0] ;
            
            
        }
        
        for(int i = 0; i<ans.size();i++){
            if(i){
                ans[i] += ans[i-1];
            }
            
        }
        return ans;
        
        
    }
};