头像

a645852220




离线:1个月前


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

a645852220
1个月前
/**
 * 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. 最小栈

a645852220
1个月前
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stk;
    stack<int> f;
    MinStack() {
        stk = stack<int>();
        f = stack<int>();
    }

    void push(int x) {
        stk.push(x);
        if (f.empty() || x <= f.top()) {
            f.push(x);
        }
    }

    void pop() {
        int x = stk.top();
        stk.pop();
        if (x <= f.top()) {
            f.pop();
        }
    }

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

    int getMin() {
        return f.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();
 */



a645852220
1个月前
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r && nums[r] == nums[0]) r--;
        if (nums[l] <= nums[r]) return nums[0];
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
};



a645852220
1个月前
class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.size() <= 1) return nums[0];
        if (nums[0] <= nums.back()) return nums[0];
        int l = 0, r = nums.size() - 1;
        while(l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= nums[0]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }   
        return nums[l];
    }
};



a645852220
1个月前
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0];
        int f = nums[0], g = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int a = nums[i], fa = nums[i] * f, ga = nums[i] * g;
            f = max(a, max(fa, ga));
            g = min(a, min(fa, ga));
            res = max(res, f);
        }
        return res;
    }
};



a645852220
1个月前
class Solution {
public:
    string reverseWords(string s) {
        string res = "";
        for (int j = s.size() - 1; j >= 0;) {
            while (j >= 0 && s[j] == ' ') j--;
            if (j < 0) break;
            int i = j;
            while (i >= 0 && s[i] != ' ') i--;
            if (res == "") {
                res = s.substr(i + 1, j - i);
            } else {
                res = res + " " + s.substr(i + 1, j - i);
            }
            j = i;
        }
        return res;
    }
};



a645852220
1个月前
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> numStk;
        stack<char> opStk;
        for (auto ch :tokens) {
            if (ch=="+") {
                auto num1 = numStk.top();
                numStk.pop();
                auto num2 = numStk.top();
                numStk.pop();
                numStk.push(num1+num2);
            } else if (ch == "-") {
                auto num1 = numStk.top();
                numStk.pop();
                auto num2 = numStk.top();
                numStk.pop();
                numStk.push(num2-num1);
            } else if (ch == "*") {
                auto num1 = numStk.top();
                numStk.pop();
                auto num2 = numStk.top();
                numStk.pop();
                numStk.push(num1*num2);
            } else if (ch == "/") {
                auto num1 = numStk.top();
                numStk.pop();
                auto num2 = numStk.top();
                numStk.pop();

                numStk.push(num2/num1);
            } else {
                auto num = stoi(ch);
                numStk.push(num);
            }
        }
        return numStk.top();
    }
};



a645852220
1个月前
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int res = 0;
        for (auto& p:points) {
            int vv = 0, ss = 0;
            unordered_map<long double, int> cnt;
            for (auto& q:points) {
                if (p == q) ss++; // 原点重合
                else if (p[0] == q[0]) vv++; //垂直线增加,无斜率
                else {
                    long double k = (long double)(p[1] - q[1]) / (p[0] - q[0]);
                    cnt[k]++;
                }
            }
            int c = vv;
            for (auto& kv : cnt) {
                c = max(kv.second, c);
            }
            res = max(res, c + ss);
        }
        return res;
    }
};


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

a645852220
1个月前
/**
 * 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* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        auto fast = head->next;
        auto slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        auto m = slow->next;
        slow->next = NULL;
        auto list1 = sortList(head);
        auto list2 = sortList(m);
        ListNode dummy(0);
        auto ret = &dummy;
        auto rear = &dummy;
        while (list1 && list2) {
            ListNode* tmp;
            if (list1->val <= list2->val) {
                tmp = list1;
                list1 = list1->next;
            } else {
                tmp = list2;
                list2 = list2->next;
            }
            rear->next = tmp;
            rear = rear->next;
            rear->next = NULL;
        }
        if (list1) {
            rear->next = list1;
        }
        if (list2) {
            rear->next = list2;
        }
        return ret->next;
    }
};



a645852220
1个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode dummy(-1);
        ListNode* ret = &dummy;
        ret->next = NULL;
        while (head) {
            auto tmp = head;
            head = head->next;
            auto last = ret;
            auto u = last->next;
            while (u && u->val < tmp->val) {
                last = u;
                u = u->next;
            }
            tmp->next = last->next;
            last->next = tmp;
        }
        return ret->next;
    }
};