Tag Archives: 回文

LeetCode Pseudo-Palindromic Paths in a Binary Tree

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。

LeetCode Palindromic Substrings

LeetCode Palindromic Substrings Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
  1. The input string length won’t exceed 1000.

给定一个字符串,问该字符串中有多少个回文子串。 暴力解法就是枚举每个子串,判断子串是否是回文串。判断一个字符串是否是回文串,可以用首尾指针法,也可以用中心扩展法,方法很多,需要O(n)时间,所以暴力总时间是O(n^3)。 稍微高效一点的方法是,不枚举子串,直接对每个字符用中心扩展法,请看讨论区代码。 我的解法是O(n^2)的DP方法,dp[i][j]表示子串[i,j]是否是回文串。首先对于长度为1的子串dp[i][i]=1肯定都是回文串;求dp[i][j]时,如果s[i]==s[j]且dp[i+1][j-1]是回文串,则dp[i][j]=1也是回文串。 最后统计一下dp数组中有多少个1就有多少个回文子串。 代码如下: [cpp] class Solution { public: int countSubstrings(string s) { int ans = 0, n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = 0; i < n; ++i) { dp[i][i] = 1; ++ans; } for (int len = 2; len <= n; ++len) { for (int i = 0; i < n; ++i) { int j = i + len – 1; if (j >= n)break; if (s[i] == s[j] && (len == 2 || dp[i + 1][j – 1] == 1)) { dp[i][j] = 1; ++ans; } } } return ans; } }; [/cpp] 本代码提交AC,用时12MS。]]>

LeetCode Palindrome Partitioning

131. Palindrome Partitioning


Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

本题要求把字符串s分割成若干个子串,使得每个子串都是回文串。如果有多种分割方法,输出所有的分割方案。 很有意思的一道题。我是这样做的:首先用DP求出任意一个子串s[i,…,j]是否为回文串,这就相当于知道了s中哪几个位置可以切割;然后就在s中DFS每个割点,求出所有的分割方案。
DP求s[i,…,j]是否为回文串的过程是这样的,如果s[i]==s[j],且dp[i+1][j-1]也是回文串,则dp[i][j]也是回文串。所以我们需要先求到长度比较短的s[i+1,j-1]是否为回文串,然后再求长度更长的是否为回文串。所以在helper函数的外层循环是子串的长度。

求到了任意一个子串是否为回文串之后,DFS每个割点就好了,这个和枚举排列情况很类似,就不再赘述了。完整代码如下:

class Solution {
private:
    void helper(const string& s, vector<vector<int> >& dp)
    {
        int n = s.size();
        for (int i = 0; i < n; ++i)
            dp[i][i] = 1; // 单个字符自身就是回文串
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len – 1 < n; ++i) {
                if (s[i] == s[i + len – 1] && ((i + 1 <= i + len – 2 && dp[i + 1][i + len – 2] == 1) || i + 1 > i + len – 2)) {
                    dp[i][i + len – 1] = 1;
                }
            }
        }
    }
    void dfs(const string& s, vector<vector<int> >& dp, vector<vector<string> >& ans, vector<string>& cand, int idx)
    {
        if (idx == s.size()) {
            ans.push_back(cand);
            return;
        }
        for (int i = idx; i < s.size(); ++i) {
            if (dp[idx][i] == 1) {
                cand.push_back(s.substr(idx, i – idx + 1));
                dfs(s, dp, ans, cand, i + 1);
                cand.pop_back();
            }
        }
    }
public:
    vector<vector<string> > partition(string s)
    {
        int n = s.size();
        vector<vector<int> > dp(n, vector<int>(n, 0));
        helper(s, dp);
        vector<vector<string> > ans;
        vector<string> cand;
        dfs(s, dp, ans, cand, 0);
        return ans;
    }
};

本代码提交AC,用时6MS。

二刷。不用DP提前判断,而是每次都暴力判断是否为回文:

class Solution {
public:
	bool IsPal(const string &s, int l, int r) {
		if (l > r)return false;
		if (l == r)return true;
		while (l < r) {
			if (s[l] != s[r])break;
			++l;
			--r;
		}
		return l >= r;
	}
	void DFS(vector<vector<string>> &ans, vector<string> &cur, string &s, int idx) {
		int n = s.size();
		if (idx >= n) {
			ans.push_back(cur);
			return;
		}
		for (int i = idx; i < n; ++i) {
			if (IsPal(s, idx, i)) {
				cur.push_back(s.substr(idx, i - idx + 1));
				DFS(ans, cur, s, i + 1);
				cur.pop_back();
			}
		}
	}
	vector<vector<string>> partition(string s) {
		vector<vector<string>> ans;
		vector<string> cur;
		DFS(ans, cur, s, 0);
		return ans;
	}
};

