숫자 문자열에서 문자를 제거하여 8로 나누어지는 C++ 프로그램

문자열 형식의 숫자가 주어지면 0개 이상의 요소를 삭제한 후 숫자를 8로 나눌 수 있는 위치를 찾아야 합니다. 즉, 문자열의 하위 시퀀스가 ​​있는지 찾아야 합니다. 은 8로 나눌 수 있습니다. 수정된 문자열을 반환하거나, 불가능할 경우 -1을 반환합니다.

나누기 법칙에 따르면 마지막 세 자리 숫자가 8로 나누어지는 숫자는 모두 8로 나누어집니다. 예를 들어, 56992992와 476360은 8로 나눌 수 있지만 2587788은 그렇지 않습니다. 결과가 정수이면 원래 숫자는 8로 나누어집니다.

방법을 자세히 설명하는 입력 시나리오를 살펴보겠습니다 −

메서드에 전달된 입력이 8로 나누어지는 하위 문자열을 포함하는 숫자 문자열인 경우 결과 목록에서 8로 나누어지는 하위 문자열을 얻을 수 있습니다−

으아악

메서드에 대한 입력이 8로 나눌 수 있는 하위 문자열을 포함하지 않는 숫자 문자열인 경우 출력은 −

로 반환됩니다. 으아악

알고리즘

• 문자열 입력이 반복되어 하위 문자열이 8의 배수인지 확인합니다.

• 입력에 결과 하위 문자열이 있는 경우 해당 하위 문자열이 출력으로 반환됩니다.

• 하위 문자열이 발견되면 프로그램이 종료되고, 그렇지 않으면 하위 문자열을 찾을 때까지 2단계를 반복합니다.

• 입력에 8로 나눌 수 있는 하위 문자열이 없으면 반환되는 출력은 -1입니다.

예

아래 C++ 프로그램에서는 두 개의 문자열을 사용합니다. 하나는 8로 나눌 수 있는 문자열로 변환할 수 있고 다른 하나는 변환할 수 없는 문자열로 각 경우의 출력을 찾습니다. 0, 8, 16, 24, 32...1000과 같이 8의 배수로 0부터 1000까지 반복하고 이 숫자가 주어진 문자열의 하위 시퀀스로 존재하는지 확인할 수 있습니다.

으아악

출력

으아악

위 출력에서 ​​볼 수 있듯이 95258에서 9525가 제거되고, 74516에서 745가 제거되어 왼쪽 숫자가 8로 나누어지게 됩니다.

결론

보시다시피, 간단한 관찰 후에는 하위 집합이 존재하는지 확인하면 됩니다. 문자열에 하위 시퀀스가 ​​포함되어 있는지 확인하고 최악의 경우 전체 문자열을 확인합니다. 따라서 길이가 n인 숫자 문자열이 주어지면 최악의 경우 시간 복잡도는 O(126*n), 즉 O(n)입니다.

위 내용은 숫자 문자열에서 문자를 제거하여 8로 나누어지는 C++ 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!