leetcode 1859. 将句子排序

句子排序"/>

leetcode 1859. 将句子排序

leetcode 1859. 将句子排序

一个 句子 指的是一个序列的单词用单个空格连接起来，且开头和结尾没有任何空格。每个单词都只包含小写或大写英文字母。

我们可以给一个句子添加 从 1 开始的单词位置索引 ，并且将句子中所有单词 打乱顺序 。

• 比方说，句子 "This is a sentence" 可以被打乱顺序得到 "sentence4 a3 is2 This1" 或者 "is2 sentence4 This1 a3" 。

给你一个 打乱顺序 的句子 s ，它包含的单词不超过 9 个，请你重新构造并得到原本顺序的句子。

示例 1：

输入：s = "is2 sentence4 This1 a3"
输出："This is a sentence"
解释：将 s 中的单词按照初始位置排序，得到 "This1 is2 a3 sentence4" ，然后删除数字。

#include<iostream>
#include<bits/stdc++.h>using namespace std;class Solution {
public:string sortSentence(string s) {stringstream iss(s);vector<string> strs;char token = ' ';while(getline(iss, s, token)) {strs.push_back(s);}int len = strs.size();vector<pair<string,int>> nums;string result = "";for(int i=0;i<len;i++) {string temp = strs[i];int c = *(--temp.end()) - '0';nums.push_back(make_pair(temp.substr(0,temp.size()-1),c));}sort(nums.begin(),nums.end(),cmp);for(auto i:nums) {result+=i.first+" ";}return result.substr(0,result.size()-1);}static int cmp(pair<string,int>a,pair<string,int>b){return a.second<b.second;}};int main() {string s = "is2 sentence4 This1 a3";Solution solution;cout<<solution.sortSentence(s)<<endl;return 0;
}

Python的极简实现：

class Solution:def sortSentence(self, s: str) -> str:words = s.split(" ")words = sorted(words, key=lambda w : w[-1])return ' '.join(w[:-1] for w in words)

一个小小的题目涉及到多个算法：

对于C++ 处理字符串略占劣势，

1. 字符串分割

// C++ 来构建一个Split函数来解决字符串的分割问题#include<iostream>
#include<bits/stdc++.h>using namespace std;vector<string> split(string s, char token) {stringstream iss(s);string word;vector<string> vs;while(getline(iss, word,token)) {vs.push_back(word);}return vs;
}int main(int argc, char *argv[]) {// 下面是测试用例string s="aaa,bbb,ccc,ddd";vector<string> s2 = split(s,',');for(unsigned int i=0;i<s2.size();i++) {cout<<s2[i]<<endl;}system("pause");return 0;
}

2. 字符串截取

#include <iostream>
#include <string>int main() {std::string str = "Hello, World!";// 提取从位置 7 开始的子串std::string sub1 = str.substr(7);std::cout << "sub1: " << sub1 << std::endl;  // 输出 "World!"// 提取从位置 7 开始的长度为 5 的子串std::string sub2 = str.substr(7, 5);std::cout << "sub2: " << sub2 << std::endl;  // 输出 "World"return 0;
}

3. 字符串位置

#include <iostream>
using namespace std;
int main()
{string str("Spider Man");cout<<"Character at position 3: "<<str.at(3)<<endl;int length = str.size();cout<<"Character at last position: "<<str.at(length-1)<<endl;
}

#include <iostream>
#include<string>using namespace std;
int main()
{string str("Hello World");string::reverse_iterator it = str.rbegin();cout<<"The last character of the string is: "<<*it;
}

#include <iostream>using namespace std;int main()
{string str("Hello World");char ch = str.back();cout<<"Character at the end "<<ch<<endl;str.back() = '@';cout<<"String after replacing the last character: "<<str<<endl;
}

4.Pair 的使用 

#include <iostream>
#include <utility>using namespace std;int main()
{pair<int, string> p1;//①默认构造函数p1 = make_pair( 1,"Hello" );cout << "p1.first: " << p1.first << "   p1.second : " << p1.second << endl;return 0;
}

#include <iostream>
#include <bits/stdc++.h>using namespace std;typedef pair<int,int> PII;
//降序函数bool cmpa(int a, int b)
{return a>b;//升序则为a<b
}
//改成相应的参数bool cmp2(PII a,PII b)
{return a.first<b.first;//根据fisrt的值升序排序//return a.second<b.second;//根据second的值升序排序
}int main()
{vector<int> nums;nums.push_back(2);nums.push_back(1);nums.push_back(3);nums.push_back(4);nums.push_back(5);nums.push_back(10);sort(nums.begin(),nums.end(),cmpa);for(auto i:nums) {cout<<i<<" ";}cout<<endl<<"------------------------"<<endl;vector<pair<int,int>> vec;vec.push_back(make_pair(3,2));vec.push_back(make_pair(3,5));vec.push_back(make_pair(6,7));vec.push_back(make_pair(9,3));vec.push_back(make_pair(10,1));//如何调用sort(vec.begin(),vec.end(),cmp2);//降序排列for(auto i:vec) {cout<<i.first<<" "<<i.second<<endl;}return 0;
}