竞赛常用数据结构和算法(续)

篇幅原因，这篇博客继续记录常用算法和数据结构，主要是我不知道或者容易出错的部分。

string和int，char类型的转换

string作为C++的一个类模板，提供了方便的转换函数，to_string通过重载的方式将所有类型的数值转换为string类型。此外，string可以采用类似数组访问的形式访问字符串中的每个字符，也就是string[i]，得到字符串在该位置上的字符，但是其类型并不是string，而是char类型。而stoi函数可以将string类型转换为int，并且只保留string中的整数部分，例如输入表示小数的字符串会被截断，带有其他字符的会自动忽略。

char类型作为基本的字符类型，采用八位存储，ACSII编码，因此可以看作整型int处理。也就是说，加减不同的字符常量就能对char和int进行转换，这取决于ACSII码，例如要进行数字之间的转换，那么由于’0’的ACSII编码是30，因此char转数字就是减去’0’，数字转char就是加上’0’；而对于字母来说，要得到字母在字母表中的序号，也是减去’a’或者‘A’，但是小写大写字母在ACSII编码中并不连续，因此要分情况处理。

最后，string可以和char数组转换，strnig.c_str()方法返回一个以’\0’结束符为结尾的char*指针地址，而string.data()方法则直接返回地址，并不添加结束符。而string则可以直接读取char的值，因此直接赋值即可。

另外，ACSII码的重要点也要记住，小写字母从97开始，大写字母从65开始。

总结一些具体的转换方法：

//string->int
int myint = stoi(str);

// int->string
string str = to_string(myint);

// int->char
char mychar = myint + ‘0’;
char mychar = myint + 'a';

// char->int
int myint = mychar - '0';
int myint = mychar - 'a';

//string->char*
char *mychar = string.c_str();
char *mychar = string.data();

//char*->string
string mystr = mychar;

四舍五入的实现

实现输出的四舍五入

第一是用printf函数，规定输出小数位数的同时会自动四舍五入，因此如果要在输出的时候得到四舍五入的结果直接用这个就行了。

另外还可以用的函数实现，不过这个比较麻烦，cout的同时需要先流入两个函数fixed和setprecision(x)的返回，然后才是正常的输出内容。

实现数值的四舍五入

除了自己写函数实现外，对整数能用库的函数round，这个函数会返回输入浮点数的四舍五入的整数的结果。因此如果还要进一步设置保留位数，那只能自己写了。

STL容器的遍历

使用迭代器和auto关键字最简单：

for(auto iter : slt)
{
	iter.first;
	iter.second;
}

string、map、vector也都可以直接用下标找对应元素。

较大数据

一定要注意会不会超过ll的界限，有时候可能自己调试是正确的，但是实际运算过程中数据越界了，边界条件下得出的答案并不正确，所以要注意结合问题本身考虑是不是要取模，先除后乘等操作。

二分

二分查找是常用的一种算法，但是其模板并不单一，会衍生出许多的边界问题导致最终写法不一，这里简单总结一下。

根据查找目标可以将其分为以下几类：

• 查找最大值中的最小值

• 查找最小值中的最大值

• 查找最佳值(也就是普通的目标二分查找)

三者区别在于满足条件的区间范围不一致，设l和r是二分的两端，mid是中间，如果要找最大值中的最小值，那么判断mid是否符合，如果符合则应该查找[l,mid]（因为mid可能就是最小的，但是还要看看mid前面是不是还有更小的），反之查找[mid+1,r]（因为此时mid不符合，肯定不会取到）；同理，找最小值中的最大值则是符合时查找[mid,r]，反之查找[l,mid-1]，另外，此时计算mid有所改变：mid=(l+r+1)/2，因为不加的话会导致mid==l，从而更新无效，进入死循环，例如最后一次查找[2,3]中的3；而最佳值查找则不用保存“上一个最佳的”这种信息，而且一般最佳值查找还能根据信息比较目标和mid的大小，因此不用保留mid，而是根据比较结果在[l,mid-1]和[mid+1,r]中进行查找，当mid符合时返回或者用ans保存mid的值直到l>r。

下面是模板：

