// 双链表(数组模拟)
#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;
}
Wilson79
访客：17032
离线：4天前
活动打卡代码
AcWing 827. 双链表
// 在笔试题中需要用到单链表的数组模拟，因为 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. 有效的括号
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(); // 看是否有女生剩余
}
};
活动打卡代码
LeetCode 13. 罗马数字转整数
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;
}
};
活动打卡代码
LeetCode 12. 整数转罗马数字
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;
}
};
活动打卡代码
AcWing 799. 最长连续不重复子序列
#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. 整数反转
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;
}
};
