代码随想录day8

这篇具有很好参考价值的文章主要介绍了代码随想录day8。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

344.反转字符串

思路:

541. 反转字符串II

思路:

题目:剑指Offer 05.替换空格

思路:

151.翻转字符串里的单词

思路:

题目:剑指Offer58-II.左旋转字符串

思路:


344.反转字符串

力扣题目链接(opens new window)

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

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

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

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

思路:

可以直接用库函数reserve(交换),或者swap,也可以用双指针。

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left=0;
        int right=s.size()-1;
        int tmp=0;
        while(left<=right){
           tmp = s[left];
           s[left] =s [right];
           s[right] = tmp;
           left++;
           right--;
        }
    }
};

541. 反转字符串II

力扣题目链接(opens new window)

给定一个字符串 s 和一个整数 k,从字符串开头算起, 每计数至 2k 个字符,就反转这 2k 个字符中的前 k 个字符。

如果剩余字符少于 k 个,则将剩余字符全部反转。

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

示例:

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

思路:

利用for循环但要注意i不是加一,而是加2k,然后判断i+k是否大于等于数组长度,若为大于等于则说明数组大于等于3k,则反转前k个字符,否则反转全部。

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
            } else {
                // 3. 剩余字符少于 k 个,则将剩余字符全部反转。
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

题目:剑指Offer 05.替换空格

力扣题目链接(opens new window)

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

示例 1: 输入:s = "We are happy."
输出:"We%20are%20happy.“

思路:

在字符串数组中加入多个元素,先追加足够的位置,利用双指针法,left指向原数组的最后一位,right指针指向新数组最后一位,当向前移动的过程中,遇到空格时,left跳过,right指针加入02%。

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0; // 统计空格的个数
        int sOldSize = s.size();
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        // 扩充字符串s的大小,也就是每个空格替换成"%20"之后的大小
        s.resize(s.size() + count * 2);
        int sNewSize = s.size();
        // 从后先前将空格替换为"%20"
        for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
            if (s[j] != ' ') {
                s[i] = s[j];
            } else {
                s[i] = '0';
                s[i - 1] = '2';
                s[i - 2] = '%';
                i -= 2;
            }
        }
        return s;
    }
};

 扩充字符串的写法:s.resize(s.size()+ count*2);

记录原数组的长度和新数组长度,指针分别指向新旧数组长度-1,要注意条件是旧指针小于新指针或旧指针大于0

151.翻转字符串里的单词

力扣题目链接(opens new window)

给定一个字符串,逐个翻转字符串中的每个单词。

示例 1:
输入: "the sky is blue"
输出: "blue is sky the"

示例 2:
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。

示例 3:
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个

思路:

可以先将整体进行反转,将单独对局部进行反转。

内容过多复杂可以参考代码随想录

class Solution {
public:
    void reverse(string& s, int start, int end){ //翻转,区间写法:左闭右闭 []
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
        int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //遇到非空格就处理,即删除所有空格。
                if (slow != 0) s[slow++] = ' '; //手动控制空格,给单词之间添加空格。slow != 0说明不是第一个单词,需要在单词前添加空格。
                while (i < s.size() && s[i] != ' ') { //补上该单词,遇到空格说明单词结束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即为去除多余空格后的大小。
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); //去除多余空格,保证单词之间之只有一个空格,且字符串首尾没空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到达空格或者串尾,说明一个单词结束。进行翻转。
                reverse(s, start, i - 1); //翻转,注意是左闭右闭 []的翻转。
                start = i + 1; //更新下一个单词的开始下标start
            }
        }
        return s;
    }
};

虽然此方法便捷,但个人能力问题不喜欢此方法,更容易理解的方法为双指针,先去掉头部和尾部的空格,再去除掉中间的空格,并再去除的过程中获取单词的长度进行翻转。

题目:剑指Offer58-II.左旋转字符串

力扣题目链接(opens new window)

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

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

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

思路:

先进行翻转前n个,再翻转n个之后的字符串顺序,最后统一翻转整个数组

