博客

线性结构

链表

单链表倒置

倒置一个不带头节点的单链表。

Node* Reverse(Node* first) {
    Node* p = first->next;//p走在最前面
    Node* q = first;//q随p后
    Node* r = NULL;//r最后
    
    while (p != NULL) {
        q->next = r;//反转操作
        
        r = q;//p，q，r都向前走一步
        q = p;
        p = p->next;
    }
    q->next = r;//最后一步反转
    return q;
}

栈

出栈序列

给定一个长度为 $n$ 的入栈序列，所有可能的出栈序列数量为：

N=C2nnn+1N=\frac{C^{n}_{2n}}{n+1}

给定一个入栈序列，判断一个序列是否为出栈序列：

如果入栈序列依次增大，例如1,2,3,4,5，如果出现大的数字，那么之后小的数字必须反过来。就像4,5,3,2,1这个出栈序列，4已经第一个出现，比它小的1,2,3是反过来的

数制转换

任务：

将一个十进制数转换为$k$进制数。

思想：

将整数$N$一直除以$k$，余数进栈，商作为下一个$N$，输出时会反着输出（因为栈）。

代码：

void baseTrans(int N, int k) {
    stack<int> s;
    while(N){
        s.push(N % k);
        N /= k;
    }
    while(!s.empty()){
        cout << s.top();
        s.pop();
    }
    cout << endl;
}

单调栈

任务：

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

分析：

单调栈就是栈中保存递增的元素，实现是，遇到一个新元素，若新元素大于栈顶，就加入新元素；若新元素小于栈顶元素，栈顶元素出栈，进行相关处理，然后一直出栈，直到栈中栈顶元素小于新元素，将新元素入栈。

在一维数组中找第一个满足某种条件的数，就是典型的单调栈应用场景

思路是，遍历每一个柱子，假设以它作为矩形的高，再找到左右两侧最近的高度小于 h 的柱子，就能找到以这个主子作为高的最大的矩形。怎么找左右两侧最近的高度小于 h 的柱子？从左从右分别遍历一遍维护单调栈来找。

字符串

KMP匹配

任务：

给定一个字符串(长度为 $n$ )和一个模式串(长度为 $m$ )，找出模式串在字符串中出现的位置，要求时间复杂度接近 O(n+m)O(n+m)

分析：

朴素的想法是字符串从前往后每个位置去匹配模式串，这样的时间复杂度为O(n∗m)O(n*m)

当中很多时候匹配失败，这些信息不应该被简单忽略，KMP尝试利用失败的匹配步骤

比如字符串匹配到位置 10 不再匹配，其实意味着位置 9 和之前的字符都匹配

如果模式串后面 3 个和最前面 3 个又相同，由相等传递，模式串的最前面 3 个和字符串最后面 3 个匹配

已经匹配的部分不用重新检查，直接向后继续匹配，这样减少了很多步骤

那么对于模式串每个位置，怎么快速找到与最前面一段相同的长度？

用 $kmp$ 数组表示每个位置对应的长度，在处理位置 $5$ 时，位置 $4$ 已经处理好了（找到了与最前面一段相同的长度），那么从位置 $4$ 指示的长度+1找起，若相同则 kmp[5]=kmp[4]+1kmp[5]=kmp[4]+1

如果不等，就从位置 $4$ 指示的最前面一段子串找起，kmp[5]=kmp[kmp[4]−1]+1kmp[5]=kmp[kmp[4]-1]+1 ，一直到找到或为 0

例子：

	0 1 2 3 4 5 6
B = a b a b a c b
P = 0 0 1 2 3 ?

位置 $4$ 指示的最前面一段子串是a b a

另外一个例子：

a b c a a b b c a b c a a b d a b
0 0 0 1 1 2 0 0 1 2 3 4 5 6 0 1 2

核心代码：

int kmp[MAX];

void pre_kmp(string P) {
	kmp[0] = 0;
	for (int i = 1; i < P.size(); ++i) {
		int k = kmp[i - 1];
		while (k > 0 && P[i] != P[k]) k = kmp[k - 1]; //如果不等，从子串找起
		if (P[i] == P[k]) kmp[i] = k + 1;
		else kmp[i] = 0;//k = 0
	}
}

