[LeetCode]Palindrome

题目：Palindrome Number

确定一个整数是否是回文。要求没有额外的空间。

思路：

如果有首尾两个指针，则一次比较两个指针对应的数字的值，就能够知道是不是回文数字了；

但是，怎么从后往前遍历呢？

我们可以定义一个数组，分别记录个、十、百、千、万...的位数然后除以数组对应的位数就能从后往前，

const int arr[] = {1000000000,100000000,10000000,1000000,100000,10000,1000,100,10};//int的每个位的值

数组下标从0开始，循环找到第一个商不为0的，就是最高位的值。

然后，按照上面的思路就可以判断是否为回文数字。

bool LeetCode::isPalindrome2(int x){
    if (x < 0)return false;
    if (x < 10)return true;
    if (!(x % 10))return false;
    const int arr[] = {1000000000,100000000,10000000,1000000,100000,10000,1000,100,10};//int的每个位的值
    int i = 0,j = 7,left = 0, right = 0,y = x;
    while (!left){//找到最高位的值
        left = y / arr[i];
        y = y % arr[i];
        ++i;
    }
    right = x % 10;
    x = x / 10;
    if (left != right)return false;//最高位和最低位的比较
    for (; i <= j; --j,++i){
        left = y / arr[i];
        y = y % arr[i];
        right = x % 10;
        x = x / 10;
        if (left != right)return false;//对称的位比较
    }
    return true;
}

注意：

小于10的情况和小于0的情况，特殊考虑。

上面的思路会用到辅助的数组，空间开销比较大，怎么能降低空间开销，实现时间复杂度O(n)，空间复杂度O(1)呢？

思路：

将数字逆置，求给定数字的逆置数字，比较是否相等，这里用到回文数字的对称性。

逆置时，也不一定要将数字逆置完在比较，如果给定数字是回文数字，会有中间就相等的时候，可以通过这个条件来加快循环。

注意：

个位是0的情况要特殊考虑，

加快循环时，要注意奇数个位数和偶数个位数时情况是不同的。

小于10的情况和小于0的情况，特殊考虑。

bool LeetCode::isPalindrome(int x){
    if (x < 0)return false;
    if (x < 10)return true;
    if (!(x % 10))return false;
    int sum = 0, y = x;//sum为x逆置后的值
    while (y){
        sum = sum * 10 + y % 10;
        y = y / 10;
        if (sum == y)return true;//偶数位
        if (sum == y/10)return true;//奇数位
    }
    if (sum == x)return true;
    return false;
}

题目：Valid Palindrome

判断一个字符串是否是回文的，调过特殊字符和符号，只判断字母和数字。

思路：

两个指针，一个从头一个从尾部，比较头尾是否相等。

/**判断字符串是回文的**/
bool LeetCode::isPalindrome(string s){
    if (s.size() < 2)return true;
    transform(s.begin(), s.end(), s.begin(), tolower);//转成小写
    auto left = s.cbegin();
    auto right = s.cend();
    --right;
    while (left < right){
        while (left != s.cend() && !isalnum(*left))++left;//调过标点等特殊字符
        if (left == s.cend())return true;//串尾
        while (!isalnum(*right))--right;//调过标点等特殊字符
        if ((*left) != (*right))return false;//比较收尾的字符
        ++left;
        --right;
    }
    return true;
}

题目：Palindrome Partitioning

找到给定字符串的所有回文子串的不同的组合。

思路：

自己使用递归的方法，借助上面的判断字符串是否是回文字符串的方法。

每次从字符串的第一个字符开始到第i（i:0->n）个字符，将剩下的子串重新执行上面的操作。

然后合并返回的组合。得到最终的结果。

vector<vector<string>> LeetCode::partition(string s){
    vector<vector<string>> arrStr;
    if (s.length() == 0){//s是空串时
        vector<string>strs;
        arrStr.push_back(strs);
        return arrStr;
    }
    if (s.length() == 1){//s只有一个字符的时候
        vector<string>strs;
        strs.push_back(s);
        arrStr.push_back(strs);
        return arrStr;
    }
    for (int i = 1; i <= s.length(); i++){
        auto temp = s.substr(0,i);
        if (isPalindrome(temp)){//判断是否是回文的
            auto ret = partition(s.substr(i,s.length()));//递归求剩下的字符串的回文组合
            for (auto& arr : ret){//将返回的字符串中加上当前的子串,注意要插到头部
                arr.insert(arr.begin(),temp);
                arrStr.push_back(arr);
            }
        }
    }
    return arrStr;
}

注意：

递归终止的条件，不仅判断字符串长度为1，还要判断长度为0的情况，因为可能一开始就是空串，或者上一级递归到了字符串末尾，导致传到下面一级时是空串。

回文的其他算法：

http://www.cnblogs.com/yeqluofwupheng/p/6796747.html

http://www.cnblogs.com/yeqluofwupheng/p/7341905.html