leetcode day2

2020-06-19

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: “A man, a plan, a canal: Panama”
输出: true
示例 2:

输入: “race a car”
输出: false

我最初提交的答案是：

解题思路：

首先剔除非数字和字母的字符
数组首尾进行比较，比较次数是数组长度的 length / 2( 这里不太严谨 )，如果有一个字符不相等，就退出循环返回 false。


var isPalindrome = function(s) {
    //1.去除所有除字母和数字之外的字符,利用ASCII码
    //1.1 字符串的字母全部转化为大写，并替换成数组类型 
    let arr = s.toUpperCase().split('');
    
    //1.2 定义一个数组，用来存储满足条件的字符
    let arrValue = [];
    for (let i = 0; i < arr.length; i++) {
        let value = arr[i].charCodeAt();
        if ((value >= 48 && value <= 57) || value >= 65 && value <= 90 ) {  
            arrValue.push(arr[i]);
        }
    }
    //2 只要将数组一般长度的字母进行比较，就可以判断是否为回文串
    for (let i = 0, j = arrValue.length - 1; i < arrValue.length / 2 && j > 0; i++, j--) {
        
        //2.1 条件不符合就直接返回false
        if (arrValue[i] !== arrValue[j]) {
            return false;
        }
    }
    return true
};

执行结果

执行时间长，内存消耗大。

最后改进版是：

方法一：正则表达式和双指针

var isPalindrome = function(s) {

    //1. 用正则表达式的replace方法
    let str = s.replace(/\W|_/g, '').toUpperCase();
    // console.log(str);
    
    //2. 通过设置left 和 right 变量控制比较次数
    let left = 0;
    let right = str.length - 1;
    while (left > right) {
        // h5新增方法，字符串中获取单个字符
        if (str[left] !== str[right]) return false;
        left++;
        right--;
    }
    return true
};

方法二：正则表达式，比较数组和反转数组是否相同

var isPalindrome = function(s) {
    //1. 用正则表达式的replace方法,并把字符串转化为数组
    let arry = s.replace(/\W|_/g, '').toUpperCase().split('');
    // 2. 利用数组的reverse方法,之后再把数组转化为字符串，进行比较
    return arry.join('') === arry.reverse().join('');

}

最后的总结是

正则表达式可以用来很好的匹配字符串

使用str.replace(正则表达式，替换结果)，这个方法返回的是替换后的字符串。需要注意的是，正则表达式 /.../ 默认是只匹配一个字符，通常我们需要这么写/.../g

双指针算法，

就是首尾字符挨个对比，当左边的下标大于右边的下标的时候，就不需要在进行循环。我第一次是让数组遍历长度的一半，是不太严谨的。

String 和 Array 之间转换

Array 是无法通过 ==== 来判断是否相等，但是 String 可以。

1 2	str = arry.join(''); arr = str.split('');