int KMP(string T, string P, int pos) {
	if (T.size() - P.size() < pos) return -1;
	int i = pos, j = 0;
	while (i < T.size() && j < P.size()) {
		if (T[i] == P[j]) i++, j++;
		else if (j) j = kmp[j - 1];//已经匹配的部分不用重新检查
		else i++;
	}
	if (j == P.size()) return i - j;
	else return -1;
}

练练手？洛谷P3375 【模板】KMP字符串匹配

https://www.luogu.com.cn/problem/P3375

提示：使用C风格字符数组，输入输出用cstdio

STL?

string s = "hello world";
int index = s.find("hello");//0

STL常用容器操作

set

#include<iostream>
#include<set>
#include<string>
using namespace std;

int main() {
    set<int> s;
    pair<set<int>::iterator, bool> result = s.insert(12); // 返回一个pair，第一个元素是一个迭代器，指向插入的元素，第二个元素是一个bool值，表示是否插入成功
    cout << *result.first << " " << result.second << endl;
    cout << s.size() << endl;
    set<int>::iterator it = s.find(12); // 返回一个迭代器，指向元素12，如果没有找到，返回end()
    cout << *it << endl;
    s.erase(12);
    it = s.find(12);
    if (it == s.end()) cout << "Not found!" << endl;

    return 0;
}

C++ 11 为 STL 标准库增添了 4 种无序(哈希)容器，可以使用无序set，例如：

#include<unordered_set>
unordered_set<int> us;

其余用法与传统set一致。

map

#include<iostream>
#include<map>
#include<string>
using namespace std;

int main() {
    map<string, string> m;
    pair<map<string, string>::iterator, bool> ret = m.insert(make_pair("one", "what?")); // 返回一个pair，第一个元素是一个迭代器，指向插入的元素，第二个元素是一个bool值，表示是否插入成功
    cout << ret.first->first << " " << ret.first->second << " " << ret.second << endl;
    m["one"] = "yi";
    cout << m["one"] << endl;

    map<string, string>::iterator it = m.find("onee"); // 返回一个迭代器，指向元素，如果没有找到，返回end()
    if (it == m.end())cout << "Not found!" << endl;
    it = m.find("one");
    if (it != m.end())cout << it->first << " " << it->second << endl;

    m.erase("one");
    it = m.find("one");
    if (it == m.end())cout << "Not found!" << endl;

    return 0;
}

lower_bound/upper_bound/sort/自定义规则

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    vector<int> nums = {2,43,1,3,2,3,41,};
    sort(nums.begin(), nums.end());
    for(int i : nums) cout << i << " ";
    cout << endl;
    //upper_bound返回第一个大于x的数的位置
    cout << upper_bound(nums.begin(), nums.end(), 3) - nums.begin() << endl;
    //lower_bound返回第一个大于等于x的数的位置
    cout << lower_bound(nums.begin(), nums.end(), 3) - nums.begin() << endl;
    return 0;
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class TestObj {
public:
	int first;
	double second;
	TestObj(int f, double s) :first(f), second(s) {}
	bool operator<(const TestObj& that) const {
		return this->second < that.second;
	}
};

vector<TestObj> v;

int main() {
	for (int i = 10; i > 0 ; --i) v.push_back(TestObj(i, 1 * i * i * i - 4 * i * i + 10 * i - 100));
	for (int i = 0; i < 10; ++i) cout << v[i].first << " " << v[i].second << endl;
	cout << endl << endl;
	sort(v.begin(), v.end());
	for (int i = 0; i < 10; ++i) cout << v[i].first << " " << v[i].second << endl;
	cout << endl << endl;
	vector<TestObj> ::iterator it = lower_bound(v.begin(), v.end(), TestObj(1, -25));
	cout << it->first << " " << it->second << endl;
	it = upper_bound(v.begin(), v.end(), TestObj(1, -25));
	cout << it->first << " " << it->second << endl;

	return 0;
}
map<string, vector<record>> records;
for(auto it=records.begin(); it!=records.end(); it++){
    sort(it->second.begin(), it->second.end(), [](record a, record b){
        if(a.day != b.day) return a.day < b.day;
        if(a.hour != b.hour) return a.hour < b.hour;
        return a.minute < b.minute;
    });  // 这里的 sort 函数是一个lambda函数，用来对每个人的记录进行排序
}
sort(v1positive.begin(), v1positive.end(), greater<int>());  // 大的在前
sort(v1negative.begin(), v1negative.end(), less<int>());  // 小的在前
#define pq priority_queue<int, vector<int>, greater<int>>

