- Valid Palidrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note:For the purpose of this problem, we define empty string as valid palindrome.
Example 1:
Input:"A man, a plan, a canal: Panama"
Output:true
Example 2:
Input:"race a car"
Output:false
给定一个字符串，判断它是否为回文字符串。
解题思路：声明两个pointers，分别指向字符串的头和尾，然后判断两个pointers指向的字符是否相同，头指针往后移动，尾指针向前移动，继续判断两个pointers指向的字符是否相同，直到两个pointers重合或者相邻为止。这道题的小难点在于给定的字符串中，我们需要忽略所有字母和数字以外的字符。所以我们每次在判断是否为相同的字符时，都要事先判断当前字符是否为数字或者字母。
解法1：
这种解法利用了if..else if.. 最后的else语句只有在它前面所有的if 和 else if语句都是false的时候，才会执行。也就是说只有两个指针当前指向的字符都是字母或者数字时，才会执行else语句，判断两个字符是否相同。
public boolean isPalindrome(String s) {
if(s == null || s.length() == 0) return true;
int start = 0;
int end = s.length() -1 ;
while(start < end){
if(!Character.isLetterOrDigit(s.charAt(start))){
start++;
}else if(!Character.isLetterOrDigit(s.charAt(end))){
end--;
}else{
if(Character.toLowerCase(s.charAt(start)) != Character.toLowerCase(s.charAt(end))){
return false;
}
start++;
end--;
}
}
return true;
}
时间复杂度 O(n), 空间复杂度 O(1). n为字符串s的长度。
解法2：
对if..else if语句执行规则不熟悉的同学应该会更容易想到这个解法
public boolean isPalindrome(String s) {
if(s == null || s.length() == 0) return true;
int start = 0;
int end = s.length() -1 ;
while(start < end){
while(start< end && !Character.isLetterOrDigit(s.charAt(start))){
start++;
}
while(start<end && !Character.isLetterOrDigit(s.charAt(end))){
end--;
}
if(Character.toLowerCase(s.charAt(start)) != Character.toLowerCase(s.charAt(end))){
return false;
}
start++;
end--;
}
return true;
}
时间复杂度 O(n), 空间复杂度 O(1). n为字符串s的长度。
-
Valid Palindrome II
-
Palindrome number
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:
Input: 121
Output: true
Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Follow up: Could you solve it without converting the integer to a string?
这道题让我们判断一个number（可能为负数）是否为回文：number = reverse(number)，且要求不能转换为string进行判断。
解题思路：每次取number的last digit, 然后让number = number/10，这样新的number就是number去掉最后一位后的数字，如果此时number不为0，我们就把上一次获得的last digit乘以10，然后加上当前的number最后一位。 直到number为0，我们判断新获得的数字是否等于给定的数字，如果相等，返回true；反之，返回false。
public boolean isPalindrome(int x) {
if(x<0) return false;
int x2 = x;
int res = 0;
while(x2 != 0){
res = res * 10 + x2%10;
x2 = x2/10;
}
return res == x;
}
时间复杂度 O(n), 空间复杂度 O(1),n 为x的位数。
dang！现在问题来了。 因为是数字的操作，我们要特别注意是否会overflow。因为翻转之后得到的数字，也就是我们上面得到的res，有可能是超过Interger.MAX_VALUE的。所以这里借鉴了leetcode一个高频解法，可以有效的化解这个问题。
出处：https://leetcode.com/problems/palindrome-number/discuss/5127/9-line-accepted-Java-code-without-the-need-of-handling-overflow
解法2： 我们只需要比较数字的一半，比如说res我们只求到x的后半段，然后比较x的前半段和res是否相等。我们知道一半之后的数字肯定是不会overflow的。
class Solution {
public boolean isPalindrome(int x) {
if(x<0) return false;
if(x!=0 && x%10 == 0) return false; //
int res = 0;
while(res < x){
res = res * 10 + x%10;
x = x/10;
}
return res == x || x == res/10;
}
}
- Palindrome LinkedList
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?
解法1： 利用stack的FILO原理。
因为是singly linkelist， 所以很难在保留原链表的情况下得到该链表翻转之后的新链表。因为我们利用stack来保存node。
public boolean isPalindrome(ListNode head) {
if(head == null) return true;
Deque<ListNode> stack = new ArrayDeque<>();
ListNode runner = head;
while(runner!=null){
stack.push(runner);
runner = runner.next;
}
while(!stack.isEmpty()){
if(stack.pop().val != head.val){
return false;
}
head = head.next;
}
return true;
}
时间复杂度O(n),空间复杂度O(n)
解法2：follow up：要求用O(1) space complexity。
翻转前半段，与后半段进行比较。
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
ListNode slower = head;
ListNode faster = head;
ListNode prev = null, cur = slower, next = null;
while(faster != null && faster.next !=null){
faster = faster.next.next;
next = slower.next;
slower.next = prev;
prev = slower;
slower = next;
}
if(faster != null){
slower = slower.next;
}
while(prev != null){
if(prev.val != slower.val){
return false;
}
prev = prev.next;
slower = slower.next;
}
return true;
}
- Longest Palindrome
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example "Aa" is not considered a palindrome here.
Note:
Assume the length of given string will not exceed 1,010.
Example:
Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
解法1：利用hashset
public int longestPalindrome(String s) {
if(s== null || s.length() == 0) return 0;
Set<Character> hashSet = new HashSet<>();
int count = 0;
for(int i=0;i<s.length();i++){
if(hashSet.contains(s.charAt(i))){
count++;
hashSet.remove(s.charAt(i));
}else{
hashSet.add(s.charAt(i));
}
}
if(!hashSet.isEmpty()){
return count*2+1;
}
return count*2;
}
解法2：利用hashmap
public int longestPalindrome(String s) {
if(s==null || s.length() == 0) return 0;
Map<Character, Integer> hashMap = new HashMap<>();
for(Character ch : s.toCharArray()){
hashMap.put(ch, hashMap.getOrDefault(ch, 0)+1);
}
int res = 0;
int reminder = 0;
for(Character c:hashMap.keySet()){
if(hashMap.get(c) % 2 == 0){
res += hashMap.get(c);
}else{
res += hashMap.get(c) - 1;
reminder = 1;
}
}
return res+reminder;
}
解法3：
public int longestPalindrome(String s) {
boolean[] map = new boolean[128];
int len = 0;
for (char c : s.toCharArray()) {
map[c] = !map[c]; // flip on each occurrence, false when seen n*2 times
if (!map[c]) len+=2;
}
if (len < s.length()) len++; // if more than len, atleast one single is present
return len;
}
网友评论