迴文演算法復雜度

『壹』 C++迴文數的問題~\(≧▽≦)/~啦啦啦

#include<iostream>
#include<cstdio>
usingnamespacestd;
voidmain()
{
	charstr[10000];
	charb[10000];
	boolflag=true;
	inti,j,m;
	m=0;
	i=j=0;
	gets(str);//讀入字元串
	for(i=0;i<strlen(str);i++)
	{
		if(str[i]>='A'&&str[i]<='Z')
		{
			b[j]=str[i]+32;//賦值用=號
			j++;
			m+=1;
		}
		else
			if(str[i]>='a'&&str[i]<='z')
			{
				b[j]=str[i];//賦值用=號
				j++;
				m+=1;
			}
			
	}
	for(j=0;j<m;j++)
	{
		if(b[j]!=b[m-1-j])
		{flag=false;}
	}
	if(!flag)
	{	cout<<"N";}
	else
	{cout<<"Y";}
}

『貳』 如何判斷一個字元串是不是迴文串 時間復雜度o 空間復雜度o

對於單鏈表來說，判斷迴文最簡單的方法就是遍歷鏈表，將鏈表中的元素復制到數組中，然後對數組進行判斷是否是迴文數組，但是這不符合O(1)的空間復雜度。

由於空間復雜度的要求，需要就地操作鏈表，不能開辟多餘的空間來進行處理，因此引入快慢指針來進行操作。

快慢指針： slow 和 fast，每次slow指針前進一步，fast指針前進兩步，當遇到指針為空時說明遍歷鏈表完成，此時也就可以找到鏈表的中心位置。

注意，由於鏈表的長度可能是奇數也可能是偶數，因此應該做一個判斷。

找到鏈表的中心後，把鏈表的後半部分進行就地逆轉，就地逆轉是採用頭插法即可。

後半部分逆轉完成後，將鏈表的前半部分和後半部分一次比較，即可判斷是否是迴文。

實現代碼如下：

鏈表類定義：

class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}

}

鏈表就地反轉：

public static ListNode reverseList(ListNode head){
ListNode ptr = head, ptr2 = head;
ListNode fast = head.next;
while(fast!=null){

//頭插法
ptr = fast.next;
fast.next = head;
head = fast;
fast = ptr;
}

//反轉完成後將原頭指針的next設置為null
ptr2.next = null;
return head;
}

判斷鏈表是否是迴文：

1 public static boolean isPalindrome(ListNode head){
2 if(head==null || head.next==null){
3 return true;
4 }
5 //建立快慢指針，尋找鏈表中心
6 ListNode slow = head;
7 ListNode fast = head;
8 while(fast!=null && fast.next!=null){
9 slow = slow.next;
10 fast = fast.next.next;
11 }
12
13 if(fast == null){
14 //偶數個元素(進行鏈表反轉)
15 ListNode ptr = slow, ptr2 = slow;
16 ListNode fast1 = slow.next;
17 while(fast1!=null){
18 ptr = fast1.next;
19 fast1.next = slow;
20 slow = fast1;
21 fast1 = ptr;
22 }
23 ptr2.next = null;
24 }else{
25 //奇數個元素(進行鏈表反轉)
26 ListNode ptr = slow.next,ptr2 = slow.next;
27 ListNode fast1 = slow.next.next;
28 while(fast1 != null){
29 ptr = fast1.next;
30 fast1.next = slow.next;
31 slow.next = fast1;
32 fast1 = ptr;
33 }
34 ptr2.next = null;
35 slow = slow.next;
36 }
37
38 while(slow!=null){
39 if(head.val!=slow.val)
40 return false;
41 slow = slow.next;
42 head = head.next;
43 }
44 return true;
45 }
46
47 }

『叄』 設計演算法，判斷該字元串的前n個字元組成的是否為迴文，且使演算法時間復雜度最小。 （註：123321）

