Skip to content

Latest commit

 

History

History
136 lines (97 loc) · 8.84 KB

cpp.md

File metadata and controls

136 lines (97 loc) · 8.84 KB

C++起步与使用说明

使用范围:刷题接口与标准库最小工具集。 适合已了解变量、分支、循环和函数,准备使用 C++ 练习算法的读者。

开始刷题前:接口与最小语法实验

普通算法题通常保留平台提供的 class Solution、函数名与参数列表,在函数内部实现。评测程序会传入参数并检查返回结果;不需要在提交区自己写 main 读取输入。设计类题如232、303则实现题目指定的类与方法。下面只是语法演示,不是某道题的答案。

// 本地可运行的语法练习;力扣普通函数题保留平台模板。
#include <vector>
#include <iostream>
using namespace std;

void change(vector<int>& a) { a[0] = 9; }  // 修改原容器
int total(const vector<int>& a) {         // 只读,避免整段复制
    int sum = 0;
    for (int x : a) sum += x;
    return sum;
}

int main() {
    vector<int> a{1, 2, 3};
    a.push_back(4);
    change(a);
    cout << total(a) << '\n';
}

自己把 change 的引用去掉,先预测再运行;解释调用者的数组是否改变。知道 vector<int> a(n, 0) 创建n个元素,而 reserve(n) 只预留容量、不能使 a[0] 在空容器上合法。size() 的返回类型为无符号类型;初期在已确认题目规模适合int时用 int n = static_cast<int>(a.size());,不要在空数组上直接计算无符号的 a.size()-1。

GitHub只读 Hello列表的常用操作 和 C++例子 对应片段,不必下载或克隆整个仓库。

返回值与原地修改

看题目自定义评测约定。27既要求返回有效元素数,又要求修改输入数组前缀;打印内容并不能代替返回或修改。只读大容器通常用const引用;需要修改则用非const引用;小标量按值。保留题目给定接口,不机械把所有参数都改成const引用。

第 1–2 章:字符、字符串与哈希容器

string 是字符串;344的接口是 vector<char>&。下标访问前检查范围。仅在题目保证小写英文字母时,才直接使用 int count[26]{}; 和 ch-'a'。

后续示例是局部代码片段,默认已引入对应标准头文件并使用 std:: 或 using namespace std;:哈希容器用 <unordered_map> / <unordered_set>,字符串用 <string>,排序用 <algorithm>,栈用 <stack>,队列与优先队列用 <queue>。示例中的 x、a、target 代表你已有的变量。

unordered_map<int, int> count;
++count[x];                       // 不存在的整型值会先初始化为0
auto it = count.find(x);           // 查找本身不插入
if (it != count.end()) { /* use it->second */ }
unordered_set<int> seen;
seen.insert(x);
bool exists = seen.count(x) != 0;

哈希查找按平均常数时间理解,最坏可能线性;字符串键的构造、哈希和比较也有长度成本。不要把带字符串排序的49草率记为O(单词个数)。map 需要键的顺序、范围查询或对数最坏查找界时仍有用途,不存在“绝不能用”的规则。

第 3 章起:排序与二分工具

sort(a.begin(), a.end());
reverse(a.begin(), a.end());
auto it = lower_bound(a.begin(), a.end(), target);

初期先自己实现二分,再用 lower_bound 对照;使用它之前保证区间满足相同比较规则的有序要求。比较器应表示严格的小于关系,不写 x <= y。sort 的比较次数量级O(n log n),字符串比较还可能包含字符成本。

第 6 章:链表与内存

ListNode* p保存节点地址,p->next读/写节点的next成员。函数内把局部指针p改成别的地址,不等于改变调用者的头指针;可以返回新头,或显式用引用/二级指针传回更新。修改next之前先保存仍要访问的后继。不要访问已经释放的节点,别把 new/delete 和 malloc/free 混配;节点类型和评测接口以题目模板为准。

第 7 章:栈、队列与设计类接口

stack 用 top() 取值、pop() 移除;queue 用 front() 取值、pop() 移除;pop()不返回被移除的值。对空容器取顶/出队不合法。设计类题要把需要跨调用保留的数据放在成员变量中,通过构造函数初始化。普通Solution多次调用时,不依赖遗留的全局或成员状态。

