对于这样一类题目：输入是一个序列或者一个集合，求出满足条件的另一个序列或者集合。
这样的问题往往可以这样分析：
- 结果中包含某个元素x
- 结果中包含某个元素x，并且按照以x开头或者结尾（适用于有序序列），或者保持某个相对顺序，像这一类问题，应该是只需要考察这几个可能出现的位置，而且考察一遍之后，不需要重复考察。但是，这一类问题的关键是需要知道什么时候考察某个元素的可能问题
下面是一个例子：
一个字符串，如果它的每个字符都不一样，那么它是unique的；如果str1可以通过将str2中的某些字符删掉而得到，那么str1是从时str2中producible的；如果str1的长度比str2的长度大，那么str1比str2美;如果他们长度一样，那么按字典循序比较大小，b比a美。给定一个字符串，求出其producible的unique的最美字符串。
#include <iostream>
#include <map>
#include <list>
#include <
string>
using namespace std;
class StringExtractor
{
public:
void ProcessInput()
{
cout<<
" Please Input one string : "<<endl;
cin>>m_SrcString;
for(
int i =
0 ;i < m_SrcString.size();i++)
{
m_CharStats[m_SrcString.at(i)].push_back(i);
}
for(
char r =
' z '; r>=
' a ';r --)
{
list<
int> t = m_CharStats[r];
if(t.size()>
0)
{
cout<<r<<
" : "<<t.size()<<endl;
m_SelectedPos[r] = -
1;
}
}
}
int Extract(
char currentChar,
char lastChar,
int lastCharPos)
{
list<
int> t = m_CharStats[currentChar];
int firstAppearance = -
1;
char smallestChar = currentChar;
list<
int>::iterator j;
for(j = t.begin(); j != t.end();j++)
{
if((*j)>lastCharPos)
{
bool matched =
true;
for(
char c = currentChar+
1;c <=
' z ';c++)
{
if((*j) < m_SelectedPos[c])
{
matched =
false;
break;
}
}
if(matched)
{
firstAppearance = *j;
break;
}
}
}
if(firstAppearance == -
1)
{
cout<<
" -1 is hit "<<endl;
firstAppearance = t.back();
m_SelectedPos[currentChar] = firstAppearance;
}
cout<<
" processing "<<currentChar<<
" at "<<firstAppearance<<
" last char is "<<lastChar<<
" at "<<lastCharPos<<endl;
m_SelectedPos[currentChar] = firstAppearance;
int posCeil = -
1;
for(
char c =
' a ';c < currentChar; c++)
{
list<
int> tt = m_CharStats[c];
if(tt.size() >
0 && m_SelectedPos[c] == -
1 && tt.back() < firstAppearance )
{
m_SelectedPos[c] = tt.back();
posCeil = tt.back();
smallestChar = c;
cout<<
" found smallest char "<<smallestChar<<
" at "<<posCeil<<endl;
break;
}
}
int posFloor = lastCharPos;
for(
char c = currentChar;c > smallestChar; c--)
{
list<
int> tt = m_CharStats[c];
if(tt.size()>
0 && m_SelectedPos[c] == -
1)
{
list<
int>::iterator it;
for(it = tt.begin(); it!= tt.end();it++)
{
if(*it>posFloor && *it<posCeil)
{
m_SelectedPos[c] = *it;
// posCeil = *it; posFloor = *it;
cout<<
" char "<<c<<
" at "<<posFloor<<
" is taken "<<endl;
break;
}
// cout<<*it<<endl; }
}
}
return firstAppearance;
}
void Extract()
{
char lastChar =
' z ';
int lastPos = -
1;
map<
int,
char> temp;
for(
char c =
' z '; c>=
' a ';c--)
{
if(m_CharStats[c].size()>
0 && m_SelectedPos[c] == -
1)
{
lastPos = Extract(c,lastChar,lastPos);
lastChar = c;
}
}
for(
char c =
' z ';c>=
' a ';c--)
{
if((m_CharStats[c].size()>
0))
{
temp[m_SelectedPos[c]] = c;
cout<<c<<
" : "<< m_SelectedPos[c]<<endl;
}
}
map<
int,
char>::iterator it;
for(it = temp.begin();it!= temp.end();it++)
{
cout<<(*it).second;
}
}
private:
string m_SrcString;
map<
char, list<
int> > m_CharStats;
map<
char,
int> m_SelectedPos;
};
int main(
int argc,
char **argv)
{
StringExtractor *extractor =
new StringExtractor();
extractor->ProcessInput();
extractor->Extract();
}
题目：
求随机数构成的数组中找到长度大于=3 的最长的等差数列, 输出等差数列由小到大:
如果没有符合条件的就输出
格式：
输入[1,3,0,5,-1,6]
输出[-1,1,3,5]
要求时间复杂度，空间复杂度尽量小。
等差数量，肯定得排序后，才好处理。 排完序后，我们就想，在上面的例子中，第一个元素在结果中会以什么样的形式出现呢？-1 如果出现的结果中，那必然是第一个元素，而后面的元素出现不出现，就完全取决于它是否在-1开头的等差数列了，也就是说入手点应该是第一个元素。如果第一个元素所有可能的等差数量都出来了，找到最长的，也不见得它就是整个数组里最长的，还得考虑其他的，但第一步考虑了最终的等差数列中包含第一个元素的了，那考察第2个元素时，就可以不用考虑第一个元素了，因为在第一步的时候就已经被充分考虑了。而考察第2个元素的时候就可以像第一个元素的过长一样了。
看下面的问题：
有两个序列a,b，大小都为n,序列元素的值任意整数，无序；
要求：通过交换a,b 中的元素，使[序列a 元素的和]与[序列b 元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];
在这个问题中，任意一个元素在最终结果中，要么在a中，要么在b中，而且必然存在于其中之一，而且如果单独考察一个元素，是无法确定它应该在哪个数组中的。 分析方法如下：
当前数组a和数组b的和之差为 A = sum(a) - sum(b)，a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
= sum(a) - sum(b) - 2 (a[i] - b[j])
= A - 2 (a[i] - b[j])
a和b的和之差应该是越小越好，也就A - 2 (a[i] - b[j]) 越小越好，对于某次选择的i,j，A是固定的，那也就是交换的两个元素的差*2后与A越接近越好。下面是C++实现代码：