字符串句子排序问题

羑悻的小杀马特.

发布于 2025-01-23 17:01:54

2870

文章被收录于专栏：杀马特杀马特

一·题目概述：

leetcode题目链接：1859. 将句子排序 - 力扣（LeetCode）

二·思路分析：

当拿到这这道题，其实一下子就会知道此题要输出的是什么，就是按照数字字符的顺序去把单词给还原出来。

而题目要求的输入为什么数字字符要安排在原单词后面呢，于是就想到了它如果是按照倒序遍历，再给它复原确实也挺好的。

故下面以例1为例子说一下我的思路：

第一步：

就是先得到数字字符的个数，这个可以根据空格+1来完成，因此用count把它记录下来。

第二步：

把原字符串完全倒置过来（也就是利用算法库的reverse）：

第三步：

根据数字字符范围，利用find找到此处的迭代器，并利用一定范围把字符添加到临时string tmp 中（这里是倒序的）

第四步：

最后面也就是颠倒过来然后补空格，但是最后要返回的ss之后末尾会多一个空格，然后给它去掉即可。

注：可能完成代码的途中，会在迭代器遍历这里出现问题：

如没控制好范围导致的迭代器越界访问：

如果没有if 和else 而是直接it=it+1;

这样就会发生迭代器越界访问（没有if）：

但是只有上面判断也可能会导致死循环（没有else）：

其他就思路走没有什么特别注意的地方了。

三·解答代码：

class Solution {
public:

    string sortSentence(string s) {
        int count = 1;
        string ss;
        string tmp;
        for (int i = 0; i < s.size(); i++) {
            if (isspace(s[i])) {
                count++;//找到数字个数
            }
        }
        reverse(s.begin(), s.end());
        for (int j = 1; j <= count; j++) {
            string::iterator t_it = find(s.begin(), s.end(), j+'0');
            string::iterator it = t_it+1;//确定对应单词开头位置
            while (!isspace(*it) && !isdigit(*it) && (*it) != '\0') {//判断终止条件
                tmp += *it;
                if (it != s.end() - 1) it = it + 1;//防止迭代器循环或者越界访问，（当遍历到最后的时候）
                else break;
            }
            //完成到ss中添加：
            reverse(tmp.begin(), tmp.end());
            tmp += ' ';
            ss += tmp;
            tmp.clear();



        }
        ss.pop_back();//去掉最后一个空格
        return ss;
    }

};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-08-23，如有侵权请联系 cloudcommunity@tencent.com 删除

算法