天天看点

<LeetCode天梯>Day015 反转字符串(双指针) | 初级算法 | Python

以下为我的天梯积分规则:

每日至少一题:一题积分+10分

若多做了一题(或多一种方法解答),则当日积分+20分(+10+10)

若做了三道以上,则从第三题开始算+20分(如:做了三道题则积分-10+10+20=40;做了四道题则积分–10+10+20+20=60)

初始分为100分

若差一天没做题,则扣积分-10分(周六、周日除外注:休息)

坚持!!!

初级算法

刷题目录

字符串

<LeetCode天梯>Day015 反转字符串(双指针) | 初级算法 | Python
<LeetCode天梯>Day015 反转字符串(双指针) | 初级算法 | Python

题干

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例1:

输入:s = [“h”,“e”,“l”,“l”,“o”]

输出:[“o”,“l”,“l”,“e”,“h”]

示例2:

输入:s = [“H”,“a”,“n”,“n”,“a”,“h”]

输出:[“h”,“a”,“n”,“n”,“a”,“H”]

分析:

这里说两句,虽然Python提供了很多很多的库和内置函数,可以解决很多问题,留言区有位题友说的很好,但是如果是来刷力扣,那么请记得自己的初心,如果仅仅是为了找工作,请左转百度题库。

<LeetCode天梯>Day015 反转字符串(双指针) | 初级算法 | Python

回归正题,为了让自己变强,少用便捷的方法。

今天的字符串的题还算比较简单吧,本题我们需要操作字符串,让其翻转,那么和之前的数组的翻转操作类似,我们可以用双指针,递归的思想,只能对原数组进行操作,不开辟新的数据空间。

双指针法

我们可以设两个指针,p1、p2,一个头指针,一个尾指针,一头一尾,然后进行交换操作,遍历所有,最终完成操作。

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        n = len(s)
        p1 = n-1
        p2 = 0
        while p1 >= (n//2):
            s[p1], s[p2] = s[p2], s[p1]
        p2 += 1
        p1 -= 1      

速度感觉还行吧~

<LeetCode天梯>Day015 反转字符串(双指针) | 初级算法 | Python
<LeetCode天梯>Day015 反转字符串(双指针) | 初级算法 | Python

内置函数法(玩笑)

由于是数组,我们可以用切片翻转,虽然这个方法不太聪明,且违背初心,我们还是得掌握一下

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = s[::-1]      
<LeetCode天梯>Day015 反转字符串(双指针) | 初级算法 | Python
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()      
<LeetCode天梯>Day015 反转字符串(双指针) | 初级算法 | Python