来源:Meetqun, Google phone interview
原帖:meetqun.
题目:
找到比当前数字大的第一个palindrome.
代码:
原帖: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