主页

C++ snippets ostream& operator<<(ostream& os, const vector<int>& v) { for (auto i : v) os << i << " "; return os << endl; } ostream& operator<<(ostream& os, const vector<vector<int>>& v) { for (auto i : v) os << i; return os; } 入门 ...

二分-STL算法库 下面是二分查找相关的一些STL算法函数, 方便之后使用, 手写二分熟悉之后用STL刷题会更加快速. 计数: count和count_if 一般查找: find和find_if 基本二分查找: binary_search 寻找下边界: lower_bound 寻找上边界: upper_bound 寻找边界: equal_range 二分查找模板(基础版) 左闭右闭区间(常用) class Solution { public: int search(vector<int>& nums, int target) { int l{}, r = nums.size() - 1; while (l ...

找路径问题 模板题 剑指 Offer 35. 复杂链表的复制; 感觉跟下一个题很类似, 就放在这里了, 哈希记录遍历情况, 然后递归创建新节点即可(当然还有纯链表做法) class Solution { unordered_map<Node*, Node*> used; public: Node* copyRandomList(Node* head) { if (!head) return head; if (!used.count(head)) { auto node = new Node(head->val); used[head] = node; ...

写在前面 最近力扣周赛出了很多关于数字位数的题, 顾名思义, 就是对一个大整数的每一个十进制位进行操作, 由于之前对这方面的内容不太熟悉, 真正写的时候就吃亏了. 下面写一下这方面的常用的一些技巧, 例如取出任意整数的每一位等等. 取出整数的每一位 通过对10取余或者整除, 可以从个位到最高位依次得到每一个位的值, 如下: n = 12345 ans = [] while n: ans.append(n % 10) n //= 10 print(ans) # [5, 4, 3, 2, 1] 上面的是数学方法, 速度比较快, 下面是一个基于字符串的方法, 虽然慢但是直观(我初刷lc时候钟爱这种方法) n = 12345 s = str(n) ans = [i...

写在前面 最近刷LeetCode, 发现很多双百题解中用到的都是位运算技巧, 下面来总结一下位运算的常用技巧. 一开始参考了知乎的一篇回答, 里面推荐一本书叫做算法心得, 英文原版为Hackers Delight, 听这个名字就知道是一些hack技巧, 有机会一定要研读一下. 下面的代码用C++给出. 可能出现的一些数字: 48: ‘0’ 65: ‘A’ 97: ‘a’ 预备知识 首先给出一些预备知识, 包括如何进制转换等. 任意进制到十进制 // 直观的想法 int x2dec_v1(string x, int k) { int ans{}, n = x.size(); for (int i{}; i <...

可能用到的STL算法一览 前缀和计算: partial_sum 使用方法: std::partial_sum - cppreference.com; #include <numeric> #include <vector> #include <iostream> #include <iterator> #include <functional> void t1() { std::vector<int> v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}; // 或 std::vector<int>v(10, 2...

写在前面 \[\mathbb Z\\ \mathbb N +\dots+,\dots,\] 日期计算 日期替换 2437. 有效时间的数目; class Solution { public: int countTime(string time) { if (time.find('?') == string::npos) return 1; auto h1 = time[0], h2 = time[1]; auto m1 = time[3], m2 = time[4]; int ans1{}, ans2{}; // hour: if (h1 == '?') { ...

基本哈希问题 剑指 Offer 50. 第一个只出现一次的字符 - 力扣（LeetCode）; class Solution { public: char firstUniqChar(string s) { char ans{' '}; unordered_map<char, int> st; for (auto c : s) ++st[c]; for (auto c : s) if (st[c] == 1) return c; return ans; } }; // 遍历哈希表的方法 class Solution { publ...