[알고리즘 문제] 문자열 을 왼쪽으로 또는 오른쪽으로 순환 이동 합 니 다.

2006 단어 알고리즘
문제 설명: n 개의 요 소 를 가 진 문자열 을 왼쪽으로 이동 합 니 다.예 를 들 어 n = 8, i = 3 을 가정 하면 문자열 abcdefgh 가 이동 한 후에 defghbc 가 됩 니 다. 정수 배열 에 대해 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 순환 으로 5 자 리 를 왼쪽으로 이동 한 결 과 는 6, 7, 8, 9, 10 순환 으로 5 자 리 를 이동 한 결과 6, 9, 9, 10, 1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 8, 9, 9,
조건: 시간 복잡 도 O (n), 공간 복잡 도 O (1).
사람들 이 생각 할 수 있 는 해법: 첫째, 배열 이나 문자열 의 앞 i 요 소 를 임시 배열 로 복사 한 다음 에 남 은 n - i 요 소 를 왼쪽 으로 i 위 치 를 옮 긴 다음 에 앞 i 요 소 를 임시 배열 에서 배열 의 뒤쪽 위치 로 복사 합 니 다.이 방안 은 i 개의 추가 위 치 를 사용 하여 공간 을 낭비 했다.2. 하나의 함 수 를 정의 하여 x 를 왼쪽으로 한 위 치 를 회전 시 킨 다음 에 이 함수 i 회 를 호출 하지만 이런 방법 은 시간 을 너무 낭비 합 니 다.시간 과 n 이 비례 하 다
가장 간단 하고 가장 효과 적 인 방법 은 다음 과 같다 (블록 회전 과 전체 회전). 10 개의 요 소 를 가 진 배열 (1, 2, 3, 4, 5, 6, 7, 89 10) 을 왼쪽 순환 으로 5 개의 위 치 를 이동 시 키 려 면 손 을 흔 드 는 방법 을 사용한다. 먼저 손바닥 으로 자신 을 향 하고 왼손 은 오른손 위 에 있다. 다음 과 같다.
  구현 코드 는 다음 과 같 습 니 다:
#include<stdio.h>
void  reverse(int a[],int start,int end ) //   a start end     
{
  int temp=0;
  int i=start;
  int j=end;
  while(i<=j)
  {
    temp=a[i];
  a[i]=a[j];
     a[j]=temp;
  i++;
  j--;
  }

}

void show(int a[],int len)
{
 for(int i=0;i<len;i++)
 {
  printf("%d ",a[i]);
 }
 printf("
"); } void main() { int a[]={1,2,3,4,5,6,7,8,9,10}; int len=sizeof(a)/sizeof(int); show(a,len); int steps=5;// reverse(a,0,steps-1); show(a,len); reverse(a,steps,len-1); show(a,len); reverse(a,0,len-1); show(a,len); }

문자열 의 반전 은 strcpy 나 memcpy 함수 로 이 루어 질 수 있 습 니 다. 다음 문 제 는 많은 회사 필기시험 문제 에서 나 왔 습 니 다.예:
void loopmove(char *pStr,int steps)
{
int n=strlen(pStr)-steps;
char temp[100];
strcpy(temp,pStr+n);
strcpy(temp+steps,pStr);
*(temp+strlen(pStr))='\0';
strcpy(pStr,temp);
}

좋은 웹페이지 즐겨찾기