本文主要是介绍9.15（ 31.（数组）题目：下一个排列 12.（字符串）整数转罗马数字），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
31.（数组）题目：下一个排列
思路：
1.从后向前遍历数组，相邻数值比较。找到第一个满足a[i]<a[i+1]的i，并标记为tmp;
2.如果tmp==0:说明原字符串是从大到小排序的，只需要使用冒泡排序翻一下序列就行了。因为不能占用额外的空间，所以我选择了冒泡排序，使用快速排序也可以，但是不能使用归并排序；
如果tmp!=0：从tmp后面的位置开始对原字符串进行排序。排完之后，选择第一个大于a[tmp]的数字和a[tmp]进行交换即可；
代码如下：
class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size();int tmp = 0;//记录元素下标int flag = 0;//这个初始化表示最终是按照从大到小排列for (int i = nums.size()-2; i >= 0; i--) {if (nums[i] >= nums[i + 1]);else {tmp = i;//记录下第一个比后面小的元素下标flag = 1;break;//找到之后立即退出} }if (flag == 1) {//把最开始的和后面的大于它的交换for (int i = 0; i < nums.size() - tmp - 1; i++) {for (int j = tmp + 1; j < nums.size() - i - 1; j++) {//按照升序排列if (nums[j] > nums[j + 1])swap(nums[j], nums[j + 1]);}}for (int i = tmp + 1; i < nums.size(); i++)if (nums[i] > nums[tmp]) {swap(nums[tmp], nums[i]);//交换前两个元素的位置break;}}else {//表示把原本的字符串反过来就行了for (int i = 0; i < nums.size() - tmp; i++) {for (int j = tmp; j < nums.size() - i - 1; j++) {//按照升序排列if (nums[j] > nums[j + 1])swap(nums[j], nums[j + 1]);}}}}void swap(int &a, int &b) {int t = a;a = b;b = t;//在原位交换两个元素的内容}
};
12.（字符串）整数转罗马数字
思路：
1.类似于数值在十进制下的逐位分解，只是本道题不是1000，100，10这种
，而是1000,900,500,400,100,90,50,40,10,9,5,4,1这种。
代码如下：
class Solution {
public:string intToRoman(int num) {int count;//表示字符串加的次数int i = 0;int a[13] = { 1000,900,500,400,100,90,50,40,10,9,5,4,1 };string b[13] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};string s="";//表示目标字符串while (num!=0) {count = num / a[i];while (count--) {//这个可以s += b[i];}num = num % a[i];i++;}return s;}};
这篇关于9.15（ 31.（数组）题目：下一个排列 12.（字符串）整数转罗马数字）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
