华为OD机试 - 回文字符串（Java）

梦里梦外; 2024-03-17 22:22 106阅读 0赞

#### 题目描述 ####

如果一个字符串正读和反渎都一样（大小写敏感），则称它为一个「回文串」，例如：

*  leVel是一个「回文串」，因为它的正读和反读都是leVel；同理a也是「回文串」
 *  art不是一个「回文串」，因为它的反读tra与正读不同
 *  Level不是一个「回文串」，因为它的反读leveL与正读不同（因大小写敏感）

给你一个仅包含大小写字母的字符串，请用这些字母构造出一个最长的回文串，若有多个最长的，返回其中字典序最小的回文串。

字符串中的每个位置的字母最多备用一次，也可以不用。

#### 输入描述 ####

无

#### 输出描述 ####

无

#### 用例 ####

<table> 
 <tbody> 
  <tr> 
   <td style="width:101px;">输入</td> 
   <td style="width:587px;">abczcccddzz</td> 
  </tr> 
  <tr> 
   <td style="width:101px;">输出</td> 
   <td style="width:587px;">ccdzazdcc</td> 
  </tr> 
  <tr> 
   <td style="width:101px;">说明</td> 
   <td style="width:587px;">无</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td style="width:100px;">输入</td> 
   <td style="width:588px;">ABabBabA</td> 
  </tr> 
  <tr> 
   <td style="width:100px;">输出</td> 
   <td style="width:588px;">ABabbaBA</td> 
  </tr> 
  <tr> 
   <td style="width:100px;">说明</td> 
   <td style="width:588px;">无</td> 
  </tr> 
 </tbody> 
</table>

#### 题目解析 ####

回文串必然是对称的，可以分为三部分，即： 左边部分， 中间部分， 右边部分

其中左边部分 和 右边部分 互为倒序

而中间部分 可以是空串，可以是单字母。

比如 aba，其中左边部分是a，右边部分也是a，而中间部分是b

再比如 aa，其中左边部分是a，右边部分也是a，而中间部分是”“

因此，我的解题思路如下：

统计输入字符串各字母出现的次数：

*  如果字母出现次数>=2：

1.  字母出现次数为偶数，则可以平均分到左边部分，和右边部分
2.  字母出现次数为奇数，则平均分到左，右部分后，必然还会剩余一个无法成对

*  如果字母出现次数 == 1，则无法成对

对于剩余无法成对的字母，我们记录字典序最小的到mid中（题目要求返回其中字典序最小的回文串）

对于可以平均分配到左，右部分的字母，我们可以将可以成对的字母记录到ans数组，将ans字典序升序，拼接字符串即为回文串左边部分，ans字典序降序，拼接字符串即为回文串右边部分。

最终拼接：回文串左边部分 + 中间部分 + 回文串右边部分，即为题解。

#### Java算法源码 ####

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.Scanner;
    
    public class Main {
      public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        System.out.println(getResult(str));
      }
    
      private static String getResult(String str) {
        HashMap<Character, Integer> count = new HashMap<>();
    
        // 统计各字母个数
        for (int i = 0; i < str.length(); i++) {
          char c = str.charAt(i);
          count.put(c, count.getOrDefault(c, 0) + 1);
        }
    
        ArrayList<Character> half = new ArrayList<>();
        String mid = "";
    
        for (char c : count.keySet()) {
          int n = count.get(c);
          // 如果字母数量大于等于2，则可以成对出现，
          if (n >= 2) {
            for (int i = 0; i < n / 2; i++) half.add(c);
          }
    
          // 如果字母数量只有1个，或者字母数量大于2但是为奇数，则最后必然只剩单个字母可用，此时我们应该在这些无法成对的单字母中选择一个字典序最小的
          if (n % 2 != 0 && ("".equals(mid) || mid.compareTo(c + "") > 0)) {
            mid = c + "";
          }
        }
    
        half.sort((a, b) -> a - b);
        StringBuilder sb = new StringBuilder();
        for (Character c : half) sb.append(c);
    
        return sb + mid + sb.reverse(); // 回文串左边部分 + 中间单字母 + 回文串右边部分
      }
    }