이진 문자열에서 증가하지 않는 가장 긴 하위 시퀀스
이 문제에서는 주어진 문자열에서 증가하지 않는 가장 긴 부분 수열을 찾아야 합니다.
비증가는 문자가 동일하거나 내림차순임을 의미합니다. 이진 문자열에는 "0"과 "1"만 포함되므로 결과 문자열은 "1"로 시작하고 "0"으로 끝나거나 "0" 또는 "1"로 시작하고 끝나야 합니다.
이 문제를 해결하기 위해 문자열의 각 위치에서 접두사 "1"과 접미사 "0"을 세고 접두사 "1"과 접미사 "0"의 최대 합을 구합니다.
문제 설명 - 바이너리 문자열 str이 제공됩니다. 주어진 문자열에서 증가하지 않는 가장 긴 부분 수열을 찾아야 합니다.
예
으아악 으아악지침
가장 긴 비증가 부분 수열은 "1100"입니다.
으아악 으아악지침
가장 긴 비증가 부분 수열은 "111000"입니다.
으아악 으아악지침
가장 긴 비증가 하위 수열은 '00000000'이며, 이는 주어진 문자열과 같습니다.
방법 1
이 방법에서는 배열의 각 인덱스에 대해 접두사 '1'과 접미사 '0'의 개수를 저장합니다. 그런 다음 두 배열의 동일한 인덱스에서 값을 가져와 추가하고 최대 합계를 찾습니다.
알고리즘
1단계 - pre1s 및 suffix0s 배열을 정의하여 접두사 1과 접미사 0을 저장합니다. 또한 모든 배열 요소를 0으로 초기화합니다.
2단계 - for 루프를 사용하여 문자열을 반복하고 각 인덱스의 접두사 1을 계산합니다. i > 0이면 이전 요소의 값이 현재 요소에 추가됩니다.
3단계 - 현재 문자가 "1"이면 pre1s[i]의 현재 값에 1을 더합니다.
4단계 - 이제 주어진 문자열에서 접미사 0을 셉니다. 끝부터 시작하여 문자열을 탐색합니다.
5단계 - "I" 값이 "n – 1"과 같지 않으면 "I + 1" 요소의 값을 가져와 현재 요소에 추가합니다.
6단계 - 현재 요소가 "0"이면 현재 요소에 1을 추가합니다.
7단계 - 이제 "res" 변수를 0으로 초기화합니다.
8단계 - 루프를 사용하여 "pre1s" 및 "suffix0s"를 반복합니다.
9단계 - "pre1s" 및 "suffix0s" 배열의 i번째 인덱스에서 값을 가져와 함께 추가합니다. 또한 "sum"이 "res" 변수의 현재 값보다 큰 경우 "res" 변수 값이 "sum" 값으로 변경됩니다.
10단계 - "res" 변수의 값을 반환합니다.
예
입력 '010100'의 경우 접두사 배열은 [0, 1, 1, 2, 2, 2]이고 접미사 0 배열은 [4, 3, 3, 2, 2, 1]입니다. 합계 배열은 [4, 4, 4, 4, 4, 1]이고 합계 배열의 최대값은 4입니다. 그러므로 답은 4가 될 것이다.
으아악출력
으아악시간 복잡도 - O(N) 접두사 1과 접미사 0으로 배열을 초기화해야 하기 때문입니다.
공간 복잡도 - 배열에 접두사 1과 접미사 0을 저장하므로 O(N)
방법 2
이 방법에서는 먼저 총 0의 개수를 계산합니다. 그런 다음 문자열을 반복하면서 "1"을 계속 세고, 0이 발견되면 "0"씩 감소시킵니다. 또한 각 반복마다 0과 1의 개수를 더하고 최대 결과 값을 찾습니다.
알고리즘
1단계 - 'count1', 'count0' 및 'res' 변수를 정의하고 0으로 초기화하여 각각 1, 0의 개수와 최종 결과를 저장합니다.
2단계 - 문자열을 반복하고 "count0" 변수에 저장하여 총 0의 개수를 셉니다.
3단계 - 이제 루프를 사용하여 문자열을 반복합니다.
4단계 - 루프에서 현재 문자가 "1"이면 "count1"의 값을 1만큼 늘리고, 그렇지 않으면 "count0"의 값을 1만큼 줄입니다.
5단계 - 또한 "res" 및 "count0 + count1"의 최대값을 "res" 변수에 저장합니다.
6단계 - 루프가 종료되면 "res" 변수의 값을 반환합니다.
예
으아악출력
으아악시간 복잡도 - O(N) 문자열에 있는 0의 총 개수를 세고 문자열을 순회하여 가장 긴 부분 수열을 찾습니다.
공간 복잡성 - O(1)
결론
여기서 두 방법 모두 시간 복잡도는 동일하지만 공간 복잡도가 다릅니다. 두 번째 방법은 코드를 최적화할 때 일정한 공간을 사용하지만, 첫 번째 방법은 접두사 1과 접미사 0의 총 개수를 저장하기 위해 동적 공간을 사용합니다.
위 내용은 이진 문자열에서 증가하지 않는 가장 긴 하위 시퀀스의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
핫 AI 도구
Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱
AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.
Undress AI Tool
무료로 이미지를 벗다
Clothoff.io
AI 옷 제거제
AI Hentai Generator
AI Hentai를 무료로 생성하십시오.
인기 기사
뜨거운 도구
메모장++7.3.1
사용하기 쉬운 무료 코드 편집기
SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.
스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경
드림위버 CS6
시각적 웹 개발 도구
SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)
뜨거운 주제
7517
15
1378
52
79
11
53
19
21
66
Xiaohongshu가 동영상을 공개한 시간을 확인하는 방법은 무엇입니까? 동영상을 게시하는 데 가장 오랜 시간이 걸리나요?
Mar 21, 2024 pm 04:26 PM
라이프스타일 공유 플랫폼인 Xiaohongshu는 점점 더 많은 사용자가 자신의 비디오 콘텐츠를 게시하고 다른 사용자와 일상을 공유하기로 선택하는 곳입니다. 많은 사용자가 동영상을 게시할 때 문제에 직면할 수 있습니다. 자신이나 다른 사람이 동영상을 게시한 시간을 어떻게 확인하나요? 1. 샤오홍슈가 영상을 공개한 시간을 어떻게 확인하나요? 1. 영상을 게시한 시간을 확인하려면 먼저 Xiaohongshu 앱을 열고 개인 계정에 로그인해야 합니다. 개인 홈페이지 인터페이스 하단에 '생성'이라고 표시된 옵션이 있습니다. 클릭하여 입력하면 '동영상'이라는 열이 표시됩니다. 여기에서 게시된 모든 비디오 목록을 탐색하고 게시된 시기를 쉽게 확인할 수 있습니다. 각 동영상을 클릭하면 오른쪽 상단에 '세부정보 보기' 버튼이 있습니다.
이진 문자열에서 증가하지 않는 가장 긴 하위 시퀀스
Sep 07, 2023 pm 11:13 PM
이 문제에서는 주어진 문자열에서 증가하지 않는 가장 긴 부분 수열을 찾아야 합니다. 증가하지 않는다는 것은 문자가 동일하거나 내림차순임을 의미합니다. 이진 문자열에는 "0"과 "1"만 포함되므로 결과 문자열은 "1"로 시작하고 "0"으로 끝나거나 "0" 또는 "1"로 시작하고 끝나야 합니다. 이 문제를 해결하기 위해 문자열의 각 위치에서 접두사 "1"과 접미사 "0"을 세고 접두사 "1"과 접미사 "0"의 최대 합을 찾습니다. 문제 설명 - 바이너리 문자열 str이 제공됩니다. 주어진 문자열에서 증가하지 않는 가장 긴 부분 수열을 찾아야 합니다. 예 입력–str="010100"Output–4는 가장 긴 비재귀를 보여줍니다.
PHP에서 pack() 함수의 기능은 데이터를 이진 문자열로 변환하는 것입니다.
Aug 31, 2023 pm 02:05 PM
pack() 함수는 데이터를 이진 문자열로 압축합니다. 구문 pack(format,args) 매개변수 format - 사용할 형식입니다. 다음은 가능한 값입니다. - a - NUL 패딩 문자열 A - 공백 패딩 문자열 h - 16진수 문자열, 낮은 니블 먼저 H - 16진수 문자열, 높은 니블 먼저 c - 부호 있는 문자 C - 부호 없는 문자 s - 부호 있는 짧은(항상 16비트) , 머신 바이트 순서) S - unsigned short(항상 16비트, 머신 바이트 순서) n - unsigned short(항상 16비트, big endian 바이트 순서) v - unsigned short(항상 16비트, little endian 바이트 순서) i - 부호 있는 정수 (머신 크기 및 바이트 순서에 따라 다름) I - 없음 부호 있는 정수(머신 크기 및 바이트 순서에 따라 다름)
C++로 작성되어 1로 시작하는 이진 문자열의 고유 순열 수를 찾습니다.
Sep 05, 2023 am 09:01 AM
주어진 문제에서는 0과 1로 구성된 문자열이 주어집니다. 1로 시작하는 모든 순열의 총 개수를 찾아야 합니다. 대답은 엄청난 숫자일 수 있으므로 모듈로 1000000007을 가져와 출력합니다. Input:str="10101001001"Output:210Input:str="101110011"Output:56 우리는 몇 가지 조합 수학을 적용하고 몇 가지 공식을 설정하여 이 문제를 해결할 것입니다. 풀이 방법 이 방법에서는 0과 1의 개수를 세어보겠습니다. 이제 n이 문자열에 나타나는 1의 수이고 m이 문자열에 나타나는 0의 수라고 가정합니다.
이진 문자열에서 동일하지 않은 문자가 있는 인덱스의 문자 쌍을 교환하여 문자열이 회문 문자열을 형성할 수 있는지 확인합니다.
Sep 02, 2023 pm 08:09 PM
문제 설명 문자열 str과 이진 문자열 B가 있습니다. 두 문자열의 길이는 N과 같습니다. 문자열 B에서 동일하지 않은 문자를 포함하는 인덱스 쌍에서 해당 문자를 여러 번 교환하여 문자열 str을 회문 문자열로 만들 수 있는지 확인해야 합니다. 예 예 입력 str='AAS' B='101' 출력 'YES' 설명의 중국어 번역은 다음과 같습니다. 설명 B[1]과 B[2]가 동일하지 않기 때문에 str[1]과 str[2]를 교환할 수 있습니다. . 최종 문자열은 'ASA'일 수 있습니다. str='AASS' B='1111'을 입력하고 'No'를 출력합니다. 설명의 중국어 번역은 다음과 같습니다. 문자열 회문을 만들 수 없다는 설명,
주어진 바이너리 문자열에서 동일한 길이의 부분 문자열을 선택하여 주어진 기능을 최대화하십시오.
Aug 28, 2023 am 09:49 AM
동일한 길이의 두 이진 문자열 str1과 str2가 주어지면 주어진 동일한 길이의 문자열에서 부분 문자열을 선택하여 주어진 함수 값을 최대화해야 합니다. 주어진 함수는 다음과 같습니다 - fun(str1,str2)=(len(substring))/(2^xor(sub1,sub2)). 여기서 len(substring)은 첫 번째 부분 문자열의 길이이고 xor(sub1,sub2)는 주어진 부분 문자열의 XOR입니다. 이는 이진 문자열이므로 가능합니다. 예:Input1:stringstr1=10110&stringstr2=11101Output:3은 다음을 보여줍니다.
(비어있지 않은 하위 문자열을 제거하여) 바이너리 문자열을 비운 후 0의 개수가 가장 적은 플레이어를 찾습니다.
Sep 16, 2023 am 10:21 AM
이 기사에서는 문자열 조작 및 게임 이론 분야와 관련된 흥미로운 문제인 "비어 있지 않은 부분 문자열을 제거하여 이진 문자열을 비우고 남은 0이 가장 적은 플레이어를 찾습니다"라는 흥미로운 문제에 대해 논의할 것입니다. 이 질문은 경쟁 게임에 바이너리 문자열을 사용하는 개념을 탐구합니다. 우리의 목표는 게임이 끝났을 때 0이 가장 적게 남은 플레이어를 찾는 것입니다. 우리는 이 문제를 논의하고, C++ 코드 구현을 제공하고, 예제를 통해 개념을 설명할 것입니다. 문제 설명 이해하기 두 명의 플레이어에게 이진 문자열이 주어지고 그들은 차례로 게임을 합니다. 매 턴마다 플레이어는 "1"이 하나 이상 포함된 비어 있지 않은 하위 문자열을 제거합니다. 문자열이 비어 있거나 문자열에 "1"이 없으면 게임이 종료됩니다. 행동을 취할 수 없는 플레이어는 게임에서 패배합니다. 임무는 마지막 0을 찾는 것입니다.
부분 문자열을 반복적으로 연결한 길이 N의 이진 문자열을 계산합니다.
Sep 07, 2023 am 10:13 AM
이 기사의 목적은 부분 문자열의 반복된 연결로 형성된 길이 N의 이진 문자열 수를 계산하는 프로그램을 구현하는 것입니다. 목표는 주어진 텍스트의 개별 하위 문자열을 반복적으로 연결하여 길이 N의 이진 문자열을 얼마나 많이 생성할 수 있는지 결정하는 것입니다. 여기서 N은 양의 정수입니다. 문제 설명 부분 문자열을 반복적으로 연결하는 길이 N의 이진 문자열 수를 세는 프로그램을 구현하십시오. 예 예 1 입력, N = 3 출력: 2 설명의 중국어 번역은 다음과 같습니다. 설명 다음은 길이 N = 3의 실행 가능한 이진 문자열을 나열하며, 여기서 하위 문자열은 반복적으로 연결됩니다. "000":하위 문자열
