소문자 문자열 s가 있다고 가정합니다. s에서 알파벳의 출현이 가능한 모든 방식으로 재배열한 후 Recaman's Sequence(첫 번째 항은 무시)를 생성하는지 확인해야 합니다.
Recaman의 순서는 다음과 같습니다 -
$$a_{n}=\begin{케이스}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:0(if\:n=0 ) &\\a_{n-1}-n(if\:a_{n}-n>0\wedge not\:present\in sequence) &\\\:\:\:\:\:\:\ :\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:a_{n-1}+n(그렇지 않으면)\end{케이스 }$$
Recaman's Sequence의 항목 중 일부는 [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24,...]입니다(첫 번째 항은 0이므로 무시됨)
따라서 입력이 s ="pppuvuuqquuu"와 같으면 문자와 빈도가 (p, 3), (u, 6), (v, 1) 및 (q, 2)이므로 출력은 True가 됩니다. 따라서 주파수는 Recaman 수열 [1, 3, 6, 2]의 처음 몇 항을 형성합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- freq :=s의 모든 문자와 해당 빈도를 포함하는 맵
- n :=주파수 크기
- 배열 :=처음 n개 Recaman의 시퀀스 항
- f :=1
- freq의 각 문자에 대해 다음을 수행합니다.
- is_found :=0
- 1~n 범위의 j에 대해 다음을 수행합니다.
- freq[keys]가 array[j]와 같으면
- is_found :=1
- 루프에서 나오다
- freq[keys]가 array[j]와 같으면
- is_found가 거짓이면
- f :=0
- 루프에서 나오다
- f가 설정되면 True, 그렇지 않으면 False를 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import defaultdict def recaman(array, n) : array[0] = 0 for i in range(1, n + 1): temp = array[i - 1] - i for j in range(i): if array[j] == temp or temp < 0: temp = array[i - 1] + i break array[i] = temp def solve(s) : freq = defaultdict(int) for i in range(len(s)) : freq[s[i]] += 1 n = len(freq) array = [0] * (n + 1) recaman(array, n) f = 1 for keys in freq.keys() : is_found = 0 for j in range(1, n + 1) : if freq[keys] == array[j]: is_found = 1 break; if not is_found: f = 0 break return True if f else False s = "pppuvuuqquuu" print(solve(s))
입력
"pppuvuuqquuu"
출력
True