概念

所謂回文串，就是字符串反轉(zhuǎn)以后和原串相同，如 abba 和 lippil。對(duì)于回文串還是比較容易去驗(yàn)證的，從字符數(shù)組的兩端開(kāi)始向中間靠攏去驗(yàn)證字符是否相等，但這里是否需要考慮字符數(shù)組長(zhǎng)度的奇偶性呢？其實(shí)是不用的，下面一起來(lái)看看：

Leetcode例題：

1.回文串的驗(yàn)證

2.有效回文

3.回文排列

（1,2題是一樣的，合并講解吧）

點(diǎn)殺回文排列

先講回文排列吧，簡(jiǎn)單一點(diǎn)。首先我們的思路要清楚，無(wú)非就是找出相同的字符并統(tǒng)計(jì)他出現(xiàn)的次數(shù)，我們保證每個(gè)字符只能出現(xiàn)偶數(shù)次，最多允許一個(gè)字符出現(xiàn)奇數(shù)個(gè)（奇數(shù)位字符串的中間元素）

代碼如下：

char Func(char* s)
{
	int  i, count = 0;
	int a[128] = { 0 };
	int sz = strlen(s);//計(jì)算字符數(shù)組長(zhǎng)度來(lái)作為循環(huán)判斷部分
	for (i = 0; i < sz; i++)
	{
		a[s[i]]++;//統(tǒng)計(jì)相同字符出現(xiàn)次數(shù)，有點(diǎn)像哈希表
	}
	for (i = 0; i < 128; i++)
	{
		if (a[i] % 2 == 1)//判斷出現(xiàn)次數(shù)是否為偶數(shù)
			count++;
		if (count >= 2)//判斷是否最多存在一個(gè)出現(xiàn)奇數(shù)次的元素
			return false;
	}
	return true;
}

注意，這里面有一些重要細(xì)節(jié)：

1.數(shù)組 s 為 char 類(lèi)型，字符數(shù)組在內(nèi)存中存儲(chǔ)方式是ASCII碼值，s[ i ]就是在一一列舉其中元素，假如我收到一個(gè) ‘ a ’，a以ASCII碼值作為下標(biāo)++，第二個(gè)‘ a ’找到后依然是用相同的ASCII碼值作為下標(biāo)再++；這就是我統(tǒng)計(jì)數(shù)組中相同元素的次數(shù)的原理。

2. 數(shù)組初始化 a [128]不能更改是因?yàn)锳SCII碼值一共是128個(gè)，0~127。

3.強(qiáng)調(diào)最多一位為奇數(shù)次出現(xiàn)的字符的特殊情況。

點(diǎn)殺回文驗(yàn)證（有效性）

這道題就是典型的指針對(duì)撞題，因?yàn)轭}目告訴考慮數(shù)字和字符，我們寫(xiě)的時(shí)候就可以不考慮字符的大小寫(xiě)，這種方法需要靈活使用庫(kù)函數(shù)。

需要先判斷字符串中的字符是字母或數(shù)字，若不是，就pass掉。在 C 語(yǔ)言中可以用 isalnum() 函數(shù)去判斷。

忽略字母的大小寫(xiě)，所以可以將待比較的字符轉(zhuǎn)化為小寫(xiě)或大寫(xiě)，然后再比較。在 C 語(yǔ)言中可以用 tolower() 和 toupper() 函數(shù)。

對(duì)撞指針

一根指針指向頭，滿足條件時(shí)，往右移動(dòng)；一根指針指向尾，滿足條件時(shí)，往左移動(dòng)；最后兩根指針相遇，循環(huán)條件一般是前下標(biāo)（指針）小于后下標(biāo)（指針）。

送上代碼：

char Fun(char * s)
{
    int left = 0, right = strlen(s) - 1;
    while (left < right) 
    {       //篩選出數(shù)字與字符
        if (!isalnum(s[left])) {
            left++; 
        } else if (!isalnum(s[right])) {
            right--;
        } else { //合并為小寫(xiě)（大寫(xiě)）來(lái)判斷
            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }            
            left++;
            right--;
        }
    }
    return true;
    }         

今天就到這里了家人們，先摸了。

以上就是C語(yǔ)言算法打卡回文串驗(yàn)證算法題解的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言回文串算法驗(yàn)證的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論