LeetCode:1328. 破坏回文串(贪心 Java)

打印 上一主题 下一主题

主题 985|帖子 985|积分 2955

目录
1328. 破坏回文串
题目形貌:
实现代码与解析:
贪心
原理思路:


1328. 破坏回文串

题目形貌:

        给你一个由小写英文字母组成的回文字符串 palindrome ,请你将此中 一个 字符用恣意小写英文字母更换,使得结果字符串的 字典序最小 ,且 不是 回文串。
请你返回结果字符串。如果无法做到,则返回一个 空串 。
如果两个字符串长度相同,那么字符串 a 字典序比字符串 b 小可以这样界说:在 a 和 b 出现不同的第一个位置上,字符串 a 中的字符严格小于 b 中的对应字符。比方,"abcc” 字典序比 "abcd" 小,由于不同的第一个位置是在第四个字符,显然 'c' 比 'd' 小。

示例 1:
  1. <strong>输入:</strong>palindrome = "abccba"
  2. <strong>输出:</strong>"aaccba"
  3. <strong>解释:</strong>存在多种方法可以使 "abccba" 不是回文,例如 "<em><strong>z</strong></em>bccba", "a<em><strong>a</strong></em>ccba", 和 "ab<em><strong>a</strong></em>cba" 。
  4. 在所有方法中,"aaccba" 的字典序最小。
复制代码
示例 2:
  1. <strong>输入:</strong>palindrome = "a"
  2. <strong>输出:</strong>""
  3. <strong>解释:</strong>不存在替换一个字符使 "a" 变成非回文的方法,所以返回空字符串。
复制代码
提示:


  • 1 <= palindrome.length <= 1000
  • palindrome 只包罗小写英文字母。
实现代码与解析:

贪心

  1. class Solution {
  2.     public String breakPalindrome(String palindrome) {
  3.         
  4.         int n = palindrome.length();
  5.         if (n == 1) {
  6.             return "";
  7.         }
  8.         char[] cs = palindrome.toCharArray();
  9.         for (int i = 0; i * 2 + 1 < n; i++) {
  10.             if (cs[i] != 'a') {
  11.                 cs[i] = 'a';
  12.                 return new String(cs);
  13.             }
  14.         }
  15.         cs[n - 1] = 'b';
  16.         return new String(cs);
  17.     }
  18. }
复制代码
原理思路:

        n = 1,无论如何换都是回文。遍历字符串一半,如果不为a换成a。如果前半部门全为a,那么根据回文特性,该字符串全为a,只有把最后一个字符修改为小于a的第一个值b即可。


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

伤心客

金牌会员
这个人很懒什么都没写!
快速回复 返回顶部 返回列表