Monday, April 6, 2015

First Larger Palindrome

来源:Meetqun, Google phone interview

原帖:meetqun.

题目:
找到比当前数字大的第一个palindrome.


代码:
 string largerPanlidrome(string s) {   
     if (s.empty()) return "1";   
     int i, j, L = s.size();   
     if (L % 2 == 0) {   
         i = L / 2 - 1; j = L / 2;   
     } else {   
         i = j = L / 2;   
     }   
   
     // determine carry   
     int ii = i, jj = j;   
     while (ii >= 0 && jj < L && s[ii] == s[jj]) {   
         ii--; jj++;   
     }   
     int carry = ii == -1 || s[ii] < s[jj] ? 1 : 0;    
     while (i >= 0 && j < L) {   
         if (carry == 1) {   
             carry = (s[i] - '0' + 1) / 10;   
             s[i] = s[j] = (s[i] - '0' + 1) % 10 + '0';   
         } else {   
             s[j] = s[i];   
         }   
         i--; j++;   
     }   
     if (carry == 1) {   
         s.insert(s.begin(), '1');   
         s[s.size()-1] = '1';   
     }   
     return s;   
 }   
   
 int main() {   
     //string s = "1231";   
     string s = "456";   
     cout << largerPanlidrome(s) << endl;   
     return 0;   
 }   

No comments:

Post a Comment