class Solution {
public:
    string reverseLeftWords(string s, int n) {
       reverse(s.begin(), s.begin() + n);
        reverse(s.begin() + n, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};

总结:在字符串中使用双指针法的概率比较大。文章来源地址https://www.toymoban.com/news/detail-492394.html

到了这里,关于代码随想录day8的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表

    直接让前一个节点指向后一个节点即可 两种方法 第一种:直接删除 第二种:头删的时候,直接 head=head-next 其实这两种方法都没有做到统一 第三种:虚拟头结点法 这样的话,咱们删除的时候,就是以统一的规则来进行删除啦! 203.移除链表元素 法一:原始删除法 1、while(h

    2024年02月16日
    浏览(36)
  • 代码随想录day9|实现strStr()、重复的子字符串

    一般的字符串匹配问题我们可以使用KMP算法来处理,当我们搜索文本串和模式串是否匹配的时候,我们先得到模式串的一个前缀表,其中前缀表中存放的内容是模式串的最长相等前后缀。例如文本串为:aabaabaafa,模式串为:aabaaf,那么文本串的前缀表就是010120。当我们开始搜

    2024年02月15日
    浏览(62)
  • 代码随想录Day3|链表理论基础|203.移除链表元素|707.设计链表|206.反转链表

    虽然以前写过一次链表,但是真的已经忘得一干二净了 链表 :通过 指针 串联在一起的线性结构,每个 节点 都由数据域和指针域组成。 指针域 :存放下一个节点的指针,最后一个节点的指针域指向null,也即空指针 head :链表的入口节点,也即链表的头节点 链表的类型 单

    2024年02月11日
    浏览(52)
  • 第8天-代码随想录刷题训练-字符串● 344.反转字符串 ● 541. 反转字符串II ● 剑指Offer 05.替换空格 ● 151.翻转字符串里的单词 ● 剑指Offer58-II.左旋转字符串

    LeetCode链接 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 swap常见的两种交换形式 常见的值交换 通过位运算 LeetCode链接 给定一个

    2024年02月04日
    浏览(61)
  • 1月3日代码随想录反转二叉树

    给你一棵二叉树的根节点  root  ,翻转这棵二叉树,并返回其根节点。 示例 1: 示例 2: 示例 3: 提示: 树中节点数目范围在  [0, 100]  内 -100 = Node.val = 100 这道题用递归的思想就是将根节点的左右儿子交换,然后再对子节点进行递归操作,直到子节点均为空。 但是我感觉

    2024年02月03日
    浏览(44)
  • 代码随想录Day9 栈与队列 LeetCodeT20 有效的括号 T1047 删除字符串中所有相邻重复项 T150 逆波兰表达式求值

    题目详细思路和解法来自于:代码随想录 (programmercarl.com) 这道题分为三种情况 1.左括号多了         ([{}]() 2.括号不匹配         [{(]}] 3.右括号多了         []{}()))) 处理思路:我们在遇到左括号的时候,直接入栈其对应的右括号即可,然后在遇到右括号的时候直接与栈顶元素比

    2024年02月06日
    浏览(141)
  • 代码随想录 字符串 Java

    复杂度分析: 时间复杂度:O(N),其中N为字符数组的长度。一共执行了N/2次的交换 空间复杂度:O(1),只使用了常数空间来存放若干变量 我的思路:2k个字符为一组,先将前k个字符(或者不足k个字符)添加到StringBuilder中,然后调用reverse()方法,然后再将后k个字符(或者不足

    2024年02月06日
    浏览(39)
  • 代码随想录笔记--字符串篇

    目录 1--反转字符串 2--反转字符串II 3--反转字符串中的单词 4--KMP算法 5--重复的子字符串 主要思路:         双指针算法,交换两个指针的字符; 主要思路:         以 2k 个字符为一组进行遍历; 主要思路1:         遍历提取每一个有效的单词,存储在一个栈中,最后遍

    2024年02月10日
    浏览(66)
  • 代码随想录day44

    完全背包 其实就是每个物品可以使用无数次,给我们一个容器,装满这个容器的最大价值是多少。 思路: 如果求组合数就是外层for循环遍历物品,内层for遍历背包。 如果求排列数就是外层for遍历背包,内层for循环遍历物品。 完全背包的组合和排序 518. 零钱兑换 II 题目 给你

    2023年04月17日
    浏览(62)
  • 代码随想录Day58

    昨天因为志愿活动和笔试耽误了一整天,今天继续学习动规解决子序列问题。 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,\\\"ace\\\"是\\\"abcde\\\"的一个子序列,

    2023年04月27日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包