前言
回文字符串，是指正读和倒读的结果一样的字符串，从结构上来看，两侧的字符呈中心对称。在汉语中，有很多有趣的回文诗词，回文对联熟语，比如“响水池中池水响，黄金谷里谷金黄”、“雾锁山头山锁雾，天连水尾水连天”等。
算法语言
- Python
- C#
详情
数字121从左往右读与从右往左读是一样的，这种数称为回文数。
找出>=0并且<=n的全部回文数。
注意：单个的数字0，数字1，... 数字9也认为是回文数。
输入格式:
n
输出格式:
多行输出，一行一个数
输入样例:
13输出样例:
0
1
2
3
4
5
6
7
8
9
11
算法实现
使用for循环以及切片方法实现
//使用语言Python
intNum = int(input())
for i in range(intNum+1):
if i<10:
print(i)
elif i<100:
gw=i%10
bw=int(i/10)
if gw==bw:
print(i)
else:
intStr=str(i)
intcount=len(intStr)
halfindex=(int)(intcount/2)
intisDouble=intcount%2==0
left=intStr[0:(intisDouble and halfindex-1 or halfindex) ]
right=intStr[(intisDouble and halfindex or halfindex)+1::intcount]
if left==right:
if intisDouble:
if intStr[halfindex-1]==intStr[halfindex]:
print(i)
else:
print(i)
笔者这里主要为了实现研究回文算法，实际上可以从Python库中调用回文字符串判断的函数。
让我们单独把判断回文字符串的算法拿出来分析
使用For循环实现
只要从前往后判断中心点（根据Length奇偶，中心点存在一个或两个）两边的字符串是否相等，遍历过程应保证两边的字符都相等，否则不是回文字符串。当遍历到中心点或index相同时候则退出循环（如果i>=j发生则说明当前已经遍历到了中心点），则该字符串为回文字符串。
static void Main(string[] args)
{
Console.WriteLine("请输入一组数字");
string str = Console.ReadLine();
Console.WriteLine($"字符串{str}是回文：{IsPalindromic_For(str)}");
Console.ReadLine();
}
public static bool IsPalindromic_For(string str)
{
int i = 0;
int j = str.Length-1;
while (i<j)
{
if (str[i]!=str[j])
{
return false;
}
i++;
j--;
}
return true;
}
使用堆栈实现
我们可以利用栈先进后出的特性，把字符串存入栈中，再遍历时候再从栈中一一取出，得到一个逆序的字符串。拿到逆序的字符串与原字符串进行比较，判断字符串是否相等即可。
//C#语言实现
static void Main(string[] args)
{
Console.WriteLine("请输入一组数字");
string str = Console.ReadLine();
Console.WriteLine($"字符串{str}是回文：{IsPalindromic(str)}");
Console.ReadLine();
}
public static bool IsPalindromic(string str)
{
//利用堆栈的特性
Stack<char> stack = new Stack<char>();
//Queue<char> queue = new Queue<char>();
//分别放入
foreach (char c in str)
{
stack.Push(c);
//queue.Enqueue(c);
}
//string front = null;
string last = "";
//可以优化，只需要对一半字符串进行判断即可，没必要遍历所有字符串。
while (stack.Count>0)
{
//front+=queue.Dequeue();
char c=stack.Pop();
if (str[last.Length] !=c)
{
return false;
}
last += c;
}
return true;
}上面的算法，其实可以认为将原字符串逆序了，使用逆序函数也可以。最终问题是比较逆序前后的字符串。
优化：实际上，上面算法有一定的缺陷的，是可以优化的，我们知道算法在计算机中运行需要耗费一定的时间,我们应当尽量降低不必要的执行次数，以降低时间复杂度。在这里我们只需要对一半字符串进行判断即可，没必要遍历所有字符串。
