专栏首页架构说151. 翻转字符串里的单词

151. 翻转字符串里的单词

reverse-words-in-a-string

一、描述

151. 翻转字符串里的单词

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

说明:

  • 无空格字符构成一个单词。
  • 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

进阶: 请选用 C 语言的用户尝试使 ,意思是说原地反转。

 输入: "  hello world!  "
 输出: "world! hello"
 解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
 示例 3:
     
 输入: "a good   example"
 输出: "example good a"
 解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。 

这个题目试着这里开始入手

算法五个重要的特征:

  • 有输入,有输出(题目已经给了)
  • 可行性(复杂问题转化成熟悉子问题)
  • 有穷性(在算法描述体现)
  • 确切性(在算法描述体现)

二、思路

  • 问题转化:三步走,重点:是连续空间删除一个字符,如何避免整体copy

题目明明是要求的反转字符串单词问题, 要想保证反转后没有多余空格。 在反转前消除空格 最终转化成在同一个连续空间,移动copy字符串问题。 不同空间肯定没有问题,同一个空间呢?内存重叠呢? 解决了:数组特点 地址空间连续,删除一个元素,后面整体一定问题。

子问题:

  1. 单词有空格,去掉多余空格。
  2. 反转单词。
  3. 反转步骤1和2之后的字符串。
  • 算法描述:

第一步:如何删除多余空格?

因为数据结构是数组,只能靠移动,

  • 这个有一个拦路虎是 字符串,多个单词 ,如何循环移动多次?(通过队列保存拆分后单词这个想法可以想到)
  • 假设 这是这个单词位置 A |B |C |D
  • 输出: "example good a"

第二步:反转一个单词

如何确定每个单词位置。非空

第三步:反转一个句子

三、代码

  • 放轻松,虽然是c++实现,拒绝奇技淫巧,通俗易懂。
 class Solution {
 public:
 string reverseWords(string s) {
 
 int index =0;
         // 去除多余空格后,字符串s大小肯定会发生变化置.[0 index]表示反转新结束位。
 //理想情况 eg1,大小没有发生变化
         
 //遍历一次 start单词开始位置,end单词位置。
 for (int start=0;start<s.size();start++)
 {
 if (s[start] ==' ')
 {
 continue;//
 }
 //01 多个空格变成一个空格,反转后必须单词开头 eg2
 if (index >0)
 {
 s[index++]=' ';
 }
 
 //02 寻找单词开始位置,结束位置
 int end =start;
 while (end <s.size() && s[end] !=' ' )
 {
 s[index++]=s[end++];//c语言中的 memmove和memcpy区别。 
 
 }
 //03 反转单词长度
 int word=end-start;
 reverse(s.begin()+index-word,s.begin()+index);
 //这里反转移动之后新单词位置index,不是start 和end。
             //reverse(s.begin()+start,s.begin()+end);
 
 start =end;
 }
 //04 反转句子
 s.resize(index);
 reverse(s.begin(),s.end());
 return s;
 
 
 }
 };
  • bug1 :如果有多余空格,单词不是原地反转,//reverse(s.begin()+start,s.begin()+end);
  • golang

分享最实用的经验 , 希望每一位来访的朋友都能有所收获! 如果有疑问请联系我,一起探讨,进步。

本文分享自微信公众号 - 架构说(JiaGouS),作者:王传义

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 题目:判断一个单链表是否回文链表

    题目:判断一个单链表是否回文链表 Given a singly linked list, determine if it is a palindrome. C...

    程序员小王
  • c++在编译中遇到符合不存在如何解决?

    今日问题:symbol 不存在 : symbol lookup error: ./libinterface.so: undefined symbol: _ZN...

    程序员小王
  • 声明和定义的区别(深入理解)

    问题 声明和定义区别 definition declared 微信排版支持makdown语法不友好 可以查看原文链接 先看一下 例子1 编译有没有问题? cl...

    程序员小王
  • 画解算法:58. 最后一个单词的长度

    https://leetcode-cn.com/problems/length-of-last-word/

    灵魂画师牧码
  • 网络编程之HTTP请求报文和HTTP响应报文

    HTTP报文是面向文本的,报文中的每一个字段都是一些ASCII码串,各个字段的长度是不确定的。HTTP有两类报文:请求报文和响应报文。

    lyb-geek
  • TableLayout实现均匀布局(条目横向1:1排列)

    像下面的布局效果,我们经常使用LinearLayout实现,其实也可以使用TableLayout去简单的实现

    夏洛克的猫
  • android8.0采坑 Only fullscreen opaque activities can request orientation

    也就是说只有全屏不透明的activity才可以设置方向,既然知道问题所在就好办了。

    用户2235302
  • ListView专题

    ListView专题 1.ListView属性: fadingEdge属性 ListView上边和下边有黑色的阴影,android : fadingEdge ...

    xiangzhihong
  • Android 自定义最大宽度,高度, 宽高比例 Layout

    这篇博客主要介绍的是怎样自定义一个可以指定最大宽度,高度,以及宽高比的 Layout。原理其实很简单,就是通过重写 onMeasure 方法,重新制定 Meas...

    用户2965908
  • Android智能刷新加载框架-SmartRefreshLayout

      SmartRefreshLayout是目前为止笔者用过的嘴方便的刷新加载组件,它对下拉刷新功能进行系统的拆分、组合,主要由四个部分组成:

    饮水思源为名

扫码关注云+社区

领取腾讯云代金券