沈阳大型网站设计公司,WordPress纯代码添加雪花,学院路网站建设,学ui设计需要具备哪些条件目录
1.题目
2.自解
提交结果
反思
大小写之间的位运算
提交结果
3.代码优化
提交结果
编辑
4.LeetCode网友提供的解法 1.题目
https://leetcode.cn/problems/XltzEq/description/ 给定一个字符串 s #xff0c;验证 s 是否是 回文串 #xff0c;只考虑字母和数…目录
1.题目
2.自解
提交结果
反思
大小写之间的位运算
提交结果
3.代码优化
提交结果
编辑
4.LeetCode网友提供的解法 1.题目
https://leetcode.cn/problems/XltzEq/description/ 给定一个字符串 s 验证 s 是否是 回文串 只考虑字母和数字字符可以忽略字母的大小写。 本题中将空字符串定义为有效的 回文串 。 示例 1: 输入: s A man, a plan, a canal: Panama
输出: true
解释amanaplanacanalpanama 是回文串 示例 2: 输入: s race a car
输出: false
解释raceacar 不是回文串 提示 1 s.length 2 * 105字符串 s 由 ASCII 字符组成 2.自解
将原数组中所有字母(将小写字母转换为大写字母)和数字字符复制到另一个数组中之后用双指针算法
双指针算法参见L8.【LeetCode笔记】回文数
bool isPalindrome(char * s)
{if (sNULL)return true;int lengthstrlen(s);char* arr(char*)malloc(length);int length_c0;for (int i0;ilength;i){if (!((s[i]As[i]Z)||(s[i]as[i]z)||(s[i]0 s[i]9)))continue;arr[length_c]toupper(s[i]);}char* leftarr[0];char* rightarr[length_c-1];while (left right){if (*left *right){left;right--;continue;}elsereturn false;}free(arr);return true;}
备注:toupper函数为将小写字母转换为大写字母返回,如果非小写字母,返回原字符
cplusplus网对该函数的详细解释 提交结果 空间复杂度为,可以想办法降至
反思
其实没有必要调用toupper,用位运算更加简洁而且更快 A: 0100 0001b a: 0110 0001b Z: 0101 1010 z: 0111 1010 ,可以发现大小写之间只差了
0010_ 0000b 大小写之间的位运算 对于字符c有 c ^ 32 大小写反转 (汇编 xor byte c,0010_0001b) c | 32 大写转小写或者小写转小写(汇编 or byte c,0010_0001b) c ~32 小写转大写或者大写转大写(汇编 and byte c,1101_1111b) 因此将arr[length_c]toupper(s[i]);改成arr[length_c]s[i] ~32;或arr[length_c]s[i] | 32;都可
提交结果 3.代码优化
直接在原数组的基础上使用双指针,时间复杂度为
bool isPalindrome(char * s)
{if (sNULL)return true;int lengthstrlen(s);char* lefts[0];char* rights[length-1];while (left right){if (!((*leftA*leftZ)||(*lefta*leftz)||(*left0 *left9))){left;continue;}if (!((*rightA*rightZ)||(*righta*rightz)||(*right0 *right9))){right--;continue;}if ((*left| 32) (*right| 32)){left;right--;continue;}elsereturn false;}return true;
}
注意这里:*left和*right强制转为小写再比较(*left| 32) (*right| 32)
提交结果 4.LeetCode网友提供的解法
bool isPalindrome(char* s)
{int len strlen(s);int i 0, j 0;for (i 0, j len - 1; i j; i, j--){for (; !isdigit(s[i]) !isalpha(s[i]) i j;){i;}for (; !isdigit(s[j]) !isalpha(s[j]) i j;){j--;}s[i] toupper(s[i]);s[j] toupper(s[j]);if (s[i] ! s[j]){return false;}}return true;
}
积累两个函数 isdigit(c):如果待检测的字符c是0到9之间(十进制)的数字字符,则返回非0值,否则返回0 isalpha(c):如果待检测的字符c字母,则返回非0值,否则返回0
