这题考查的是排序吧… 还有rbegin的使用。
普通排序：时间 O(nlogn) / 空间 O(1)
前半部分顺序排序，后半部分逆序排序。
|
1 2 3 4 5 6 7 8 9 |
class Solution { public: string smallestPalindrome(string s) { const int n = s.length(); sort(begin(s), begin(s) + n / 2); sort(rbegin(s), rbegin(s) + n / 2); return s; } }; |
计数排序：时间：O(n)，空间：O(n) -> O(1)
首尾一起写
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// 7 ms, 54.65MB class Solution { public: string smallestPalindrome(string s) { vector<int> f(128); for (size_t i = 0; i < s.size() / 2; ++i) ++f[s[i]]; auto h=begin(s); auto t=rbegin(s); for (char c = 'a'; c <= 'z'; ++c) while (f[c]--) *h++ = *t++ = c; return s; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment