回文字符串算法多种实现
前言
回文字符串,是指正读和倒读的结果一样的字符串,从结构上来看,两侧的字符呈中心对称。在汉语中,有很多有趣的回文诗词,回文对联熟语,比如“响水池中池水响,黄金谷里谷金黄”、“雾锁山头山锁雾,天连水尾水连天”等。
算法语言
- 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;
}
上面的算法,其实可以认为将原字符串逆序了,使用逆序函数也可以。最终问题是比较逆序前后的字符串。
优化:实际上,上面算法有一定的缺陷的,是可以优化的,我们知道算法在计算机中运行需要耗费一定的时间,我们应当尽量降低不必要的执行次数,以降低时间复杂度。在这里我们只需要对一半字符串进行判断即可,没必要遍历所有字符串。
作者:Miracle
来源:麦瑞克博客
链接:https://www.playcreator.cn/archives/programming-life/datastruct/2013/
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0许可协议,转载请注明!
来源:麦瑞克博客
链接:https://www.playcreator.cn/archives/programming-life/datastruct/2013/
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0许可协议,转载请注明!
THE END
1
打赏
海报
回文字符串算法多种实现
前言
回文字符串,是指正读和倒读的结果一样的字符串,从结构上来看,两侧的字符呈中心对称。在汉语中,有很多有趣的回文诗词,回文对联熟语,比如“响水池中池……
文章目录
关闭