算法
1. 计算机编程语言是人类和计算机交流的语言工具。
2. 计算机的本质是状态机，内存里存储的所有数据构成了当前的状态；
3. 数据结构相当于告诉计算机怎么来记录当前的状态，算法相当于告诉计算机怎么根据当前的状态计算出下一个状态。
4. 空间复杂度就是你需要的必需存储的状态最多有多少；
5. 时间复杂度就是从初始状态到达最终状态中间需要多少步，这个和算法强相关，是算法关注的事情；
6. 程序在计算过程中，将问题层层分解之后，会有大量的中间过程数据，这个本质上就是记录问题的中间状态；中间过程数据就是由你设计的数据结 构来承载。
cpp性能优化
单线程下, 智能指针作为参数传递的时候没有使用引用 每次都拷贝构造 造成了额外的 性能开销 。
只要是个类型变量都可以传参，例如share_ptr
错误贪心 lc3458
class Solution {
public:
bool maxSubstringLength(string s, int k) {
unordered_map<char,int> hash;
for(auto c:s)
hash[c]++;
int cnt=0;
for(auto& [a,b]:hash)
{
if(b==1) cnt++;
}
if(cnt>=k) return true;
else return false;
}
};
正确贪心：
class Solution {
public:
bool maxSubstringLength(string s, int K) {
int n = s.size();
vector<int> pos[26];
for (int i = 0; i < n; i++) {
int c = s[i] - 'a';
pos[c].push_back(i);
}
typedef pair<int, int> pii;
vector<pii> vec;
// 枚举每一种子串
for (int i = 0; i < 26; i++) if (!pos[i].empty()) {
// 一开始先用这种字母的范围作为子串的范围
int l = pos[i][0], r = pos[i].back();
bool flag = true;
while (flag) {
flag = false;
// 检查子串里是否出现了其它字母
for (int j = 0; j < 26; j++) {
int cnt = upper_bound(pos[j].begin(), pos[j].end(), r) - lower_bound(pos[j].begin(), pos[j].end(), l);
if (cnt > 0 && cnt < pos[j].size()) {
// 有一种字母没有被完全包含，用它的范围更新子串的范围
l = min(l, pos[j][0]);
r = max(r, pos[j].back());
flag = true;
}
}
}
// 得到了这种子串里的最短子串
if (l > 0 || r < n - 1) vec.push_back({r, l});
}
// leetcode 435. 无重叠区间
sort(vec.begin(), vec.end());
int R = -1, cnt = 0;
for (pii p : vec) if (p.second > R) {
R = p.first;
cnt++;
}
return cnt >= K;
}
};