算法问题(三)-删数问题

题目描述：

键盘输入一个高精度的正整数n, 去掉任意ｓ个数字后剩下的数字按原左右次序将组成一个新的正整数。

编程对给定的n和s，寻找一种方案，使得剩下的数最小

示例：

输入文件示例

178543

4

输出文件示例

13

解析：

首先确定输入的数有几位数，这里是6位数，需要删除4位，那么输出的数就还剩2位

第1位的确定：从原数中倒数第2位从左到右开始，寻找最小的

第2位的确定：从原数中倒数第1为从左到右开始，寻找最小的（此时已删除已找到的第1位数）

代码：

//删数问题
//P112 4-11
//2015年11月12日 16:30:27

#include <iostream>
#include <fstream>//读文件
#include <string>
#include <sstream>//过滤
#include <vector>
#include <algorithm>//提供反转方法
using namespace std;

string* readFile(string*);//读取文件
void changeToVector(vector<int> &, string *, int &);//将字符串中的数字放在vector中，以便操作
void findMin(vector<int> &, vector<int> &, int &);
int main()
{
	string theText[2];
	string* s = readFile(theText);
	if(s == NULL)
		return -1;
	vector<int> oldNum;//没有找时的向量
	vector<int> newNum;//找出最小数的向量
	int k;//需要删除数的个数
	changeToVector(oldNum, s, k);//改变向量
	findMin(oldNum, newNum, k);//改变向量，这里也可以不改变
	return 0;
}

void findMin(vector<int> &oldNum, vector<int> &newNum, int &k)
{
	int leftNum = oldNum.size() - k - 1;//删除数之后还剩下多少个数，-1是因为在oldNum[0]处，添加了0
	int min;//序列中最小数的位置

	while(leftNum > 0)
	{
		min = oldNum.size() - 1;
		for(int i = min; i >= leftNum; i--)//找出最小位置
			if(oldNum[min] > oldNum[i])
				min = i;
		newNum.push_back(oldNum[min]);//将找出的元素放在newNum向量中
		leftNum--;//还需要找的个数减少
		for(int i = oldNum.size() - 1; i >= min; i--)//将最小位置之后的全部删除
			oldNum.pop_back();
	}
	/*找到最少数*/
	for(int i = 0; i < newNum.size(); i++)
		cout<<newNum[i];
	cout<<endl;
}

void changeToVector(vector<int> &oldNum, string *s, int &k)
{
	/*
	stringstream可以吞下任何类型，根据实际需要吐出不同的类型
	相当于一个过滤器
	*/
	stringstream *ss = new stringstream[s[0].size()];

	for(int i = 0, temp = 0; i < s[0].size(); i++)
	{
		ss[i]<<s[0][i];
		ss[i]>>temp;
		oldNum.push_back(temp);
	}
	oldNum.push_back(0);//在oldNum的尾部添加一个元素0，反转之后成为第0个元素，便于操作
	reverse(oldNum.begin(),oldNum.end());//反转向量

	/*将字符串中的代表需要删除几个数字的字符串，放在整型变量中*/
	stringstream ss2;
	ss2<<s[1];
	ss2>>k;
}

string* readFile(string* theText)
{
	ifstream in("input.txt");

	string line;
	int lineNumber = 0;
	if(in)
		while(getline(in, line))//只有两行，所以只有两个判断
		{
			if(lineNumber == 0)
				theText[0] = line;
			if(lineNumber == 1)
				theText[1] = line;
			lineNumber++;
		}
	else
	{
		cout<<"没有文件可供读取"<<endl;
		return NULL;
	}
	return theText;
}

这个代码中写得太乱了，而且有些地方是不够正确/规范的。

比如：

改变changeToVector函数中（此函数的作用是想向量中输入从文本中读取到的数据，并改变向量的方向）

这里用到了<sstream>中的方法。

示例：

int main()
{
    string s = "123";
    int i;
    stringstream stream;
    stream << s; stream >> i;
    cout<<i<<endl;
    return 0;
}

这里相当于提供了一个过滤器的作用。

在删除数的程序中，也用到了这样的方法，但是我定义了多个stringstream的对象，其实

更合理的情况应该为使用stream.clear()对其内容进行情况，因为如果构造多个的话，构造和析构都会浪费时间。