头像

Vodka编程菜菜

NYU + Gatech


访客:9677

离线:1个月前


活动打卡代码 LeetCode 160. 相交链表

/**
 * 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) {
        auto p = headA, q = headB;
        while (p != q) {
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }
        return p;       
    }
};


活动打卡代码 LeetCode 155. 最小栈

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> st;
    stack<int> st_min;
    MinStack() {

    }

    void push(int x) {
        st.emplace(x);
        int cur_min = st_min.empty()? x: min(x,st_min.top());
        st_min.emplace(cur_min);
    }

    void pop() {
        if(!st.empty())st.pop();
        if(!st_min.empty())st_min.pop();
    }

    int top() {
        return st.top();
    }

    int getMin() {
        return st_min.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */



class Solution {
public:
    int findMin(vector<int>& nums) {

        int l = 0, r = nums.size()-1;
        int res = -1;
        while(l<=r){
            int m = l + (r-l)/2;
            if(nums[m]>nums[nums.size()-1]) {
                l = m+1;
            }else{
                res = m;
                r = m-1;
            }
        }
        return nums[res];
    }
};



class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0];
        int min_val = nums[0], max_val = nums[0];
        for(int i =1; i < nums.size();++i){
            int max_new = max_val*nums[i];
            int min_new = min_val*nums[i];
            min_val = min(min(max_new, min_new), nums[i]);
            max_val = max(max(min_new, max_new), nums[i]);
            res = max(max_val, res);
        }
        return res;
    }
};



class Solution {
public:

    string reverseWords(string s) {
        if(s.size() == 0) return s;
        int n = s.size();
        int l = 0, r = s.size()-1;
        while(l<n && s[l] ==' ') l++;
        while(r>=0 && s[r] == ' ') r--;      
        string res = "";
        int pos = r;
        while(pos >=l ){
            int p = pos;
            while(p >=l && s[p] !=' ') p--;
            string tmp = s.substr(p+1, pos-p);
            res += tmp +" ";
            while(p >=l && s[p] ==' ') p--;
            pos = p;
        }
        if(res.size())res.pop_back();
        return res;
    }
};



class Solution {
public:
    int gcd(int y, int x){
        if(x == 0) return y;
        return gcd(x, y % x);
    }
    int maxPoints(vector<vector<int>>& points) {
        //核心是如何表示除数
        int n  = points.size();
        if(n == 0) return 0;
        if(n == 1) return 1;
        int res = 0;
        for (int i = 0; i <n-1; ++i){
            unordered_map<string, int> slop_map;
            int repeat = 0;
            int cur_max = 0;
            for(int j = i+1; j < n; ++j){
                int dy = points[i][1] - points[j][1];
                int dx = points[i][0] - points[j][0];
                if(dy == 0 && dx == 0) {
                    repeat++;
                    continue;
                }
                int g = gcd(dy, dx);
                if(g !=0){
                    dy /= g;
                    dx /= g;
                }
                string key = to_string(dy) +"/"+to_string(dx);
                slop_map[key]++;
                cur_max = max(cur_max, slop_map[key]); 
            }
            res = max(res, repeat + cur_max+1);
        }
        return res;
    }
};


活动打卡代码 LeetCode 146. LRU缓存机制

class LRUCache {
private:
   int capacity_;
   list<pair<int,int>> lst;
   unordered_map<int, list<pair<int,int>>::iterator> key_iter_map;
public:
    LRUCache(int capacity) {
        capacity_ = capacity;
    }

    int get(int key) {
        auto iter = key_iter_map.find(key);
        if(iter == key_iter_map.end()){
            return -1;
        }
        int val = iter->second->second;
        lst.splice(lst.begin(), lst, iter->second);
        return val;
    }

    void put(int key, int value) {
        if(get(key) != -1){
            key_iter_map[key]->second = value;
            return;
        }
        if(lst.size() == capacity_){
            auto item = lst.back();
            lst.pop_back();
            key_iter_map.erase(item.first);
        }
        lst.emplace_front(key,value);
        key_iter_map[key] = lst.begin();
        return ;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */



class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        while (head) {
            ListNode *t = head->next;
            cur = dummy;
            while (cur->next && cur->next->val <= head->val) {
                cur = cur->next;
            }
            head->next = cur->next;
            cur->next = head;
            head = t;
        }
        return dummy->next;
    }
};


活动打卡代码 LeetCode 148. 排序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    ListNode* merge(ListNode* l, ListNode* r){
        ListNode* dummy = new ListNode(-1);
        ListNode* tmp = dummy;
        while(l && r){
            if(l->val < r->val){
                tmp->next = l;
                l = l->next;
            }else {
                tmp->next = r;
                r = r->next;
            }
            tmp = tmp->next;
        }
        if(l) tmp->next = l;
        if(r) tmp->next = r;
        return dummy->next;
    }

    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *slow = head, *fast = head, *pre = head;
        while (fast && fast->next) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;
        return merge(sortList(head), sortList(slow));
    }
};



class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto& str : tokens){
            if(str == "+"){
                int right = st.top();st.pop();
                int left = st.top();st.pop();
                int val = left + right;
                st.emplace(val);
            }else if(str == "-") {
                int right = st.top();st.pop();
                int left = st.top();st.pop();
                int val = left - right; 
                st.emplace(val);
            }else if(str == "*") {
                int right = st.top();st.pop();
                int left = st.top();st.pop();
                int val = left * right;
                st.emplace(val);
            }else if(str == "/") {
                int right = st.top();st.pop();
                int left = st.top();st.pop();
                int val = left / right;
                st.emplace(val);
            }else{
                int val = stoi(str);
                st.emplace(val);
            }
        }
        return st.top();
    }
};