tmp_获取下一个回文数

 

直接拿之前一次竞赛中写的code，稍微完善了点，后面有机会在优化

 

uint64_t GetNextPalindrome(uint64_t data)
    {
        //100以内的数字已经特殊考虑过，不存在差值1的两个回文数
        //首先得到长度，如果是奇数，取前一半+中间值构造，如果是偶数，取前一半构造
        
        //====================
        //添加部分code，得到通用的获取下一个回文数的函数，记录到代码库里面，有需要时候直接拿来用
        //函数功能是获取下一个回文数，
        //下面的是100意外的部分，这里添加100以内的处理
        //if (data < 100)
        //{
        //    if (data < 9)
        //    {
        //        //个位数，直接加1
        //        return data + 1;
        //    }
        //    //两位数
        //}
        //构建表直接返回好了
        if (data < 100) { vector<int> tmpdata= { 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99,101 }; for (int i = 0; i < tmpdata.size(); i++) { if (data < tmpdata[i]) { return tmpdata[i]; } } } //====================  uint64_t tmpdata = data; uint64_t length = 0; while (tmpdata) { tmpdata /= 10; length++; } //到这里得到数据长度，根据奇偶判断 if (length % 2 == 0) { //偶数长度  uint64_t highhalf; highhalf = data / (uint64_t)(pow(10, length / 2)); //得到前一半  uint64_t lowhalf; lowhalf = data % (uint64_t)(pow(10, length / 2)); //低一半 uint64_t tmphigh = GetPallindrom(highhalf); if (tmphigh > lowhalf) { //只需要将高一般构建结果即可 return data + (tmphigh - lowhalf); } else { highhalf += 1; uint64_t tmplength = 0; tmpdata = highhalf; while (tmpdata) { tmpdata /= 10; tmplength++; } if (tmplength == length / 2) { //没产生进位 return highhalf*pow(10, tmplength) + GetPallindrom(highhalf); } else { //返回奇数个的10X01 return highhalf*pow(10, tmplength - 1) + GetPallindrom(highhalf); } } } else { //奇数长度中间+1即可，如果原来是9，变为10XX01 uint64_t highhalf = data / (uint64_t)(pow(10, length / 2)); uint64_t mid = highhalf % 10; highhalf /= 10; uint64_t lowhalf = data % (uint64_t)(pow(10, length / 2)); uint64_t tmphighhalf = GetPallindrom(highhalf); //不需要动到中间位置数组 if (tmphighhalf > lowhalf) { return data + (tmphighhalf - lowhalf); } //需要更新中间数字 if (mid < 9) { return (highhalf * 10 + mid + 1)*pow(10, length / 2) + tmphighhalf; } else { //高一半+1不进位，只需要高一半+1，该位变0即可，比如191 -> 202 //如果高位+1后需要进位，如99X，则需要变为1001，即最小的高一位 mid = 0; highhalf += 1; tmphighhalf = GetPallindrom(highhalf); uint64_t tmplength = 0; tmpdata = highhalf; while (tmpdata) { tmpdata /= 10; tmplength++; } if (tmplength == length / 2) { //没产生进位 return (highhalf * 10 + mid)*pow(10, length / 2) + tmphighhalf; } else { //产生了进位 比如999应该变为1001 return highhalf*pow(10, tmplength) + tmphighhalf; } } } } uint64_t GetPallindrom(uint64_t data) { uint64_t ret = 0; while (data>0) { ret = ret * 10 + data % 10; data = data / 10; } //cout << "debug:" << data << " -> " << ret << endl;; return ret; }