C语言算法打卡回文串验证算法题解

目录
  • 概念
  • Leetcode例题：
    • 1.回文串的验证
    • 2.有效回文
    • 3.回文排列
  • 点杀回文排列
  • 点杀回文验证（有效性）
  • 对撞指针

概念

所谓回文串，就是字符串反转以后和原串相同，如 abba 和 lippil。对于回文串还是比较容易去验证的，从字符数组的两端开始向中间靠拢去验证字符是否相等，但这里是否需要考虑字符数组长度的奇偶性呢？其实是不用的，下面一起来看看：

Leetcode例题：

1.回文串的验证

2.有效回文

3.回文排列

（1,2题是一样的，合并讲解吧）

点杀回文排列

先讲回文排列吧，简单一点。首先我们的思路要清楚，无非就是找出相同的字符并统计他出现的次数，我们保证每个字符只能出现偶数次，最多允许一个字符出现奇数个（奇数位字符串的中间元素）

代码如下：

char Func(char* s)
{
	int  i, count = 0;
	int a[128] = { 0 };
	int sz = strlen(s);//计算字符数组长度来作为循环判断部分
	for (i = 0; i < sz; i++)
	{
		a[s[i]]++;//统计相同字符出现次数，有点像哈希表
	}
	for (i = 0; i < 128; i++)
	{
		if (a[i] % 2 == 1)//判断出现次数是否为偶数
			count++;
		if (count >= 2)//判断是否最多存在一个出现奇数次的元素
			return false;
	}
	return true;
}

注意，这里面有一些重要细节：

1.数组 s 为 char 类型，字符数组在内存中存储方式是ASCII码值，s[ i ]就是在一一列举其中元素，假如我收到一个 ‘ a ’，a以ASCII码值作为下标++，第二个‘ a ’找到后依然是用相同的ASCII码值作为下标再++；这就是我统计数组中相同元素的次数的原理。

2. 数组初始化 a [128]不能更改是因为ASCII码值一共是128个，0~127。

3.强调最多一位为奇数次出现的字符的特殊情况。

点杀回文验证（有效性）

这道题就是典型的指针对撞题，因为题目告诉考虑数字和字符，我们写的时候就可以不考虑字符的大小写，这种方法需要灵活使用库函数。

需要先判断字符串中的字符是字母或数字，若不是，就pass掉。在 C 语言中可以用 isalnum() 函数去判断。

忽略字母的大小写，所以可以将待比较的字符转化为小写或大写，然后再比较。在 C 语言中可以用 tolower() 和 toupper() 函数。

对撞指针

一根指针指向头，满足条件时，往右移动；一根指针指向尾，满足条件时，往左移动；最后两根指针相遇，循环条件一般是前下标（指针）小于后下标（指针）。

送上代码：

