C++
Array/Vector
二分
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
if (nums[middle] > target) {
right = middle - 1; // target 在左区间，所以[left, middle - 1]
} else if (nums[middle] < target) {
left = middle + 1; // target 在右区间，所以[middle + 1, right]
} else { // nums[middle] == target
return middle; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}
滑动窗口
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0; // 滑动窗口数值之和
int i = 0; // 滑动窗口起始位置
int subLength = 0; // 滑动窗口的长度
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
while (sum >= s) {
subLength = (j - i + 1); // 取子序列的长度
result = result < subLength ? result : subLength;
sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
}
}
// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
return result == INT32_MAX ? 0 : result;
}
最小滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最小长度（上方代码便是最小滑窗）。
while j < len(nums):
判断[i, j]是否满足条件
while 满足条件：
不断更新结果(注意在while内更新！)
i += 1 （最大程度的压缩i，使得滑窗尽可能的小）
j += 1
最大滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最大长度。
while j < len(nums):
判断[i, j]是否满足条件
while 不满足条件：
i += 1 （最保守的压缩i，一旦满足条件了就退出压缩i的过程，使得滑窗尽可能的大）
不断更新结果（注意在while外更新！）
j += 1
关键的区别在于，最大滑窗是在迭代右移右边界的过程中更新结果，而最小滑窗是在迭代右移左边界的过程中更新结果。因此虽然都是滑窗，但是两者的模板和对应的贪心思路并不一样，而真正理解后就可以在lc.76，lc.904，lc.3, lc.1004写出非常无脑的代码。
时间复杂度：O(N) 空间复杂度：O(N)
链表
定义
// 单链表
struct ListNode {
int val; // 节点上存储的元素
ListNode *next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};
删除链表元素
区分头节点和非头节点
ListNode* removeElements(ListNode* head, int val) {
// 删除头结点
while (head != NULL && head->val == val) { // 注意这里不是if
ListNode* tmp = head;
head = head->next;
delete tmp;
}
// 删除非头结点
ListNode* cur = head;
while (cur != NULL && cur->next!= NULL) {
if (cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
return head;
}
设置一个虚拟头节点
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode* cur = dummyHead;
while (cur->next != NULL) {
if(cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
head = dummyHead->next;
delete dummyHead;
return head;
}
二叉树遍历
前中后序遍历（递归简单）
// 以前序为例
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
vec.push_back(cur->val); // 中
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
层序遍历（用队列简单）
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
自定义比较函数
bool cmp(const std::pair<int, int>& p1, const std::pair<int, int>& p2) { return p1.second > p2.second; }
技巧
指向赋值看懂技巧：cur->next = cur->next->next; 把左边看成cur的连线 右边看成具体节点 即cur指向它的后面第二个节点
如果是cur->next->next = p->next; 就是把cur->next这个节点指向p->next这个具体节点 注意左边总是少看一个next 因为要做连线
STL
Vector
初始化：① vector<int> v(nums.size()); //指定大小为nums.size （详见C++提高编程笔记）
② int a[] = {2,3,1,2,4,3}; vector<int> v(a, a + sizeof(a)/sizeof(a[0])); //利用数组创建vector
③ vector<int> v(nums.size(), 0); //大小为nums.size，元素均为0
排序：sort(v.begin(), v.end());
尾插：push_back(x);
尾删：push_pop();
插入：v.insert( v.begin, a）;
删除：erase(const_iterator pos); erase(const_iterator start, const_iterator end);
清空：clear();
取头：front(); //返回容器中第一个数据元素
取尾：back(); //返回容器中最后一个数据元素
改变容器长度：resize(int num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置；若容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置；若变短，则末尾超出容器长度的元素被删除。
以vector初始化set：unordered_set<int> nums_set(nums1.begin(), nums1.end());
以set返回vector类型：return vector<int>(result_set.begin(), result_set.end()); 用set新建vector也可以
Set
set<int,greater<int>> p; //降序排列 默认就是升序
q.insert(x); q.erase(x); //删除q中的x元素,返回0或1,0表示set中不存在x q.clear(); //清空q q.empty(); //判断q是否为空，若是返回1，否则返回0 q.size(); q.find(x);
范围-based for 循环：遍历 num_set 中的每个元素，并打印出来 for (int num : num_set) cout << num << ” “; //num表示内部的元素
Map
与unordered_map区别：map有序，unordered_map查找速度快
善用auto迭代器：让编译器自动识别是什么容器(但可能会增加时间复杂度)
auto it = mp.begin();
while (it!= mp.end())
{
cout << it->first << " " << it->second << endl;
it++;
}
String
截取子串：string t = s.substr(start, len);
查找函数：str.find(“de”) str.rfind(“de”) //find是从左向右找，rfind是从右向左找
替换函数：str.replace(1, 3, “1111”); //从下标为1的位置开始替换，将三个元素替换为“1111”
比较函数：str.compare(s); // = 返回 0; > 返回 1; < 返回 -1
插入函数：str.insert(1, “aaa”); //从下标位置1开始插入
删除函数：str.erase(1, 3); //从下标位置1开始删除三个字符
交换函数：swap(s[i], s[j]);
反转函数：reverse(s.begin() + i, s.begin() + i + k);
扩充长度：s.resize(s.size() + count * 2);
将字符串转换为long long类型的整数：long long num = stoll(str);
将char数组转换为string：int startPos = 6; // 起始位置 int length = 5; // 需要转换的字符数 string str(charArray + startPos, length); // 将char数组的一部分转换成std::string类型
