前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode-翻转字符串里的单词

leetcode-翻转字符串里的单词

作者头像
程序员小王
发布2019-05-05 16:33:09
7880
发布2019-05-05 16:33:09
举报
文章被收录于专栏:架构说

耗时一天时间竟然还是没有做出来

,整理出来下面三个思路。

主要涉及while循环和重复内存拷贝这2个问题。

平时根本体会不到。

151. 翻转字符串里的单词

  • 去空格 多个只保留一个,字符串开始不是空格
  • 单词顺序不变,但是字符串位置发生了翻转

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

示例 1:

代码语言:javascript
复制
输入: "the sky is blue"
输出: "blue is sky the"

测试

输入: " hello world! " 输出: "world! hello"

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

开头存在空格

只存在一个空格

结尾存在空格

方法1 不需要考虑任何复杂情况

代码语言:javascript
复制
执行用时 : 16 ms, 在Reverse Words in a String的C++提交中击败了16.12% 的用户
内存消耗 : 10.6 MB, 在Reverse Words in a String的C++提交中击败了0.93% 的用户
class Solution {
public:
    string reverseWords(string s) {
        stack<string> stk;//LIFO context (last-in first-out)
        int pos = 0;
        string res;

        while (pos < s.length()) {
            int end, start;

            while(s[pos] == ' ' && pos < s.length())
                pos++;

            start = pos;

            while (s[pos] != ' ' && pos < s.length())
                pos++;

            end = pos;

            if (end == start)
                break;

            stk.push(s.substr(start, end - start));
        }

        while (!stk.empty()) {
            res += stk.top();
            stk.pop();
            if (!stk.empty())
                res += " ";
        }

        return res;
    }
};

旁白:

  • while适合用于状态变化控制,说高大上点就是while适合做状态机,而for仅仅是为了循环而循环
  • while语句的历史更久,表达方式上更自由灵活,常用于无法事先判断循环次数的循环。譬如经典的计算C风格字符串的长度的代码,又如后根遍历二叉树的非递归实现。此时用while语句会使程序更清晰。
  • 嵌套循环应该遵循“外小内大”的原则

方法2 去空格 然后翻转

代码语言:javascript
复制
class Solution {
public:
    void reverse(string &s, int l, int r) {
        while (l < r) swap(s[l++], s[r--]);
    }
    void reverseWords(string &s) {
        int w = 0, r = 0, sz = s.size();
        while (r < sz) {
            if (s[r] == ' ') {
                ++r;
                if (w - 1 >= 0 && s[w - 1] != ' ' && r < sz) s[w++] = ' '; // if not added space
            }
            else s[w++] = s[r++];
        }

        s.resize(w);
        if (s.back() == ' ') s.resize(s.size() - 1); // remove possible space at the end of string
        w = r = 0, sz = s.size();
        while (r < sz) {
            while (r < sz && s[r] != ' ') ++r;
            reverse(s, w, r - 1);
            while (r < sz && s[r] == ' ') ++r;
            w = r;
        }
        reverse(s, 0, sz-1);
    }
};

方法3 合并1和2

代码语言:javascript
复制
class Solution {
public:
    void reverseWords(string &s) {
        int sz = s.size();
        int i = 0, j = 0;
        while (i < sz)
        {
            while (i < sz && s[i] == ' ') i++; //i is the start of the word
            if (i < sz && j > 0)
                s[j++] = ' ';
            int start = j;



            while (i < sz && s[i] != ' ')
                s[j++] = s[i++];
            reverse(s.begin()+start, s.begin()+j);
        }
        s.resize(j);
        reverse(s.begin(), s.end());
    }
};

内存不重叠的拷贝。移动位置操作

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-04-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Offer多多 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 151. 翻转字符串里的单词
  • 测试
  • 方法1 不需要考虑任何复杂情况
  • 方法2 去空格 然后翻转
  • 方法3 合并1和2
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档