目录
1.手套（贪心算法）
2.字符串通配符（回溯算法）
1.手套
题目描述：
在地下室里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手手套个数不一定相同。A先生现在要出门，所以他要去地下室选手套。但是昏暗的灯光让 他无法分辨手套的颜色，只能分辨出左右手。所以他会多拿一些手套，然后选出一双颜色相同的左右手手套。现在的问题是，他至少要拿多少只手套(左手加右 手)，才能保证一定能选出一双颜色相同的手套。 给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26，且一定存在至少一 种合法方案。
输入描述：第一行输入一个正整数n(n ≤ 1000) 第二行为n个数正整数x (x ≤ 1000)
输出描述：输出可以产生的幸运的袋子数
测试样例：
4,[0,7,1,6],[1,5,0,6]
返回：10(解释：可以左手手套取2只，右手手套取8只)
思路分析：
我们从题目中可以看到，我们需要得出一个结果就是至少要拿多少只手套。这里一般采用贪心算法。我们来分析一下：
因为在拿手套的时候，是盲拿的，拿了多少不知道，拿的是右手还是左手的也不知道。因此，我们就必须保证，在拿手套的时候，拿到的数量最起码能够覆盖左手或者右手的所有颜色！基于此再拿一只另外一只手的手套，便是我们需要的结果。
比如测试样例中，我们需要拿到覆盖左手的手套颜色那么多的数量，那就将左手手套的数量全部加起来，然后减去最少的那个颜色的数量再加一，这就是覆盖了左手的颜色可拿到至少的左手手套的数量了！然后再从右手的手套随便取一个，那么就能够保证至少有一个颜色的手套可以匹配得上。
但是要注意0数量的情况，对于0数量的颜色的手套，我们需要将其额外拿出来，因为如果一种颜色的手套，它的右手或者左手的手套数量为0，即使覆盖了一只手的手套颜色的数量，也可能会使另外一只手的手套匹配不上的问题。
代码如下：
class Gloves
{
public:int FindMininum(int n, vector<int> left, vector<int>right){int left_sum = 0, left_min = INT_MAX;int right_sum = 0, right_min = INT_MAX;int sum = 0;//用于统计另一只手的手套为零时，另一只手的手套的个数for (int i = 0; i < n; ++i){if (left[i] * right[i] == 0){sum += left[i] + right[i];//需要额外统计}else{left_sum += left[i];left_min = left_min < left[i] ? left_min : left[i];right_sum += right[i];right_min = right_min < right[i] ? right_min : right[i];}}//将它们加起来，sum + min(left_sum - left_min + 1, right_sum - right_min + 1)这一步//相当于把一只手的所有颜色的手套都拿了，然后再加个1，就是从另外一只手的手套堆取一只。//这样就必定能够至少匹配一双出来。return sum + min(left_sum - left_min + 1, right_sum - right_min + 1) + 1;}
};2.字符串通配符
题目描述：
问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。 要求： 实现如下2个通配符： *：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同） ？：匹配1个字符 注意：匹配时不区分大小写。 输入： 通配符表达式； 一组字符串。 输出： 返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
输入描述：先输入一个带有通配符的字符串，再输入一个需要匹配的字符串
输出描述：返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
样例：
输入: te？*.*
输出: txtec.cpp
返回：false
输入: te？*.*
输出: tetedsdsdc.cpp
返回：true
思路分析
要匹配字符串，有以下三种情况：
①它是字符，并且相等。那么就直接往下走。
②它是'?',问号可以跟任何字符匹配。那么直接往下走。
③它是'*'，星号有三种情况：
⭐它没得匹配，即已经走完，这个星号不需要匹配任何字符。
⭐它只需要匹配一个字符，那么直接往下走。
⭐它需要匹配很多个字符，那么这个字符串不需要往下走，需要匹配的字符串往下走。
往下走即使用回溯，即递归算法。
#include <iostream>
#include <string>
using namespace std;
bool strMach(const char* parten, const char* str)
{if (*parten == '\0' && *str == '\0'){return true;}if (*parten == '\0' || *str == '\0'){return false;}if (*parten == '?'){return strMach(parten + 1, str + 1);}else if (*parten == '*'){return strMach(parten + 1, str) || strMach(parten + 1, str + 1) || strMach(parten, str + 1);}else if (*parten == *str){return strMach(parten + 1, str + 1);}return false;
}
int main() {string parten, str;cin >> parten >> str;bool ret = strMach(parten.c_str(), str.c_str());if (ret){cout << "true" << endl;}else {cout << "false" << endl;}return 0;
}
