您现在的位置是:首页 > 正文

Leetcode--------字符串

2024-01-30 22:03:03阅读 0

344. 反转字符串

 

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

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

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1:

输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]

示例 2:

输入:["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

代码:

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        #在该字符串数组上定义2个指针来进行反转
        lens = len(s)
        #含有字符数大于1才有反转的必要性
        if lens > 1:
            front = 0
            tail = lens - 1
            while front < tail:
                #开始反转
                temp = s[tail]
                s[tail] = s[front]
                s[front] = temp
                front += 1
                tail -= 1
            return s
        else:
            return s

541. 反转字符串 II

给定一个字符串 s 和一个整数 k,你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。

如果剩余字符少于 k 个,则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。

示例:

输入: s = "abcdefg", k = 2
输出: "bacdfeg"

代码:

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        s = list(s)
        def reverse(s):
            #在该字符串数组上定义2个指针来进行反转
            lens = len(s)
            #含有字符数大于1才有反转的必要性
            if lens > 1:
                front = 0
                tail = lens - 1
                while front < tail:
                    #开始反转
                    temp = s[tail]
                    s[tail] = s[front]
                    s[front] = temp
                    front += 1
                    tail -= 1
                return s
            else:
                return s
        result = []
        for i in range(0,len(s),2*k):
            #判断当前区间的元素是否够k个元素
            if len(s) - i >= k:
                result[i:i+k] = reverse(s[i:i+k])
                result[i+k:i+2*k] = s[i+k:i+2*k]
            else:
                result[i:len(s)] = reverse(s[i:len(s)])
        return "".join(result)

 

 剑指 Offer 05. 替换空格

请实现一个函数,把字符串 s 中的每个空格替换成"%20"。

示例 1:

输入:s = "We are happy."
输出:"We%20are%20happy."

代码:

方法一:

"""
方法一:一行代码搞定,但是刷题这样搞没一点意义
"""
class Solution:
    def replaceSpace(self, s: str) -> str:
        return "%20".join(s.split(" "))

方法二:

class Solution:
    def replaceSpace(self, s: str) -> str:
        """
        方法一:调用库方法
        """
        # return "%20".join(s.split(" "))
        """
        方法二:双指针法
        """
        s = list(s)
        front = len(s) - 1
        #遇到一个空格就在后面填充一个" "
        for i in range(len(s)):
            if s[i] == " ":
                s.append(" ")
                s.append(" ")
        #定义2个指针,一个指向原来的下标,一个指向新的下标
        tail = len(s) - 1
        #2个指针同时向前面移动,若front指针遇到元素,tail指向的位置就
        #被复制成该元素,若front遇到空格,从tail指向的位置向前赋值%20
        while front < tail:
            if s[front] != " ":
                s[tail] = s[front]
            else:
                #tail向前移动2个位,加上当前的位置,都赋值上%20
                s[tail] = "0"
                tail -= 1
                s[tail] = "2"
                tail -= 1
                s[tail] = "%"
            front -= 1
            tail -= 1
        return "".join(s)

剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1:

输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2:

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

代码:

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        """
        方法一:
        """
        # tail_str = s[:n]
        # return s[n:] + tail_str
        """
        方法二:使用双指针
        """
        def reverse(strs,begin,end):
            strs = list(strs)
            front = begin
            tail = end
            while front < tail:
                temp = strs[front]
                strs[front] = strs[tail]
                strs[tail] = temp
                front += 1
                tail -= 1
            return "".join(strs)
        #先对前部分进行反转
        s = reverse(s,0,n-1)
        #再对后半部分进行反转
        s = reverse(s,n,len(list(s))-1)
        #对所有进行一次反转
        s = reverse(s,0,len(list(s))-1)
        return s

28. 实现 strStr()

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回  -1 。

说明:

当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1:

输入:haystack = "hello", needle = "ll"
输出:2

示例 2:

输入:haystack = "aaaaa", needle = "bba"
输出:-1

示例 3:

输入:haystack = "", needle = ""
输出:0

代码:

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        haystack = list(haystack)
        needle = list(needle)
        if len(needle) == 0:
            return 0
        def get_next(str_model):
            #构建next数组,j指向前缀末尾,i指向后缀末尾
            next = ["" for i in range(len(str_model))]
            j = -1
            next[0] = j
            for i in range(1,len(str_model)):
                #若i,j上位置对应元素不相等
                while j > -1 and str_model[i] != str_model[j+1]:
                    #j向前回退
                    j = next[j]
                #若i,j上位置对应元素相等
                if str_model[i] == str_model[j+1]:
                    #j要加1,并赋值给next数组
                    j += 1
                next[i] = j
            return next
        next = get_next(needle)

        #注意,这里为-1比较好
        n = -1
        for m in range(len(haystack)):
            while n >= 0 and needle[n+1] != haystack[m]:
                n = next[n]
            #成功匹配,n往后移动
            if needle[n+1] == haystack[m]:
                n += 1
            #到最后一个元素了,说明匹配上啦
            if n == len(needle) - 1:
                return m - len(needle) + 1
        return -1

Link

网站文章

  • 掌握C语言中的操作符:编程必备技巧

    掌握C语言中的操作符:编程必备技巧

    详解C语言里的操作符。

    2024-01-30 22:02:32
  • Ant执行build文件时报input file XXX .jtl does not exist

    Ant执行build文件时报input file XXX .jtl does not exist

    Ant执行build文件时报input file XXX .jtl does not exist 最近突然想到,把Jmeter+Ant+Jenkins+git放到远程堡垒机上使用,就可以共享给其他人使...

    2024-01-30 22:02:26
  • 大数的取余运算

    问题描述: 给出两个数a,b,求a%b;(其中1^9) 分析: 由于数字太大,所以用字符数组进行处理比较方便,然后转化为数字即可。 举个例子:999 % 8; c = 9 &gt; 8 //只要大于8,就求余 c = 9 % 8 ——&gt; c = 1; c = 1 * 10 + 9 ——&gt; c = 19 &gt; 8;

    2024-01-30 22:02:19
  • Pycharm控制台中文输出乱码问题解决方案

    Pycharm控制台中文输出乱码问题解决方案

    Pycharm控制台中文输出乱码问题解决方法

    2024-01-30 22:01:48
  • Linux启动nginx时端口被占用

    Linux启动nginx时端口被占用

    Linux启动nginx时端口被占用,linux查看端口占用

    2024-01-30 22:01:41
  • 课后习题---输入输出系统

    Part A 试着说明I/O系统的基本功能 隐藏物理设备的细节,与设备的无关性, 提高处理机和I/O设备的利用率 对I/O设备进行控制,确保对设备的正确共享,错误处理 简要说明I/O软件的四个层次的基...

    2024-01-30 22:01:33
  • 把cv::Mat转化为QImage

    把cv::Mat转化为QImage

    前一篇博客《把QImage转换为cv::Mat》介绍了像素在QImage和Mat里面不同的存储方式,以及如何实现从QImage到Mat的转换。了解了存储像素的机理之后,从Mat向QImage的转化也不难。Qimage的构造函数有很多种,其中一种构造函数的使用方法与我们在上一篇《把QImage转换为cv::Mat》Mat的构造方法相似:在构造时,都要告知构造函数,图像的每行有几个字节(bytesPe

    2024-01-30 22:01:26
  • CentOS6.7配置Java环境、安装Tomcat、部署Web项目记录

    CentOS6.7配置Java环境、安装Tomcat、部署Web项目记录

    V!P!S版本:[root@www ~]# cat /etc/issueCentOS release 6.7 (Final)Kernel \r on an \m一、准备工作首先安装wget下载工具yum install wget -y查看CentOS的系统位数:uname -a可以看到是64位系统二、安装Java环境1.下载64位版本JDK...

    2024-01-30 22:00:57
  • CSDN实训 | Java虚拟机 JVM

    什么是 Java 虚拟机?为什么 Java 被称作是“平台无关的编程语言”?Java 虚拟机是一个可以执行 Java 字节码的虚拟机进程。Java 源文件(.java)被编译成能被 Java 虚拟机执...

    2024-01-30 22:00:50
  • pyqt的基本组件

    熟悉常用的窗口组件:1按钮类QPushButton 普通按钮QToolButton 工具按钮:通常在工具栏使用QRadioButton 单选框QCheckBox 复选框QCommanLinkButtonVist...

    2024-01-30 22:00:44