头像

Wilson79


访客:17124

离线:6天前


活动打卡代码 AcWing 827. 双链表

// 双链表(数组模拟)
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100010;

int e[N], l[N], r[N], idx;

// 初始化
void init() {
    // 结点0表示左哨兵,1表示右哨兵
    r[0] = 1, l[1] = 0;
    idx = 2; // 下标0和1已经被用过
}

// 插入元素 - 在下标为k的点的右边插入x
void add(int k, int x) {
    e[idx] = x;

    r[idx] = r[k]; // 先连
    l[idx] = k;    // 先连

    l[r[k]] = idx; // 后断 (这行必须在r[k] = idx前面)
    r[k] = idx;    // 后断
    idx ++;
}
// 注:插入元素 - 在下标为k的点的左边插入x,只需 add(l[k], x);

// 删除元素 - 删除下标为k的结点
void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main() {
    int m;
    cin >> m;

    init();

    // L : add(0, x)
    // R : add(l[1], x)
    // D : remove(k + 1, x) // 第 k 个插入的数,下标为 k + 1
    // IL : add(l[k + 1], x)
    // IR : add(k + 1, x)
    while (m--) {
        int x, k;
        string s;
        cin >> s;
        if (s == "L") {
            cin >> x;
            add(0, x);
        } else if (s == "R") {
            cin >> x;
            add(l[1], x);
        } else if (s == "D") {
            cin >> k;
            remove(k + 1);
        } else if (s == "IL") {
            cin >> k >> x;
            add(l[k + 1], x);
        } else if (s == "IR") {
            cin >> k >> x;
            add(k + 1, x);
        }
    }

    // 从左往右遍历双链表
    for (int i = r[0]; i != 1; i = r[i]) {
        cout << e[i] << " ";
    }

    return 0;
}



// 在笔试题中需要用到单链表的数组模拟,因为 new 操作很慢

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e5 + 7;

// head 表示头结点的下标(竖着画)
// e[i] 表示结点 i 的值
// ne[i] 表示结点 i 的 next 指针是多少
// idx 存储当前已经用到了哪个点
int head, idx, e[N], ne[N];

// 初始化
void init() {
    head = -1; // head = -1 表示当前头结点是空节点(-1)
    idx = 0;   // idx = 0 表示从 0 号结点开始用
}

// 头插法:将 x 插到头结点head后面
void add_to_head(int x) {
    e[idx] = x;
    ne[idx] = head; // 先连
    head = idx;     // 后断
    idx++;          // 当前 idx 结点已经用过了
}

// 尾插法:将 x 插到尾结点idx-1后面(适用范围小,必须依次进行插入操作)
void add_to_end(int x) {
    e[idx] = x;
    ne[idx] = -1; // 先连

    if (!idx)
        head = idx; // 后断
    else
        ne[idx - 1] = idx; // 后断

    idx++;
}

// 将 x 插到下标是k的节点后面
void add(int k, int x) {
    e[idx] = x;      // 设置 val 值
    ne[idx] = ne[k]; // 先连
    ne[k] = idx;     // 后断
    idx++;
}

// 将下标是 k 的结点后面的结点删除
void remove(int k) {
    ne[k] = ne[ne[k]];
}

int main() {
    int m;
    cin >> m;

    init();

    while (m--) {
        int k, x;
        string s;
        cin >> s;
        if (s == "H") {
            cin >> x;
            add_to_head(x);
        } else if (s == "I") {
            cin >> k >> x;
            add(k - 1, x);
        } else if (s == "D") {
            cin >> k;
            if (!k)
                head = ne[head];
            else
                remove(k - 1);
        }
    }

    for (int i = head; i != -1; i = ne[i]) {
        cout << e[i] << " ";
    }

    return 0;
}


活动打卡代码 AcWing 826. 单链表

// 在笔试题中需要用到单链表的数组模拟,因为 new 操作很慢

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e5 + 7;

// head 表示头结点的下标(竖着画)
// e[i] 表示结点 i 的值
// ne[i] 表示结点 i 的 next 指针是多少
// idx 存储当前已经用到了哪个点
int head, idx, e[N], ne[N];

// 初始化
void init() {
    head = -1; // head = -1 表示当前头结点是空节点(-1)
    idx = 0;   // idx = 0 表示从 0 号结点开始用
}