本代码提交AC,用时12MS,比第一种方法慢,还是第一种方法提前求DP更高效。

LeetCode Longest Palindromic Subsequence

LeetCode Longest Palindromic Subsequence Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000. Example 1: Input:

"bbbab"
Output:
4
One possible longest palindromic subsequence is “bbbb”. Example 2: Input:
"cbbd"
Output:
2
One possible longest palindromic subsequence is “bb”.
求一个字符串的最长回文子序列。 使用DP求解,假设dp[i][j]表示原字符串范围[i,j]中的最长回文子序列的长度。则如果s[i]==s[j],则dp[i][j]=dp[i+1][j-1]+2,即是临近内层的最长回文子序列长度加2。如果s[i]!=s[j],则dp[i][j]=max(dp[i][j-1],dp[i+1][j]),即是左端或者右端最长回文子序列长度的最大值。 初始时dp[i][i]=1,即单个字符自成回文,长度为1。 代码如下: [cpp] class Solution2 { public: int longestPalindromeSubseq(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = n – 1; i >= 0; –i) { dp[i][i] = 1; for (int j = i + 1; j < n; ++j) { if (s[i] == s[j])dp[i][j] = dp[i + 1][j – 1] + 2; else dp[i][j] = max(dp[i][j – 1], dp[i + 1][j]); } } return dp[0][n – 1]; } }; [/cpp] 本代码提交AC,用时68MS。 上述计算有些区间会重复计算dp[i][j],可以用递归方法求解,并且把计算过的值记录下来,下次遇到查询时直接返回。代码如下: [cpp] class Solution { private: int helper(int l, int r, const string &s, vector<vector<int>> &dp) { if (l > r)return 0; if (l == r)return 1; if (dp[l][r] != 0)return dp[l][r]; if (s[l] == s[r])dp[l][r] = helper(l + 1, r – 1, s, dp) + 2; else dp[l][r] = max(helper(l, r – 1, s, dp), helper(l + 1, r, s, dp)); return dp[l][r]; } public: int longestPalindromeSubseq(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); return helper(0, n – 1, s, dp); } }; [/cpp] 本代码提交AC,用时49MS。 参考:https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution/2]]>

LeetCode Longest Palindrome

LeetCode 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.

题意:给定一个字符串,现要从字符串中抽取若干个字符,构成一个回文串,问最长能构成多长的回文串。 回文串有两种形式,偶数型abba和奇数型abcba,所以我们先hash统计每个字符出现的次数,然后对于偶数的字符可以直接全拿来用,对于奇数的字符,减1之后只拿偶数个字符,但是我们最后还可以把减去的那个字符拿回来构成奇数型回文串,但也就只能拿回一个字符,所以要提前做好标记。 完整代码如下: [cpp] class Solution { public: int longestPalindrome(string s) { unordered_map<char, int> hash; for (int i = 0; i < s.size(); ++i) { ++hash[s[i]]; } int ans = 0; int odd = 0; unordered_map<char, int>::iterator it = hash.begin(); while (it != hash.end()) { if ((it->second) & 1) { odd = 1; ans += it->second – 1; } else { ans += it->second; } ++it; } return ans + odd; } }; [/cpp] 本代码提交AC,用时9MS。]]>

LeetCode Palindrome Linked List

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。

LeetCode Valid Palindrome

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。

LeetCode Palindrome Partitioning II

132. Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

动态规划题目,类似于矩阵链相乘。设dp[i][j]表示s[i,…,j]是否为回文串,cut[j]表示s[1,…,j]需要多少刀才能切成回文串。动态规划运行到最后返回cut[n]。
对于cut[j],切第一刀的时候,我们尝试前面j个切割位点,比如我们尝试切第i点,则s[1,…,j]被分成了s[1,…,i-1]和s[i,…,j],如果s[i,…,j]为回文串,则s[i,…,j]不需要再切了,又因为cut[i-1]我们之前已经算过了,所以在i处切一刀,有cut[j]=cut[i-1]+1。尝试所有的切割位点i,找最小的cut[j]。
如果发现i=1的时候s[i,…,j]为回文串,则s[1,…,j]不需要再切了,所以cut[j]=0。
完整代码如下:

