bigger is greater

heckerrank 算法题。

原题地址

此题大意为找到，字典序的下一个最小序列。

input

dhck
dkhc

output

dhkc
hcdk

通过代码

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

string rever(string str, int index ){
    
    string temp = str.substr(index+1);

    int length = temp.length();
    for(int i = 0 ; i< length / 2;i++){
        char aa = temp[i];
        temp[i] = temp[length-i-1];
        temp[length-i-1] = aa;
    }
    string result = str.substr(0,index+1) + temp;
    return result;
}
void handle(string str){
    if( str.length() == 1 ){
        cout<<"no answer"<<endl;
        return;
    }
    int flag = 0;
    int length = str.length();
    string result;
     for( int i = length - 2 ; i >= 0 ; i-- ){
        if( str[ i ] < str[ i + 1 ] ) {
        
            for( int j = i + 1 ; j < length ; j++ ){
                if( str[i] < str[j] && (!str[j+1]||str[i] >= str[j+1])){
                    char temp = str[i];
                    str[i] = str[j];
                    str[j] = temp;
                    cout<<str<<endl;
                    result = rever(str,i);
                    break;
                }
            } 
            flag = 1;
            break;
        }
        
     }
     if( flag == 1 ) {
        cout<<result<<endl;
     }else{
        cout<<"no answer"<<endl;
     }
     
}

int main() {
    int count = 0;
    
    cin>>count;
    string s[count];
    for( int i = 0 ; i < count ; i++ ){
        cin>>s[i];
        handle(s[i]);
    }
    
    return 0;
}

我的解题思路

首先此题的难点就是找到最小的下一个字典序，所以，我从一个字符串的最后往前，进行遍历。

for( int i = length - 2 ; i >= 0 ; i-- )

如果str[i] < str[i+1]，找到需要改变的子字符串。为str[i,length)

if( str[ i ] < str[ i + 1 ] ) {
        
            for( int j = i + 1 ; j < length ; j++ ){
                if( str[i] < str[j] && (!str[j+1]||str[i] >= str[j+1])){
                    char temp = str[i];
                    str[i] = str[j];
                    str[j] = temp;
                    cout<<str<<endl;
                    result = rever(str,i);
                    break;
                }
            } 
            flag = 1;
            break;
        }

// 从[i+1,length) 找到大于str[i],如果有多于一个字符大于str[i],那么就找到最小的哪一个。和str[i],进行交换。最后将str[i+1,length]rever，替换之前的str[i+1,length]。