其他常用方法

批量内存（数组）设置

#include<cstring>
a[123][4342][123][234];
memset(a,0,sizeof(a));
memset(a,0x3f,sizeof(a));//初始化为无穷大
memset(a,63, sizeof(a));//初始化为无穷大，与上一行效果一样

不定长输入

int a[MAX],num;
while(cin>>num) a[++N]=num;//输入EOF使用Ctrl+D

字符串与数的转换

#include<string>
int num = 1000;
string s = to_string(num);
int i = stoi(s.substr(0, 3));
double d = stod(s);

预留vector空间

vector<int> dp(1000);
vector<vector<int>> children(103, vector<int>());

读取一整行

string line;
getline(cin, line);

警告，getline很容易出现bug（因为linux与windows不同的换行标准），不要普通的 cin >> 和getline 混用

快读

inline int read()
{
    char c = getchar();int x = 0,s = 1;
    while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}//是符号
    while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}//是数字
    return x*s;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);//加速器
    int n = read();
    cout << n << endl;
    return 0;
}

分割字符串

vector<string> spilt(string str, string pattern){
    vector<string> res;
    if(pattern.empty()) return res;
    int start = 0, index = str.find_first_of(pattern, 0); 
    // find_first_of()返回第一个匹配的位置，两个参数分别是要查找的字符串和开始查找的位置
    while(index != str.npos){
        // str.nops是string类的一个静态成员，表示不存在的位置
        if(start != index){
            res.push_back(str.substr(start, index - start));
        }
        start = index + 1;
        index = str.find_first_of(pattern, start);
    }
    if(!str.substr(start).empty()){
        res.push_back(str.substr(start));
    }
    return res;
}

字符串常用方法：

#include<string>
#include<algorithm>
using namespace std;

string s = "hello world 34";
cout << isdigit(s[12]) << endl;  // 1
reverse(s.begin(), s.end());  // 反转
cout << s << endl;  // 43 dlrow olleh
cout << s.substr(3, 5) << endl;  // dlrow，从第三个char开始后的5个char

杂题思路

大部分来自力扣热题100

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。（思路：哈希表保存值和下标）

给你一个字符串数组，请你将 字母异位词（重新排列源单词的所有字母得到的一个新单词） 组合在一起。可以按任意顺序返回结果列表。（思路：哈希表保存key和对应列表，将每个字母出现的次数使用字符串表示，作为哈希表的键）

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。例如，nums = [100,4,200,1,3,2]，最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。（思路：set保存值，最后遍历一遍，请自己思考如何遍历）

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

思路：双指针，每次移动 数字较小的那个指针。

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

思路：排序，遍历第一个元素，然后双指针，一个从前向后，一个从后向前，时间复杂度 O(N2)O(N^2)

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

思路：维护一个双指针维护的滑动窗口，使用 set 来判断是否含有重复字符

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

思路：如果我们按照区间的左端点排序，那么在排完序的列表中，可以合并的区间一定是连续的。

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

思路：按照区间的右端点排序，贪心

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

思路：当我们将数组的元素向右移动 k 次后，尾部 kmodn 个元素会移动至数组头部，其余元素向后移动 kmodn 个位置。

我们以 n=7，k=3 为例进行如下展示：

  1. 原始数组 1 2 3 4 5 6 7

  2. 翻转所有元素 7 6 5 4 3 2 1

  3. 翻转 [0,kmodn−1] 区间的元素 5 6 7 4 3 2 1

  4. 翻转 [kmodn,n−1] 区间的元素 5 6 7 1 2 3 4

给你一个单链表的头节点 head ，请你判断该链表是否为 回文链表 。如果是，返回 true ；否则，返回 false 。时间复杂度 O(N)O(N)，空间复杂度O(1)O(1)（思路：反转后半部分，然后比较就行）

给你一个链表的头节点 head ，判断链表中是否有环。

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路：快慢指针

实现 LRU (最近最少使用，操作系统概念) 缓存约束的数据结构

思路：类似于Java的LinkedHashMap（看Java的Map笔记），用一个哈希表和一个双向链表维护所有在缓存中的键值对。

  • 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

  • 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表节点。

核心是在访问后将节点移到链表头（即删除该节点+在头部新增节点）

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

思路：单调栈

上一页algorithm下一页二叉树

最后更新于