首页 > 代码库 > leetcode 564,546
leetcode 564,546
564 Find the Closest Palindrome:给出一个长度不超过18的非负整数，求出与其最近接的回文整数（不包括它自己）。
思路：假设其长度为偶数。将其分为两半，前一半设为$x$，那么最后的答案的前一部分一定是$x-1,x,x+1$三个中的一个。在这里，$x-1$有可能变成少一位的数字，比如100到99； $x+1$可能多一位，比如99到100.长度为奇数时类似的思路。
long long strToInt(string s) { long long t=0; for(int i=0;i<(int)s.size();++i) { t=t*10+s[i]-‘0‘; } return t;}string intToString(long long x) { if(x==0) return "0"; stack<int> st; while(x) { st.push(x%10); x/=10; } string s=""; while(!st.empty()) { s+=‘0‘+st.top(); st.pop(); } return s;}void up(long long &x,long long p,long long q) { if(p==q) return; if(x==-1) { x=p; } else if(abs(p-q)<abs(x-q)) { x=p; }}string revStr(string s) { int ll=0,rr=(int)s.size()-1; while(ll<rr) { swap(s[ll++],s[rr--]); } return s;}class Solution {public: string nearestPalindromic(string s) { long long x=strToInt(s); int n=(int)s.size(); if(s.size()==1) { if(s=="0") return "1"; return intToString(x-1); } long long ans=-1; if(n&1) { long long t0=strToInt(s.substr(0,n/2+1)); for(int i=-1;i<=1;++i) { string s1=intToString(t0+i); string s2=s1; revStr(s1.substr(0,s1.size()-(s1.size()==n/2+1))); if(s1.size()<n/2+1) { s2+=s1; } else if(s1.size()==n/2+1) { s2+=revStr(s1.substr(0,n/2)); } else { s2+=revStr(s1.substr(0,s1.size()-2)); } long long k=strToInt(s2); up(ans,k,x); } } else { long long t0=strToInt(s.substr(0,n>>1)); if(t0==1) { up(ans,9,x); up(ans,11,x); up(ans,22,x); return intToString(ans); } for(int i=-1;i<=1;++i) { string s1=intToString(t0+i); string s2=s1; if(s1.size()<n/2) { s2+=revStr(s1+"9"); } else if(s1.size()==n/2) { s2+=revStr(s1); } else { s2+=revStr(s1.substr(0,n/2)); } long long k=strToInt(s2); up(ans,k,x); } } return intToString(ans); }};546 Remove Boxes：给定一个长度不超过100的整数数列。每次可以删除连续的相同的一段（删除后两端的会连接到一起）。设该次删除的数字的个数为$k$，那么将得到$k*k$个分数。选择一种删除的序列，使得删除完所有数字后得到的分数最多？
思路：对于某一段连续的数字，可以将其单独删除，或者是跟其他的连在一起的时候再删除。设$f[L][R][k]$表示现在删除$[L,R]$之间的所有数字，且$R$位置之后有$k$个数字跟$R$位置上的数字相同.如果单独删除$R$以及后面的数字，有分数$f[L][R-1][0]+(1+k)^{2}$；否则可以选择跟之前的某一段合并，设合并的位置为$t$，那么有$f[L][t][k+1]+f[t+1][R-1][0]$。
实际实现的时候可以将连续相同的进行合并，速度会快一些。
vector<pair<int,int>> all;int f[111][111][111];int dfs(int L,int R,int k) { if(L>R) return 0; if(f[L][R][k]!=-1) return f[L][R][k]; if(L==R) return (k+all[L].second)*(k+all[L].second); int &ans=f[L][R][k]; ans=dfs(L,R-1,0)+(k+all[R].second)*(k+all[R].second); for(int i=R-1;i>=L;--i) { if(all[i].first==all[R].first) { int tmp=dfs(L,i,all[R].second+k)+dfs(i+1,R-1,0); ans=max(ans,tmp); } } return ans;}class Solution {public: int removeBoxes(vector<int>& a) { all.clear(); int n=(int)a.size(); if(n==0) return 0; all.push_back(make_pair(a[0],1)); for(int i=1;i<n;++i) { if(a[i]==all.back().first) { ++all.back().second; } else { all.push_back(make_pair(a[i],1)); } } memset(f,-1,sizeof(f)); return dfs(0,(int)all.size()-1,0); }};
leetcode 564,546
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。