头像

GinSoda




离线:17分钟前


最近来访(13)
用户头像
rd0
用户头像
InsiApple
用户头像
lzjune
用户头像
OnjoujiToki
用户头像
zzw_7
用户头像
cdm
用户头像
念生晏河阡
用户头像
YikN
用户头像
一只奇怪的小魔女
用户头像
CrazyShanShan
用户头像
hlydxxz
用户头像
neepoo
用户头像
lixiaoqian

活动打卡代码 LeetCode 162. 寻找峰值

GinSoda
1天前
/*
思路:
由于nums[i] != nums[i + 1],序列的最短连续子序列(连续两个数),只有两种状态:升序和降序
二段性 可以分为
    (满足/不满足)的 二段性
    (一定满足/不一定满足)的 二段性

由于a[-1]、a[n]被视为-∞,对于任意数组而言,一定存在峰值(一定有解);
    左半段必须升序才没有峰值,右半段必须降序才没有峰值。所以前半段、后半段交汇至少会有一个峰值。
二分不会错过峰值。
    如果nums[mid]和nums[mid+1]是升序,那就向右找降序左端点
    如果nums[mid]和nums[mid+1]是降序,那就向左找升序右端点
*/
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1; // 高位二分
            if (nums[mid] > nums[mid + 1]) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};


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

GinSoda
1天前

/*
思路:
类似LeetCode 142 环形链表II
p走a、c、b
q走b、c、a
相遇即返回
若A、B相交
    a + c + b = b + c + a,
    p、q同时走到交点
若A、B不相交
    a + b = b + a,
    p、q同时走到nullptr
*/
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p = headA, *q = headB;
        while (p != q) {
            if (p) p = p->next;
            else p = headB;
            if (q) q = q->next;
            else q = headA;
        }
        return p;
    }
};


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

GinSoda
1天前

/*
LeetCode 155 最小栈 等价于acwing 41
参考:leetcode.wang/leetcode-155-Min-Stack.html
思路原型:
使用两个数组f、g,f[i]代表栈,g[i]代表f[:i+1]中的前缀最小值
存在重复元素时,区分两种最小值(严格最小值val < minVal和非严格最小值val = minVal)
思路1:
使用链表,每个节点存有两个属性,val和minVal,分别代表数组f和g
思路2:单调栈
使用单调栈(非严格递减)代表g[i]
思路3:缓存法
只使用f,融合f和g,使用一个数minV代表g[i]。
遇见新的非严格最小值,则将minV/g[i-1]入栈,再将新的最小值入栈,最后更新minV
思路4:差值法
只使用f,融合f和g,使用一个数minV代表g[i]。
f[0] =  nums[0]
f[i] = nums[i] - g[i-1] // 如果f[i] < 0代表nums[i]是新的严格最小值
(1)当nums[i] > g[i-1],有g[i] = g[i-1],f[i] > 0
    nums[i] = f[i] + g[i-1] = f[i] + g[i]
(2)当nums[i] = g[i-1],有g[i] = g[i-1],f[i] = 0
    nums[i] = f[i] + g[i-1] = f[i] + g[i] = g[i]
(3)当nums[i] < g[i-1],有g[i] != g[i-1],f[i] < 0
    nums[i] = g[i]
    g[i-1] = nums[i] - f[i] = g[i] - f[i]; // 复原之前的严格最小值
*/
/*思路2*/
class MinStack {
public:
    vector<int> stk, minStk;
    MinStack() {
    }

    void push(int val) {
        stk.push_back(val);
        if (minStk.empty() || val <= minStk.back()) 
            minStk.push_back(val);
    }

    void pop() {
        int x = stk.back(); stk.pop_back();
        if (x == minStk.back()) minStk.pop_back();
    }

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

    int getMin() {
        return minStk.back();
    }
};
/*思路4*/
class MinStack {
public:
    using LL = long long;
    vector<LL> f;
    LL minV=0;
    MinStack() {}

    void push(int val) {
        if (f.empty()) {
            f.push_back(val);
            minV = val;
        }
        else {
            f.push_back(val - minV); // nums[i] - g[i-1]
            minV = min(LL(val), minV);
        }
    }

    void pop() { // 是否是严格最小值,需要还原minV
        if (f.back() < 0) minV = minV - f.back(); 
        f.pop_back();
    }

    int top() { // 是否是首元素,是否是严格最小值
        if (f.size() == 1) return minV;
        else if (f.back() < 0) return minV;
        else return minV + f.back();
    }

    int getMin() {
        return int(minV);
    }
};



GinSoda
1天前
/*
重复元素,首尾相同会破坏二段性,需要人工去重(最坏时间复杂度O(n))。
然后二分查找
*/
class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        while (n > 0 && nums[n-1] == nums[0]) n --; // 人为构造二段性
        if (n-1 < 0 || nums[0] < nums[n-1]) return nums[0]; // 不存在高位分界点
        int l = 0, r = n - 1, mid;
        while (l < r) {
            mid = (l + r) >> 1;
            if (nums[mid] >= nums[0]) l = mid+1;
            else r = mid;
        }
        return nums[l];
    }
};



GinSoda
1天前
/*
思路:
旋转数组具有二段性,使用二分查找
前半部分>=nums[0],后半部分<nums[0]。高位二分
*/
class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums[0] <= nums.back()) return nums[0]; // 高位分界点不存在
        int l = 0, r = nums.size() - 1;
        int mid;
        while (l < r) {
            mid = (l+r) >> 1;
            if(nums[mid] >= nums[0]) l = mid + 1;
            else r = mid;
        }
        return nums[l];
    }
};



GinSoda
1天前
/*
思路1:
数列里有偶数个负数、无0
将数组分割成0之间的区间。
使用g[i]记录区间中最早出现的负数
使用前缀乘积f[i]记录以nums[i]为结尾的区间前k个数的乘积
if f[i-1] != 0
    f[i] = f[i-1] * nums[i]
else f[i] = nums[i]

思路2:
同时记录以nums[i]为结尾的前缀乘积的最大值、最小值(以防nums[i]为负数)
maxnum[i] = max(nums[i], maxnum[i-1] * nums[i], minnum[i-1] * nums[i])
minnum[i] = min(nums[i], maxnum[i-1] * nums[i], minnum[i-1] * nums[i])
*/
/*思路1*/
class Solution {
public:
    using ll = long long; // ans在int范围内,不代表中间结果在int范围内
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0]; // 单个元素时,答案可能为负数

        vector<ll> f(n);
        vector<int> g(n);

        f[0] = nums[0];
        g[0] = -1;
        for (int i = 1; i < n; i ++) {
            if (f[i-1]) f[i] = f[i-1] * nums[i];
            else f[i] = nums[i];

            if (nums[i-1] == 0) g[i] = -1; // 出现0,重置区间中负数下标
            else if (nums[i-1] < 0 && g[i-1] == -1) g[i] = i-1; // 记录区间第一个负数
            else g[i] = g[i-1];
        }

        int ans = 0;
        for (int i = 0; i < n; i ++) {
            if (f[i] >= 0) ans = max(int(f[i]), ans);
            else if (g[i] != -1) ans = max(int(f[i] / f[g[i]]), ans);
        }
        return ans;
    }
};
/*思路2*/
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty()) return 0;
        int maxv = nums[0], minv = nums[0], ans = nums[0];
        int mx, mn; // 代表maxn[i-1], minn[i-1]
        for (int i = 1; i < nums.size(); i ++) {
            mx = maxv, mn = minv;
            maxv = max(nums[i], max(nums[i] * mx, nums[i] * mn));// 如果mx和mn为0,那么此时最大值为nums[i];
            minv = min(nums[i], min(nums[i] * mx, nums[i] * mn));
            ans = max(ans, maxv);
        }
        return ans;
    }
};



