【LeetCode】删除字符串中的所有相邻重复项&&回文数&&整数反转

Shark Xu 2023/1/1 LeetCode

# 删除字符串中的所有相邻重复项

这是力扣 1047 题

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

# 解题思路

这是一道简单题，也是一道关于栈的字符串题目。一眼看过去，感觉没什么难点，十分简单，但是这里有一个需要注意的地方，如果删除一对重复项，可能会导致新的重复项出现，所以这里我们还需要有一步保存当前字符串的步骤，这样才能使它能有效进行下去。

栈的解法在上一篇提到过，并且也是应用在字符串题目中，由此可见栈与字符串有着千丝万缕的联系。因此对于这道题，显而易见用栈的方法来解决此题是最好的选择。

# 栈

利用栈的思想来解决此题，定义一个新的数组，通过循环遍历每一个参数。如果该字符和结果数组的最后一个元素相符，则将结果数组的栈顶元素弹出，最后返回栈的字符串格式，否则将遍历到的这个字符放入到结果数组中。简化一下整体思路大致如下：

初始化栈并循环遍历字符串
如果字符串某个值和栈顶元素相符，则出栈，否则将其入栈
最后返回栈的字符串格式

相关代码如下：

var removeDuplicates = function(s) {
    let stack = [];
    for(let item of s){
        if(stack[stack.length - 1] === item){
            stack.pop();
        }else{
            stock.push(item);
        }
    }
    return stack.join("");
};

这样的解法达到的时间复杂度是 O(n)，因为只循环遍历了一次。从时间复杂度上看，这是关于此题的最好解法，大家可以多研究一下。

# 回文数

这是力扣第 9 题

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

# 解题思路

回文数的定义是指正序（从左向右）和倒序（从右向左）读都是一样的整数。这是一道简单题，不难。我看到此题第一眼，就有一种思路浮现 —— 整数转换数组。可能是上一篇文章写的是有关整数反转类型的题目，和这题性质一样，所以首先就想到了这种方法。因此就来介绍一下我所想到的几种方法。

# 整数转换数组

这是我首先想到的一种思路，就是将整数转换为数组后，然后进行循环遍历，来判断是否是回文数。

通过 toString 方式转换成数组后，开启循环遍历，如果第 i 个（i 从 0 开始计数）和数组第 len 个（len 是数组长度）相等，则以此循环，i 不断加一，len 不断减一，这样就可以判断是否是回文数了。从另一个角度理解，判断是否是回文数就是判断数组是否对称即可。

相关代码如下：

var isPalindrome = function(x) {
    let arry = x.toString().split('');
    let len = arry.length-1
    for(let i = 0;i<arry.length;i++){
        if(arry[i]==arry[len]){
            len--;
        }else{
            return false;
        }
    }
    return true;
};

这种思路是非常容易理解的。

# 数学法

这种方法就比较有技巧了。就和字符串一样，既然字符串可以直接反转，为何不考虑直接让数字直接反转呢？所以，数学逻辑能力比较强的同学可以想到这种方式。数字的直接反转思路如下：

我们拿 10 当除数，然后将 num 对除数 10 取余得到的数字作为后续的最高位即可。

相关代码如下：

var isPalindrome = function(x) {
    if (x === 0) return true;
    if (x < 0 || x % 10 === 0) return false;
    let reverse = 0;
    let rest = x;
    while (res >= 10) {
        reverse = reverse * 10 + res % 10;
        res = Math.floor(res / 10);
    }
    return (reverse * 10 + res) === x;
};

这种方式考验大家对数学的敏感度以及逻辑能力。

# 整数反转

这是力扣第 7 题

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

# 解题思路

这道题属于中等难度的题目，第一眼看过去和反转字符串很像，但是仔细一看还是有很大区别的。不过既然觉得和反转字符串类似，那为何不把它变成字符串来求解呢？因此，第一种最容易想到的解题思路诞生了 —— 转换为字符串后反转。

# Number 转换 String 法

看到小标题，应该大概知道是什么思路了吧。把整数 X 先变成字符串 Y，因为字符串的反转题目已经做过，或者说已经有思路，因此这样转换是比较直接的方式。至于 Number 如何转为为 String，在网上搜一下有很多方式，比如 toString、newString（） 等等，这里我们使用 toString 方式，是用的比较多的一种转换方法。

整体思路如下：

将整数 X 转换为 String 类型
然后用 split 方法将 String 类型分割成 Array 对象
然后用 Array 对象的 reverse 方法进行翻转，这样就到达反转效果。到了这一步后，就需要重新之前的操作，将 Array 对象变回 String 类型，再将 String 类型变回 Number。
分别用到 Array 对象的 join 方法和 String 类型的 parseInt 方法
最后用三目运算符 return 最终结果

相关代码如下：

var reverse = function (x) {
    let y = parseInt(x.toString().split("").reverse().join(""));
    if (x < 0)
        y = - y;
    return y > 2147483647 || y < -2147483648 ? 0 : y;
};

整体解题的流程可以理解成这样：Number 类型 -> String 类型 -> Array 类型 -> String 类型 -> Number 类型。由此可见解题流程也能看成是一个被反转的对称的过程。

有效的括号&&Pow(x, n)&&合并两个有序链表【LeetCode】只出现一次的数字&&最长回文子串&&无重复字符的最长子串

Shark Xu 的博客

Choose mode