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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。