一些经典的算法与模板--笔试用

很久没有写博客了，最近也是换了电脑，也就把博客迁移过来顺便写一篇博客吧

前言

最近也是金九银十的秋招季，投出去的简历也是陆陆续续受到了答复，笔试自己也要开始来准备了，总之好好抓紧吧。

笔试中，算法毫无疑问是一个大头，很多东西可能不考，唯独算法一定会考，要过第一趟笔试，算法是无法避免的，很多东西还是得多多规划总结，才没那么容易忘，所以还是写写好。

如何入手

当你拿到一道题目，首先应该按顺序干如下几件事：

看懂题目在说什么
搞明白题目需要你做什么
找到思路
写代码

某种程度上说，并不是完全按照步骤一步步做，因为从其他步骤也可能更好地入手，对这几方面大概探一下吧

题目在说什么

对于算法，我们大多数时候需要的是针对输入做一个输出，所以这个问题可以被简化为：

输入
输出
条件

重点关注以上三点就可以理解题目在说什么了

需要做什么

在明白输入输出条件后，我们还需要明白题目需要做什么，也就是所谓操作，一般来说分成如下两种：

数据处理：将抽象的数据转换为算法能够进行处理的数据结构
搜索求解：寻找问题的答案

找到思路

这一步骤可谓是最难的了，基本上也是这部分才是算法真正考验的地方，我还是大体来说一下这个思路怎么出来的过程吧（我自己的经验）

模拟：模拟问题的操作来求出结果，一般在小规模问题下做一遍也更能理解题目含义
可行解：是否能有暴力的方法能够求出，还是需要做其他文章
复杂度分析：数据总共有多少，如何去遍历，真正笔试时候还是要以求解优先，但是对于问题求解的规模是怎么样的也更能辅助你获得答案
确认算法：以上三步服务于这一步
实验：在小规模问题下实验思路的可行性

写代码

能用模板多用模板，不仅加快速度，更重要的是降低失误，对于像二分查找这种容易搞混的东西，在考场才研究+1-1这种细枝末节的东西往往花费时间，更搞乱了自己的心态，所以大体来说还是需要让自己做的更胸有成竹一些，写代码的步骤大概就是这样，少点犹豫。

输入处理成数据结构
套模板
输出

题型的模板究竟都有那些，主流的哪几类算法是怎么运作的，接下来就会大概谈谈。

算法及其模板

DFS

使用递归的回溯法

class Node{
    int val;
    vector<Node> childNodes;
}

void DFS(Node node, int steps, int n)
{
    if(steps == n) return;
    for(Node child : node.childNodes)
    {
        // 做操作
        DFS(child, steps + 1, n);  
        // 撤销操作
    }
}

BFS

相较于DFS，一般能算出最优，而且不依赖递归，更容易debug找问题，不过如果是需要记录之前的状态，它会比DFS要难写不少（需要保存）

class Node{
    int val;
    vector<Node> childNodes;
}

void BFS(Node root)
{
    queue<Node> q;
    q.push(root);
    while(!q.empty())
    {
        // 获取队头
        Node node = q.front();
        q.pop();

        for(Node child : node.childNodes)
        {
            q.push(child);
        }
    }
}

上述两种算法都可以用备忘录来优化

滑动窗口算法

因为不怎么用经常忘掉，大体来说是维护窗口，一般这类题目的特征是当序列的子串不满足条件时，序列一定不满足条件，而一般题目目的是寻找最大窗口

void SlidingWindow(string s, string t)
{
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    while(right < s.size())
    {
        char c = s[right];
        right++;
        // 更新窗口数据

        // 判断窗口左边是否需要收缩
        while (window need shrink)
        {
            char c = s[left];
            left++;
            // 更新窗口
        }
    }
}

不要倒在起点

与力扣不同，笔试的环境不一定足够好（比如不允许使用自己的IDE），总之还是需要做好一些准备的

特殊输入处理

不带次数直到结束

while(cin >> n);

根据每行获得输入

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

int main()
{
    string line;
    while(getline(cin, line))
    {
        stringstrem ss;
        ss << line;
        int tmp;
        while(ss >> tmp);
    }
}

模板类的使用

vector

构造

vector<T> v;
vector<T> v(n); // 数量为n
vector<T> v(n, val); // 数量为n，值为val

插入

v.push_back(a); // 尾部添加
v.insert(it, a); // 在迭代器的前一个位置添加

删除

v.pop_back(); // 尾部删除
v.erase(it); // 删除迭代指向
v.clear(); // 清空

常用的指向

v.front(); // 返回首元素引用
v.back(); // 返回尾元素引用
v.begin(); // 迭代器指向首元素
v.end(); // 迭代器指向

增加删除vector中下标为i的元素

v.insert(v.begin() + i, num); // 插入num
v.erase(v.begin() + i); // 删除

其他

v.size(); // 数组大小

unordered_set

初始化

unordered_set<T> set; // T不能用vector但可以用string

当你需要存储vector时可以如此操作

unordered_set<string> set;
string str = "";
for(auto a: v)
{
    str += to_string(a) + "-";
}
set.emplace(str);

添加元素

set.emplace(val);
set.insert(val); // 效率低点

查找该元素个数

set.count(key);

查找该元素引用（先确定元素个数不为０）

set.find(key);

删除元素

set.erase(val);

遍历元素

for(auto element: set)
{
    cout << element << endl;
}

其他

排序

sort从小到大排序

#include<algorithm>

vector<int> v;
sort(v.begin(), v.end()); // 升序

从大到小

sort(v.begin(), v.end(), greater<int>()); // 降序

自定义

// 根据第二个元素从小到大
bool cmp(vector<int> a, vector<int> b)
{
    return a[1] < b[1];
}

vector<vector<int>> nums;
sort(nums.begin(), nums.end(), cmp);

在类中，cmp函数要定义为static

class Solution{
public:
    static bool cmp(string a, string b)
    {
        return a.length() < b.length(); // 字符串长度升序排序
    }
    
    void Solve(vector<string>strs)
    {
        sort(strs.begin(), strs.end(), cmp);
    }
}