第六周LeetCode算法题两道

本文主要是介绍第六周LeetCode算法题两道，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一道

题目名称：5. Longest Palindromic Substring

题目难度：Medium

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

Example:

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

Example:

Input: "cbbd"
Output: "bb"

题目思路：
找一个中心点，向两边扩散。如果即将扩散的两边的值相等，则继续扩散，否则，以当前中心点开始扩散的回文数的寻找宣告结束。
注意回文数的中点可能有两种情况，一种是回文数的长度为奇数，这种情况下中点只有一个，不影响回文性质。另一种情况是回文数的长度为偶数，这种情况下我们认为中点是由两个相同的字符组成的。
具体的代码如下：

class Solution {
public:string getNextOne(string s, int low, int high) {while (low >= 0 && high < s.size() && s[low] == s[high]) {low--;high++;}string sub = s.substr(low+1, high - low - 1);return sub;}string longestPalindrome(string s) {string longest = "";for (int i = 0; i < s.size(); ++i) {string nextStr = getNextOne(s, i, i);if (nextStr.size() > longest.size())longest = nextStr;nextStr = getNextOne(s, i, i + 1);if (nextStr.size() > longest.size())longest = nextStr;}return longest;}
};

第二道

题目名称：9. Palindrome Number

题目难度：Easy

题目描述：Determine whether an integer is a palindrome. Do this without extra space.

题目分析：
觉得本题出得特别不合理，一开始被题目中的要求“without extra space“限制得死死的，想不出合理的办法。后来想着利用几个int整型试试看能不能过。试了一下，结果是AC，于是有的下面的代码。

class Solution {
public:bool isPalindrome(int x) {if (x == 0) {return true;} else if (x < 0 || x % 10 == 0) {return false;} int test = 0, temp;while (x > test) {test = test * 10 + (x % 10);temp = x;x /= 10;}if (x == test || temp == test)return true;elsereturn false;}
};