//最大值中的最小值
int bf()
{
    int l,r;
    while(l < r)
    {
        int mid = (l+r)/2;
        if(check(mid) == true)
        {
            r = mid;
        }
        else
        {
            l = mid+1;
        }
    }
    return l;
}

//最小值中的最大值
int bf()
{
    int l,r;
    while(l < r)
    {
        int mid = (l + r + 1)/2;
        if(check(mid) == true)
        {
            r = mid;
        }
        else
        {
            l = mid-1;
        }
    }
    return l;
}

//查找target
int bf()
{
    int l,r;
	while(l <= r)
    {
		int mid = (r + l)/2;
		if(check(mid) > target) 
            right = mid-1;
		else if(check(mid) < target) 
            left = mid+1;
		else
        {
			return mid;
		}	
	}
}

最后关于终止条件，前两个没有用小于等于，最后一个用了，因为最后一个需要判断一次是否和target相等，这个逻辑在前面是不需要的，因此如果不用等号，无法在最后一次判断的时候查看是否找到target，非要不用的话就是在退出循环后比较一次，看看是不是找到了（此时l和r相等）。前面两个模板则是将等于的判断合并到左右区间两个判断分支中了，并且即使满足也不直接返回，而是进一步查找，如果l和r相等了，那么此时的这个值一定是边界值。

总之记住对于要找边界值的问题用前两个模板就行，最后那种模板属于常规写法，要想清楚区间如何划分，要不要接受mid继续查找，还是放弃mid，就没有问题。

贪心

说是贪心其实不是暴力，指的是将问题从局部进行考虑，用局部的选择策略来对整个问题进行解决，这个策略必须具备无后效性，也就是说策略的执行并不会影响以前的状态，只与当前的情况有关。将多个局部策略的局部最优解合并为问题的最终解，就是贪心的方法。

例如蓝桥杯2018省赛C++A组，付账问题，让n个人分别带着a[i]的钱去吃饭，最后花了S元，现在要让这些人近似AA，也就是一起凑钱付账，让每个人付的钱的标准差最小。

对这个问题考虑贪心策略，如果整体上看最优策略是每个人付总账的平均值就行，但是有些人肯定带的钱不够，所以这时就分出来两类人考虑，钱不够肯定就全部掏出来，钱够的话只需要拿出一部分。因此我们的贪心就得到了两个局部问题要解决：

• 如果这个人钱不够怎么办？
• 如果这个人钱够怎么办？

怎么判断够不够就是问题的关键了，由于要尽可能靠近平均值(让标准差最小)，显然的想法就是如果一个人钱不够平均值，那么全部拿出来付掉，此时总账减去他付掉的这部分，剩下的人再来平分这部分的钱。考虑对数组直接使用这个策略，如果前面一个人不够付钱，会导致后面的人付钱的标准”上升”，也就是说很多本来够付原始AA的钱的人现在可能不够了，那么这些人也要全部掏出来。但是我们又没法知道谁最后一个达到这个上升的标准(带的钱比新的这个标准多)，所以就先排序一次，前面的都是穷人，不断付钱，直到这个人带的钱足够付得起现在的平均标准，那么显然他后面的人比他有钱，都能付得起这个钱了，那么就让他们出这个钱就行。

总结下上面的例子，这种策略将最终的问题拆分成两个子问题，并给出两个子问题的局部最优解方法，通过遍历的方式模拟得出最后的答案；而且策略具有无后效性，每人不断付钱只会影响后面的人的付钱额度(后面的人付钱标准在变化)，而对前面的人的付钱额度没有影响(穷人不够就全部拿出来)。因此，这就是一个典型的贪心问题。

贪心问题没有固定的模板，也没有固定的解法，只是一种大体上的思想，可以在很多问题中应用。

关于子序列和双指针

很多问题会让找某个区间中符合要求的子序列，这里说的是连续的那种，而不是如最长不下降子序列那样断开的。对于连续的子序列可以采用遍历的方法进行查看，对于一维数组序列来说，左指针固定，右指针遍历区间，用O(N^2)的时间完成遍历；对于矩阵来说，则要用到两个双指针，固定列区间后还要用相同的方法遍历行区间，也就是用O(N^4)的时间完成遍历。

