目录
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，即使覆盖了一只手的手套颜色的数量，也可能会使另外一只手的手套匹配不上的问题。
代码如下：
代码语言：javascript复制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
思路分析
要匹配字符串，有以下三种情况：
①它是字符，并且相等。那么就直接往下走。
②它是'?',问号可以跟任何字符匹配。那么直接往下走。
③它是'*'，星号有三种情况：
⭐它没得匹配，即已经走完，这个星号不需要匹配任何字符。 ⭐它只需要匹配一个字符，那么直接往下走。 ⭐它需要匹配很多个字符，那么这个字符串不需要往下走，需要匹配的字符串往下走。
往下走即使用回溯，即递归算法。
代码语言：javascript复制#include <iostream>
#include <string>
using namespace std;
bool strMach(const char* parten, const char* str)
{
if (*parten == ' ' && *str == ' ')
{
return true;
}
if (*parten == ' ' || *str == ' ')
{
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;
}