// 头插法:将 x 插到头结点head后面
void add_to_head(int x) {
    e[idx] = x;
    ne[idx] = head; // 先连
    head = idx;     // 后断
    idx++;          // 当前 idx 结点已经用过了
}

// 尾插法:将 x 插到尾结点idx-1后面(适用范围小,必须依次进行插入操作)
void add_to_end(int x) {
    e[idx] = x;
    ne[idx] = -1; // 先连

    if (!idx)
        head = idx; // 后断
    else
        ne[idx - 1] = idx; // 后断

    idx++;
}

// 将 x 插到下标是k的节点后面
void add(int k, int x) {
    e[idx] = x;      // 设置 val 值
    ne[idx] = ne[k]; // 先连
    ne[k] = idx;     // 后断
    idx++;
}

// 将下标是 k 的结点后面的结点删除
void remove(int k) {
    ne[k] = ne[ne[k]];
}

int main() {
    int m;
    cin >> m;

    init();

    while (m--) {
        int k, x;
        string s;
        cin >> s;
        if (s == "H") {
            cin >> x;
            add_to_head(x);
        } else if (s == "I") {
            cin >> k >> x;
            add(k - 1, x);
        } else if (s == "D") {
            cin >> k;
            if (!k)
                head = ne[head];
            else
                remove(k - 1);
        }
    }

    for (int i = head; i != -1; i = ne[i]) {
        cout << e[i] << " ";
    }

    return 0;
}


活动打卡代码 LeetCode 70. 爬楼梯

class Solution {
public:
    // 不用开数组,用两个变量滚动一下就可以了
    int climbStairs(int n) {
        int a = 1, b = 1;
        for (int i = 2; i <= n; i ++) {
            int c = a + b;
            a = b;
            b = c;
        }

        return b;
    }
};


活动打卡代码 LeetCode 20. 有效的括号

Wilson79
16天前
class Solution {
public:
    bool isValid(string s) {
        stack <int> stk;

        for (int i = 0; i < s.size(); i ++) {
            char c = s[i];
            if (c == '(' || c == '[' || c == '{') stk.push(c); // 加入栈等待
            else {
                // 小技巧:一对括号的 ASCII 码的差不会超过 2
                if (stk.size() && abs(stk.top() - c) <= 2) stk.pop();
                else return false; // 有男生看不对眼 
            }
        }

        return stk.empty(); // 看是否有女生剩余
    }
};



Wilson79
17天前
class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> table = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000},
        };

        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            if (i < s.size() - 1 && table[s[i]] < table[s[i + 1]]) {
                res -= table[s[i]];
            } else {
                res += table[s[i]];
            }
        }

        return res;
    }
};



Wilson79
17天前
class Solution {
public:
    string intToRoman(int num) {
        // 模拟题
        int values[] = {
            1000,
            900, 500, 400, 100,
            90, 50, 40, 10,
            9, 5, 4, 1,
        };

        string reps[] = {
            "M",
            "CM", "D", "CD", "C",
            "XC", "L", "XL", "X",
            "IX", "V", "IV", "I",
        };

        string res = "";
        for (int i = 0; i <= 12; i ++) {
            while (num >= values[i]) {
                num -= values[i];
                res += reps[i];
            }
        }

        return res;
    }
};


新鲜事 原文

Wilson79
1个月前
趁着大四的时间,抓紧时间刷题



Wilson79
1个月前
#include <iostream>

using namespace std;

const int N = 1e5 + 7;

int a[N], window[N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i ++) cin >> a[i];

    int res = 0;
    for (int i = 0, j = 0; i < n; i++) {
        // 动指针 i,更新一系列数据
        window[a[i]] ++; // 103:1 437:1

        // 缩小窗口的时机
        while (window[a[i]] > 1) {
            window[a[j]] --;
            j ++;
        }

        // 在扩大时更新答案
        res = max(res, i - j + 1);
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 LeetCode 7. 整数反转

Wilson79
1个月前
class Solution {
public:
    int reverse(int x) {
        long long res = 0;
        while (x) {
            res = res * 10 + x % 10; // 负数也OK
            x /= 10;
        }
        if (res < INT_MIN || res > INT_MAX) return 0;

        return res;
    }
};