70 개의 면접 흔 한 알고리즘 문제

10648 단어 CS 대학원 재시험
  • 문자열 의 순환 이동 세 번 뒤 집기
  • 문자열 의 해시 표 포함
  • 문자열 전체 배열 nextpermutation 알고리즘
  • 문자열 의 모든 조합 dfs
  • 문자열 회전 정수 stoi (), stol (), 경계 주의
  • 답장 판단: 문자열 이 답장 문자열 인지 아 닌 지 를 판단 하기 위해 양쪽 에서 중간 으로 스 캔
  • 링크 의 답장 여 부 를 판단 한다 (1) 빠 르 고 느 린 포인터 가 중심 점 을 찾는다 (2) 뒤 집기 후반 부분 (3) 두 개의 링크 를 옮 겨 다 니 며 비교 한다
  • 스 택 이 스 택 에 되 돌아 온 후에 스 택 에 들 어 갈 지 여 부 를 판단 하고 원래 문자열 과 똑 같은 지 비교 합 니 다
  • 최 장 답장 하위 문자열 manacher 알고리즘: (1) 전처리 (2) id 기록 최 원 답장 문자열 중심, mx 기록 최 원 답장 문자열 위치 확장 KMP: 원래 문자열 의 접미사 와 뒤 집기 문자열 의 접두사 의 최 장 공공 접두사 비교
  • 최 장 중복 하위 문자열 next [] 배열 의 최대 값
  • 최 장 공공 하위 문자열 동적 계획: 확장 KMP:
  • 가장 작은 K 개 수 를 찾 아 정렬 하고 최소 더미, partition 알고리즘
  • 정렬 된 배열 을 찾 고 정 해진 값 의 두 수 를 찾 으 면 두 바늘 로 두 머리 를 스 캔 할 수 있 습 니 다
  • 이 진 트 리 와 정 해진 값 으로 뿌리 노드 에서 출발 하 는 모든 경로 dfs + 가지치기
  • 를 찾 습 니 다.
  • 정 해진 값 을 찾 는 네 개의 수 매 거 + 2 점
  • 찾 거나 정 해진 값 의 여러 개 수 를 01 가방 문제 로 전환시킨다
  • 최대 연속 서브 배열 과 동적 계획: maxSum 기록 최대 화, curSum 기록 현재 화, curSum 이 0 보다 적 을 때 현재 요소 값 으로 초기 화
  • 최대 서브 매트릭스 와 동적 계획: 매 거 진 i 줄 에서 j 줄 범위, 유사 최대 연속 서브 배열 과, 이동 범위 내 에서 0 열 에서 k 열 까지 의 총화 curSum 을 구하 고, curSum 이 0 보다 적 을 때 현재 열 과
  • 로 초기 화 합 니 다.
  • 계단 뛰 어 넘 기 문제 피 보 나치 추이
  • 동전 을 바 꾸 는 문제: 100 원, 1 원, 2 원, 5 원, 10 원 짜 리 동전, 몇 가지 방법 으로 가방 을 완전히 바 꾸 는 문제
  • 짝수 정렬: 홀수 는 앞 에 놓 고 짝수 는 뒤에 놓 으 면 상대 적 인 순서 로 두 바늘
  • 을 바 꿀 수 있 습 니 다.
  • 네덜란드 국기 문제: 배열 은 0, 1, 2 만 포함 하고 0 줄 의 맨 앞, 1 줄 의 중간, 2 줄 의 마지막 세 지침, 비교 빠 른 배열 알고리즘
  • 을 요구한다.
  • 유일 하 게 중복 되 는 원소 양음 표기 법
  • 세 개 에 한 번 만 나타 나 는 수: 세 개 에 한 번 만 나타 나 고 나머지 수 는 모두 두 번 나타 나 이 세 개의 수 하 쉬
  • 를 찾 아 라.
  • 두 개 에 한 번 만 나타 나 는 수: 두 개의 수 는 한 번 만 나타 나 거나 홀수 번 만 나타 나 고 나머지 수 는 모두 두 번 (또는 짝수 번) 이 나타 나 며 이 두 개의 수 를 모두 다 르 거나 이 또는 1 비트 비트 에 따라 분류 한 다음 에 각각 다 르 거나
  • n 개 정수 중 1 이 나타 난 횟수 동적 계획 보존 결과
  • 주어진 것 과 가 까 운 몇 개의 마이너스 회전 정 수 를 찾 아 가방 문제 로 전환한다
  • 값 을 찾 고 정 하 는 연속 서브 배열 접두사 와 + 해시
  • 직사 도 에서 면적 이 가장 큰 사각형 류 비 를 찾 아 빗물 을 받 고 단조 로 운 스 택
  • 을 찾는다.
  • 문자열 에서 문자열 을 추출 합 니 다: n 개의 수, 하위 문자열 의 숫자 와 mod 3 = 0 의 문자열 추출 법
  • 을 구 합 니 다.
  • 한 열 수 에서 가능 한 한 적은 수 를 삭제 하여 배열 을 산맥 배열 의 동적 계획 으로 만 들 었 습 니 다. dp1 [i] 는 i 로 끝 나 는 최 장 스 트 링 길 이 를 표시 하고 dp2 [i] 는 i 로 시작 하 는 최 장 스 트 링 길이
  • 를 표시 합 니 다.
  • 파도 배열 에서 어떤 수의 확장 2 점 을 찾 습 니 다
  • 최 장 체감 서브 시퀀스 소박 dp: 대기 열 최적화:
  • 숫자 맵: 아래 줄 의 모든 수 는 위 줄 의 대응 숫자 가 아래 줄 에 나타 난 횟수 입 니 다.0: n - 4 회, 1: 2 회, 2: 1 회, n - 4: 1 회
  • 배열 분할: 배열 의 길 이 는 n 이 고 m 로 나 누 며 각 부분의 합 이 같 고 m 의 최대 치 를 요구한다.2 점 찾기
  • 회전 배열 의 최소 값 동 구성 문자열 의 최소 표시
  • 계란 은 바 구 니 를 넣는다. n 개의 계란 은 m 개의 바구니 에 넣 고 바 구 니 는 비어 있 으 면 안 된다. n 보다 크 지 않 은 수량 을 만족 시 키 려 면 몇 개의 바구니 의 계란 총 수 를 사용 할 수 있다.조건 을 만족 시 키 는 모든 방 법 을 구하 다.dfs, 바구니 계란 수 증가, 작은 것 부터 큰 것 까지 모든 수 를 표시 할 수 있 도록
  • 배열 분열: n 개 요소 의 배열 로 두 그룹 으로 나 누 어 두 그룹의 합 차 를 최소 01 가방 문제
  • 두 정렬 배열 의 더 블 포인터
  • 를 합 친다.
  • 배열 의 등 과 문제: n 개 요소, m 개 를 취하 여 m 개 수의 합 을 다른 n - m 개 수의 가방 문제
  • 임무 의 분배: n 개의 임 무 는 n 개인 에 게 위임 되 고 모든 사람 이 하 는 서로 다른 임 무 는 cost [i] [j] 로 총 비용 이 가장 적은 분배 방식 을 요구한다.헝가리 알고리즘, 2 부 그림 의 완벽 한 일치
  • 사이트 간 의 거리: 인접 한 사이트 간 의 거 리 를 알 고 임 의 사이트 간 의 거리 접두사 와
  • 를 효율적으로 구 합 니 다.
  • 배열 의 역순 대 개 수 를 병합 하여 정렬 파생: 트 리 배열: 먼저 분 산 된 다음 에 각 수 에 대해 범위 내 접두사 와 를 구 한 다음 에 트 리 배열 에 이 수 를 추가 합 니 다
  • 격자 색칠 동적 계획
  • 계란 드 랍 문제 동적 계획 + 기억 화 검색 + 2 점: dp (K, N) = 1 + min (max (dp (K - 1, X - 1), dp (K, N - X) 가 X 층 에서 깨 지면 아래로 찾 습 니 다.X 층 의 알 이 깨 지지 않 으 면 위로 찾 아 라.
  • 통계 출현 횟수 가 가장 많은 데이터 hashmap, map 등
  • 억 행 에 달 하 는 데이터 의 빠 른 조회 B 트 리, B + 트 리
  • 이 진 트 리 노드 의 최근 공공 조상 (LCA) dfs 경로: 마지막 공공 요소 라인 트 리 비교: 예비 처리 + 조회
  • 이 진 트 리 노드 의 최대 거 리 를 두 번 dfs: 직접 재 귀:
  • 이 진 트 리 의 깊이 dfs
  • 나무 노드 의 합: 두 갈래 나 무 를 지정 합 니 다. 모든 노드 의 값 은 정수 입 니 다. 키 나 무 를 찾 아서 가장 큽 니 다.다음 순서 옮 겨 다 니 기:
  • O (1) 공간 은 이 진 트 리 Morris 의 역법 을 옮 겨 다 닌 다.
  • 행렬 이 증가 하 는 행렬 의 찾기 분 치 법: 대각선 2 분 에서 찾 은 다음 에 왼쪽 아래 와 오른쪽 위 두 행렬 에서 각각 포 지 셔 닝 법 을 찾 습 니 다. 오른쪽 상단 부터 target 보다 크 면 왼쪽으로, target 보다 작 으 면 아래로
  • 출현 횟수 가 절반 을 넘 는 수 동적 계획: curAns 와 curCnt, curAns 와 같 으 면 curCnt +;그렇지 않 으 면 curCnt –;curCnt 가 0 으로 줄 어 들 면 curAns 를 더 잘 합 니 다.

  • 55. 문자열 패턴 일치: KMP
    void getNxt() {
    	memset(nxt, 0, sizeof(nxt));
    	nxt[0] = -1;
    	int j = 0, k = -1;
    	while (j < n) {
    		if (k == -1 || str[k] == str[j]) {
    			j++, k++;
    			nxt[j] = k;
    		} else k = nxt[k];
    	}
    }
    
    int kmp(void) {
    	int cnt = 0;
    	getNxt();
    	int i = 0, j = 0;
    	while (i < n) {
    		if (j == -1 || T[i] == W[j]) i++, j++;
    		else j = nxt[j];
    		if (j >= m) j = nxt[j], cnt++;
    	}
    	return cnt;
    }
    
  • 최대 연속 곱 하기 서브 배열 의 동태 계획: 최대 치 mx 와 최소 치 mi 를 동시에 기록 하고 음 수 를 만나면 이들
  • 을 교환 합 니 다.
  • 문자열 편집 거리 (임의의 위치 삽입, 교체, 삭제) 동적 계획: dp [i] [j] 는 S [0i] 에서 T [0j] 까지 의 최 단 편집 거 리 를 표시 하면 dp [i] [j] = min {dp [i - 1] [j] + 1, S [i] 는 T [0 ~ j] 에 없습니다. dp [i - 1] [j - 1] + 1 / 0, S [i] 는 T [j] 에서 S [i] = T [j] 에서 0; dp [i] [j - 1] + 1, S [i] 는 T [0 ~ j - 1] 에서}
  • 격자 취 수 문제 동태 계획: 유사 탑 문제
  • 골패 문제 (1 * 2 골패 평평 하 게 깔 기) 경계 dp
  • 타이어 나무
  • 링크 의 마지막 n 번 째 요소 의 선후 지침
  • 을 찾 았 다.
  • 두 개의 무 환 링크 가 교차 하 는 지 여 부 를 판단 한다. 꼬리 노드 가 같 는 지 판단 하면 첫 번 째 교점 을 찾 을 수 있다. 길이 에 따라 선후 지침
  • 을 설치한다.
  • 링크 에 고리 가 있 는 지 판단 합 니 다. 빠 르 고 느 린 지침 은 링 의 출발점 을 찾 습 니 다. 만 남 점 과 출발점 에 동기 화 지침 을 두 개 더 설치 하면 반드시 입구 점 에서 만 납 니 다
  • 전체 0 행렬: 행렬 의 특정한 요 소 를 일시 적 으로 추가 하면 그 주변의 네 가지 요소 도 하 나 를 추가 할 수 있 습 니 다. 지 정 된 정수 행렬 스위치 문 제 를 얻 을 수 있 습 니까? 첫 번 째 줄 의 상 태 를 매 거 진 다음 에 모든 줄 은 이전 줄 과 관련 이 있 습 니 다
  • 디자인 min 스 택: 한 스 택 저장 값, 한 스 택 저장 최소 값
  • 두 개의 스 택 이 대기 열 을 실현 합 니 다. 한 스 택 은 입 주 를 책임 지고 한 스 택 은 입 주 를 책임 집 니 다
  • 8 황후 문제: dfs
  • 최소 생 성 트 리: prim, kruskal
  • 개미 기어 오 르 기: 탄성 충돌 이 타임 슬립 으로 바 뀌 었 다
  • 트랙 경주 마: 5 개의 트랙, 각 트랙 은 최대 한 마리 의 말 을 달리 고 25 마리 의 말 은 최소 몇 번 경 기 를 하면 가장 빠 른 5 마리 의 말 을 비교 할 수 있 습 니까?먼저 적어도 5 + 1 번 경 기 를 해서 양 씨 행렬 을 얻어 낸 다음 에 구체 적 인 상황 을 구체 적 으로 분석 해 야 한다.
  • 좋은 웹페이지 즐겨찾기