【LeetCode】﹝回文?﹞数、串、链表、对
回文数★
【题目】给你一个整数 x ，如果 x是一个回文整数，返回 true；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123不是。
提示：
-231 <= x <= 231 - 1
【示例】
输入：x = 121
输出：true
---------------------------------------------
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
【解题思路】
排除负数，变为字符串再判断
class Solution {
public boolean isPalindrome(int x) {
if( x < 0 || ( x % 10 == 0 && x != 0)) {
return false;
}
String str = Integer.toString(x);
int p = 0, q = str.length() - 1;
while(p <= q){
if(str.charAt(p++) != str.charAt(q--)){
return false;
}
}
return true;
}
}
回文链表★
【题目】给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
提示：
- 链表中节点数目在范围
[1, 105]内 0 <= Node.val <= 9
【示例】
输入：head = [1,2,2,1]
输出：true
【解题思路】
分三步
- 快慢指针找链表中点
- 反转后半段链表
- 判断这两段链表值是否相等
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null){
return true;
}
ListNode slow = head, fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
ListNode cur = slow.next, pre = null;
while(cur != null){
ListNode nextNode = cur.next;
cur.next = pre;
pre = cur;
cur = nextNode;
}
ListNode begin = head;
while(begin != null && pre != null){
if(begin.val != pre.val){
return false;
}
begin = begin.next;
pre = pre.next;
}
return true;
}
}
最长回文串★
【题目】给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 “``Aa`” 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
【示例】
输入: "abccccdd"
输出: 7
解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
【解题思路】
统计字符出现词频，奇数字符只能放在中间算作1个，偶数字符对称排列。
class Solution {
public int longestPalindrome(String s) {
int[] mark = new int[58];
for (char c : s.toCharArray()) {
mark[c - 'A']++;
}
int res = 0;
for (int x : mark) {
res += x - (x & 1);
}
return res < s.length() ? res + 1 : res;
}
}
验证回文串★
【题目】给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
**说明：**本题中，我们将空字符串定义为有效的回文串。
提示：
1 <= s.length <= 2 * 105- 字符串
s由 ASCII 字符组成
【示例】
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
----------------------------------------
输入: "race a car"
输出: false
解释："raceacar" 不是回文串
【解题思路】
大写变小写，跳过空格标点符号，再判断
偷个懒
- 这里将符合要求的字符加入StringBuffer中，判断它的逆序和正序是否相等。
class Solution {
public boolean isPalindrome(String s) {
s = s.toLowerCase();
StringBuffer str = new StringBuffer();
for(char c : s.toCharArray()){
if((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z')){
str.append(c);
}
}
return str.toString().equals(str.reverse().toString());
}
}
破坏回文串★★
【题目】给你一个由小写英文字母组成的回文字符串 palindrome ，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的 字典序最小 ，且 不是 回文串。
请你返回结果字符串。如果无法做到，则返回一个 空串 。
如果两个字符串长度相同，那么字符串a 字典序比字符串 b小可以这样定义：在 a 和b 出现不同的第一个位置上，字符串 a中的字符严格小于 b中的对应字符。例如，"``abcc” 字典序比 "abcd" 小，因为不同的第一个位置是在第四个字符，显然 'c' 比 'd`’ 小。
提示：
1 <= palindrome.length <= 1000palindrome只包含小写英文字母。
【示例】
输入：palindrome = "abccba"
输出："aaccba"
解释：存在多种方法可以使 "abccba" 不是回文，例如 "zbccba", "aaccba", 和 "abacba" 。
在所有方法中，"aaccba" 的字典序最小。
-----------------------------------------------------------------------------
输入：palindrome = "aba"
输出："abb"
【解题思路】
找规律：见注释
class Solution {
public String breakPalindrome(String palindrome) {
// len = 1 null,
// 遍历一半， 替换一个a
// 若都为a，将最后一个替换为b
if (palindrome.length() == 1) return "";
char[] chars = palindrome.toCharArray();
boolean flag = false;
for (int i = 0; i < chars.length / 2; i++) {
if (chars[i] != 'a') {
chars[i] = 'a';
flag = true;
break;
}
}
if (!flag) chars[chars.length - 1] = 'b';
return new String(chars);
}
}
最长回文子序列★★
【题目】给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
【示例】
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
【解题思路】
可以转换为求当前字符串与其逆序字符串的最长公共子序列
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n + 1][n + 1];
//最长公共子序列
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
char a = s.charAt(i);
char b = s.charAt(n - j - 1);
if (a == b) {
dp[i + 1][j + 1] = dp[i][j] + 1;
} else {
dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
return dp[n][n];
}
}
回文对★★★
【题目】给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
提示：
1 <= words.length <= 50000 <= words[i].length <= 300words[i]由小写英文字母组成
【示例】
输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
-----------------------------------------------------------------
输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]]
解释：可拼接成的回文串为 ["battab","tabbat"]
【解题思路】
方法一：暴力法
134 / 136 个通过测试用例
Java两个测试用例过不了…
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res = new ArrayList();
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words.length; j++) {
if (i != j && isOk(words, i, j)) {
res.add(Arrays.asList(i, j));
}
}
}
return res;
}
private boolean isOk(String[] words, int k1, int k2) {
String s1 = words[k1] + words[k2];
int i = 0, j = s1.length() - 1;
while (i < j) {
if (s1.charAt(i) != s1.charAt(j)) return false;
i++;
j--;
}
return true;
}
}
方法二：前缀树
详细参考热门题解方法二：字典树（Trie树）[通过]
看样子以前是可以通过的，后期又增加了测试用例，135 / 136 个通过测试用例
class Solution {
class Node{
Node[] ns;
List<Integer> words;
List<Integer> suffixs;
public Node() {
this.ns = new Node[26];
this.words = new ArrayList();
this.suffixs = new ArrayList();
}
}
Node root;
public List<List<Integer>> palindromePairs(String[] words) {
root = new Node();
int n = words.length;
// 字典树的插入
for (int i = 0; i < n; i++) {
String rev = new StringBuffer(words[i]).reverse().toString();
Node cur = root;
if (isOk(rev.substring(0))) {
cur.suffixs.add(i);
}
for (int j = 0; j < rev.length(); j++) {
char c = rev.charAt(j);
if (cur.ns[c - 'a'] == null) {
cur.ns[c - 'a'] = new Node();
}
cur = cur.ns[c - 'a'];
if (isOk(rev.substring(j + 1))) {
cur.suffixs.add(i);
}
}
cur.words.add(i);
}
List<List<Integer>> res = new ArrayList();
for (int i = 0; i < n; i++) {
String word = words[i];
Node cur = root;
int j = 0;
for (; j < word.length(); j++) {
if (isOk(word.substring(j))) {
for (int k : cur.words) {
if (k != i) {
res.add(Arrays.asList(i, k));
}
}
}
char c = word.charAt(j);
if (cur.ns[c - 'a'] == null) {
break;
}
cur = cur.ns[c - 'a'];
}
if (j == word.length()) {
for (int k : cur.suffixs) {
if (k != i) {
res.add(Arrays.asList(i, k));
}
}
}
}
return res;
}
private boolean isOk(String word) {
int i = 0, j = word.length() - 1;
while (i < j) {
if (word.charAt(i) != word.charAt(j)) return false;
i++;
j--;
}
return true;
}
}
方法三：马拉车
😱再说吧···
最短回文串★★★
【题目】给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
提示：
0 <= s.length <= 5 * 104s仅由小写英文字母组成
【示例】
输入：s = "aacecaaa"
输出："aaacecaaa"
【解题思路】
方法一：逆序选取字符串的字符依次判断
java超时，119 / 120 个通过测试用例
class Solution {
public String shortestPalindrome(String s) {
String rev = new StringBuffer(s).reverse().toString();
for (int i = 0; i < rev.length(); i++) {
String pre = rev.substring(0, i);
if (isOk(pre + s)) {
return pre + s;
}
}
return rev + s;
}
private boolean isOk(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
}
方法二：KMP
😱再说吧···
···