下面用一个与题目无关的计数器展示最小类语法。构造函数与类同名、没有返回类型;冒号后是成员初始化。public 后的方法可由类外调用。

class Counter {
    int value;  // 成员:在同一个对象的多次调用之间保留
public:
    Counter(int start) : value(start) {}
    void add() { ++value; }
    int get() const { return value; }
};
// 在main或其他函数中:Counter c(3); c.add(); // 此时c.get()为4

第 7–13 章:递归、堆、图与回溯

每个递归函数先用一句话定义“输入是什么、返回什么”,再写终止条件。结果容器按引用共享时要考虑回溯恢复;按值复制路径也合法,但必须把复制成本算进去。priority_queue<int> 默认大顶堆;小顶堆可用 priority_queue<int, vector<int>, greater<int>>。top()与pop()分开调用。

图可用 vector<vector<int>> graph(n); 存邻接表;网格不一定需要显式建图。DFS递归栈可能达到节点数或格子数,不能仅因为代码简短就忽略空间。回溯中的path弹出和一般图中visited是否恢复,要由“状态是路径内还是全局”的含义决定。

第 14–16 章:动态规划

先写状态的完整中文含义、依赖与初始化,再写循环。01背包的一维容量倒序,来自需要保留上一物品层;完全背包中可重复取用,依赖可不同。最小值、是否可达、组合数、有序序列数不是同一种状态,不能只靠背循环顺序互相替换。

用可能超出int的和/乘积时,确保运算在足够宽的类型里发生;不是最后赋给long long就自动避免先前溢出。INF加1之前检查可达性或选择留足余量的表示。

GitHub资料怎样看

  1. 直接点章节题单里的具体文件,选Preview;不用从仓库主页到处找,也不用先安装Git。
  2. 前读只看章节题单指定的定义、图、状态说明。代码随想录同页可能包含答案,先不要往下读完整代码。
  3. 自己尝试后,再打开当前题解,先看思路段与图;仍卡住才看C++。其他语言、其他复杂解法先略过。
  4. Hello算法的GitHub Markdown可能显示多语言标记和网站专用语法,直接搜索“C++”;若想看更清楚的图,可从作者网站进入同名章节。
  5. Doocs是补充题解库,读题意、思路、C++,不顺着目录继续加题。643在本计划链接到含C++的英文README。
  6. 105链接落在106文章中,向下找“105.从前序与中序遍历序列构造二叉树”;只读这个对应小节。图论理论有些用卡码网完整程序,学习算法后按当前平台要求选择 LeetCode 函数接口或完整输入输出程序。
  7. 347第二次阅读看NeetCode文件的频率分桶部分;总额外空间包括频次表,不能只数容量k的堆。
  8. 灵神与labuladong作为二轮或卡点补充:可按知识缺口选择查阅。GitHub页面加载不稳定时过一会重试或读项目官方站同名内容。

第 1 章起:竞赛的标准输入输出

AtCoder、洛谷及通常的竞赛编程题提交完整程序:头文件、main、读入、计算、输出。题目究竟是一组输入、有 T 组测试,还是读到 EOF,必须逐题看输入说明,不擅自加一层测试次数。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    long long sum = 0;
    for (auto& x : a) { cin >> x; sum += x; }
    cout << sum << '\n';
    return 0;
}

这只是“输入 n 个数并求和”的格式示范,不是 PracticeA 的答案。关闭流同步后不要混用 scanf/printf 和 cin/cout。用 \n 换行,只有题目要求即时刷新时再显式刷新。输出中不要额外打印“请输入”等提示语。

乘法需要在相乘前提升类型,如 1LL * a * b;在结果已经溢出后赋给 long long 来不及。位运算时检查移位次数与类型,例如 64 位掩码用 1ULL << k,并保证 k 小于位宽。模减法要处理负数;对模数做除法不能随意使用普通整数除法。

编程训练可使用平台支持的 C++17;实际比赛以当届提供的编译器和标准为准。使用标准头文件,不把 bits/stdc++.h 当作所有编译器都支持的标准头。推导后仍需独立编码与边界测试。