GinSoda
2天前
/*
思路:
leetcode 151 翻转字符串里的单词 等同 acwing 77 翻转单词顺序
对字符串使用双指针
*/
class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        int i = 0, j = 0;
        // 原地复制,处理多余空格
        while (j < n) {
            if (s[j] == ' ' && (i == 0 || s[i-1] == ' ')) j ++; // i==0清除s前面空格、s[i-1]清除多个空格
            else s[i ++] = s[j ++];
        }
        while (i-1 >= 0 && s[i-1] == ' ') i --; // 清除s后面空格
        // 先整体反转,再分步反转
        s = s.substr(0, i);
        n = i;
        reverse(s.begin(), s.end());
        i = 0, j = 0;
        while (i < n) {
            while (j < n && s[j] != ' ') j ++;
            reverse(s.begin()+i, s.begin()+j);
            i = j = j + 1;
        }
        return s;
    }
};



GinSoda
7天前
/*
逆波兰表达式的解释器一般是基于堆栈的。
解释过程一般是:操作数入栈;遇到操作符时,操作数出栈,求值,将结果入栈。
遍历结束后,栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现,并且能很快求值。
*/
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        int a, b;
        for (auto& token: tokens) {
            if (token == "+") {
                b = stk.top(); stk.pop();
                a = stk.top(); stk.pop();
                stk.push(a + b);
            }
            else if (token == "-") {
                b = stk.top(); stk.pop();
                a = stk.top(); stk.pop();
                stk.push(a - b);
            }
            else if (token == "*") {
                b = stk.top(); stk.pop();
                a = stk.top(); stk.pop();
                stk.push(a * b);
            }
            else if (token == "/") {
                b = stk.top(); stk.pop();
                a = stk.top(); stk.pop();
                stk.push(a / b);
            }
            else stk.push(stoi(token)); // stoi(s) <=> atoi(s.c_str())
        }
        return stk.top();
    }
};



GinSoda
7天前
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        typedef long double LD; // float精度不足以处理斜率

        int res = 0;
        for (auto& p: points) {
            int vs = 0;
            unordered_map<LD, int> cnt; // 通过斜率和坐标本身,唯一确定一条线
            for (auto& q: points)
                if (p == q) continue; // 坐标p本身不计入数据
                else if (p[0] == q[0]) vs ++ ; // x = b,斜率趋于无穷大
                else { // y = kx + b
                    LD k = (LD)(q[1] - p[1]) / (q[0] - p[0]);
                    cnt[k] ++;
                }
            int c = vs; // c代表有多少坐标和坐标p在同一条线上
            for (auto [k, t]: cnt) c = max(c, t);
            res = max(res, c + 1); // 加上坐标p本身
        }
        return res;
    }
};


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

GinSoda
8天前
/*
归并排序-迭代版
本题lc 148算是leetcode上链表最难的题之一了。实际想明白了也很简单
时间复杂度O(nlogn),空间复杂度O(1)
1、区间长度固定为2的幂
2、使用区间长度切分区间,不使用中点切分
*/
class Solution {
public:
    void insert(ListNode*& cur, ListNode*& node, int& val) { // cur->next = node
        cur = cur->next = node;
        node = node->next;
        val ++;
    }

    ListNode* sortList(ListNode* head) {
        int n = 0;
        for (auto p = head; p; p = p->next) n ++ ;

        auto dummy = new ListNode(-1);
        dummy->next = head;
        int x = 0, y = 0, k = 0;
        for (int i = 1; i < n; i *= 2) { // i代表区间长度,固定为2的幂
            auto cur = dummy;
            for (int j = 1; j + i <= n; j += i * 2) { // 每次遍历两个区间
                auto p = cur->next, q = p; // p指向第一个区间头节点,q指向第二个区间头节点
                k = i;
                while (k --) q = q->next; // 使用区间长度切分两个区间,而非中点切分
                x = 0, y = 0; // x、y用于确定非最后一区间的区间长度,q用于约束最后一个区间
                // 合并p、q两区间,cur为合并后的区间的最后一个节点,cur->next视为nullptr
                while (x < i && y < i && p && q) {
                    if (p->val <= q->val) insert(cur, p, x);
                    else insert(cur, q, y);
                }
                while (x < i && p) insert(cur, p, x);
                while (y < i && q) insert(cur, q, y);
                cur->next = q; // cur->next指向第二个区间末尾
            }
        }
        return dummy->next;
    }
};