class Solution {
public:
    int minCut(string s)
    {
        int n = s.size();
        vector<vector<bool> > dp(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++)
            dp[i][i] = true;
        vector<int> cut(n, 0); // # of cut for s[0,j]
        for (int j = 0; j < n; j++) {
            cut[j] = j; // set maximum # of cut
            for (int i = 0; i <= j; i++) {
                if (s[i] == s[j] && (j – i <= 1 || dp[i + 1][j – 1])) {
                    dp[i][j] = true;
                    if (i > 0) // if need to cut, add 1 to the previous cut[i-1]
                        cut[j] = min(cut[j], cut[i – 1] + 1);
                    else // if [0…j] is palindrome, no need to cut cut[j] = 0;
                }
            }
        }
        return cut[n – 1];
    }
};

本代码提交AC,用时84MS。

二刷。参考讨论区一个大神的做法:https://discuss.leetcode.com/topic/2840/my-solution-does-not-need-a-table-for-palindrome-is-it-right-it-uses-only-o-n-space。这种方法不需要上面的做法的dp数组,效率也会高很多。

还是需要cuts数组,cuts[i]表示前i个字符切成回文子串,最少的刀数。对于每一个字符,我们枚举以该字符为中心,能够扩展到的最长的回文子串的长度,比如下图,以b为中心扩展,扩展到aba是一个回文子串,那么要把Y切成回文子串,需要的刀数不超过把X切成回文子串需要的刀数加1,也就是cuts[Y]=min(cuts[Y],cuts[X]+1)。
注意,扩展的时候,需要考虑到以b为中心的回文子串的长度是奇数还是偶数。

.......aba...
|<-X->| ^
|<---Y-->|

通过枚举每一个回文中心点,我们可以算到所有的cuts,最后返回cuts[n]。完整代码如下:

class Solution {
public:
    int minCut(string s)
    {
        int n = s.size();
        vector<int> cuts(n + 1, 0); // cuts[i] 表示前i个字符切成回文子串,最少的刀数
        for (int i = 0; i <= n; ++i)
            cuts[i] = i – 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; i – j >= 0 && i + j < n && s[i – j] == s[i + j]; ++j) // 最后一个是奇数长回文子串
                cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i – j] + 1);
            for (int j = 1; i – j + 1 >= 0 && i + j < n && s[i – j + 1] == s[i + j]; ++j) // 最后一个是偶数长回文子串
                cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i – j + 1] + 1);
        }
        return cuts[n];
    }
};

本代码提交AC,用时6MS,神速。

三刷。两个DP,第一个DP求解出任意两个位置的子串[i:j]是否为回文。第二个DP2,DP2[j]表示前j长的字符串,需要的最小cut数,对于第j个字符,它可以自己独立成为一个回文,所以DP2[j]=DP2[j-1]+1;还可以遍历j前面的字符i,如果[i:j]能形成回文的话,则DP2[j]=DP2[i-1]+1。完整代码如下:

class Solution {
public:
	void preprocess(const string &s, vector<vector<int>> &dp) {
		int n = s.size();
		for (int i = 0; i < n; ++i)dp[i][i] = 1;
		for (int len = 2; len <= n; ++len) {
			for (int i = 0; i < n; ++i) {
				int j = i + len - 1;
				if (j < n && s[i] == s[j] && (len == 2 || dp[i + 1][j - 1] == 1)) {
					dp[i][j] = 1;
				}
			}
		}
	}
	int minCut(string s) {
		int n = s.size();
		if (n == 0 || n == 1)return 0;
		vector<vector<int>> dp(n, vector<int>(n, 0));
		preprocess(s, dp);
		vector<int> dp2(n, 0);
		for (int j = 1; j < n; ++j) {
			dp2[j] = dp2[j - 1] + 1;
			for (int i = j - 1; i >= 0; --i) {
				if (dp[i][j] == 1) {
					int pre_cut = i > 0 ? dp2[i - 1] + 1 : 0;
					dp2[j] = min(dp2[j], pre_cut);
				}
			}
		}
		return dp2[n - 1];
	}
};

本代码提交AC,用时44MS。

