00125 驗證回文串
題目描述
給定一個字符串，驗證它是否是回文串，只考慮字母和數(shù)字字符，可以忽略字母的大小寫。
說明：本題中，我們將空字符串定義為有效的回文串。
示例 1:
輸入: "A man, a plan, a canal: Panama"
輸出: true
示例 2:
輸入: "race a car"
輸出: false
力扣地址
解題報告
采用雙指針
本題解由微信公眾號
小猿刷題提供, 錯誤之處, 歡迎指正.
- 分別從頭部和尾部進(jìn)行掃描(只掃描字母和數(shù)字), 比較對應(yīng)位置是否相同字母(考慮到存在大小寫,所以統(tǒng)一轉(zhuǎn)換為大/小寫進(jìn)行比較),
- 對應(yīng)位字母不同則表示不是回文串,直至比較結(jié)束,均相等則表示是回文串.
/**
* 微信公眾號"小猿刷題"
*/
class Solution {
public boolean isPalindrome(String s) {
int i = 0;
int j = s.length() - 1;
while(i <= j) {
char ci = s.charAt(i);
char cj = s.charAt(j);
if(!Character.isLetterOrDigit(ci)){
i ++;
} else if(!Character.isLetterOrDigit(cj)){
j --;
} else {
// 判斷是否相等(不區(qū)分大小寫)
if(Character.toLowerCase(ci) != Character.toLowerCase(cj)){
return false;
}
j --;
i ++;
}
}
return true;
}
}
上面雙指針通過在遍歷過程中篩選字母/數(shù)字進(jìn)行比較,也可以先進(jìn)行串規(guī)整(正則替換掉字母數(shù)字以外的字符,統(tǒng)一轉(zhuǎn)換大/小寫),再頭尾進(jìn)行對比.
/**
* 微信公眾號"小猿刷題"
*/
class Solution {
public boolean isPalindrome(String s) {
s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
for(int i = 0; i < s.length() / 2; i ++){
if(s.charAt(i) != s.charAt(s.length() - 1 -i)){
return false;
}
}
return true;
}
}
小猿刷題
00234 回文鏈表
題目描述
請判斷一個鏈表是否為回文鏈表。
示例 1:
輸入: 1->2
輸出: false
示例 2:
輸入: 1->2->2->1
輸出: true
進(jìn)階：
- 你能否用 O(n) 時間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題？
力扣地址
- https://leetcode.com/problems/palindrome-linked-list/
- https://leetcode-cn.com/problems/palindrome-linked-list/
解題報告
利用棧
本題解由微信公眾號
小猿刷題提供, 錯誤之處, 歡迎指正.
利用棧的特性(先進(jìn)后出)保存鏈表,然后在元素逐個出棧過程中，從鏈表依次進(jìn)行比較.
/**
* 微信公眾號"小猿刷題"
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
Stack<Integer> stack = new Stack<>();
ListNode curr = head;
while(curr != null){
stack.add(curr.val);
curr = curr.next;
}
curr = head;
while(!stack.isEmpty()){
int val = stack.pop();
if(val != curr.val){
return false;
}
curr = curr.next;
}
return true;
}
}
利用List
本題解由微信公眾號
小猿刷題提供, 錯誤之處, 歡迎指正.
既然利用?？梢?同樣的利用list也可以解決,鏈表存儲list,再利用list的特性依次遍歷首尾對比.
/**
* 微信公眾號"小猿刷題"
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> list = new ArrayList<>();
ListNode curr = head;
while(curr != null){
list.add(curr.val);
curr = curr.next;
}
for (int i = 0; i < list.size() / 2; i++){
if((int)list.get(i) != (int)list.get(list.size() - 1 -i)){
return false;
}
}
return true;
}
}
雙指針
本題解由微信公眾號
小猿刷題提供, 錯誤之處, 歡迎指正.
- 快慢指針,快指針移動2次,滿指針移動1次,當(dāng)快指針移動至末尾時,慢指針剛好在鏈表中間位置.
- 反轉(zhuǎn)慢指針, 同鏈表頭部元素依次進(jìn)行比較, 遇到不相同的元素則表示非回文聯(lián)表. 直至結(jié)束.
/**
* 微信公眾號"小猿刷題"
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
fast = head;
slow = reverse(slow);
while (slow != null) {
if (slow.val != fast.val) {
return false;
}
slow = slow.next;
fast = fast.next;
}
return true;
}
// 鏈表反轉(zhuǎn)
public ListNode reverse(ListNode head) {
ListNode target = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next;
current.next = target;
target = current;
current = nextTemp;
}
return target;
}
}
小猿刷題
