有道难题讨论区
higer
数终于为负了，不能cha别人的了，本次挑战宣告失败。
第一题好像需要优化，鱼头有时间把你的算法贴出来分享一下吧。
第二题重点在于字符串变换的问题，有时间大家好好讨论讨论。
第一题题目：
如果一个数字十进制表达时，不存在连续两位相同，则称之为“不重复数”。例如，105、1234和12121都是“不重复数”，而11、100和
1225不是。
给定一个long类型数字A，返回大于A的最小“不重复数”。
DEFINITION
Class:UnrepeatingNumbers
Method:getNext
Parameters:long
Returns:long
Method signature:long getNext(long A)
CONSTRAINTS
-A 取值范围是[0, 10^17]，注意是闭区间。
EXAMPLES
0)
54
Returns: 56
大于54的最小数字是55，但55不是“不重复数”。下一个数字是56，它满足条件。
1)
10
Returns: 12
2)
9
Returns: 10
3)
98
Returns: 101
99和100都不是“不重复数”，但101是。
4)
21099
Returns: 21201
第二题题目：
“回文分数”游戏并不简单。游戏的目标是修改最多maxChanges个字符使得一个字符串word的回文分数最高。只允许修改，不许增加或者删除字
符。一个字符串的回文分数定义如下：
如果字符串不是回文串，则分数为0。
如果字符串是回文串，且长度为奇数，则分数为1。
如果字符串是回文串，且长度为偶数，我们将它分为左右两半。计算它的一半子串的回文分数为K（两个一半子串得分一定相同），则原字符串的回文分数为K
+ 1。
给定一个字符串word和一个型整数maxChanges，返回最多修改maxChanges个字符后最大可能的回文分数。
DEFINITION
Class:MaximumPalindromeScore
Method:maximize
Parameters:String, int
Returns:int
Method signature:int maximize(String word, int maxChanges)
NOTES
-回文串的定义是一个字符串从前向后读和从后向前读完全一样。
CONSTRAINTS
-word包含1到50个字符（含1和50）。
-word 只包含小写字母 ('a'-'z')。
-maxChanges 取值范围是0到50（含0和50）。
EXAMPLES
0)
"coder"
2
Returns: 1
我们可以把c改成r，把e改成o，得到"rodor"。这是一个奇数长度的回文串，所以得分为1。
1)
"abcbxabcba"
1
Returns: 2
如果把x改成a，得到偶数长度的回文串"abcbaabcba"。它的一半子串是奇数长度的回文串"abcba"，所以子串分数为K = 1，因而最后
得分是K + 1 = 2。
2)
"abcdefghijklmnop"
15
Returns: 5
可以把这个字符串修改成"aaaaaaaaaaaaaaaa"、"eeeeeeeeeeeeeeee"或其他14种串，回文得分均为5。
3)
"ssssssssssssssss"
15
Returns: 5
有时不做所有允许的改变可能更好。
4)
"vyyvvzzvvxxvvxxv"
4
Returns: 3
5)
"a"
0
Returns: 1
Ziyu Yu
我的程序。。
做的太慢了，还重交了一次。。
class UnrepeatingNumbers
{
public:
long long getNext(long long A)
{
return _get(A+1);
}
//获得>=A的第一个非重复数
/*如果A是一个非重复数，直接返回。否则
A必然为 xxaaXXXX形式。
其中XXXX为非重复的。也就是说我们找第一个重复数字。那
么下一个非重复数，必然大于(xxaa+1)0000。这样就跟暴力比就大大减小了计算次
数。这就是我的基本思路。算法过system test。但成绩很烂。。。
*/
long long _get(long long A){
long long t = 1;
long long res = A;
int last = A%10;
A/=10;
while( A){
if( A%10==last){
return _get((A*10+last+1)*t);
}else{
last = A%10;
A/=10;
t*=10;
}
}
return res;
}
}
higer
看了一下鱼头的算法，的确非常精炼，效率也比较高，我之前cha别人的时候，看到别人的算法写的都比较长，这里给鱼头赞一下。
Ziyu Yu
我做得太慢了。中间又折腾好久。
higer 写道:
higer
higer
public class MaximumPalindromeScore {
public int maximize(String word, int maxChanges) {
int n=word.length();
if(isPalid(word)){
if(n%2==0){
String half=word.substring(0, n/2);
return maximize(half,maxChanges)+1;
}else{
return 1;
}
}else{
int m=n/2;
int num=0;
for(int i=0;i<m;i++){
if(word.charAt(i)!=word.charAt(n-1-i)) num++;
}
if(num>maxChanges)return 0;
else{
String half=transfer(word.substring(0, n/2));//这个部分是本题最难的地方，不知道要怎么实
现这个转换函数
return maximize(half,maxChanges-num)+1;
}
}
}
private boolean isPalid(String str){
int n=str.length();
int m=n/2;
for(int i=0;i<m;i++){
if(str.charAt(i)!=str.charAt(n-1-i)) return false;
}
return true;
}
}
Ziyu Yu
higer 写道:
Ziyu Yu
higer 写道:
Ziyu Yu
nobody
我用函数min_to_make_equal来生成一个vector<string>中的所有字符串转换成同一个字符串，所需要改变的最小字符数。
我逐步生成长度分别为word.size()/2,/4,/8的字符串，并把每奇数个字符串翻转。如果m小于min_to_make_equal，那么
说明可以继续。
否则标记一下finish，下一轮可以停止了。
如果到某一阶段的所有字符串的长度为奇数时，说明到了最后一步了，这个时候，我们要先计算把 所有的中间字符转换成相同的 所需要转换次数，用m减去
它。然后标记一下finish位。
如果到了最后一轮，且m不够用，说明最下面的字符串不是回文串了，要减去1.
class MaximumPalindromeScore
{
public:
int maximize(string word, int m)
{
vector<string>last;
last.push_back(word);
int res = 0;
bool finish = false;
if(word.size()%2==1) finish = true;
int i;
while(true){
if(min_to_make_equal(last)<=m)
res++;
else if(last[0].size()==1||finish)
res--;
if(last[0].size()==1||finish) break;
if(last[0].size()%2==1){
vector<string> mid;
for(i=0;i<last.size();++i){
mid.push_back(string(1,last[i][last[i].size()/2]));
}
m-=min_to_make_equal(mid);
finish = true;
}
vector<string> tmp;
for(i=0;i<last.size();++i){
int n = last[i].size();
string s1 = last[i].substr(0,n/2);
string s2 = last[i].substr(n-n/2,n/2);
reverse(s2.begin(),s2.end());
tmp.push_back(s1);
tmp.push_back(s2);
}
last = tmp;
}
return res;
}
int min_to_make_equal(vector<string> &vs){
memset(cnt,0,sizeof(cnt));
int i,j;
for(i=0;i<vs[0].size();++i)
for(j=0;j<vs.size();++j)
cnt[i][vs[j][i]-'a']++;
vector<char> equal;
for(i=0;i<vs[0].size();++i){
int max = INT_MIN;
for(j=0;j<26;++j){
if(cnt[i][j]>max)
max = j;
}
equal.push_back('a'+max);
}
int res = 0;
for(i=0;i<vs.size();++i){
for(j=0;j<vs[i].size();++j){
if(vs[i][j]!=equal[j])
res++;
}
}
return res;
}
nobody
这个程序有bug。。我改一下再发。。。
nobody
现在改了下，主程序部分也错了。现在应该是正确的了。
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int cnt[51][26];
class MaximumPalindromeScore
{
public:
int maximize(string word, int m)
{
vector<string>last;
last.push_back(word);
int res = 0;
while(true){
//如果是串的长度为奇数，m减去"将中间字符变成统一字符需要的转换次数"
vector<string> mid;
for(i=0;i<last.size();++i){
mid.push_back(string(1,last[i][last[i].size()/2]));
}
m-=min_to_make_equal(mid);
}
//将每个字符串分割成两个子串，前半部不变，后半部翻转
//如果在这一层次上仍满足回文性质，则这些字符串应该能够转换成相同的字符串
int n = last[i].size();
string s1 = last[i].substr(0,n/2);
string s2 = last[i].substr(n-n/2,n/2);
reverse(s2.begin(),s2.end());
tmp.push_back(s1);
tmp.push_back(s2);
}
res++;
else
break;
//长度为奇数，不需要再计算下去了。
if(last[0].size()%2==1) break;
/* for(i=0;i<last.size();++i)
cout<<last[i]<<' ';
*/ cout<<min_to_make_equal(last)<<' '<<m<<endl;
last = tmp;
}
return res;
}
int min_to_make_equal(vector<string> &vs){
memset(cnt,0,sizeof(cnt));
int i,j;
for(i=0;i<vs[0].size();++i)
for(j=0;j<vs.size();++j)
cnt[i][vs[j][i]-'a']++;
vector<char> equal;
for(i=0;i<vs[0].size();++i){
for(j=0;j<26;++j){
if(cnt[i][j]>cnt[i][max])
wukewen2010
wukewen2010
Ziyu Yu
后面应该添加0101.但是为了简化代码.我直接添加的0000.这样再递归几次以后,自
然会变成0101
我的_get(A)程序计算的是>=A的第一个非重复数.
每一次递归,我只需要略过尽量多的重复数就可以了.不必要一步到位
Ziyu Yu
从最低位开始,程序写起来方便.时间复杂度也是(logn*logn).
实际效率差不多.
wukewen2010
wukewen2010
Ziyu Yu
在这一次计算中aa是不变的,但最终会到达改变aa这一步的.
Ziyu Yu
错.相对于获得的轻微效率改进来说,在比赛中是不值得的.
Ziyu Yu
wukewen2010 写道:
> 你说实际效率差不多，是针对一般情况说的么？
Ziyu Yu
暴力法这样做.
{
while(!is_rep_num(A))
A++;
return A;
}
我是这样做
{
while (!is_rep_num(A))
A+={1,10,1000,10000....}
}
同样是迭代,然后判断是否是重复数.
只不过是迭代的步长更长一些而已.
迭代的步长如aaxxxx为10000.