A.每日一题：3517. 最小回文排列 I

题目链接3517. 最小回文排列 I中等算法原理解法一计数排序时间复杂度O(N)写法一StringBuffer79ms击败5.76%1.思路很简单利用计数排序的思想既然字符串给的是回文的那么我们只需要统计前一半就行了统计前一半中26个小写英文字符出现的次数然后从 a 遍历到 z 依次拼接即可2.拼接之后后半部分就直接翻转过来再接上这一点用 StringBuffer 可以很简单的实现3.最后一点就是看这个回文串长度是奇数还是偶数我们上述做法得到的回文串必定是偶数的如果是奇数的话差的一定是中间的那个而中间的那个在最终结果的位置必然还是在中间否则这个字符串必然不再是回文因此我们直接把原字符串的正中间的字符取出来接在中间即可4.最后根据原字符串的奇偶长度返回不同的结果即可写法二StringBuilder33ms击败54.86%思路与写法一完全相同但这个会更快因为 StringBuffer 是线程安全的中间加了很多锁而 StringBuffer 是线程不安全的没有那么多锁效率要比 StringBuffer 快不少关于线程中上锁的知识可参考Java EE2.多线程-初阶第四弹synchronized 锁内存可见性Java EE3.多线程-进阶第一弹常见的锁策略synchronized原理优化16ms击败98.96%中间重复添加相同字符的部分可以借助 repeat 实现String a a; String fiveAs a.repeat(5); // 结果就是 aaaaa解法二排序左半部分48ms击败15.03%时间复杂度O(n logn)由于 s 是回文字符串我们只需关心左半部分如何排列即可因此我们可以将左半部分拿出来排列后在用 StringBuilder 拼接上去后半部分只需要逆序拼接即可Java代码class Solution { //3517. 最小回文排列 I //解法一计数排序-写法一StringBuffer public String smallestPalindrome(String s) { if(s.length()1) return s; int[] hashnew int[26]; StringBuffer curnew StringBuffer(); for(int i0;is.length()/2;i) hash[s.charAt(i)-a]; for(int i0;i26;i) while(hash[i]--0) cur.append((char)(ia)); if(s.length()%20) return cur.toString()cur.reverse().toString(); else return cur.toString()s.charAt(s.length()/2)cur.reverse().toString(); } }class Solution { //3517. 最小回文排列 I //解法一计数排序-写法二StringBuilder public String smallestPalindrome(String s) { if(s.length()1) return s; int[] hashnew int[26]; StringBuilder curnew StringBuilder(); for(int i0;is.length()/2;i) hash[s.charAt(i)-a]; for(int i0;i26;i) while(hash[i]--0) cur.append((char)(ia)); if(s.length()%20) return cur.toString()cur.reverse().toString(); else return cur.toString()s.charAt(s.length()/2)cur.reverse().toString(); } }class Solution { //3517. 最小回文排列 I //解法一计数排序-优化 public String smallestPalindrome(String s) { int ns.length(); if(n1) return s; int[] hashnew int[26]; StringBuilder curnew StringBuilder(); for(int i0;in/2;i) hash[s.charAt(i)-a]; for(int i0;i26;i) cur.repeat(ai,hash[i]); //提前拷贝一份 StringBuilder tnew StringBuilder(cur); //回文串长度为奇数就把中间的加上 if(n%21) cur.append(s.charAt(n/2)); cur.append(t.reverse()); return cur.toString(); } }class Solution { //3517. 最小回文排列 I //解法二排序左半部分 public String smallestPalindrome(String s) { int ns.length(); int mn/2; char[] ts.substring(0,m).toCharArray(); Arrays.sort(t); StringBuilder curnew StringBuilder(); cur.append(t); //判断是否是奇数长度回文串 if(n%21) cur.append(s.charAt(m)); //逆序拼接 for(int im-1;i0;i--) cur.append(t[i]); return cur.toString(); } }