char Fun(char * s)
{
    int left = 0, right = strlen(s) - 1;
    while (left < right)
    {       //筛选出数字与字符
        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语言算法打卡回文串验证算法题解的详细内容，更多关于C语言回文串算法验证的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C语言用栈和队列实现的回文检测功能示例

    C语言用栈和队列实现的回文检测功能示例

    本文实例讲述了C语言用栈和队列实现的回文功能.分享给大家供大家参考,具体如下: #include<stdio.h> #include<malloc.h>//内存分配头文件 #include<math.h>//在math.h中已定义OVERFLOW的值为3 #define SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typede

  • C++/C 回文字符串的实例详解

    C++/C 回文字符串的实例详解

    C++/C回文字符串的实例详解 判断输入的字符串是不是回文字符串,正反读一样. .C版 #include<stdio.h> int main() { char he[100]; char a; int i=0,flag=1; while((a=getchar())!='\n') { he[i]=a; i++; } int n=i; for(i=0;i<n/2;i++) { printf("%c\t%c\n",he[i],he[n-1-i]); if(he[i]!=he

  • C语言如何用顺序栈实现回文序列判断

    C语言如何用顺序栈实现回文序列判断

    我是采用了两个栈值得比较大小判断得(可能比较浪费空间但是代码我感觉简单一点) 首先是定义一个栈的结构元素,由于是字符串类型就直接定义一个char的数组就可以:. typedef struct stack { char data[MAX_SIZE]; //储存字符串// int top; //记录栈顶// }SeqStack; 下来就是初始化,我这里是用的耿国华老师的方法就直接给一个top元素指向栈顶,传入的指针地址:. void Initstack(SeqStack *S) //初始化栈,让to

  • c语言描述回文数的三种算法

    题目描述 注意:(这些回文数都没有前导0) 1位的回文数有0,1,2,3,4,5,6,7,8,9 共10个: 2位的回文数有11,22,33,44,55,66,77,88,99 共9个: * 请问:n位的回文数有多少个?请编写一个递归函数来解决此问题!!! [输入形式]一行一个正整数,代表多少位 [输出形式]一行一个正整数,代表回文诗的个数 [样例输入]2 [样例输出]9 输入: 3 输出: 90 输入: 5 输出: 900 **输入: 10 输出: 90000** 输入: 8 输出: 9000

  • C++实现LeetCode(验证回文字符串)

    [LeetCode] 125.Valid Palindrome 验证回文字符串 Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a

  • C语言算法打卡回文串验证算法题解

    C语言算法打卡回文串验证算法题解

    目录 概念 Leetcode例题: 1.回文串的验证 2.有效回文 3.回文排列 点杀回文排列 点杀回文验证(有效性) 对撞指针 概念 所谓回文串,就是字符串反转以后和原串相同,如 abba 和 lippil.对于回文串还是比较容易去验证的,从字符数组的两端开始向中间靠拢去验证字符是否相等,但这里是否需要考虑字符数组长度的奇偶性呢?其实是不用的,下面一起来看看: Leetcode例题: 1.回文串的验证 2.有效回文 3.回文排列 (1,2题是一样的,合并讲解吧) 点杀回文排列 先讲回文排列吧,

  • python最长回文串算法

    给定一个字符串,要求在这个字符串中找到符合回文性质的最长子串.所谓回文性是指诸如 "aba","ababa","abba"这类的字符串,当然单个字符以及两个相邻相同字符也满足回文性质. 看到这个问题,最先想到的解决方法自然是暴力枚举,通过枚举字符串所有字串的起点,逐一判断满足回文性的子串,记录长度并更新最长长度.显然这种算法的时间复杂度是很高的,最坏情况可以达到O(N*N).所以呢,这里提出一个优化的方案,通过枚举字符串子串的中心而不是起点,向两

  • Java实现查找当前字符串最大回文串代码分享

    先看代码 public class MaxHuiWen { public static void main(String[] args) { // TODO Auto-generated method stub String s = "abb"; MaxHuiWen(s); } //1.输出回文串 public static void MaxHuiWen(String s){ //存储字符串的长度 int length = s.length(); //存储最长的回文串 String M

  • Python实现"验证回文串"的几种方法

    一.LeetCode--125.验证回文串 1.问题描述 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写. 说明:本题中,我们将空字符串定义为有效的回文串. 2.示例 示例 1: 输入: "A man, a plan, a canal: Panama" 输出: True 示例 1: 输入: "race a car" 输出: False 示例 3: 输入: "!!!" 输出: True 二.解题分析 在排除空格及特殊

  • js如何找出字符串中的最长回文串

    本文实例为大家分享了js找出字符串中的最长回文串的具体代码,供大家参考,具体内容如下 <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <title>回文</title> <link rel=&q

  • 用JAVA实现单链表，检测字符串是否是回文串

    一.需求 使用JAVA实现单链表,使用单链表检测字符串是否是回文串 二.需求分析 回文串最重要的就是对称,那么最重要的问题就是找到那个中心,用快指针每步走两格,当他到达链表末端的时候,慢指针刚好到达中心,慢指针在遍历过程中(快指针到达末端时)把走过的节点进行反向操作,此时从中位点分为前后两部分,此时前半部分的指针开始往回指(取next的时候,取的是前一个节点),而慢指针继续向前,跟前半部分的数据依次进行比对,当慢指针扫完整个链表,就可以判断这是回文串,否则就提前退出,同时在前半部分往回遍历的过程

  • C++实现LeetCode(132.拆分回文串之二)

    [LeetCode] 132.Palindrome Partitioning II 拆分回文串之二 Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. Example: Input: "aab" Output: 1 Explan

  • C++实现LeetCode(131.拆分回文串)

    [LeetCode] 131.Palindrome Partitioning 拆分回文串 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example: Input: "aab" Output: [ ["aa","b"

  • Java花式解决'分割回文串 ii'问题详解

    Java花式解决'分割回文串 ii'问题详解

    目录 前言 题目 思路分析 案例说明 初级代码 代码升级 1.回文串动归 2.综合动归 3.奇思妙想 前言 最学习动态规划思想的路上,遇见了'分割回文串问题',如临大敌啊,题目听起来蛮简单,思考起来却也没那么容易,比解决问题更头疼的是如何将解决方法进行优化,使得时间空间复杂度尽量的小,经过了反复的挣扎思考,终于总结出来了这一篇 分割回文串 ii 的文章,花式解决该问题,总有一款适合你. 牛客链接 题目 给出一个字符串s,分割s使得分割出的每一个子串都是回文串 计算将字符串s分割成回文分割结果的最

  • Python实现常见的回文字符串算法

    回文 利用python 自带的翻转 函数 reversed() def is_plalindrome(string): return string == ''.join(list(reversed(string)))` 自己实现 def is_plalindrome(string): string = list(string) length = len(string) left = 0 right = length - 1 while left < right: if string[left]

随机推荐