5418. Pseudo-Palindromic Paths in a Binary Tree

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example 1:

Input: root = [2,3,1,3,1,null,1]
Output: 2 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 3:

Input: root = [9]
Output: 1

Constraints:

• The given binary tree will have between 1 and 10^5 nodes.
• Node values are digits from 1 to 9.

给定一棵二叉树，问树中从根到叶子的路径构成的一个数组，能调整成回文数组串的个数。

简单题，直接DFS，记录每条路径中包含1~9的个数，如果该数组中包含的奇数的个数不超过1个，则能调整成回文串，否则不能。

回文串有两种形式，一种是123321，即串中每个数字都对称出现偶数次，另一种是1234321，中间的4只出现1次，其他数字都出现偶数次。

完整代码如下：

class Solution {
private:
	void DFS(TreeNode* root, vector<int> &hash, int &ans) {
		if (root == NULL)return;
		++hash[root->val];

		if (root->left == NULL && root->right == NULL) {
			int odd = 0;
			for (int i = 1; i <= 9; ++i) {
				if (hash[i] % 2 == 1) {
					++odd;
					if (odd > 1) {
						break;
					}
				}
			}
			if (odd <= 1) {
				++ans;
			}
			--hash[root->val];
			return;
		}

		DFS(root->left, hash, ans);
		DFS(root->right, hash, ans);
		--hash[root->val];
	}
public:
	int pseudoPalindromicPaths(TreeNode* root) {
		vector<int> hash(10, 0);
		int ans = 0;
		DFS(root, hash, ans);
		return ans;
	}
};

本代码提交AC。

234. Palindrome Linked List

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? 234. Palindrome Linked List

本题要判断一个单向链表是否为回文链表。之前LeetCode Valid Palindrome判断的是数组，可以直接访问数组的头尾元素，但是链表不可以随机访问。 仔细观察一下，下面两条回文链表：

1. 1->2->3->4->5->4->3->2->1
2. 1->2->3->4->4->3->2->1

判断回文链表最原始的方法是从左往右读一遍和从右往左读一遍，如果读得的结果一样就是回文，比如第1条回文，从左往右是123454321，从右往左也是123454321，所以它是回文。 但是其实我们可以不用完整读一遍，我们只读一半就可以了，比如回文1的前半部分是1234，后半部分是4321，前半部分顺着读和后半部分倒着读都是1234，这样就足以说明是回文串了。 紧接着，对于链表，我们就有这样一种解题思路：首先找到链表的中间节点，然后把后半部分链表逆序，最后看看逆序的后半部分和顺序的前半部分是否相同。 找链表的中间节点的常规思路就是快慢指针，这个在很多题中都用到了，需要指出的是，回文链表有两种情况，一种是形如1的奇数个元素，另一种是形如2的偶数个元素。如果用快慢指针找中点，1能找到真正的中点5，2能找到前一个中点4，所以我们判断回文的时候，只需要把中点后面的链表逆序，然后只比较后半部分的链表元素。比如1的情况，逆序后半部分之后得到1->2->3->4，那么前半部分也只需要比较1->2->3->4，不需要比较5，因为这是奇数链表的中点，前后链表共享的元素；2的情况，逆序后半部分之后得到1->2->3->4，前半部分也是1->2->3->4，偶数长度的情况就会把中间的两个元素分到前后两部分。 完整代码如下：

class Solution {
public:
    bool isPalindrome(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return true;
        ListNode *faster = head, *slower = head;
        while (faster->next != NULL && faster->next->next != NULL) {
            faster = faster->next->next;
            slower = slower->next;
        } //bool odd = faster->next == NULL ? true : false; // 链表长度是否为奇数
        ListNode *head2 = slower, *prior = slower->next, *tail;
        head2->next = NULL;
        while (prior != NULL) { // 逆序后半段链表
            tail = prior->next;
            prior->next = head2->next;
            head2->next = prior;
            prior = tail;
        }
        head2 = head2->next;
        while (head2 != NULL) {
            if (head->val != head2->val)
                return false;
            head = head->next;
            head2 = head2->next;
        }
        return true;
    }
};

本代码提交AC，用时25MS。

二刷。同样的思路：

class Solution {
public:
	bool isPalindrome(ListNode* head) {
		if (head == NULL || head->next == NULL)return true;
		// 快慢指针
		ListNode *fast = head, *slow = head;
		while (fast != NULL && fast->next != NULL) {
			fast = fast->next->next;
			slow = slow->next;
		}
		// 逆序后半段
		ListNode *dummy = new ListNode(0);
		ListNode *par = slow, *child = slow->next;
		while (par != NULL) {
			child = par->next;
			par->next = dummy->next;
			dummy->next = par;
			par = child;
		}
		// 判断是否相等
		slow = head;
		fast = dummy->next;
		while (fast != NULL) {
			if (slow->val != fast->val)return false;
			slow = slow->next;
			fast = fast->next;
		}
		return true;
	}
};

本代码提交AC，用时28MS。

125. Valid Palindrome

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

本题要判断一个字符串是否是回文串，回文串的意思是从左往右读和从右往左读出来的字符串是一样的。本题在判断是否为回文时，只考虑数字和字母，并且忽略字母的大小写。 思路很简单，两个指针i,j，分别指向字符串的头尾，各自跳过所有非数字和字母的字符，然后把大写字母转换为小写字母，如果出现头尾字符不一样的情况，则不是回文，立即返回false。如果比完整个字符串都相等，则是回文，返回true。 完整代码如下：

bool isAlphaNum(char c) { return (c >= ‘A’&& c <= ‘Z’) || (c >= ‘a’&& c <= ‘z’) || (c >= ‘0’&& c <= ‘9’); }
char upper2lower(char c)
{
    if (c >= ‘A’&& c <= ‘Z’)
        return c + 32;
    return c;
}
class Solution {
public:
    bool isPalindrome(string s)
    {
        int i = 0, j = s.size() – 1;
        while (i < s.size() && j >= 0) {
            while (!isAlphaNum(s[i]) && i < s.size())
                i++;
            if (i >= s.size())
                break;
            char c1 = upper2lower(s[i]);
            while (!isAlphaNum(s[j]) && j >= 0)
                j–;
            if (j < 0)
                break;
            char c2 = upper2lower(s[j]);
            if (c1 != c2)
                return false;
            i++;
            j–;
        }
        return true;
    }
};

本代码提交AC，用时12MS。

二刷。其实i,j不用走完全程，只需要走到他们交错之后就可以了，也就是只需要判断整个字符串的前半段和后半段是否逆序相等。
至于代码，其实就是把while循环和if条件判断改一下，如下：

bool isAlphaNum(char c) { return (c >= ‘A’&& c <= ‘Z’) || (c >= ‘a’&& c <= ‘z’) || (c >= ‘0’&& c <= ‘9’); }
char upper2lower(char c)
{
    if (c >= ‘A’&& c <= ‘Z’)
        return c + 32;
    return c;
}
class Solution {
public:
    bool isPalindrome(string s)
    {
        int i = 0, j = s.size() – 1;
        while (i <= j) {
            while (!isAlphaNum(s[i]) && i <= j)
                i++;
            if (i > j)
                break;
            char c1 = upper2lower(s[i]);
            while (!isAlphaNum(s[j]) && i <= j)
                j–;
            if (i > j)
                break;
            char c2 = upper2lower(s[j]);
            if (c1 != c2)
                return false;
            i++;
            j–;
        }
        return true;
    }
};

本代码提交AC，用时9MS。

三刷。更简洁的代码：

class Solution {
public:
	bool IsValid(char c) {
		return (c >= '0'&&c <= '9') || (c >= 'a'&&c <= 'z');
	}
	bool isPalindrome(string s) {
		int n = s.size();
		if (n == 0 || n == 1)return true;
		int i = 0, j = n - 1;
		while (i < j) {
			s[i] = tolower(s[i]);
			s[j] = tolower(s[j]);

			if (!IsValid(s[i]))++i;
			else if (!IsValid(s[j]))--j;
			else {
				if (s[i] != s[j])break;
				else {
					++i;
					--j;
				}
			}
		}
		return i >= j;
	}
};

本代码提交AC，用时16MS。

9. 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:

Coud you solve it without converting the integer to a string?

这一题很有意思，要我们判断一个整数是否是回文数。 首先负数不是回文数，个位数是回文数。但是怎样判断大于9的整数是否是回文数呢？ 首先想到的是把int转换为string表示，这样就很方便判断了，但是题目要求不能用额外的存储空间，也就是不能用和x位数线性以上的存储空间，当然几个常数空间是可以的。 后来想依次取出数字的首尾数字，判断是否相等。但是中间有0出现时会有问题，比如1000021，去掉首尾1之后只剩int x=2了，导致判断错误。 还有一个办法是将x转换为x的逆序x’，然后依次判断x和x’的末尾是否相等，但是x’可能超出int表示范围，又作罢。 后来观察发现，回文数字765567在转换为逆序数的过程中，肯定有某个状态，x==x’，比如765=765，而这时x’肯定不会超出int的表示范围。所以我们可以在边逆序的时候边判断。 完整代码如下：

class Solution {
public:
    bool isPalindrome(int x)
    {
        if (x < 10)
            return x >= 0;
        if (x % 10 == 0)
            return false;
        int y = 0;
        while (x > y) {
            y = y * 10 + x % 10;
            if (x == y) //76567
                return true;
            x /= 10;
            if (x == y) //765567
                return true;
        }
        return false;
    }
};

本代码提交AC，用时76MS。

二刷。常规解法，取出每一位数字进行判断：

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        if(x == 0) return true;
        if(x % 10 == 0) return false;
        
        vector<int> digits;
        while(x != 0) {
            digits.push_back(x % 10);
            x /= 10;
        }
        int l = 0, r = digits.size() - 1;
        while(l < r) {
            if(digits[l] != digits[r]) return false;
            ++l;
            --r;
        }
        return true;
    }
};

本代码提交AC，用时52MS。