习题一：子序列
题目描述：输入两个字符串s和t，判断是否可以从t中删除0个或多个字符（其他字符顺序不变），得到字符串s。例如，abcde可以得到bce，但无法得到dc.
第一思路（实际上是错误的）：依次判断子字符串的各个字符（这里是b,c,e）处在字符串(abcde)中的位置，如果不存在就直接判定不能得到，如果位置情况b<c<e，则说明排序顺序无误，就可以得到。
代码如下：
#include<iostream>
#include<sstream>
#include<string>
#include <iomanip>
using namespace std;
int main(void)
{
int i,j;
int flag;
string String;
char childString[105];
while (true)
{
flag = 1;
cin >> String;
cin >> childString;
for (i = 1; i < strlen(childString); i++)
{
if (String.find(childString[i]) < String.find(childString[i - 1])|| String.find(childString[i - 1]) == string::npos)
{
flag = 0;
break;
}
}
if (flag) cout << "可以得到" << endl;
else cout << "得不到" << endl;
}
}
如图所示,abcac与cac,abcac删去ab就可以得到cac,但结果却是no。因为a出现了两次，在判定的时候a的位置要小于c的位置，就不满足我源代码的条件，但字符串里有多个a，实际上是可以组出字符串的。
第二思路（复杂思路）：依次判断子字符串的各个字符（这里是b,c,e）处在字符串(abcde)中的位置，如果不存在就直接判定不能得到，如果位置情况b<c<e，则说明排序顺序无误，如果出现了abcac出现cac的情况，会出现a<c，此时就记录下当前a的坐标，往后面循环找a，直到找到一个最小满足条件的a为止
修改后代码：
#include<iostream>
#include<sstream>
#include<string>
#include <iomanip>
using namespace std;
int main(void)
{
int i,j;
int flag;
int index,minindex;
string String;
char childString[105];
while (true)
{
flag = 0;
cin >> childString;
cin >> String;
for (i = 1; i < strlen(childString); i++)
{
index=minindex = String.find(childString[i - 1]);//第一个坐标等于第一个字符出现的最小位置
if (minindex == string::npos)
{
flag = 0;
}
else if (String.find(childString[i]) > minindex)
{
minindex = String.find(childString[i], index + 1);//记录满足条件的最小坐标
flag = 1;
}
else if (String.find(childString[i]) < minindex)//如果这个字符出现的最小位置比上一个满足条件的字符位置小，那就通过循环往后面找
{
index = String.find(childString[i]);
while(index <= String.find_last_of(childString[i]))//跳出条件，找到最后一个字符为止
{
if (String.find(childString[i], index + 1) == string::npos)
{
flag = 0;
break;
}
else if (String.find(childString[i], index+1) < minindex)//如果还是不满足，就移动找字符的坐标index,一直判断为不可组成新字符串,并继续往后面找
{
index = String.find(childString[i], index+1);
flag = 0;
}
else//如果有一个满足要求，就可以不继续找字母了,同时要记录下坐标
{
minindex = String.find(childString[i], index + 1);//记录满足条件的最小坐标
flag = 1;
break;
}
}
}
if (flag == 0) break;
}
if (flag) cout << "可以得到" << endl;
else cout << "得不到" << endl;
}
}
第三思路：遍历长串，从子串第一位开始找起，看最后能在长串里找到多少个子串的字符，这样直接就不用考虑顺序问题，因为是从头遍历长串，如果比如abcac，找到c已经是第2位了，就不用了考虑第0位的a。
代码如下：#include <stdio.h>
include <string.h>
int main() {
char a[1000], b[1000];
while (scanf("%s%s", a, b)!=EOF) {
int star = 0, lenb = strlen(b), lena = strlen(a);
for (int i = 0; i < lenb; i ++) {
if (a[star] == b[i])
star ++;
if (star == lena) {
printf("Yes\n");
break;
}
}
if (star != lena)
printf("No\n");
}
return 0;
}
习题二：盒子
给定6个矩形的长和宽w和h，判断他们能否构成长方体六个面。
思路：能构成长方体必然能够两两配对，也就是说我们只需要匹配出三对相同的面即可，同时有的时候三个面相同，a和b面匹配，如果c也和a,b匹配就会出现错误，所以一旦匹配成功就要消去。
代码如下：
#include<sstream>
#include<string>
#include <iomanip>
using namespace std;
int main(void)
{
int i,j;
int width_and_height[50];
int flag;
while (true)
{
flag = 0;
for (i = 0; i < 12; i++)
cin >> width_and_height[i];
for (i = 0; i < 12 ; i=i+2)
{
for (j = i+2; j < 12 ;j=j+2)
{
if(width_and_height[i]!=0&&width_and_height[j]!=0)//一旦值为0就不参与判断
if (((width_and_height[i] == width_and_height[j]) && (width_and_height[i + 1] == width_and_height[j + 1])) || ((width_and_height[i] == width_and_height[j + 1]) && (width_and_height[i + 1] == width_and_height[j])))
{
flag++;
width_and_height[i] = width_and_height[j] = width_and_height[i + 1] = width_and_height[j + 1] = 0;//一旦匹配成功就全部赋值为0
}
}
}
if (flag == 3) cout << "有可能" << endl;
else cout << "不可能" << endl;
}
}
运行截图：
