palindrome.palindromeRead the same words backwards and forwards
Today is February 02, 2020, rare Palindrome Day, palindrome title go you
9. A palindrome
Ideas and code implementation
Solution 1: flip the numbers
/** * @param {number} x * @return {boolean} */
var isPalindrome = function(x) {
if (x < 0) {
return false
} else if (x >= 0 && x < 10) {
return true
} else {
let reverse = 0
let cur = x
while (cur / 10 > 0) {
reverse = reverse * 10 + cur % 10
cur = Math.floor(cur / 10)}return reverse === x
}
};
Copy the codeOptimization, solution two: flip half number
/** * @param {number} x * @return {boolean} */
var isPalindrome = function(x) {
/ / negative
if (x < 0) {
return false
/ / 0 to 9
} else if (x >= 0 && x < 10) {
return true
// A non-zero digit ending in 0
} else if(x ! = =0 && x % 10= = =0) {
return false
} else {
let reverse = 0
// If the inverted digit is larger than the original digit, the inverted digit is the middle digit
while (x > reverse) {
reverse = reverse * 10 + x % 10
x = Math.floor(x / 10)}// Consider odd digits
return (reverse === x) || (Math.floor(reverse / 10) === x)
}
};
Copy the code866. Palindromic prime numbers
Ideas and code implementation
Validates palindromes (see 9. Palindromes above) and validates primes, noting that there are no eight-bit primes
/** * @param {number} N * @return {number} */
var primePalindrome = function(N) {
if (N <= 2) {
return 2
} else {
function isPrime (n) {
let i = 2
while (i <= Math.sqrt(n)) {
if (n % i === 0) {
return false
}
i++
}
return true
}
function isPalindrome (n) {
if (n < 10) {
return true
} else if (n % 10= = =0) {
return false
} else {
let reverse = 0
while (n > reverse) {
reverse = reverse * 10 + n % 10
n = Math.floor(n / 10)}return (n === reverse) || (n === Math.floor(reverse / 10))}}while(! (isPalindrome(N) && isPrime(N))) { N++if (N > 10000000 && N < 100000000) {
N = 100000000}}return N
}
};
Copy the code234. Palindrome linked list
Ideas and code implementation
Solution 1: bidirectional linked list
Make the list bidirectional and compare it from both ends to the middle
Complexity analysis
Time is O(n), space is O(n) because we need to store prev Pointers.
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/** * @param {ListNode} head * @return {boolean} */
var isPalindrome = function(head) {
// Consider an empty list
if (head === null) {
return true
} else {
/ / the head pointer
let headPointer = head
/ / the tail pointer
let tailPointer = head
// Change the list to a bidirectional list
while (tailPointer.next) {
tailPointer.next.prev = tailPointer
tailPointer = tailPointer.next
}
// Compare them from the beginning to the middle
while(headPointer ! == tailPointer) {if(headPointer.next ! == tailPointer) {if (headPointer.val === tailPointer.val) {
headPointer = headPointer.next
tailPointer = tailPointer.prev
} else {
return false
}
// Consider even linked lists
} else {
return headPointer.val === tailPointer.val
}
}
return true}};Copy the codeOptimization, solution two: fast and slow pointer
- The slow pointer accesses the next node in turn and flips the linked list
- The fast pointer accesses the next node in turn until there is no next node (odd-numbered list) or the next node (even-numbered list), at which point the first half of the list has been flipped
- Compare the values of the first and second linked list nodes in turn
Complexity analysis
Time complexity O(n), space complexity O(1)
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/** * @param {ListNode} head * @return {boolean} */
var isPalindrome = function(head) {
if (head === null) {
return true
} else if (head.next === null) {
return true
} else {
let slowPointer = head
let fastPointer = head
let _head = null
let temp = null
// Find the middle node and flip the first half of the list,
// make _head point to the first half of the list,
// Make slow point to the end of the list
while (fastPointer && fastPointer.next) {
_head = slowPointer
slowPointer = slowPointer.next
fastPointer = fastPointer.next.next
_head.next = temp
temp = _head
}
// The odd-numbered list skips the middle node
if (fastPointer) {
slowPointer = slowPointer.next
}
while (_head) {
if(_head.val ! == slowPointer.val) {return false
}
_head = _head.next
slowPointer = slowPointer.next
}
return true}};Copy the code680. Validate palindrome string ⅱ
Ideas and code implementation
Solution one: double pointer
Compare from beginning to end, if two characters are not equal, then determine whether the substring after deleting a character is palindrome
/** * @param {string} s * @return {boolean} */
var validPalindrome = function(s) {
let headPointer = 0
let tailPointer = s.length - 1
function isPalindrome (s) {
let headPointer = 0
let tailPointer = s.length - 1
while (headPointer < tailPointer) {
if(s[headPointer] ! == s[tailPointer]) {return false
} else {
headPointer++
tailPointer--
}
}
return true
}
while (headPointer < tailPointer) {
if(s[headPointer] ! == s[tailPointer]) {if (s[headPointer + 1] === s[tailPointer] || s[headPointer] === s[tailPointer - 1]) {
return isPalindrome(s.substring(headPointer + 1, tailPointer + 1)) || isPalindrome(s.substring(headPointer, tailPointer))
} else {
return false}}else {
headPointer++
tailPointer--
}
}
return true
};
Copy the codeOptimization, solution two: reuse double Pointers
On the basis of solution 1, the double pointer is used to judge whether the substring is palindrome or not without intercepting the substring
/** * @param {string} s * @return {boolean} */
var validPalindrome = function(s) {
let headPointer = 0
let tailPointer = s.length - 1
function isPalindrome (s, headPointer, tailPointer) {
while (headPointer < tailPointer) {
if(s[headPointer] ! == s[tailPointer]) {return false
} else {
headPointer++
tailPointer--
}
}
return true
}
while (headPointer < tailPointer) {
if(s[headPointer] ! == s[tailPointer]) {if (s[headPointer + 1] === s[tailPointer] || s[headPointer] === s[tailPointer - 1]) {
return isPalindrome(s, headPointer + 1, tailPointer) || isPalindrome(s, headPointer, tailPointer - 1)}else {
return false}}else {
headPointer++
tailPointer--
}
}
return true
};
Copy the code409. Longest palindrome string
Ideas and code implementation
Solution 1: hash table, judge the character of the odd even
/** * @param {string} s * @return {number} */
var longestPalindrome = function(s) {
const hashTable = {}
let result = 0
for(let i = s.length - 1; i >= 0; --i) {
if (hashTable[s[i]] === undefined) {
hashTable[s[i]] = 1
} else {
++hashTable[s[i]]
}
}
let flag = true
for (let key in hashTable) {
j = hashTable[key]
/ / even
if ((j & 1) = = =0) {
result += j
} else {
/ / odd
result += (j - 1)
if (flag) {
result++
flag = false}}}return result
};
Copy the codeOptimization, solution two: hash table, recording pairs of characters
/** * @param {string} s * @return {number} */
var longestPalindrome = function(s) {
const len = s.length
const hashTable = {}
let result = 0
for(let i = len - 1; i >= 0; --i) {
if (hashTable[s[i]] === undefined || hashTable[s[i]] === 0) {
hashTable[s[i]] = 1
} else {
result += 2
hashTable[s[i]] = 0}}return result < len ? result + 1 : result
};
Copy the code