public class test {
public void fun(String str , Integer target){
String rString = str.substring(0, target);
Integer length = rString.length();
char[] c = str.substring(0 , target).toCharArray();
int flag = 0;
if((length >= target) && (target%2 == 0)){
for(int i = 0 ; i < length/2 ; i++){
if(c[i] != c[length-i-1]){
++flag;
System.out.println("不是迴文");
break;
}
}
if(flag == 0){
System.out.println("是迴文");
}
}else{
System.out.println("指定的參數不符合規范,應該為偶數");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
new test().fun("abcdeedcbaaaa", 10);
}

}

『肆』 迴文數的迴文數演算法

隨意找一個十進制的數，把它倒過來成另一個數，再把這兩個數相加，得一個和數，這是第一步;然後把這個和數倒過來，與原來的和數相加，又得到一個新的和數，這是第二步。照此方法，一步步接續往下算，直到出現一個「迴文數」為n。例如:28+82=110,110+011=121，兩步就得出了一個「迴文數」。如果接著算下去，還會得到更多的「迴文數」。這個過程稱為「196演算法」。

『伍』 利用Stack類和Queue類實現判斷一個字元是否為迴文的演算法。所謂迴文就是正讀和反讀都相同的序列

雙端隊列，讀入後左右兩邊出隊進行比較，如果有不同返回假，最後隊列中只有一個元素或空時返回真。時間復雜度O(n/2)。代碼是爪機所以沒法碼了。

『陸』 C語言迴文演算法

我前幾天剛好做過類似題，這里才3位數比較簡單，已經調試並運行過了，絕對准確！
main()
{
int
n,i,a[5];
for(i=10;i<=200;i++)/*迴文數至少為兩位數，即大於9*/
{
if(i/100>=1)/*三位數得情況*/
{
a[0]=i/100;/*百位數*/
a[1]=i%100/10;
a[2]=i%10;
if(a[0]==a[2])printf("\n%d",i);
}
else
/*兩位數得情況*/
{
a[0]=i/10;
a[1]=i%10;
if(a[0]==a[1])printf("\n%d",i);
}
}
}

『柒』 關於迴文演算法

這個函數不對奇偶長度的字元串都通用的 我給你稍微改了下 空都補上了
int IsHuiWen(char *s)
{
SeqStack T; // 定義一個順序棧T
char t;
Init Stack(T); //初始化棧
l=strlen(s); //變數l的值為字元串長度
for(i=0;i <= l/2;i++) Push(&T,s[i]); //i<=l/2和後面的push 作用就是把字元串前半截壓入棧結構
while(!EmptyStock(&T))
{
t=Pop(&T); //讓元素出棧並且賦給t 用來和後面的字元比較
if(t != s[l-i]) //如果中間的2個字元不相同就返回0
{return 0;}
--i; //如果第一次比較相同就比較第二次 從中間向兩邊比較直到棧為空
} // 這個後面的while是多餘的 沒用
return 1;//比較完後都不返回0就是迴文 返回1
}

『捌』 這是100000000內求迴文素數的演算法，誰能幫忙優化下~

//迴文
int palindromic( unsigned long dat )
{
unsigned char buf[20]; //64位2進制最長20位10進制
int i,len;
//10進製取出
len = 0;
while( dat > 0 && len < sizeof(buf) )
{
buf[ len++ ] = dat % 10;
dat /= 10;
}
//判斷迴文
i = 0;
while( i < len )
if( buf[ i++ ] != buf[ --len ] )
return 0;
return 1;
}

//質數(素數)
int prime( unsigned long dat )
{
unsigned long k;
if( !(dat & 0x01 ) && dat != 2 ) //偶數非質數(2例外)
return 0;
for( k=3; k < dat/2; k+=2 ) //因子為偶的情況已經在上一句程序剔除
{
if( !(dat % k ))
return 0;
}
return 1; //質數
}

int main()
{
unsigned long i;
for(i=1; i<9999999; ++i)
if( prime(i) )
if( palindromic(i) )
printf("%d,", i);
}

『玖』 pascal 迴文數問題

先把符號保存好，要連位置也要保存。再求s1的倒序s2，求s1與s2的lcs，而此時的lcs即是迴文數了，求的同時要用標記數組做好標記。輸出時結合先前保存好的字元輸出就行了。時間復雜度是O(n^2)，要看你的除去符號之後的長度了。

『拾』 什麼是迴文數演算法

迴文數演算法 c語言和java語言實現迴文數演算法的區別
問題:
將所有迴文數從小到大排列,求第N個迴文數。
一個正數如果順著和反過來都是一樣的(如13431,反過來也是...