当前位置：首页 > article >正文

【算法】回文数索引、回文子串输出、整数反转

article 2024/11/19 0:06:23

回文数索引

思路：

回文子串输出

思路

回文数索引

思路：

目标字母索引可能是一个或者是两个，返回任意的一个索引即可，如果已经是回文串则直接返回-1。

下面列出几种目标删除字母可能出现的位置：

我们可以先定义两个指针left和right，分别指向字符串的起始和末尾，while(left < right)，如果该循环中没有str[left] != str[right]，则直接返回-1;若有str[left] != str[right]，则返回的索引就是此时的left或者right，可以看出上图中的情况二，left和right均为目标字母的索引。那其他情况怎么判断目标字母索引是left和right中的哪一个？我们可以进行一个简单的判断：if(str[left+1] == str[right])则目标字母索引就是left，否则就是right。

#include <iostream>
#include <string>
using namespace std;

int grapIndex(const string& str)
{
    int left = 0,right = str.length()-1;
    while(left < right)
    {
        if(str[left] != str[right])
        {
            if(str[left+1] == str[right])
            return left;
            else
            return right;
        }
        ++left;
        --right;
    }
    return -1;
}

int main() {
    int cnt = 0;
    cin >> cnt;
    while(cnt--)
    {
        string str;
        cin>>str;
        cout<< grapIndex(str) << endl;
    }
    return 0;
}

回文子串输出

思路：

首先求出所有的回文子串，可以使用中心扩展算法、动态规划，由于要考虑到打印所有回文子串的顺序问题因此该题使用中心扩展算法会好一些。利用中心扩展思想求出所有回文子串后，将这些子串全部存入到一个vector<string> vv中，题目要求是子串长度小的优先输出，长度相同的按其在原字符串中出现位置靠左的先输出，我们可以使用map<int,vector<int>> mymap容器(自动排序)，key表示子串的可能的长度，value代表长度相同的所有子串索引(vector<string> vv的索引)的数组集合。

#include <iostream>
#include <string>
#include <vector>
#include <map>
using std::cout;
using std::cin;
using std::endl;
using std::string;
using std::vector;
using std::map;
void outputString()
{
    string s;
    cin >> s;
    //中心扩展思想
    int size = s.length();
    vector<string> vv;
    for (int i = 0;i < size;++i)
    {
        int left = i, right = i;
        int len = 0;
        while (left >= 0 && right < size && s[left] == s[right])
        {
            len = right - left + 1;
            if (len >= 2)
                vv.push_back(s.substr(left, len));
            --left;
            ++right;
        }
        left = i;
        right = i + 1;
        while (left >= 0 && right < size && s[left] == s[right])
        {
            len = right - left + 1;
            if (len >= 2)
                vv.push_back(s.substr(left, len));
            --left;
            ++right;
        }
    }
    map<int,vector<int>> mymap;
    for (int i = 0;i < vv.size();++i)
    {
        mymap[vv[i].size()].emplace_back(i);
    }
    for (const auto& e : mymap)
    {
        if ((e.second).size() > 1)
        {
            for (int i = 0;i < (e.second).size();++i)
                cout << vv[(e.second)[i]] << endl;
            continue;
        }
        cout << vv[(e.second)[0]] << endl;
    }
}
int main()
{
    outputString();
    return 0;
}

整数反转

思路：

int reverse(int x) {
        int res = 0;
        while(x)
        {
        if(res > INT_MAX/10 || res < INT_MIN/10)
        return 0;
        int rev = x%10;
        res = res*10 + rev;
        x /= 10;
        }
        return res;
    }

该题是将一个32位有符号整数x进行反转，如果输入的x超过32位的有符号整数范围[-2^31，2^31-1]，就返回0。那我们就从整数x的最后一位开始一位一位的重新拼成一个反转后的数字，如果想完成这样的操作必须使用%和/运算符，我们现在是要x的最后一位可以进行x%10，这样就可以的到x的最后一位(反转后的数的最高位，重复后面的操作可以得到反转后得数的次高位，次次高位)，接下来x /= 10(更新x)，如此重复直至当0 == x是退出循环，但是要保证反转后得到的数字res >= INT_MAX && res <= INT_MAX，因此我们要在while循环里给出这样一个条件：if(res > INT_MAX/10 || res < INT_MIN/10)，为什么是/10为什么不除100或者是1000呢？我们假定现在限制的最大值是[-5157,5158]，如果大于这个区间的数都会溢出，假定给定的x = -7555，如果不加判断条件，则反转后的整数就是-5557就会溢出，因此/10的作用：-555 < -515 条件成立则直接返回0；如果/100判断，假定x = -535，-53 < -51此时返回0的话就错了，明显-535没有超过我们规定的区间。

查看全文

http://www.kler.cn/a/399379.html