1000 병 의 물 에서 독이 있 는 병 을 찾 아 냈 습 니 다. 독성 은 일주일 후에 발작 합 니 다. 일주일 동안 최소 몇 마리 의 쥐 가 필요 합 니까? 이 문 제 는 bit 위치 에 대한 응용 입 니 다. 1000 은 1024 에 가 깝 기 때문에 10 개의 bit 자리 가 필요 합 니 다. 병 에 번 호 를 매 겨 0 부터 999 까지 10 마리 의 쥐 가 필요 합 니 다.병 의 번 호 는 각각 00000, 00000 00000, 00001 00000, 00010 00000, 00011 00000, 00101 00000, 00111...11111, 00111 동시에 쥐 에 게 번 호 를 주 고 1, 2,... 10, 낮은 자리 부터 n 번 째 쥐 에 게 n 번 째 bit 가 1 병 에 들 어 있 는 회복 제 를 마 시 게 합 니 다.일주일 후 모든 쥐 가 발병 하지 않 았 다 면 첫 번 째 병 은 독이 있 었 고, 어떤 쥐 가 발병 했다 면 낮은 비트 에서 높 은 비트 위치 로 1 이 되 었 고, 다른 것 은 0 이 되 었 다.정수 가 되면 해당 숫자 는 독이 있 는 물약 의 번호 다.
단 어 를 지정 합 니 다. a. 단어 에서 알파벳 순 서 를 교환 하면 다른 단어 b 를 얻 을 수 있 습 니 다. b 는 a 의 형제 단어 로 정의 합 니 다. 예 를 들 어 단어 army 와 mary 는 서로 형제 단어 로 정의 합 니 다.현재 사전 을 정 하고 사용 자 는 단 어 를 입력 합 니 다. 어떻게 사전 에 따라 이 단어 에 어떤 형제 단어 가 있 는 지 찾 습 니까?시간 과 공간 효율 이 가능 한 한 높 아야 한다.해법 1: hash 사용맵 과 링크.먼저 키 를 정의 하여 형제 단어 가 같은 키 를 가지 게 하고 형제 가 아 닌 단어 가 다른 키 를 가지 게 합 니 다.예 를 들 어 단 어 를 알파벳 에 따라 작은 것 부터 큰 것 까지 정렬 한 후에 키 로 한다. 예 를 들 어 bad 의 키 는 abd 이 고 good 의 키 는 dgoo 이다.링크 를 사용 하여 모든 형제 단 어 를 연결 합 니 다. hashmap 의 key 는 단어의 key 이 고 value 는 링크 의 시작 주소 입 니 다.시작 할 때 사전 을 옮 겨 다 니 며 모든 단 어 를 key 에 따라 해당 하 는 링크 에 추가 합 니 다.형제 단 어 를 찾 으 려 면 이 단어의 키 만 가 져 와 hash맵 에서 해당 하 는 링크 를 찾 으 면 됩 니 다.이렇게 hash 만 들 기map 시 시간 복잡 도 는 O (n) 이 고 형제 단 어 를 찾 을 때 시간 복잡 도 는 O (1) 입 니 다.해법 2: 똑 같이 hash 사용맵 과 링크.모든 자 모 를 하나의 질 수 에 대응 한 다음 에 대응 하 는 질 수 를 곱 하고 얻 은 값 을 hash 로 한다. 그러면 형제 단어의 값 은 똑 같 고 서로 다른 단어의 질 수 를 곱 하면 반드시 다 를 것 이다.링크 를 사용 하여 모든 형제 단 어 를 연결 합 니 다. hashmap 의 key 는 단어의 질 수 를 곱 하고 value 는 링크 의 시작 주소 입 니 다.사용자 가 입력 한 단 어 를 계산 한 다음 hash 를 찾 아 링크 를 옮 겨 다 니 며 출력 하면 모든 형제 단 어 를 얻 을 수 있 습 니 다.이렇게 hash 만 들 기map 시 시간 복잡 도 는 O (n) 이 고 형제 단 어 를 찾 을 때 시간 복잡 도 는 O (1) 입 니 다.
두 배열 에 같은 숫자 가 있 는 지 판단 하려 면 먼저 미안 하 다 고 말 해 야 한다. 이 문 제 는 모호 하 게 말 하지만 두 방향 이 라 고 할 수 있다.즉, 주어진 두 배열 이 질서 가 있 는 지, 무질서 하면 이 문 제 를 해결 하 는 데 사용 되 는 시간 복잡 도 는 nlog (n) 이 고, 주어진 두 배열 이 질서 가 있다 면 해결 방법의 시간 복잡 도 는 O (n) 일 것 이다.다음은 두 가지 해법 을 제시 하 겠 습 니 다.(배열 이 질서 가 있다 고 가정 합 니 다. 순서 가 없 으 면 바로 빠 른 정렬 이나 정렬 으로 nlog (n) 에 정렬 하면 해결 할 수 있 기 때 문 입 니 다.첫 번 째 방법 은 반 으로 찾 는 것 이다. 첫 번 째 배열 에서 한 요 소 를 꺼 내 고 두 번 째 배열 에서 반 으로 찾 는 방법 을 사용 하 는 것 이다.이러한 순환 내 부 를 반 으로 접 고 찾 는 내장 은 총 시간 복잡 도 는 mlog (n) (m, n 은 각각 두 배열 의 길이) 여야 합 니 다.두 번 째 방법 은 첫 번 째 배열 과 두 번 째 배열 을 가리 키 는 두 개의 지침 을 설정 하 는 것 이다.가리 키 는 요 소 를 꺼 내 비교 합 니 다. 만약 에 ai < bj (배열 이 질서 가 있 기 때 문) 가 존재 한다 면 ak = bj 가 존재 한다 면 k 는 i 뒤에 있어 야 하기 때문에 i 는 1 을 더 해 야 합 니 다. 만약 에 i 가 1 을 더 한 후에 bj < a (i + 1) 가 존재 한다 면 a (i + 1) 와 같은 b 배열 의 요 소 는 bj 뒤에 있어 야 하기 때문에 j 는 1 을 더 해 야 합 니 다.ai = bj 를 찾 거나 존재 하지 않 거나 순환 이 끝 날 때 까지 순서대로 유추 합 니 다.이 알고리즘 의 시간 복잡 도 는 Om + n 이다. (m 와 n 은 각각 두 배열 의 길 이 를 가리킨다.)
한 배열 의 최대 요소 와 최소 요 소 를 동시에 찾 아 배열 a 를 지정 합 니 다. n 을 포함 하고 이 배열 의 최대 요소 와 최소 요 소 를 찾 습 니 다. 이 문 제 를 처음 봤 을 때 이 문 제 는 사고 성 이 없다 고 생각 했 습 니 다. 이 문 제 는 간단 하기 때문에 초기 최대 치 와 초기 최소 치 를 설정 한 다음 에 배열 을 순환 하여 비교 하 는 것 입 니 다.기껏해야 2 (n - 1) 의 시간 내 에 최대 치 와 최소 치 를 찾 을 수 있다.다음은 이 문 제 를 3 * (n / 2) 내 에 끝 낼 수 있 도록 분석 하 는 방법 을 제시 합 니 다.먼저 n 이 홀수 인지 짝수 인지 판정 해 야 한다. 홀수 라면 min = max = a [1] 를 가정 하고 배열 을 옮 겨 다 닌 다. 그러나 이때 매번 두 개의 숫자 를 취하 고 이 두 숫자 를 비교 하면 비교적 큰 값 과 max 를 비교 하고 작은 값 과 min 을 비교 해 야 한다.이렇게 순환 하면 (n - 1) / 2 또는 (n - 2) / 2 회 후에 끝나 고 이렇게 비교 하 는 횟수 는 매번 순환 할 때마다 세 번 비교 해 야 한다.이 방법 은 n 값 이 매우 작은 배열 에 있어 서 큰 영향 을 미 치지 않 지만 배열 의 n 값 이 매우 크다 면 그 시간 은 원래 의 4 분 의 1 에 해당 하 는 것 으로 줄 어 들 었 다.
길이 가 1 인 선분 은 무 작위 로 그 위 에서 두 가 지 를 선택 하고 선분 을 3 단 으로 나 누 어 이 3 개의 필드 가 삼각형 을 구성 할 수 있 는 확률 이 얼마 인지 물 었 다
.
x, y 의 수 치 를 좌표 축 에 놓 고 고려 하여 0 에서 1 까지 의 부분 을 고려한다.그 세 변 의 길 이 는 x, y - x, 1 - y 이다.만약 에 우리 가 선택 한 두 점 의 좌표 가 x 와 y (먼저 x < y) 라 고 가정 하면 삼각형 의 양쪽 과 세 번 째 변 보다 큰 성질 은 x + y - x > 1 - y x + 1 - y > y - x 1 - y + y - x > x 는 상기 부등식 에서 얻 을 수 있다. x < 0.5, 0.5 < y < x + 0.5 그리고 그림 을 그리 면 연합 확률 이 1 / 8 이라는 것 을 얻 을 수 있 습 니 다. 이 결 과 는 x < y 를 가설 할 때 얻 은 것 이 므 로 2 를 곱 하여 1 / 4 를 얻 는 것 을 잊 지 마 세 요.
싱글 체인 시트 의 반전
(1) 세 개의 변 수 를 설정 합 니 다. p, q, t 는 각각 세 개의 노드 를 가리 키 고 한 개의 체인 시 계 를 옮 겨 다 니 며 각 노드 의 지침 의 방향 을 바 꿉 니 다. 그러나 이 방법 은 매우 복잡 합 니 다. 뚜렷 한 사고 가 없 으 면 자신 을 어 지 럽 히 기 쉽 습 니 다.(2) 스 택 사용.링크 를 한 번 에 옮 겨 다 니 며 링크 의 각 노드 를 스 택 에 저장 한 다음 에 스 택 을 조작 할 수 있 습 니 다. 스 택 의 특성 이 후진 이 먼저 나 오 는 것 이기 때문에 이렇게 간단 하면 링크 를 반전 시 킬 수 있 습 니 다.(3) 머리 노드 를 다시 설정 하여 새로운 링크 를 대표 하 게 한 다음 에 주어진 링크 를 순서대로 옮 겨 다 니 며 한 노드 를 꺼 내 새로운 링크 의 시작 에 삽입 하면 이렇게 한 번 옮 겨 다 니 면서 링크 를 다시 만 들 었 고 예전 의 링크 의 반전 이다.
비트 조작 교환 두 수
void Swap(int &a, int &b)
{
if (a != b)
{
a ^= b;
b ^= a;
a ^= b;
}
}
2 진법 중 1 의 개수
통계 바 이 너 리 중 1 의 개 수 는 직접 자 리 를 옮 긴 다음 에 판단 할 수 있다. 물론 책 에서 순환 으로 자 리 를 옮 기 거나 시 계 를 먼저 치고 계산 해도 된다.본 고 는 효율 적 인 방법 을 상세 하 게 설명 한다.34520 의 경우 다음 네 단 계 를 통 해 2 진법 중 1 의 개 수 를 계산 할 수 있다.첫 번 째 단계: 두 명 씩 한 팀 으로 팀 내 높 고 낮 음 을 더 합 니 다. 10 00 01 10 11 01 10 00 -->01 00 01 01 10 01 01 00 두 번 째 단계: 4 위 당 1 조, 조 내 높낮이 추가 0100 0101 1001 0100 -->0001 0010 0011 0001 세 번 째 단계: 8 위 마다 1 조 이 고 팀 내 높 고 낮 음 을 더 합 니 다. 00010010 00110001 -->00000011 00000000 네 번 째 단계: 16 위 마다 한 조 이 고 조 내 높 고 낮 음 을 더 합 니 다. 00000011 00000100 -->0000000000011 이렇게 마지막 으로 얻 은 0000000000011 즉 7 즉 34520 바 이 너 리 중 1 의 수 입 니 다.앞에서 말 한 바 이 너 리 역순 과 같은 방법 으로 첫 번 째 단 계 를 실현 하 는 코드: x = (x & 0xAAAA) > > 1) + (x & 0x 5555);
어떻게 나무 한 그루 를 이 진 트 리 로 바 꿉 니까?
해답: 1. 노드 의 아 이 를 왼쪽 나무 에 놓는다.2. 노드 의 형 제 를 오른쪽 나무 에 놓는다.연장: 어떤 나무 든 이 진 트 리 로 표시 할 수 있 으 며, 어떤 이 진 트 리 도 나무 로 표시 할 수 있 는 것 은 아니다.그러면 나무 가 많 습 니까? 이 진 트 리 가 많 습 니까?1. 어떤 나무 든 이 진 트 리 라 고 표시 할 수 있 으 며, 위 와 같은 문 제 를 결합 하면 쉽게 이해 할 수 있다.2. 어떤 이 진 트 리 도 나무 라 고 표시 할 수 있 는 것 이 아니다. 뿌리 노드 가 오른쪽 나 무 를 포함 할 때 나무 라 고 표시 할 수 없다.3. 나무 가 많은 지 이 진 트 리 가 많은 지 문제: 이 진 트 리 도 나무의 일종 이다. 포함 관계 에 따라 나 무 는 이 진 트 리 를 포함 하고 나무 가 많다.
19 권 의 책 에서 다섯 권 을 선택 하고 이 다섯 권 이 서로 인접 하지 않도록 요구 하 는데 모두 몇 가지 방법 이 있 습 니까?
제목: 19 권 의 책 중에서 다섯 권 을 선택 하고 이 다섯 권 이 서로 인접 하지 않도록 요구 하 는 방법 은 모두 몇 가지 가 있 습 니까?해결 방안 1: 댐퍼 문제 - 삽입 법 은 현재 책장 에 14 권 의 책 이 놓 여 있다 고 가정 하면 나머지 5 권 의 책 을 공중 에 삽입 하면 된다.14 권 의 책 은 15 개 를 삽입 할 수 있 는 빈 공간 이 있 기 때문에 총 방법 은 C (15, 5) 이다.해결 방 아 2: 2 진 은 2 진 방식 으로 바 뀌 고 0 은 중국 을 선택 하고 1 은 선택 하지 않 았 음 을 나타 낸다.서로 인접 하지 말 라 는 취지 로 바 뀌 었 다.프로 그래 밍 이 가능 합 니 다.
질서 있 는 정수 배열 과 K 로 된 수의 대수
를 구하 십시오. 제목: 질서 있 는 정수 배열 과 K 로 된 수의 대 수 를 구 합 니 다.해결 방안: 두 개의 지침, 하 나 는 머리 에 있 고 하 나 는 꼬리 에 있다.크 면 -, 작 으 면 플러스.연장 제목: (1) 정수 배열 과 K 의 대 수 를 구하 십시오.먼저 정렬 하고 O (N * logN), 상기 알고리즘 에 따라 O (N) 를 찾 습 니 다.(2) 정수 배열 의 차이 가 K 인 수의 대 수 를 구한다.먼저 정렬, O (N * logN), 그 다음 에 두 개의 바늘 로 모두 머리 부터 시작 하고 하 나 는 먼저 하 나 를 먼저 한 다음 에 가 며, 작은 것 은 앞 지침 +, 큰 것 은 뒤 지침 +.배열 에 중복 요소 가 있다 면 처리 해 야 할 문 제 를 고려 해 야 한다.나 는 천 왕 개 지 호의 분할 선 이다. 참고:http://blog.csdn.net/yahohi
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
