2014-05-04 00:10
原题：
Write a function return an integer that satisfies the following conditions:
) positive integer
) no repeated digits, eg., (valid), (invalid)
) incremental digit sequence, eg., (valid) (invalid)
) the returned integer MUST be the smallest one that greater than the input. eg., input=, return= function signature could be like this:
String nextInteger(String input)
题目：请设计一个函数nextInteger()，以字符串形式的整数为输入，返回一个字符串形式的整数。要去这个整数：1. 是正整数 2. 任何数位的数字不能相同 3. 各个数位由高到低必须严格递增 4. 输出的数字必须是满足上述三条件并且比输入数大的最小的数。其实用英语描述，一个“next”就表达这个意思了。
解法：分析这三个条件，可以很快发现满足条件的数是很少的。各个位的数不能重复，并且还得保持升序，这样的话可以数位动态规划的思想找出所有的数，并进行排序。对于得到的所有符合条件的数组成的数组，进行upper_bound二分查找就能得到题目要求的数了。
代码：
// http://www.careercup.com/question?id=4857362737266688
#include <algorithm>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std; class Solution {
public:
Solution() {
generateNumbers();
}; string nextInteger(string input) {
int n1, n2;
vector<int>::iterator it;
stringstream ss; ss << input;
ss >> n1;
it = upper_bound(arr.begin(), arr.end(), n1);
if (it == arr.end()) {
n2 = n1;
} else {
n2 = *it;
} string output = to_string(n2); return output;
};
private:
vector<int> arr; void generateNumbers() {
queue<int> q;
int n, n1;
int i, d; arr.push_back();
q.push();
while (!q.empty()) {
n = q.front();
q.pop();
d = n % ;
for (i = d + ; i <= ; ++i) {
n1 = n * + i;
arr.push_back(n1);
q.push(n1);
}
}
};
};