알고리즘 학습 - 문자열 순환 왼쪽으로 이동

1483 단어
제목.
문자열 S [0... N - 1] 을 지정 합 니 다. 문자열 'abcdef' 앞의 2 글자 'a', 'b' 를 문자열 의 끝으로 이동 시 키 고 새 문자열 'cdefab' 를 가 져 오 십시오. 즉, 문자열 을 왼쪽으로 이동 합 니 다.
  • 왼쪽 으로 n + k 비트 와 k 비트 를 순환 하 는 효과 가 같 습 니 다.
  • 순환 왼쪽 이동 k 비트 는 순환 오른쪽 이동 n - k 비트 와 같다.

    • 알고리즘 요구 사항:
  • 시간 복잡 도 는 O (n) 이 고 공간 복잡 도 는 O (1) 이다.

    • 분석 하 다.
    폭력 변위 법
  • 매번 왼쪽으로 1 위 를 이동 하고 k 회 를 호출 하면 됩 니 다
  • 시간 복잡 도 O (kN), 공간 복잡 도 O (1)
    • 트 라이 카피
  • S[0...k]->T[0...k]
  • S[k+1...N-1]->S[0...N-k-1]
  • T[0...k]->S[N-k...N-1]
  • 시간 복잡 도 O (N), 공간 복잡 도 O (k)
    • 적합 한 알고리즘
  • 행렬 의 한 가지 성질 은 행렬 A 와 B 이 고 (A * B) 의 전 치 는 B 의 전 치 곱 하기 A 의 전 치
    • 가 있다.
  • 문자열 벡터 도 이러한 성질 이 있 습 니 다. 예 를 들 어 문자열 X 와 Y 는 (x 'Y') '= YX 가 있 습 니 다.
  • 예: abcdef
  • X=ab X'=ba
  • Y=cdef Y'=fedc
  • （X'Y'）‘=（bafedc）‘=cdefab

  • 시간 복잡 도 는 O (N) 이 고 공간 복잡 도 는 O (1) 이다.
  • 이 문 제 는 '완벽 한 카드 세탁' 알고리즘 과 관련 이 있 으 니 시간 이 있 으 면 토론 하고 기록 하 세 요.


    • 코드 는 간단 합 니 다. 다음 과 같 습 니 다.
    void ReverseString(char* s, int from, int to)
{
	while (from < to)
	{
		char t = s[from];
		s[from++] = s[to];
		s[to--] = t;
	}
}

void LeftRotateString(char* s, int n, int m)
{
	m %= n;
	ReverseString(s, 0, m - 1);
	ReverseString(s, m, n - 1);
	ReverseString(s, 0, n - 1);
}

    제목 이 어렵 지 않 습 니 다. 여러 문자열 배열 이 비슷 한 변 화 를 할 수 있 습 니 다.
    Automated Watch 상세 배포 설치 Ansible 서비스(초간단)
    Keras 스타일 이전 실현

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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