C語言算法打卡回文串驗證算法題解

更新時間：2022年02月16日 10:55:43 作者：喬喬家的龍龍

這篇文章主要為大家介紹了C語言算法打卡萬人千提的leetcode回文串的驗證算法題解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步

概念

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

Leetcode例題：

1.回文串的驗證

2.有效回文

3.回文排列

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

點殺回文排列

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

代碼如下：

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

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

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

2. 數(shù)組初始化 a [128]不能更改是因為ASCII碼值一共是128個，0~127。

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

點殺回文驗證（有效性）

這道題就是典型的指針對撞題，因為題目告訴考慮數(shù)字和字符，我們寫的時候就可以不考慮字符的大小寫，這種方法需要靈活使用庫函數(shù)。

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

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

對撞指針

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

送上代碼：

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 { //合并為小寫（大寫）來判斷
            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }            
            left++;
            right--;
        }
    }
    return true;
    }

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

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

您可能感興趣的文章: