首页 > 其他分享 >代码随想录刷题记录(8)| 字符串(151.反转字符串里的单词,卡码网:55.右旋转字符串,28. 找出字符串中第一个匹配项的下标,459.重复的子字符串,字符串总结,双指针回顾)

代码随想录刷题记录(8)| 字符串(151.反转字符串里的单词,卡码网:55.右旋转字符串,28. 找出字符串中第一个匹配项的下标,459.重复的子字符串,字符串总结,双指针回顾)

时间:2024-06-16 16:59:22浏览次数:28  
标签:151 空格 string 反转 随想录 fast 单词 字符串

目录

(四)反转字符串里的单词

1.  题目描述

2. 思路

3. 解题过程

(1)使用额外空间存储

(2)原地反转 

(五)右旋转字符串

1. 题目描述

2. 思路

3. 解题过程

 (六)找出字符串中第一个匹配项的下标

1. 题目描述

2. 思路

3. 解题思路

(七)重复的子字符串

1. 题目描述

2. 思路

3. 解题过程

(八)总结


(四)反转字符串里的单词

151. 反转字符串中的单词 - 力扣(LeetCode)

1.  题目描述

        给你一个字符串 s ,请你反转字符串中 单词 的顺序。

        单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

        返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

        注意:输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。

2. 思路

  1. 移除多余空格
  2. 将整个字符串反转
  3. 将每个单词反转

3. 解题过程

难易程度:中等

标签:双指针、字符串

(1)使用额外空间存储

        先把单词存在字符串数组,然后从后往前存到结果字符串中返回。

class Solution {
public:
    string reverseWords(string s) {
        vector<string> words;
        // 把每个单词存下来
        for(int i = 0; i < s.size(); i++){
            string temp;
            while(i < s.size() && s[i] != ' '){
                temp += s[i++];
            }
            if(temp.size()){
                words.push_back(temp);
            }
        }
        string result;
        for(int i = words.size() - 1; i > 0; i--){
            result += words[i] + ' ';
        }
        result += words[0];
        return result;
    }
};

 

(2)原地反转 
class Solution {
public:
    // 去除多余的空格
    void RemoveSpace(string &s){
        int slow = 0, fast = 0;
        while(fast < s.size()){
            if(s[fast] != ' '){
                // slow!=0时,不是第一个单词,在前面加空格
                if(slow){
                    s[slow++] = ' ';
                }
                while(fast < s.size() && s[fast] != ' '){
                    s[slow++] = s[fast++];
                }
            }
            fast++;
        }
        s.resize(slow);
    }

    string reverseWords(string s) {
        RemoveSpace(s);
        // 反转整个字符串
        reverse(s.begin(), s.end());
        // 反转每个单词
        int start = 0;
        for(int i = 0; i <= s.size(); i++){
            if(i == s.size() || s[i] == ' '){
                reverse(s.begin() + start, s.begin() + i);
                start = i + 1;
            }
        }
        return s;
    }
};

 

(五)右旋转字符串

55. 右旋字符串(第八期模拟笔试) (kamacoder.com)

1. 题目描述

        字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k,请编写一个函数,将字符串中的后面 k 个字符移到字符串的前面,实现字符串的右旋转操作。 

        例如,对于输入字符串 "abcdefg" 和整数 2,函数应该将其转换为 "fgabcde"。

 

2. 思路

        先把字符串整体反转,然后再分别反转前 k 个,和剩余部分。

3. 解题过程

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int k;
    cin >> k;
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    reverse(s.begin(), s.begin() + k);
    reverse(s.begin() + k, s.end());
    cout << s;
    return 0;
}

 

 (六)找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标 - 力扣(LeetCode)

1. 题目描述

        给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回  -1 

 

2. 思路

        kmp算法。

        前缀表(prefix table)记录下标i之前(包括i)的字符串中,有多大长度的相同前缀后缀。前缀表是用来回退的,当模式串与主串(文本串)不匹配的时候,将模式串回退到前一个字符的前缀表的数值位置处。

        next数组可以是前缀表,但是很多实现都是把前缀表统一减一(右移一位,初始位置为-1)之后作为next数组。构造next数组其实就是计算模式串s,前缀表的过程。 主要有如下三步:

  1. 初始化
  2. 处理前后缀不相同的情况
  3. 处理前后缀相同的情况

 

3. 解题思路

难易程度:简单

标签:双指针、字符串、字符串匹配

之后再补。。。

 

(七)重复的子字符串

459. 重复的子字符串 - 力扣(LeetCode)

1. 题目描述

        给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。

2. 思路

假设字符串s使用多个重复子串构成(这个子串是最小重复单位),重复出现的子字符串长度是x,所以s是由n * x组成。

因为字符串s的最长相同前后缀的长度一定是不包含s本身,所以 最长相同前后缀长度必然是m * x,而且 n - m = 1,(这里如果不懂,看上面的推理)

所以如果 nx % (n - m)x = 0,就可以判定有重复出现的子字符串。

3. 解题过程

难易程度:简单

