검지 오 프 - 004 - 스페이스 바 꾸 기

링크
우 객 OJ: 스페이스 바 꾸 기
구도 OJ:http://ac.jobdu.com/problem.php?pid=1510
GitHub 코드: 004 - 스페이스 바 꾸 기
CSDN 문제 풀이: 검 지 Offer – 004 - 빈 칸 교체
우 객 OJ
구도 OJ
CSDN 문제 풀이
GitHub 코드
공백 바 꾸 기
1510 - 스페이스 바 꾸 기
검지 오 프 – 004 - 스페이스 바 꾸 기
004 - 스페이스 바 꾸 기
디 렉 터 리 로 돌아 가 는 것 도 선택 할 수 있 습 니 다 – 검 지 Offer – 문제 집 디 렉 터 리 색인
제목
제목 설명
문자열 의 빈 칸 을 '% 20' 으로 바 꾸 는 함 수 를 구현 하 십시오.예 를 들 어, 문자열 이 We Are Happy 일 때, 교 체 된 문자열 은 We% 20Are% 20Happy 입 니 다.
We Are Happy
We%20Are%20Happy
원래 문자열 에서 바 꾸 는 것 을 고려 하지 않 는 다 면, 우 리 는 직접 배열 을 하나 더 열 고, 이동 한 후에 순서대로 값 을 부여 합 니 다.
빈 칸 을 만나면% 20 을 (를) 채 워 라. 그렇지 않 으 면 현재 문 자 를 채 워 라.
근 데 이 건 면접 관 이 기대 하 는 게 아 닐 거 예요.
그렇다면 어떻게 원 문자열 에서 효율 적 인 교 체 를 합 니까?
폭력 교체
가장 원시 적 인 방법 은 문자열 을 한 번 훑 어 보 는 것 입 니 다. 문자 의 모든 빈 칸 을% 20 으로 바 꿉 니 다.% 20 으로 빈 칸 을 바 꾸 면 문자열 의 길이 가 증가 하기 때문에 주의해 야 합 니 다. * 뒤에서 문자열 을 옮 겨 다 니 며 * 빈 칸 을 찾 을 때마다 ' ' 뒤의 문자열 을 두 자리 뒤로 옮 겨 서% 20 의 공간 을 미리 남 겨 두 어야 합 니 다.
코드 는 다음 과 같다.

#include 

using namespace std;

#define __tmain main


class Solution
{
public:
    void replaceSpace(char *str,int length)
    {
        int i = length - 1, j;
        int len = length;

        //        
        for(i = length - 1; i >= 0; i--)
        {
            //cout <
            //           
            if(str[i] == ' ')
            {
                //       %20     2
                len += 2;

                for(j = len - 1; j > i + 2; j--)
                {
                    str[j] = str[j - 2];
                }
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '\%';
            }
            //cout <
        }
        str[len] = '\0';
    }
};


int __tmain( )
{
    char str[10 + 1] = "a b c d";

    Solution solu;
    solu.replaceSpace(str, 10);

    cout <return 0;
}

최적화 하 다.
위의 그 방법 은 너무 폭력 적 인 데, 더 좋 은 방법 이 없 을 까?
우리 의 코드 는 주로 빈 칸 이 여러 개 있 으 면 빈 칸 을 만 날 때마다 자 리 를 옮 기 는 데 시간 을 소모 합 니 다.
사실 앞의 자 리 를 옮 기 는 것 은 불필요 하 다. 왜냐하면 다시 빈 칸 을 만나면 이전의 자 리 를 옮 기 는 것 은 모두 헛 된 것 이기 때문이다.
따라서 우 리 는 먼저 문자열 을 한 번 옮 겨 다 니 며 빈 칸 의 수 를 계산 하 는 것 을 고려 할 수 있다.
우 리 는 빈 칸 의 수 를 알 게 되 었 습 니 다. 사실은 바 꾼 문자열 의 길 이 를 알 게 되 었 습 니 다. 그러면 한 번 만 바 꾸 면 됩 니 다.
우리 일 때문에

문자열 을 한 번 훑 어보 고 문자 가 나타 난 숫자 를 통계 하 며 교 체 된 문자열 의 길 이 를 계산한다

문자열 을 다시 한 번 옮 겨 다 니 며 교체 완료

코드 는 다음 과 같다.

#include 

using namespace std;

#define __tmain main


class Solution
{
public:
    void replaceSpace(char *str,int length)
    {
        int i, j;
        int count = 0;
        int len = length;
        for(int i = 0; i < length; i++)
        {
            if(str[i] == ' ')
            {
                count++;
            }
        }

        len = length + count * 2;
        for(i = length - 1, j = len - 1;
            i >= 0 && j >= 0;)
        {
            if(str[i] == ' ')
            {
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '%';
                i--;
            }
            else
            {
                str[j--]  = str[i--];
            }
        }
        str[len] = '0';

    }
};


int __tmain( )
{
    char str[10 + 1] = "a b c d";

    Solution solu;
    solu.replaceSpace(str, 10);

    cout <return 0;
}