LeetCode题解125.valid-palindrome

题目地址

https://leetcode.com/problems/valid-palindrome/description/

题目描述

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true
Example 2:

Input: "race a car"
Output: false

思路

这是一道考察回文的题目，而且是最简单的形式，即判断一个字符串是否是回文。

针对这个问题，我们可以使用头尾双指针，

• 如果两个指针的元素不相同，则直接返回false,
• 如果两个指针的元素相同，我们同时更新头尾指针，循环。 直到头尾指针相遇。

时间复杂度为O(n).

拿“noon”这样一个回文串来说，我们的判断过程是这样的：

拿“abaa”这样一个不是回文的字符串来说，我们的判断过程是这样的：

关键点解析

• 双指针

代码

• 语言支持：JS，C++，Python

JavaScript Code:

/*
 * @lc app=leetcode id=125 lang=javascript
 *
 * [125] Valid Palindrome
 */
// 只处理英文字符（题目忽略大小写，我们前面全部转化成了小写， 因此这里我们只判断小写）和数字
function isValid(c) {
  const charCode = c.charCodeAt(0);
  const isDigit =
    charCode >= "0".charCodeAt(0) && charCode <= "9".charCodeAt(0);
  const isChar = charCode >= "a".charCodeAt(0) && charCode <= "z".charCodeAt(0);

  return isDigit || isChar;
}
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
  s = s.toLowerCase();
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    if (!isValid(s[left])) {
      left++;
      continue;
    }
    if (!isValid(s[right])) {
      right--;
      continue;
    }

    if (s[left] === s[right]) {
      left++;
      right--;
    } else {
      break;
    }
  }

  return right <= left;
};

C++ Code:

class Solution {
public:
    bool isPalindrome(string s) {
        if (s.empty())
            return true;
        const char* s1 = s.c_str();
        const char* e = s1 + s.length() - 1;
        while (e > s1) {
            if (!isalnum(*s1)) {++s1; continue;}
            if (!isalnum(*e)) {--e; continue;}
            if (tolower(*s1) != tolower(*e)) return false;
            else {--e; ++s1;}
        }
        return true;
    }
};

Python Code:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            if not s[left].isalnum():
                left += 1
                continue
            if not s[right].isalnum():
                right -= 1
                continue
            if s[left].lower() == s[right].lower():
                left += 1
                right -= 1
            else:
                break
        return right <= left

    def isPalindrome2(self, s: str) -> bool:
        """
        使用语言特性进行求解
        """
        s = ''.join(i for i in s if i.isalnum()).lower()
        return s == s[::-1]

LeetCode题解堆排序和快速排序

堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法，其中 n 为数据规模。 那么两者谁更快呢？ 为什么？题解：快排最坏情况下是O(n^2)，平均和最好是O(nlogn) ，堆排序始终为O(nlogn)，还是堆排序快吧

LeetCode题解斜着遍历

遍历是算法的基础。 我们平时看到的 DFS 和 BFS 都是搜索， 而搜索的核心就是遍历，而关键点就是遍历的方式。 从根本上说动态规划也是枚举所有的可能，而枚举就需要用到遍历。 而平时遍历一个二维数组 martrix 的时候， 我们习惯的方式是按行从左到右或者从右到左遍历。 少有情况是按照列遍历， 更少有情况是斜着遍历。那么这次就考考你， 怎么斜着遍历一个二…

LeetCode题解砝码的最小数量

假设有三种重量的砝码，2g、3g、7g，对于任意重量物品，请设计一个函数getResult(weight)，接收一个参数weight，返回所需砝码的最小数量。输入示例：const weight = 100;输出示例：getResult(weight) // 15 其中7g的14个，2g的1个题解：```phpfunction getResult($weigh…

LeetCode题解93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。 示例:输入: \"25525511135\"输出: [\"255.255.11.135\", \"255.255.111.35\"]来源：力扣（LeetCode）链接：https://le…

可以在没有操作系统的情况下运行Java程序吗？ - java

我知道所有Java程序都由JVM执行。这使Java与所有操作系统兼容（一次编写，可在任何地方运行）。但是我可以在没有操作系统的情况下运行Java程序吗？也许只运行JVM？并且，如果可能，功能是否会受到任何影响？注意：我的主要问题是，java程序可以直接在硬件上运行（通过JVM）吗？我可以在计算机中“启动”任何低级别的JVM吗？ java大神给出的解决方案 实…