标签:字符串、字符串匹配 

暂时跳过 

(八)总结

        字符串是若干字符组成的有限序列,也可以理解为是一个字符数组,在C语言中,把一个字符串存入一个数组时,也把结束符 '\0' 存入数组,并以此作为该字符串是否结束的标志。vector< char > 和 string 在基本操作上没有区别,但是 string 提供更多的字符串处理的相关接口,例如string 重载了 +,而 vector 却没有。

标签:151,空格,string,反转,随想录,fast,单词,字符串
From: https://blog.csdn.net/weixin_44839832/article/details/139687601

相关文章

  • 代码随想录算法训练营第六十天 | 647. 回文子串、516.最长回文子序列
    647.回文子串文字讲解:代码随想录视频讲解:动态规划,字符串性质决定了DP数组的定义|LeetCode:647.回文子串_哔哩哔哩_bilibili解题思路1.dp[i][j]     [i,j]子串是否是回文的      是则返回true,不是则返回false2.递推公式if(s[i]==s[j])   ......
  • 代码随想录算法训练营第五十九天 | 115.不同的子序列、583. 两个字符串的删除操作、72
    115.不同的子序列题目链接:代码随想录视频讲解:动态规划之子序列,为了编辑距离做铺垫|LeetCode:115.不同的子序列_哔哩哔哩_bilibili解题思路1.dp[i][j]  为在s的前i个元素(即s[0,i-1])(以i-1结尾)中,有多少个t[0,j-1]匹配(以t[j -1]为结尾)2.递推公式//如果......
  • 代码随想录算法训练营第五十八天 | 392.判断子序列
    392.判断子序列 题目链接:代码随想录视频讲解:动态规划,用相似思路解决复杂问题|LeetCode:392.判断子序列_哔哩哔哩_bilibili解题思路本题和求最长公共子序列是一样的,值就是s字符串的长度,如果一致就返回true,如果不一致就是false这题也可以看作编辑距离入门级别的题目......
  • 代码随想录算法训练营第六十二天 | 739.每日温度、496.下一个更大元素 I、503.下一个
    739.每日温度文字讲解:代码随想录视频讲解:单调栈,你该了解的,这里都讲了!LeetCode:739.每日温度_哔哩哔哩_bilibili解题思路思路一:暴力双循环O(n^2)思路二:单调栈(用来找到右边或者左边第一个比它大的元素)元素:利用一个栈来存下标i,用T[i]来做映射顺序(递增还是递减):如果是递增是......
  • 华为OD机试C卷(100分)-字符串分割(二)(C语言)
    题目描述给定一个非空字符串S,其被N个‘-’分隔成N+1的子串,给定正整数K,要求除第一个子串外,其余的子串每K个字符组成新的子串,并用‘-’分隔。对于新组成的每一个子串,如果它含有的小写字母比大写字母多,则将这个子串的所有大写字母转换为小写字母;反之,如果它含有的大写字母比......
  • 华为OD刷题C卷 - 每日刷题30(小明找位置,分隔均衡字符串)
    1、(小明找位置):这段代码是解决“小明找位置”的问题。它提供了一个Java类Main,其中包含main方法和getResult方法,用于帮助小明快速找到他在排队中应该站的位置。main方法首先读取已排列好的小朋友的学号数组和小明的学号,然后调用getResult方法并打印小明应该站的位置。getRe......
  • 第八天 第四章 字符串 part02 151.翻转字符串里的单词 卡码网:55.右旋转字符串
    151.翻转字符串里的单词方法很巧妙,进行了两次反转。其中细节太多了。1.如何处理首个单词前面的空格,以及后面单词之间的空格处理(最重要的部分)。2.单词反转时的下标。classSolution{public:voidreverse(string&s,intleft,intright){......
  • 代码随想录 算法训练营 day10 leetcode232 用栈实现队列 Leetcode225 用队列实现栈 Le
    Leetcode232用栈实现队列题目链接讲解用两个栈实现队列每次需要出队列或者查看队头元素时,将输入栈的所有元素放到输出栈classMyQueue{Stack<Integer>stackIn;Stack<Integer>stackOut;publicMyQueue(){stackIn=newStack<>();//负责进......
  • 代码随想录算法训练营第十天
    python语法:一、通常使用列表(list)来实现栈。append(),pop()点击查看代码stack=[]#压栈(push)stack.append(1)#弹栈(pop)top_element=stack.pop()#查看栈顶元素(peek)top_element=stack[-1]#检查栈是否为空is_empty=len(stack)==0二、可以使用列表(list)或col......
  • Python 潮流周刊#56:NumPy 2.0 里更快速的字符串函数(摘要)
    本周刊由Python猫出品,精心筛选国内外的250+信息源,为你挑选最值得分享的文章、教程、开源项目、软件工具、播客和视频、热门话题等内容。愿景:帮助所有读者精进Python技术,并增长职业和副业的收入。本期周刊分享了12篇文章,12个开源项目,赠书5本,全文2100字。(PS.全新的赠......