Letcode 899--간단한 하드 문제 1

7360 단어 Leetcode

Letcode 899--간단한 하드 문제 1

  • 제목설명
  • 분석
  • 코드
  • Solution 1
  • Solution 2

    • 제목 설명


    A string S of lowercase letters is given. Then, we may make any number of moves.
    In each move, we choose one of the first K letters (starting from the left), remove it, and place it at the end of the string.
    Return the lexicographically smallest string we could have after any number of moves.

    분석하다.

  • 규칙에 따라 변환된string의 사전 최소 서열을 구한다. 만약에 k=1이라면 매우 간단하다. 매번 자모를 마지막에 놓고 S.size()개의 문자열을 형성할 수 있다. 그 중에서 사전 서열의 가장 작은 출력을 찾으면 된다.
  • k>=2, 매번 전 k자 중에서 끝까지 놓인 문자를 선택하는 것이 중요하다.마지막으로 순환 조작한 후에 사전 순서가 가능한 한 작다는 것을 보증해야 한다.
  • k=2의 경우 한 번 순환하면 전체 문자열의 최소 자모를 수위에 놓고 변하지 않으면 자모의 최소를 보장할 수 있다. 그러나 이렇게 하면 나머지 자모에 대해 k=1의 조작을 응용한다.그러나 이렇게 해서 마지막에 얻은 결과가 가장 적다는 것을 보장할 수 없다.
  • 이렇게 하면 k의 공간을 손실할 수 있으므로 우리는 순환의 특성을 이용해야 한다. 마찬가지로 가장 작은 알파벳을 찾아서 한 번 훑어본 후에 한 번 조작을 하고 가장 작은 알파벳을 끝에 놓아야 한다. 그러면 S.size()-1의 문자열로 변하고 k=2의 조작을 응용해야 한다. 다음에 두 번째 알파벳을 훑어보면 자연스럽게 첫 번째 알파벳이 된다. 이때 다시 조작하면 끝에 던져진 가장 작은 알파벳을 만나게 된다.최소자모와 차소자모를 순서대로 끝까지 던지기;반복하면 규정된 조작하의 최소 사전 서열 S를 얻을 수 있다.
  • k>2의 경우 더욱 그렇다. 얻은 것은 S가 사전 순서에 따라 정렬한 결과이다.

    • 코드


    Solution 1

    string orderlyQueue(string S,int K){
        string result=S;
        int num=S.size();
        if(K==1){
                for(int i=1;i<num;++i){
                        S+=S[0];
                        S.erase(S.begin());
                        result=result<S?result:S;
                }
        }
        else
                sort(result.begin(),result.end());
        return result;
}

    이 코드는 테스트를 통과할 수 있지만 K=1의 상황은 매우 추악하다. 매번 문자의 삭제를 해야 하기 때문에 Solution 2로 대체할 수 있다.

    Solution 2


    두 개의 S 처음과 끝을 연결하여 각각 다른 시작 위치의 긴 문자열을 찾으면 됩니다.
    string orderlyQueue(string S,int K){
        if(K>1){
                sort(S.begin(),S.end());
                return S;
        }
        
        string result=S;
        int num=S.size();
        S+=S;
        for(int i=0;i<num;++i){
                result=min(result,S.substr(i,num));
        }
        return result;
}
    Different types of function parameters (*args, **kwargs, keyword-only arguments)
    JSON에서 AG 메쉬 열 동적으로 만들기

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage