📢前言
🚀 算法题 🚀
🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
🌲 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
🌲 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧🧐！
🌲 今天是力扣算法题持续打卡第36天🎈！
🚀 算法题 🚀
🌲原题样例：验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
**说明：**本题中，我们将空字符串定义为有效的回文串。
示例 1：
输入: "A man, a plan, a canal: Panama" 输出: true 解释："amanaplanacanalpanama" 是回文串
示例 2：
输入: "race a car" 输出: false 解释："raceacar" 不是回文串
提示：
- 1 <= s.length <= 2 * 10^5
- 字符串 s 由 ASCII 字符组成
🌻C#方法：双指针
思路解析
利用双指针，从字符串两头往中间遍历并进行比对，跳过非数字或字母项。
代码：
public class Solution { public bool IsPalindrome(string s) { if (s == null) { return false; } int left = 0; int right = s.Length - 1; while (left <= right) { var leftElement = char.ToLower(s[left]); var rightElement = char.ToLower(s[right]); if ((leftElement >= 'a' && leftElement <= 'z' || leftElement >= '0' && leftElement <= '9') && rightElement >= 'a' && rightElement <= 'z' || rightElement >= '0' && rightElement <= '9') { if (leftElement != rightElement) { return false; } left++; right--; } else if (leftElement >= 'a' && leftElement <= 'z' || leftElement >= '0' && leftElement <= '9') { right--; } else { left++; } } return true; } }
执行结果
通过 执行用时：212 ms，在所有 C# 提交中击败了31.47%的用户 内存消耗：25.9 MB，在所有 C# 提交中击败了52.99%的用户
🌻Java 方法一：筛选 + 判断
思路解析
最简单的方法是对字符串 s 进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串sgood 中。这样我们只需要判断 sgood 是否是一个普通的回文串即可。
判断的方法有两种。第一种是使用语言中的字符串翻转 API 得到 sgood 的逆序字符串 sgood_rev，只要这两个字符串相同，那么 sgood 就是回文串。
代码：
class Solution { public boolean isPalindrome(String s) { StringBuffer sgood = new StringBuffer(); int length = s.length(); for (int i = 0; i < length; i++) { char ch = s.charAt(i); if (Character.isLetterOrDigit(ch)) { sgood.append(Character.toLowerCase(ch)); } } StringBuffer sgood_rev = new StringBuffer(sgood).reverse(); return sgood.toString().equals(sgood_rev.toString()); } }
执行结果
通过 执行用时：5 ms，在所有 Java 提交中击败了32.73%的用户 内存消耗：38.4 MB，在所有 Java 提交中击败了76.12%的用户
复杂度分析
时间复杂度：O( |s| ),其中 ∣s∣ 是字符串 s 的长度。 空间复杂度：O( |s| )，由于我们需要将所有的字母和数字字符存放在另一个字符串中，在最坏情况下，新的字符串sgood 与原字符串 s 完全相同
🌻Java 方法二：在原字符串上直接双指针判断
思路解析
直接在原字符串 s 上使用双指针。
在移动任意一个指针时，需要不断地向另一指针的方向移动，直到遇到一个字母或数字字符，或者两指针重合为止。
也就是说，我们每次将指针移到下一个字母字符或数字字符，再判断这两个指针指向的字符是否相同。
代码：
class Solution { public boolean isPalindrome(String s) { int n = s.length(); int left = 0, right = n - 1; while (left < right) { while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { ++left; } while (left < right && !Character.isLetterOrDigit(s.charAt(right))) { --right; } if (left < right) { if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) { return false; } ++left; --right; } } return true; } }
执行结果
通过 执行用时：2 ms，在所有 Java 提交中击败了98.39%的用户 内存消耗：38.7 MB，在所有 Java 提交中击败了21.96%的用户
复杂度分析
时间复杂度：O( n ) 空间复杂度：O( 1 )
总结
- 今天是力扣算法题打卡的第三十六天！
- 文章采用
C#和Java两种编程语言进行解题 - 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！
