关于一些通用变量的命名:
索引:index, idx
数组:arr, array
左,中,右:left, mid, right, l, m, r;
和,差,商,积:sum, diff, quot(ient), prod(uct)
邻接数组形式的bfs模板:
vector<int> visited; void bfs(vector<vector<int>> &graph, int start) { queue<int> q; q.push(start); visited[start] = 1; while(!q.empty()) { int size = q.size(); while(size-- > 0) { int cur = q.front(); q.pop(); visited[cur] = 1; for(auto nxt : graph[n]) { if(!visited[nxt]) { q.push(nxt); visited[nxt] = 1; } } } } }
数组元素循环右移n个元素的方法:
先反转开头的n个元素,再反转剩下的元素,再反转整个数组。
对一维数组vector进行首尾填充:
vector<int> nums = {1,2,3,4}; nums.insert(nums.begin(), 0); nums.push_back(5);
二叉树的中序遍历,一定是将所有结点按从小到大的顺序输出。
使用递归收集与root距离为d的结点
void collect(TreeNode *root, int d) { if(root == nullptr || d < 0) { return; } if(d == 0) { ans.push_back(root->val); } collect(root->left, d - 1); collect(root->right, d - 1); }
翻转链表:
list* reverse(list *head) { if(!head || !(head->next)) return head; list *pre = head; list *p = head->next; list *next = NULL; while(p) { next = p->next; p->next = pre; pre = p; p = next; } head->next = NULL; return pre; }
给定一个数组nums,求nums的所有排列组合,不能重复。
构造并查集时如果没有直接提供整数型编号,比如对一堆字符串建立并查集,可以先将每个字符串映射成唯一的数字,使用map<string, int>配合自增来实现。
对坐标点进行顺时针排序,参考:https://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order
涉及单链表插入问题,可以先给链表补一个空的头结点,以方便处理在头结点这前进行插入的情况。
涉及链表插入,原则一定是先补全待插入结点的指针域,再调整前后结点的指针域。
空间换时间的常用技巧:
- 记录出现次数或出现位置(哈希表可以看成是O(1)复杂度)
- 查表法(打表)
数组
- 前缀和
- 双指针
- map<int, int> count;
关于数组的数量级,一些比较微妙的点如下:
- num[i] <= 10^9,如果不涉及求和,则可以用int表示,如果涉及求和,则只能用long long
- num[i] <= 10^5,k <= 10^5,k表示数组成员个数,这里如果涉及求和,则结果就是刚好int溢出,所以只能用long long。
字符串
- 分隔字符串
- 统计单词数
- 回文
除前缀后,后缀后也是可以用的,比如:https://leetcode-cn.com/problems/shifting-letters/