找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2447|回复: 5
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Reverse Words in a String 】【刷题第一弹2014】

[复制链接]

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 10-24-2014 08:48 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-7-2014 12:11 AM 编辑

leetcode: https://oj.leetcode.com/problems/reverse-words-in-a-string/
汇总帖:http://www.meetqun.com/forum.php?mod=viewthread&tid=703
1. 题目:
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

2. 分析
string的细节实现题,注意所有的情况就好了。首先去掉空格,然后将整个字符串翻转,最后将翻转后的字符串按单词翻转。
小提醒,压缩字符串空格的时候如果不更改string类的size,length等,则仍然无法通过。我就碰到过输出和期待输出一致,但显示wrong answer的情况
3. 复杂度
压缩空格,翻转整个字符串,翻转每个单词,3次遍历,时间复杂度O(n),空间复杂度O(1)
4. 代码
  1. class Solution {
  2. public:
  3.     void reverseWords(string &s) {
  4.         if(s.length() <= 0) return;
  5.         int newLen = squeeze(s, s.length());

  6.         reverse(s, 0, newLen - 1);
  7.         
  8.         for(int i = 0, sIndex = -1, eIndex = -1; i < newLen; i++){
  9.             if(sIndex == -1){
  10.                 if(s【i】 != ' ')
  11.                     sIndex = i;
  12.             }
  13.             else if(s【i】 == ' ' || i == newLen - 1){
  14.                 eIndex = (i == newLen - 1) ? i : i - 1;
  15.                 reverse(s, sIndex, eIndex);
  16.                 sIndex = -1;
  17.             }
  18.         }
  19.         s = s.substr(0, newLen);
  20.     }
  21.    
  22.     int squeeze(string &s, int len){
  23.         bool numSpace = true;
  24.         
  25.         int newLen;
  26.         int prev = 0;
  27.         for(int back = 0; back < len; back++){
  28.             if(s[back] != ' '){
  29.                 s[prev++] = s[back];
  30.                 numSpace = true;
  31.             }
  32.             else if(numSpace){
  33.                     s[prev++] = s[back];
  34.                     numSpace = false;
  35.             }
  36.         }
  37.         newLen = prev;

  38.         if(s[newLen - 1] == ' ' && --newLen == 0) return newLen;
  39.             
  40.         if(s[0] == ' ')  s = s.substr(1, --newLen);
  41.         
  42.         return newLen;
  43.     }
  44.    
  45.     void reverse(string &s, int start, int end){
  46.         for(int i = start, j = end; i < j; i++, j--){
  47.             char tmp = s【i】;
  48.             s【i】 = s[j];
  49.             s[j] = tmp;
  50.         }
  51.     }
  52. };
复制代码

【i】【i】【i】【i】5. 相关题目:




本帖被以下淘专辑推荐:

0

主题

0

精华

62

积分

资深会员

Rank: 2

积分
62
发表于 10-25-2014 11:48 PM | 显示全部楼层
我的思路是从后向前扫这个string,维护头和尾两个指针,如果头指针的前面是空格,则将当前的word放入stringbuilder里,然后头指针扫到空格时,将尾指针移到头指针处,头指针继续往前扫。大体思路就是这样,然后需要注意如果stringbuilder不为空的话在append新的word前先append一个空格,再注意下边界条件
回复 支持 反对

使用道具 举报

0

主题

0

精华

131

积分

资深会员

Rank: 2

积分
131
发表于 11-13-2014 10:01 PM | 显示全部楼层
m# w$ L, w/ o% K8 k) A
思路: *      需要注意给定字符串存在的几种特殊情况
*      1. 有前导空格leading spaces, 处理方法remove
*      2. 有尾随空格trailing spaces, 处理方法remove
*      3. words之间的空格数大于1, 处理方法保留一个space
*      4. 字符串为empty or null的情况, 处理方法直接返回empty or null
*      5. 既有前导空格又有尾随空格
*      6. 给定字符串中只有一个word时,不用在输入多余的空格。
*      
*      
*      我们从给定字符串的最后一个字符用String.charAt()方法开始遍历,如果遇到space就skip, 当遇到非space时我们记录下当前
*  遍历到的index加1作为word结束的那个位置.然后继续往前遍历,当遇到非space时就skip, 当遇到space时我们记录下该space后的那个非space字符的index. 这样
*  这两个index之间我们用String.substring(beginIndex, endIndex)截取到的就是一个有效word.每次截取后的word,我们都把他们append
*  到StringBuilder对象的末尾。继续运行直到遍历完字符串。
j: x( C2 l5 Y3 k; b8 l# ?6 ^+ L& L
代码:
  1. public class Solution {
  2.     public String reverseWords(String s) {
  3.             
  4.             if(s==null||s.length()==0)
  5.                     return s;
  6.            
  7.             int i = s.length()-1;
  8.             int wordStart = 0,wordEnd = 0;
  9.             boolean flag = false;
  10.             StringBuilder reverseWord = new StringBuilder();  
  11.            
  12.             while(i>=0){
  13.                     char currentChar = s.charAt(i);
  14.                     if(currentChar==' '){
  15.                             if(flag==true){
  16.                                     wordStart = i+1;
  17.                                     flag = false;
  18.                                     reverseWord.append(s.substring(wordStart, wordEnd)+" ");
  19.                             }
  20.                     }else{
  21.                             if(flag==false){
  22.                                     wordEnd = i+1;
  23.                                     flag = true;
  24.                             }
  25.                     }
  26.                     i--;
  27.             }
  28.             if(flag==true)
  29.                     reverseWord.append(s.substring(0, wordEnd));
  30.                    
  31.             return reverseWord.toString().trim();
  32.     }
  33. }
复制代码


复杂度分析:





*      时间复杂度 ------ O(n), StringBuilder对象的append操作和trim操作不太清楚时间复杂度
*      空间复杂度 ------ O(k), k为字符串长度

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表