LeetCode Palindrome Number

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。

LeetCode Longest Palindromic Substring

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

这题要求我们找出一个字符串S中的最长回文子串,之前在hihoCoder 1032-最长回文子串就详细讨论过相关问题,这里就不再赘述了,代码完全一样,如下:

class Solution {
public:
	string preProcess(string s)
	{
		int n = s.size();
		if (n == 0)
			return "^#";
		string ret = "^";
		for (int i = 0; i < n; i++)
			ret += "#" + s.substr(i, 1);
		return ret + "#$";
	}
	string longestPalindrome(string s) {
		string t = preProcess(s);
		vector<int> p(t.size(), 0);
		int c = 0, r = 0, n = t.size();
		for (int i = 1; i < n - 1; i++)
		{
			int i_mirror = 2 * c - i;
			p[i] = (r > i) ? min(p[i_mirror], r - i) : 0;
			while (t[i + p[i] + 1] == t[i - p[i] - 1])
				p[i]++;
			if (i + p[i] > r)
			{
				c = i;
				r = i + p[i];
			}
		}
		
		int maxLen = 0, centerIndex = 0;
		for (int i = 1; i < n - 1; i++)
		{
			if (p[i] > maxLen)
			{
				maxLen = p[i];
				centerIndex = i;
			}
		}
		
		return s.substr((centerIndex - 1 - maxLen) / 2, maxLen);
	}
};

本代码提交AC,用时12MS,击败了73%的CPP用户,看来效率不错,估计中心扩展法$O(n^2)$也能过。

二刷。上面的Manacher’s算法过于小众,咱们还是来点大众算法吧,容易理解和记忆。

首先是DP方法,设dp[i][j]=1表示s[i:j]形成回文,=0表示不是回文。则如果s[i:j]形成回文,且s[i-1]==s[j+1],则可以在s[i:j]的基础上进一步扩展,使得s[i-1:j+1]也是回文,即dp[i-1][j+1]=1。

稍微要注意的是DP的时候,第一层循环是子串的长度,因为我们是在短的子串上看起周围2个字符是否相等,所以先要求出短的dp[i][j],再求长的dp[i-1][j+1]。

完整代码如下:

class Solution {
public:
	string longestPalindrome(string s) {
		int n = s.size();
		if (n == 0)return "";
		vector<vector<int>> dp(n, vector<int>(n, 0));
		int ans = 1, u = 0, v = 0;
		for (int len = 0; len < n; ++len) {
			for (int i = 0; i < n; ++i) {
				int j = i + len;
				if (j >= n)break;

				if (len == 0)dp[i][j] = 1;
				else if (len == 1) {
					if (s[i] == s[j]) {
						dp[i][j] = 1;
						if (2 > ans) {
							ans = 2;
							u = i;
							v = j;
						}
					}
				}
				else {
					if (dp[i + 1][j - 1] == 1 && s[i] == s[j]) {
						dp[i][j] = 1;
						if (j - i + 1 > ans) {
							ans = j - i + 1;
							u = i;
							v = j;
						}
					}
				}
			}
		}
		return s.substr(u, v - u + 1);
	}
};

本代码提交AC,用时184MS。

还有一种中心扩展法也很好理解,即假设每个字符是回文的中心字符,然后看看两端字符是否相等,如果相等的话,则继续扩展。需要注意的是,回文有两种形式,一种是aba,即中心只有一个字符,且总长度是奇数;另一种是abba,即中心有两个字符,且总长度是偶数。这种解法相比于上一种解法,只需要O(1)的空间复杂度。

完整代码如下:

class Solution {
public:
	int expand(string &s, int l, int r) {
		int n = s.size();
		while (l >= 0 && r < n&&s[l] == s[r]) {
			--l;
			++r;
		}
		return r - l - 1;
	}
	string longestPalindrome(string s) {
		if (s.size() == 0)return "";
		string ans = "";
		for (int i = 0; i < s.size(); ++i) {
			int len1= expand(s, i, i);
			int len2= expand(s, i, i + 1);
			if (len1 > len2&&len1 > ans.size()) {
				ans = s.substr(i - len1 / 2, len1);
			}
			if (len2 > len1&&len2 > ans.size()) {
				ans = s.substr(i - len2 / 2 + 1, len2);
			}
		}
		return ans;
	}
};

本代码提交AC,用时20MS。