一、栈和队列
1、栈，队列设计题
剑指 Offer 09. 用两个栈实现队列
class CQueue {
public:
CQueue() {
}
void appendTail(int value) {
stk1.push(value);
}
int deleteHead() {
if(stk2.empty()){
while(!stk1.empty()){
stk2.push(stk1.top());
stk1.pop();
}
}
if(!stk2.empty()){
int value = stk2.top();
stk2.pop();
return value;
}
return -1;
}
private:
stack<int> stk1,stk2;
};
剑指 Offer 30. 包含min函数的栈
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
minStk.push(INT_MAX);
}
void push(int x) {
stk.push(x);
minStk.push(std::min(minStk.top(),x));
}
void pop() {
stk.pop();
minStk.pop();
}
int top() {
if(!stk.empty()) return stk.top();
return -1;
}
int min() {
return minStk.top();
}
private:
stack<int> stk,minStk;
};
622. 设计循环队列
class MyCircularQueue {
public:
MyCircularQueue(int k) {
len=k;
circularQueue.clear();
}
bool enQueue(int value) {
if(isFull()){
return false;
}
circularQueue.push_back(value);
return true;
}
bool deQueue() {
if(isEmpty()){
return false;
}
circularQueue.erase(circularQueue.begin());
return true;
}
int Front() {
if(isEmpty()){
return -1;
}
return circularQueue.front();
}
int Rear() {
if(isEmpty()){
return -1;
}
return circularQueue.back();
}
bool isEmpty() {
if(circularQueue.size()==0){
return true;
}else{
return false;
}
}
bool isFull() {
if(circularQueue.size()==len){
return true;
}else{
return false;
}
}
private:
int len;
vector<int> circularQueue;
};
2、单调栈
739. 每日温度
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
stack<int> stk;
vector<int> res(n);
for(int i=0;i<n;++i){
while(!stk.empty()&&temperatures[stk.top()]<temperatures[i]){
int prev = stk.top();
stk.pop();
res[prev] = i-prev;
}
stk.push(i);
}
return res;
}
316. 去除重复字母
用string模拟stack
string removeDuplicateLetters(string s) {
vector<int> nums(26),visited(26);
for(auto &ch:s){
nums[ch-'a']++;
}
string stk;
for(auto &ch:s){
if(!visited[ch-'a']){
while(!stk.empty()&&stk.back()>ch){
if(nums[stk.back()-'a']>0){
visited[stk.back()-'a']=0;
stk.pop_back();
}else{
break;
}
}
visited[ch-'a']=1;
stk.push_back(ch);
}
nums[ch-'a']--;
}
return stk;
}
3、单调队列
239. 滑动窗口最大值
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> dq;
for(int i=0;i<nums.size();++i){
while(!dq.empty()&&i-dq.front()+1>k) dq.pop_front();
while(!dq.empty()&&nums[dq.back()]<=nums[i]) dq.pop_back();
dq.push_back(i);
if(i-k+1>=0) res.push_back(nums[dq.front()]);
}
return res;
}
4、树的遍历，DFS，BFS
二、字符串
1、数据转换
468. 验证IP地址
vector<string> split(string IP,char si
vector<string> res;
stringstream ss(IP);
string str;
while(getline(ss,str,sign)){
res.push_back(str);
}
if(!IP.empty()&&IP.back()==sign){
res.push_back({});
}
return res;
}
string checkIPv4(vector<string> &segs)
for(auto &seg:segs){
if(seg.size()<=0||seg.size()>3
if(seg.size()>1 && seg[0]=='0'
size_t p;
try{
int num = stoi(seg,&p,10);
if(p!=seg.size()||num>255)
}catch(...){
return "Neither";
}
}
return "IPv4";
}
string checkIPv6(vector<string> &segs)
for(auto &seg:segs){
if(seg.size()<=0||seg.size()>4
size_t p;
try{
int num = stoi(seg,&p,16);
if(p!=seg.size()) return "
}catch(...){
return "Neither";
}
}
return "IPv6";
}
string validIPAddress(string IP) {
vector<string> segs;
segs = split(IP,'.');
if(segs.size()==4){
return checkIPv4(segs);
}
segs = split(IP,':');
if(segs.size()==8){
return checkIPv6(segs);
}
return "Neither";
}
2、重构
剑指 Offer 58 - I. 翻转单词顺序
sstream做法
string reverseWords(string s) {
string str;
stringstream ss(s);
stack<string> stk;
while(ss>>str){
stk.push(str);
stk.push(" ");
}
if(!stk.empty()){
stk.pop();
}
str="";
while(!stk.empty()){
str+=stk.top();
stk.pop();
}
return str;
}
双指针
string reverseWords(string s) {
string res;
int n = s.size();
if(n==0) return res;
int r=n-1;
while(r>=0){
while(r>=0&&s[r]==' ') r--;
if(r<0) break;
int l=r;
while(l>=0&&s[l]!=' ') l--;
res+=s.substr(l+1,r-l);
res+=" ";
r=l;
}
if(!res.empty()){
res.pop_back();
}
return res;
}
剑指 Offer 58 - II. 左旋转字符串
string reverseLeftWords(string s, int n) {
int len = s.size();
s+=s;
return s.substr(n,len);
}
767. 重构字符串
为什么std::priority_queue有一个构造函数接受Compare类型对象作为参数？
string reorganizeString(string s) {
int len = s.size();
if(len<2) return s;
vector<int> nums(26);
int maxC=0;
for(auto &ch:s){
nums[ch-'a']++;
maxC = max(maxC,nums[ch-'a']);
}
if(maxC>(len+1)/2) return "";
auto cmp = [&](const char& ch1,const char& ch2){
return nums[ch1-'a']<nums[ch2-'a'];
};
priority_queue<char,vector<char>,decltype(cmp)> heap(cmp);
for(char ch='a';ch<='z';++ch){
if(nums[ch-'a'])
heap.push(ch);
}
string res;
while(heap.size()>1){
char ch1 = heap.top();heap.pop();nums[ch1-'a']--;
char ch2 = heap.top();heap.pop();nums[ch2-'a']--;
if(nums[ch1-'a']) heap.push(ch1);
if(nums[ch2-'a']) heap.push(ch2);
res.push_back(ch1);
res.push_back(ch2);
}
if(heap.size()==1){
char ch = heap.top();
res.push_back(ch);
}
return res;
}
三、查找
1、一般查找
剑指 Offer 03. 数组中重复的数字
//遍历中，第一次遇到数字 x 时，将其交换至索引 x 处；而当第二次遇到数字 x 时，一定有 nums[x] = x ，此时即可得到一组重复数字。
int findRepeatNumber(vector<int>& nums) {
int n = nums.size();
for(int i=0;i<n;++i){
while(nums[i]!=i){
if(nums[i]==nums[nums[i]]) return nums[i];
swap(nums[i],nums[nums[i]]);
}
}
return -1;
}
int findRepeatNumber(vector<int>& nums) {
unordered_map<int, bool> map;
for(int num : nums) {
if(map[num]) return num;
map[num] = true;
}
return -1;
}
剑指 Offer 04. 二维数组中的查找
//矩阵逆时针旋转 45° ，并将其转化为二叉搜索树
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if(matrix.size()==0) return false;
int x = 0,y = matrix[0].size()-1;
while(x<matrix.size()&&y>=0){
if(matrix[x][y]>target){
--y;
}else if(matrix[x][y]<target){
++x;
}else{
return true;
}
}
return false;
}
剑指 Offer 50. 第一个只出现一次的字符
char firstUniqChar(string s) {
unordered_map<char,int> hash;
for(auto&ch:s){
hash[ch]++;
}
for(auto&ch:s){
if(hash[ch]==1) return ch;
}
return ' ';
}
2、二分
二分搜索算法，传入前向迭代器或随机访问迭代器（random-access iterator），要求序列中的元素已经是有序的。通过小于运算符（<）或 comp 比较操作实现比较。
在从小到大的排序数组中，
//从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
lower_bound(begin,end,num); //第一个大于或等于
//从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound(begin,end,num); //第一个大于
在从大到小的排序数组中，重载lower_bound()和upper_bound()
//从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
lower_bound(begin,end,num,greater<type>());//第一个小于或等于
//从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound(begin,end,num,greater<type>());//第一个小于
equal_range(beg, end, val); // 返回一个 pair，其 first 成员是 lower_bound 返回的迭代器，其 second 成员是 upper_bound 返回的迭代器
//例nums = {3,7,7,8,8,10},target = 8;则返回[3,4]
return{bounds.first - nums.begin(), bounds.second - nums.begin() - 1};
binary_search(beg, end, val); // 返回一个 bool 值，指出序列中是否包含等于 val 的元素。对于两个值 x 和 y，当 x 不小于 y 且 y 也不小于 x 时，认为它们相等。
剑指 Offer 53 - I. 在排序数组中查找数字 I
int search(vector<int>& nums, int target) {
int n = nums.size();
if(nums.size()==0) return 0;
int l=0,r = n-1;
while(l<r){
int mid = (l+r)>>1;
if(target<=nums[mid]) r = mid;
else l = mid+1;
}
if(nums[l]!=target){
return 0;
}
int st = l;
l=0,r = n-1;
while(l<r){
int mid = (l+r+1)>>1;
if(target>=nums[mid]) l = mid;
else r = mid-1;
}
return l-st+1;
}
剑指 Offer 53 - II. 0～n-1中缺失的数字
int missingNumber(vector<int>& nums) {
int l=0,r = nums.size()-1;
while(l<=r){
int mid = (l+r)>>1;
if(nums[mid]==mid){
l = mid+1;
}else{
r = mid-1;
}
}
return l;
}
剑指 Offer 11. 旋转数组的最小数字
int minArray(vector<int>& numbers) {
int n = numbers.size();
if(n==0) return -1;
int l = 0,r = n-1;
while(l<r){
int mid = (l+r)>>1;
if(numbers[mid]>numbers[r]){
l = mid+1;
}else if(numbers[mid]<numbers[r]){
r = mid;
}else{
int x = l;
for(int i=l+1;i<=r;++i){
if(numbers[i]<numbers[x]) x = i;
}
return numbers[x];
}
}
return numbers[l];
}
74. 搜索二维矩阵
由于每行的第一个元素大于前一行的最后一个元素，且每行元素是升序的，所以每行的第一个元素大于前一行的第一个元素，因此矩阵第一列的元素是升序的。
我们可以对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。
bool searchMatrix(vector<vector<int>>& matrix, int target) {
auto row = upper_bound(matrix.begin(),matrix.end(),target,[](int a,vector<int>&b){
return a<b[0];
});
if(row==matrix.begin()){
return false;
}
--row;
return binary_search(row->begin(),row->end(),target);
}
209. 长度最小的子数组
二分+前缀和
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
vector<int> sum(n+1);
for(int i=1;i<=n;++i){
sum[i] = sum[i-1]+nums[i-1];
}
int res = INT_MAX;
for(int i=1;i<=n;++i){
auto bound = lower_bound(sum.begin(),sum.end(),target+sum[i-1]);
if(bound!=sum.end()){
res = min(res,static_cast<int>(bound-sum.begin())-i+1);
}
}
return res==INT_MAX ? 0:res;
}
300. 最长递增子序列
贪心+二分
3、并查集
(1)朴素并查集：
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
(2)维护size的并查集：
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集：
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
836. 合并集合
837.连通块中点的数量
四、排序
912. 排序数组
快排
void quickSort(vector<int>& nums,int l,int r){
if(l>=r) return ;
int i=l-1,j=r+1,x=nums[l+r>>1];
while(i<j){
do i++;while(nums[i]<x);
do j--;while(nums[j]>x);
if(i<j) swap(nums[i],nums[j]);
}
quickSort(nums,l,j);
quickSort(nums,j+1,r);
}
归并
void mergeSort(vector<int>& nums,vector<int>& temp, int l,int r){
if(l>=r) return ;
int mid = (l+r)>>1;
mergeSort(nums,temp,l,mid);
mergeSort(nums,temp,mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r){
if(nums[i]<=nums[j]) temp[k++] = nums[i++];
else temp[k++] = nums[j++];
}
while(i<=mid) temp[k++] = nums[i++];
while(j<=r) temp[k++] = nums[j++];
for(int i=l;i<=r;++i){
nums[i] = temp[i];
}
}
堆排
//调整以u为根节点的堆
void heapAdjust(vector<int>& nums,int u,int n){
int maxIdx = u;
int l = 2*maxIdx+1, r = 2*maxIdx+2;
if(l<n&&nums[l]>nums[maxIdx]) maxIdx = l;
if(r<n&&nums[r]>nums[maxIdx]) maxIdx = r;
if(maxIdx!=u){
swap(nums[maxIdx],nums[u]);
heapAdjust(nums,maxIdx,n);
}
}
void heapBuild(vector<int>& nums){
for(int i=nums.size()-1;i>=0;i--){
heapAdjust(nums,i,nums.size());
}
}
void heapSort(vector<int>& nums){
heapBuild(nums);
int n = nums.size();
for(int i=n-1;i>0;i--){
swap(nums[i],nums[0]);
n--;
heapAdjust(nums,0,n);
}
}
剑指 Offer 40. 最小的k个数
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> res;
if(k>arr.size()||k==0) return res;
priority_queue<int> heap;
for(int i=0;i<k;++i){
heap.push(arr[i]);
}
for(int i=k;i<arr.size();i++){
if(arr[i]<heap.top()){
heap.pop();
heap.push(arr[i]);
}
}
while(!heap.empty()){
res.push_back(heap.top());
heap.pop();
}
return res;
剑指 Offer 41. 数据流中的中位数
class MedianFinder {
public:
MedianFinder() {
count = 0;
}
void addNum(int num) {
if(++count%2==1){
lheap.push(num);
rheap.push(lheap.top());
lheap.pop();
}else{
rheap.push(num);
lheap.push(rheap.top());
rheap.pop();
}
}
double findMedian() {
if(count%2==1){
return static_cast<double>(rheap.top());
}else{
return static_cast<double>(lheap.top()+rheap.top())/2;
}
}
private:
int count;
priority_queue<int,vector<int>,less<int>> lheap;
priority_queue<int,vector<int>,greater<int>> rheap;
};
剑指 Offer 45. 把数组排成最小的数
string minNumber(vector<int>& nums) {
vector<string> strs;
for(auto &e:nums){
strs.push_back(to_string(e));
}
sort(strs.begin(),strs.end(),[](const string &a,const string &b){
return a+b<b+a;
});
string s;
for(auto &str:strs){
s+=str;
}
return s;
剑指 Offer 61. 扑克牌中的顺子
bool isStraight(vector<int>& nums) {
int n = nums.size();
if(n<5) return false;
sort(nums.begin(),nums.end());
int count_0 = 0,count_1 = 0;
for(int i=0;i<n-1;++i){
if(nums[i]==0) ++count_0;
else if(nums[i]==nums[i+1]) return false;
else{
count_1+=nums[i+1]-nums[i]-1;
}
}
return count_0>=count_1;
}
五、链表
链表结构
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
//节点结构体
struct LinkNode
{
void * data;
struct LinkNode * next;
};
//链表结构体
struct LList
{
struct LinkNode pHeader;
int m_size;
};
插入
//头插
ListNode *head = nullptr;
ListNode* node = new ListNode(val,head);
head = node;
//尾插
ListNode *dummy = new ListNode(-1);
ListNode *curr = dummy;
ListNode* node = new ListNode(val);
curr->next = node;
curr = curr->next;
剑指 Offer 06. 从尾到头打印链表
vector<int> reversePrint(ListNode* head) {
vector<int> res;
stack<ListNode*> stk;
ListNode* curr = head;
while(curr){
stk.push(curr);
curr = curr->next;
}
while(!stk.empty()){
res.push_back(stk.top()->val);
stk.pop();
}
return res;
}
剑指 Offer 24. 反转链表
递归版：
ListNode* reverseList(ListNode* head) {
if(head==nullptr||head->next==nullptr) return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
迭代版
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while(curr){
ListNode* node = curr->next;
curr->next = prev;
prev = curr;
curr = node;
}
return prev;
}
剑指 Offer 35. 复杂链表的复制
Node* copyRandomList(Node* head) {
if(head==nullptr) return head;
unordered_map<Node*,Node*> hash;
Node* curr = head;
while(curr){
hash[curr] = new Node(curr->val);
curr = curr->next;
}
curr = head;
while(curr){
hash[curr]->next = hash[curr->next];
hash[curr]->random = hash[curr->random];
curr = curr->next;
}
return hash[head];
}
25. K 个一组翻转链表
不足k个不翻转
pair<ListNode*,ListNode*> reverseList(ListNode* head,ListNo
ListNode* prev = tail->next;
ListNode* curr = head;
//终止条件
while(prev!=tail){
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return {tail,head};
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(-1,head);
ListNode* prev = dummy;
while(head){
ListNode* tail = prev;
for(int i=0;i<k;++i){
if(tail->next==nullptr){
return dummy->next;
}
tail = tail->next;
}
ListNode* next = tail->next;
auto rList = reverseList(head,tail);
head = rList.first;
tail = rList.second;
prev->next = head;
tail->next = next;
prev = tail;
head = tail->next;
}
return dummy->next;
}
不足k个也翻转
pair<ListNode*,ListNode*> reverseList(ListNode* head,ListNode* tail
ListNode* prev = tail->next;
ListNode* curr = head;
//终止条件
while(prev!=tail){
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return {tail,head};
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(-1,head);
ListNode* prev = dummy;
while(head){
ListNode* tail = prev;
for(int i=0;i<k;++i){
//-----------------不足k个也反转--------
if(tail->next==nullptr){
auto rList = reverseList(head,tail);
prev->next = rList.first;
return dummy->next;
}
//------------------------------------
tail = tail->next;
}
ListNode* next = tail->next;
auto rList = reverseList(head,tail);
head = rList.first;
tail = rList.second;
prev->next = head;
tail->next = next;
prev = tail;
head = tail->next;
}
return dummy->next;
}
2. 两数相加
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2
ListNode* dummy = new ListNode();
ListNode* curr = dummy;
int c = 0;
while(l1||l2||c!=0){
int a = l1? l1->val:0;
int b = l2? l2->val:0;
int sum = a+b+c;
c = sum/10;
sum = sum%10;
ListNode* node = new ListNode(sum);
curr->next = node;
curr = curr->next;
if(l1) l1 = l1->next;
if(l2) l2 = l2->next;
}
return dummy->next;
}
445. 两数相加 II
栈+头插
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> stk1,stk2;
while(l1){
stk1.push(l1->val);
l1 = l1->next;
}
while(l2){
stk2.push(l2->val);
l2 = l2->next;
}
int c=0;
ListNode* head = nullptr;
while(!stk1.empty()||!stk2.empty()||c!=0){
int a = stk1.empty()? 0:stk1.top();
int b = stk2.empty()? 0:stk2.top();
int sum = a+b+c;
c = sum/10;
sum = sum%10;
ListNode* node = new ListNode(sum,head);
head = node;
if(!stk1.empty()) stk1.pop();
if(!stk2.empty()) stk2.pop();
}
return head;
}
83. 删除排序链表中的重复元素
使每个元素只出现一次
ListNode* deleteDuplicates(ListNode* head) {
ListNode* dummy = new ListNode(-101,head);
ListNode* prev = dummy;
while(prev&&prev->next){
ListNode* curr = prev->next;
if(curr->next==nullptr||curr->val!=curr->next->val){
prev = curr;
}else{
while(curr->next&&curr->val==curr->next->val){
curr = curr->next;
prev->next = curr;
}
}
}
return dummy->next;
}
82. 删除排序链表中的重复元素 II
重复的全部删除
ListNode* deleteDuplicates(ListNode* head) {
ListNode* dummy = new ListNode(-101,head);
ListNode* prev = dummy;
while(prev&&prev->next){
ListNode* curr = prev->next;
if(curr->next==nullptr||curr->val!=curr->next->val){
prev = curr;
}else{
while(curr->next&&curr->val==curr->next->val){
curr = curr->next;
prev->next = curr->next;
}
}
}
return dummy->next;
}
24. 两两交换链表中的节点
ListNode* swapPairs(ListNode* head) {
if(head==nullptr||head->next==nullptr) return head;
ListNode* newHead = head->next;
head->next = swapPairs(newHead->next);
newHead->next = head;
return newHead;
}
109. 有序链表转换二叉搜索树
ListNode* getMid(ListNode* head, ListNode* tail){
ListNode* fast = head;
ListNode* slow = head;
while(fast!=tail && fast->next!=tail){
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
TreeNode* buildTree(ListNode* head,ListNode* tail){
if(head==tail) return nullptr;
ListNode* node = getMid(head,tail);
TreeNode* root = new TreeNode(node->val);
root->left = buildTree(head,node);
root->right = buildTree(node->next,tail);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
return buildTree(head,nullptr);
}
六、双指针和滑动窗口
1、链表相关
剑指 Offer 18. 删除链表的节点
剑指 Offer 22. 链表中倒数第k个节点
19. 删除链表的倒数第 N 个结点
剑指 Offer 25. 合并两个排序的链表
剑指 Offer 52. 两个链表的第一个公共节点
141. 环形链表
142. 环形链表 II
328. 奇偶链表
2、数组字符串相关
剑指 Offer 05. 替换空格
344. 反转字符串
3. 无重复字符的最长子串
209. 长度最小的子数组
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int res = INT_MAX;
int st=0,ed=0,sum=0;
while(ed<n){
sum+=nums[ed];
while(sum>=target){
res = min(res,ed-st+1);
sum-=nums[st];
st++;
}
ed++;
}
return res==INT_MAX ? 0:res;
}
七、树
144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
102. 二叉树的层序遍历
103. 二叉树的锯齿形层序遍历
589. N 叉树的前序遍历
235. 二叉搜索树的最近公共祖先
111. 二叉树的最小深度
104. 二叉树的最大深度
572. 另一棵树的子树
剑指 Offer 26. 树的子结构
剑指 Offer 27. 二叉树的镜像
剑指 Offer 28. 对称的二叉树
八、搜索和回溯
1、树相关
257. 二叉树的所有路径
129. 求根节点到叶节点数字之和
834. 树中距离之和
112. 路径总和
113. 路径总和 II
437. 路径总和 III
2、数字相关
93. 复原 IP 地址
九、动态规划
5. 最长回文子串
300. 最长递增子序列
十、分治
十一、位运算
十二、数学与模拟
十三、贪心
1、区间问题
905. 区间选点
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int main(){
int n;
cin>>n;
vector<PII> segs(n);
for(int i=0;i<n;++i){
cin>>segs[i].first>>segs[i].second;
}
sort(segs.begin(),segs.end(),[](PII& a,PII& b){
return a.second<b.second;
});
int res=0,ed = -2e9;
for(auto &seg:segs){
if(seg.first>ed){
res++;
ed = seg.second;
}
}
cout<<res<<endl;
}
908. 最大不相交区间数量
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int main(){
int n;
cin>>n;
vector<PII> segs(n);
for(int i=0;i<n;++i){
cin>>segs[i].first>>segs[i].second;
}
sort(segs.begin(),segs.end(),[](PII& a,PII& b){
return a.second<b.second;
});
int res=0,ed = -2e9;
for(auto &seg:segs){
if(seg.first>ed){
res++;
ed = seg.second;
}
}
cout<<res<<endl;
}