另外关于如何优化，如果问题的区间之间带有单调性，那么可以利用这个性质减少遍历的次数，例如对于一维序列找区间和来说，查找符合要求的子区间可以在区间达到最低要求时停止右指针，然后进入下次操作；对于二维矩阵找子矩阵和问题来说，列区间遍历的时间不能优化了，但是行区间遍历也可以用这种方法，行的下界达到临界时，回过去向下移动上界。

结构体的排序

有时需要对具有多个属性的成员根据某个属性进行排序，此时就可以使用结构体，排序通过sort函数的cmp函数指针实现，自定义排序方案。

struct student{
	int a;
    intb b;
};

bool cmp(student a, student b)
{
    return a.a<b.a;
}

int main()
{
    struct student st[3];
    sort(st,st+3,cmp);
    return 0;
}

动态规划

二维dp

这里先记录下二维dp，出自经典的dp问题：最长公共子序列，给定两个字符串text1和text2，定义子序列是字符串任意删除字符后得到的子串，也就是不要求子序列的字符在原字符串中连续，和LIS问题(最长不下降子序列)类似，现在求其中最长的公共子序列的长度。

除了暴力枚举其中的每个子序列并比较外，利用动态规划可以很简单地解决这个问题，定义$dp[i][j]$表示text1的前i个前缀和text2的前j个前缀的最长公共子序列长度，那么最终的答案就是dp的终点，现在考虑如何进行状态转移。在边界情况，如果i或者j为零，表示前0个前缀串的公共子序列，显然为0；现在对于$dp[i][j]$如何求解，用动态规划的思路考虑与前面哪个dp值有关。

要求$dp[i][j]$，现在已经知道这个状态之前的所有i，j的最长子序列长度，又因为子序列不要求连续，所以直接看现在到达的两个字符是否相等：

• 如果相等，$dp[i][j] = dp[i-1][j-1]+1$
• 如果不相等，$dp[i][j] = max(dp[i-1][j],dp[i][j-1])$

text1[i]和text[j]相等时，在前面基础上多了一个公共字符，所以直接加1就行了；不相等的时候长度没有增加，就要看这两个字符之前两个字符串的dp状态，取个最大的就行了。这样以后dp的状态就全部分析过了，可以列出方程计算，两层循环得到最后的结果。

当然这个问题可以说还用到了双指针，也就是双指针+dp。

class Solution {
public:

    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m+1,vector<int> (n+1));
        for(int i = 0; i <= m; i++)
        {
            for(int j = 0; j <= n; j++)
            {
                if(i == 0 || j == 0)
                {
                    dp[i][j] = 0;
                }
                else if(text1[i-1] == text2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};

String方法

• string.at(i)：取出下标为i的字符；
• string.substr(i,n)：从下标为i的地方取出n个字符作为字符串返回；
• string str(n,ch)：初始化字符串str为n个ch字符组成的字符串；
• string.size() / string.length()：返回字符串长度；
• string.resize(n,ch)：字符串长度改为n，不足的部分填充ch字符；
• string.erase(i,n)：删除从下标为i开始的n个字符；

Vector方法

• vector v(n,value)：初始化一个长度为n，值为value的vector；
• vector.push_back(x)：在尾部添加元素x；
• vector.pop_back()：删除最后一个元素；
• vector.clear()：清空数组；
• vector.size()：返回数组大小；

Map方法

• map.insert(pair(value1,value2))：插入一个pair到map中；
• map[value1] = value2：将键值为value1的关键值赋值为value2；
• map.find(value1)：找到键值为value1的关键值返回；
• map.erase(map.begin(), map.end())：清空元素；
• map.size()：返回map大小；

C++枚举排列

STL提供了一个能得到数组元素不同排列顺序的方法：next_permutation(stl.begin(), stl.end())，调用后会排出新的容器序列，并返回一个bool值指示还有没有没有下一个未经遍历的序列。

另外，也可以通过递归的方法进行排列遍历，有机会的话在暴力求解中再说明。

解答树

如果一个问题的解可以通过重复的步骤和步骤中多个选择的策略得到，而且这些策略可能依赖于先前的选择，可以用递归枚举法实现，它的工作方法可以用解答树描述。