主页

背景 前缀树, 字母树. 实现 208. 实现 Trie (前缀树);剑指 Offer II 062. 实现前缀树 - 力扣（Leetcode）; class Trie { Trie *next[26]; bool is_end; public: Trie() : next(), is_end(false) { } Trie *helper(string word) { auto cur(this); for (auto c : word) { if (!cur) return nullptr; cur = cur->...

写在前面 很多动态规划的题都是先记忆化然后才去使用递推优化(动态规划), 直接想确实是比较难, 正如0x3f所说, 记忆化搜索是自动挡, 写起来比较方便, 动态规划是手动挡, 需要自己去找规律. 记忆化搜索 这部分内容很多, 几乎所有的动态规划都是可以直接用记忆化搜索的, 例如最基本的斐波那契和爬楼梯等题目: 1140. 石子游戏 II; 1048. 最长字符串链; 1262. 可被三整除的最大和 - 力扣（Leetcode）;(数据范围小, 可贪心, 正难则反) 1595. 连通两组点的最小成本 - 力扣（Leetcode）; 记忆化搜索+状态压缩 DP 6893. 特别的排列 - 力扣（Leetcode）; 996. 正方形数组的数目 - 力扣（...

写在前面 默认构造函数 编译器生成非平凡默认构造函数的四种情况 带有默认构造函数的成员类对象 带有默认构造函数的基类 带有一个虚函数的类 带有一个虚基类的类 下面会分析四种情况 带有默认构造函数的成员类对象 class Foo { public: Foo() { printf("%s\n", __func__); } }; class Bar { public: // 生成默认构造 Foo foo; // 将 Bar::foo 初始化是编译器的责任 char *str; // str初始化要让程序员来做 }; // 可能的实现 // inline Bar::Bar() { foo.Foo::...

写在前面 这部分内容主要是一个引子, 包含以下经典的问题, 介绍了 C++在对象模型这方面的设计与演进. 数据成员和成员函数的内存布局 虚函数的内存布局 继承模型, 父类和子类的内存布局 C++对象模型 两种类数据成员: 静态. 非静态 三种类成员函数: 静态 非静态 虚 几种模型 简单对象模型: 一个对象是一系列的槽(slot), 每个 slot 指向一个成员, 成员按照其声明顺序各被指定一个 slot, 每个成员(数据/函数)都有自己的 slot; 表格驱动对象模型: 把所有与成员相关的信息抽取出来, 放在一个数据成员表和成员函数表中, 类对象本身内含指向这两个表格的指针. 成员...

写在前面 写一下刷题中常用的 C++ 算法库函数 sort(), lower_bound()等函数以及优先队列等需要自己定制比较规则的方法. #include <algorithm> utils 输出 template <typename T> // nd-array can use this ostream& operator<<(ostream& os, const vector<T>& v) { for (auto i : v) os << i << " "; return os << '\n'; } void print_...

前置知识 基本贪心问题 难点在于找到能使结果一直逼近最优的一种方法(路径), 然后不断重复找到全局最优. (个人理解) 455. 分发饼干; class Solution { // 直观但是 O(N^2) public: int findContentChildren(vector<int>& g, vector<int>& s) { if (s.empty()) return 0; sort(g.begin(), g.end()); sort(s.begin(), s.end()); int n = s.size(), ans{}; bool use...

写在前面 Ubuntu 20.04 x86_64 gdb: 9.2 总结一下 C/C++ 代码调试的艺术, 这本书讲了 gdb 和 vc 的调试方法, 虽然有一些小错误, 但是不影响看, 突击面试确实是很方便的. 啃文档的话可以, 不过时间来不及了, 虽然技术是要慢慢沉淀的… 当然我还看了 软件调试的艺术 这本书, 中外作者的文笔还是有所不同的.. gdb 主要功能 总览: 支持的功能 描述 命令 断点管理 设置断点, 查看断点, 条件断点 b(break), condition 调试执行 逐语句...

写在前面 总结一波面试题 测试环境 Ubuntu+clang 之前执行 #include <iostream> using namespace std; __attribute((constructor)) void before() { // C cout << "before main 1\n"; } int a = []() { // C++ 11 cout << "before main 2\n"; return 0; }(); int t1() { cout << "before main 3\n"; return 1; } static int p1 = t1()...