Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/08/24 21:07)推噓0(0推 0噓 0→)留言0則, 0人參與討論串763/1548 (看更多)
564. Find the Closest Palindrome
題目:給你一個純數字字串n，求除了n本身外與他最相近的回文字串，如果有複數
字串距離相同則求最小的
思路:
和這個月的translate number to english很像，都是概念不難但很麻煩的hard
撇除1位數和20以下的特例外，對任一數字n而言只有3種候選答案:
1. 最直接的n長度切一半倒貼後面:7999->7997
2. n長度一半的位數+1再倒貼後面:7997->8008 99907->100001
3. n長度一半的位數-1在倒貼後面:7997->7887 100001->99999
所以就針對n列出這三種可能，並注意進位或少一位的可能列出求差最小即解，要注意
的是n的數字可以到10**18，所以轉變字串到數字用atoll
string nearestPalindromic(string n) {
string posb1="0";
string posb2="0";
string posb3="0";
string o_temp;
string m_temp;
if(n.size()==1){
if(n[0]-'0'==0){
return "1";
}
else{
return to_string(n[0]-'0'-1);
}
}
if(n.size()==2){
int yt=atoi(n.c_str());
if(yt<12){
return "9";
}
if(yt<17){
return "11";
}
if(yt<21){
return "22";
}
}
int te_len=n.size()/2;
long long int orig=atoll(n.c_str());
//cout<<"ter "<<n.substr(0,te_len)<<"\n";
stack<char> prod;
string temp_pal="";
for(int i=0;i<te_len;++i){
prod.push(n[i]);
}
while(!prod.empty()){
temp_pal+=prod.top();
prod.pop();
}
int pal=atoi(temp_pal.c_str());
///pal: if n=78995=>pal=87
//sev case:
//78987 78887 79097
//if n=7865 sev case:7887 7777 7997
if(n.size()&1){
posb1=n.substr(0,te_len+1)+temp_pal; //78987=>789
//now for +1 term: 79097
if(n[te_len]=='9'){
o_temp=to_string(atoi(n.substr(0,te_len+1).c_str())+1);
if(o_temp.size()==te_len+2){
//進位了:999->(100)1->telen=1 99997->(1000)01->telen=2
for(int k=te_len-1;k>=0;--k){
o_temp+=o_temp[k];
}
posb2=o_temp;
}
else{
for(int k=0;k<o_temp.size()-1;++k){
prod.push(o_temp[k]);
}
while(!prod.empty()){
o_temp+=prod.top();
prod.pop();
}
posb2=o_temp;
}
}
else{
o_temp=to_string(atoi(n.substr(0,te_len+1).c_str())+1);;
posb2=o_temp+temp_pal;
}
//now for -1 term: 78887
if(n[te_len]=='0'){
m_temp=to_string(atoi(n.substr(0,te_len+1).c_str())-1);
if(m_temp.size()==te_len){
//降為了
//10000->(99)99 1000009>(999)999
posb3=m_temp+m_temp;
}
else{
for(int k=0;k<m_temp.size()-1;++k){
prod.push(m_temp[k]);
}
while(!prod.empty()){
m_temp+=prod.top();
prod.pop();
}
posb3=m_temp;
}
}
else{
m_temp=to_string(atoi(n.substr(0,te_len+1).c_str())-1);;
posb3=m_temp+temp_pal;
}
}
else{
//for 7897 te_len=2 temp_pal=87. for 16 te_len=1 temp_pal=1
//no 1 term;(10-19)
//return to_string(n.size());
posb1=n.substr(0,te_len)+temp_pal;
//now for +1 term: 79097
if(n[te_len-1]=='9'){
o_temp=to_string(atoi(n.substr(0,te_len).c_str())+1);
if(o_temp.size()==te_len+1){
//進為了 99->(10)1 9999->(100)01
for(int k=te_len-1;k>=0;--k){
o_temp+=o_temp[k];
}
posb2=o_temp;
}
else{
for(int k=0;k<o_temp.size()-1;++k){
prod.push(o_temp[k]);
}
while(!prod.empty()){
o_temp+=prod.top();
prod.pop();
}
posb2=o_temp;
}
}
else{
o_temp=to_string(atoi(n.substr(0,te_len).c_str())+1);
string temp_pl=temp_pal;
temp_pl[0]=temp_pal[0]+1;
o_temp+=temp_pl;
posb2=o_temp;
}
//now for -1 term: 7007
if(n[te_len-1]=='0'){
m_temp=to_string(atoi(n.substr(0,te_len).c_str())-1);
if(m_temp.size()==te_len-1){
//降為了
//1000->(9)99 100009>(99)999
posb3=m_temp+m_temp+"9";
}
else{
for(int k=0;k<m_temp.size();++k){
prod.push(m_temp[k]);
}
string brbr="";
while(!prod.empty()){
brbr+=prod.top();
prod.pop();
}
posb3=m_temp+brbr;
}
}
else{
m_temp=to_string(atoi(n.substr(0,te_len).c_str())-1);
string temp_pl=temp_pal;
temp_pl[0]=temp_pal[0]-1;
posb3=m_temp+temp_pl;
}
}
long long int pre_ans1=atoll(posb1.c_str());
long long int pre_ans2=atoll(posb2.c_str());
long long int pre_ans3=atoll(posb3.c_str());
if(pre_ans1==orig){
if(abs(orig-pre_ans2)<abs(orig-pre_ans3)){
return posb2;
}
else{
if(abs(orig-pre_ans2)==abs(orig-pre_ans3)){
if(pre_ans2<pre_ans3){
return posb2;
}
else{
return posb3;
}
}
else{
return posb3;
}
}
}
else{
long long int tu1=abs(pre_ans1-orig);
long long int tu2=abs(pre_ans2-orig);
long long int tu3=abs(pre_ans3-orig);
long long int howans=min(tu1,min(tu2,tu3));
if(howans==tu1){
if(howans!=tu2 &&howans!=tu3){
return posb1;
}
else{
if(howans==tu2 &&howans==tu3){
return
to_string(min(pre_ans1,min(pre_ans2,pre_ans3)));
}
else if(howans==tu2){
return to_string(min(pre_ans1,pre_ans2));
}
else{
return to_string(min(pre_ans1,pre_ans3));
}
}
}
else if(howans==tu2){
if(howans==tu3){
return to_string(min(pre_ans2,pre_ans3));
}
else{
return posb2;
}
}
else{
return posb3;
}
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.216.18 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724504846.A.9AB.html
討論串 (同標題文章)
完整討論串 (本文為第 763 之 1548 篇)：