이동하는 문자 II

2381. 이동하는 글자 II

난이도:중

주제: 배열, 문자열, 접두사 합계

영문 소문자로 구성된 문자열 s와 2차원 정수 배열 시프트가 주어집니다. 여기서 Shifts[i] = [start_i, end_i, 방향_i]. 모든 i에 대해 s의 문자를 인덱스 시작i에서 인덱스 끝_i(_포함)으로 이동 if 방향_i = 1, 또는 방향_i =인 경우 문자를 뒤로 이동합니다. 0.

문자를 앞으로 이동한다는 것은 해당 문자를 알파벳의 다음 문자로 바꾸는 것을 의미합니다('z'가 'a'가 되도록 감싸는 것). 마찬가지로 문자를 뒤로 이동한다는 것은 해당 문자를 알파벳의 이전 문자로 바꾸는 것을 의미합니다('a'가 'z'가 되도록 둘러싸기).

s에 대한 모든 변화가 적용된 후 마지막 문자열을 반환합니다.

예 1:

• 입력: s = "abc", Shifts = [[0,1,0],[1,2,1],[0,2,1]]
• 출력: "ace"
• 설명: 먼저 문자를 인덱스 0에서 인덱스 1로 뒤로 이동합니다. 이제 s = "zac"입니다.
  • 두 번째로 문자를 인덱스 1에서 인덱스 2로 앞으로 이동합니다. 이제 s = "zbd"입니다.
  • 마지막으로 문자를 인덱스 0에서 인덱스 2로 앞으로 이동합니다. 이제 s = "에이스"입니다.

예 2:

• 입력: s = "dztz", Shifts = [[0,0,0],[1,1,1]]
• 출력: "catz"
• 설명: 먼저 문자를 인덱스 0에서 인덱스 0으로 뒤로 이동합니다. 이제 s = "cztz"입니다.
  • 마지막으로 문자를 인덱스 1에서 인덱스 1 앞으로 이동합니다. 이제 s = "catz"입니다.

제약조건:

• 1 <= s.length, Shifts.length <= 5 * 10⁴
• shifts[i].length == 3
• 0 <= 시작_i <= 끝_i < s.길이
• 0 <= 방향_i <= 1
• s는 영문 소문자로 구성됩니다.

힌트:

1. 각 교대조에서 모든 문자를 이동하는 대신 어떤 문자가 교대조 전체에서 얼마나 이동되었는지 추적할 수 있습니까?
2. 각 교대근무의 시작과 끝을 표시한 다음 교대근무의 접두사 합계를 수행해 보세요.

해결책:

각 교대마다 문자를 하나씩 이동하는 것은 피해야 합니다. 큰 입력의 경우 속도가 너무 느리기 때문입니다. 대신 접두사 합계라는 기술을 활용하여 보다 최적의 접근 방식을 사용할 수 있습니다.

단계:

1. 교대 경계 표시: 각 문자를 즉시 ​​이동하는 대신 각 범위의 시작과 끝 부분에 교대 효과를 표시합니다.
2. 접두사 합 적용: 모든 교대를 표시한 후 접두사 합 기술을 사용하여 각 문자의 누적 교대를 계산할 수 있습니다. 이를 통해 각 캐릭터에 누적 시프트를 효율적으로 적용할 수 있습니다.
3. 시프트 수행: 각 문자의 전체 시프트를 알고 나면 문자열에 시프트(앞으로 또는 뒤로)를 적용할 수 있습니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 2381. 문자 이동 II

  
  
  설명:



각 교대[시작, 끝, 방향]에 대해 시작 시 교대 배열을 증가시키고 끝 1에서 감소시킵니다. 이를 통해 교대 범위의 시작과 끝을 추적할 수 있습니다.
모든 시프트를 처리한 후 시프트 배열에 접두사 합계를 적용하여 각 인덱스의 누적 시프트를 얻습니다.
마지막으로 문자열의 각 문자에 누적 시프트를 적용합니다.



  
  
  코드 설명:




입력 구문 분석: 더 쉬운 조작을 위해 입력 문자열 s를 문자 배열로 변환합니다.

시프트 배열: n 크기의 시프트 배열을 1에서 0으로 초기화합니다. 이 배열은 이동 효과를 추적하는 데 사용됩니다. 각 교대[시작, 끝, 방향]에 대해 교대 시작과 끝을 반영하도록 교대[시작] 및 교대[끝 1]의 값을 조정합니다.

접두사 합계: 시프트 배열을 반복하고 누적 시프트 합계를 유지하여 각 문자의 총 시프트를 계산합니다.

문자 이동: 문자열의 각 문자에 대해 공식 (ord(currentChar) - ord('a') totalShift) % 26을 사용하여 최종 이동된 문자를 계산합니다. 이는 문자열의 순환 특성을 설명합니다. 알파벳.

반환 결과: 문자 배열을 다시 문자열로 변환하여 반환하면 최종 문자열을 얻습니다.



  
  
  시간 복잡도:




시간 복잡도: O(n·m), 여기서 n은 문자열 s의 길이이고 m은 교대 횟수입니다. 이는 문자열과 교대근무 목록을 각각 한 번씩 반복하기 때문입니다.

공간 복잡도: O(n), 여기서 n은 시프트 배열에 필요한 공간으로 인해 문자열 s의 길이입니다.


이 솔루션은 입력 제약의 상한에도 불구하고 문제를 효율적으로 처리합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

링크드인
깃허브



          

            
  

            
        
위 내용은 이동하는 문자 II의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!