java algorithms implementation

Java: 알고리즘 및 데이터 구조

알고리즘과 데이터 구조는 Java로 구현됩니다.

이것은 제가 학업과 직업 생활에서 구현한 알고리즘과 데이터 구조의 모음입니다. 코드는 최적화되지 않았지만 정확하고 읽기 쉽게 작성되었습니다. 알고리즘과 데이터 구조는 테스트되었으며, 별도의 언급이 없는 한 올바른 것으로 간주됩니다.

저스틴 웨더렐(Justin Wetherell)이 만든 것

• 질문이 있는 경우 다음을 사용하세요. http://groups.google.com/forum/#!forum/java-algorithms-implementation
• 구글: http://code.google.com/p/java-algorithms-implementation
• Github: http://github.com/phishman3579/java-algorithms-implementation
• 링크드인: http://www.linkedin.com/in/phishman3579
• 이메일: [email protected]
• 트위터: http://twitter.com/phishman3579

기부로 나를 응원해주세요

구현된 내용:

목차

• 데이터 구조
• 수학
• 숫자
• 그래프
• 찾다
• 시퀀스
• 정렬
• 문자열 함수

데이터 구조

• AVL 트리
• B-트리
• 바이너리 힙(배열 또는 트리로 지원)
• 이진 검색 트리
• Compact Suffix Trie(Patricia Trie 지원)
• 서로소 집합
• 펜윅 트리{이진 인덱스 트리(BIT)}
• 그래프
  • 방향이 지정되지 않음
  • 감독 (디그래프)
• HAMT(해시 배열 매핑 트라이)
• 해시 맵(연관 배열)
• 간격 트리
• 암시적 키 트랩
• KD 트리(k차원 트리 또는 kd 트리)
• 목록 [배열 또는 연결 목록으로 지원됨]
• LCP 배열(가장 긴 공통 접두사) [접미사 배열로 지원됨]
• 행렬
• 패트리샤 트리
• 쿼드 트리(Point-Region 또는 MX-CIF)
• 대기열 [배열 또는 연결 목록으로 지원됨]
• Radix Trie(연관 배열) [Patricia Trie 지원]
• 레드-블랙 트리
• 세그먼트 트리
• 건너뛰기 목록
• 스플레이 트리
• 스택 [배열 또는 연결 목록으로 지원됨]
• 접미사 배열
• 접미사 트리(Ukkonen 알고리즘)
• 접미사 Trie [Trie로 뒷받침됨]
• 삼항 검색 트리
• 함정
• 나무
• 트리 맵(연관 배열) [AVL 트리로 지원됨]
• 트라이
• Trie Map(연관 배열) [Trie에 의해 지원됨]

수학

• 거리
  • 체비쇼프
  • 유클리드
• 분할
  • 루프를 사용하여
  • 재귀를 사용하여
  • 교대와 곱셈을 사용하여
  • 교대만 사용
  • 로그를 사용하여
• 곱셈
  • 루프를 사용하여
  • 재귀를 사용하여
  • 교대만 사용
  • 로그 사용
  • 고속 푸리에 변환
• 지수화
  • 재귀 지수화
  • 빠른 재귀 지수화
  • 빠른 모듈 재귀 지수화
• 소수
  • 소수이다
  • 소인수분해
  • 에라토스테네스의 체
  • 밀러-라빈 테스트
  • 공동소(상대소, 상호소)
  • 최대공약수
    • 유클리드 알고리즘을 사용하여
    • 재귀를 사용하여
• 순열
  • 문자열
  • 숫자
• 모듈러 연산
  • 추가하다
  • 덜다
  • 곱하다
  • 나누다
  • 힘
• 배낭
• 라머 더글라스 퍼커

숫자

• 정수
  • 바이너리 문자열로
    • 나누기 및 모듈러스 사용
    • 오른쪽 시프트와 모듈러스 사용
    • BigDecimal 사용
    • 나누기 및 이중 사용
  • 2의 거듭제곱이다
    • 루프를 사용하여
    • 재귀를 사용하여
    • 로그를 사용하여
    • 비트를 사용하여
  • 영어로(예: 1은 "one"을 반환함)
• 롱
  • 바이너리 문자열로
    • 나누기 및 모듈러스 사용
    • 오른쪽 시프트와 모듈러스 사용
    • BigDecimal 사용
• 복잡한
  • 덧셈
  • 빼기
  • 곱셈
  • 절대값
  • 극값

그래프

• 시작 정점에서 그래프의 최단 경로 찾기
  • Dijkstra 알고리즘(음수가 아닌 가중치 그래프)
  • Bellman-Ford 알고리즘(음수 및 양수 가중치 그래프)
• 최소 스패닝 트리 찾기
  • Prim(무방향 그래프)
  • 크루스칼(무방향 그래프)
• 모든 쌍의 최단 경로 찾기
  • Johnsons 알고리즘(음수 및 양수 가중치 그래프)
  • Floyd-Warshall(음수 및 양수 가중치 그래프)
• 사이클 감지
  • 방문한 정점을 추적하면서 깊이 우선 검색
  • 연결된 구성요소
• 토폴로지 정렬
• A* 경로 찾기 알고리즘
• 최대 유량
  • 푸시 라벨 재지정
• 그래프 순회
  • 깊이 우선 순회
  • 너비 우선 순회
• 에드먼즈 카프
• 어울리는
  • 터보 매칭
• 나무의 가장 낮은 공통 조상

찾다

• 배열의 값 인덱스 가져오기
  • 선의
  • 빠른 선택
  • 바이너리 [정렬된 배열 입력 전용]
  • 하한 [정렬된 배열 입력 전용]
  • 상한 [정렬된 배열 입력만 해당]
  • 최적화된 바이너리(임계값까지 바이너리 이후 선형) [정렬된 배열 입력만]
  • 보간 [정렬된 배열 입력 전용]

시퀀스

• 가장 긴 공통 부분 수열 찾기(동적 계획법)
• 가장 긴 증가 부분 수열 찾기(동적 계획법)
• 시퀀스에서 하위 시퀀스가 ​​발생하는 횟수 찾기(동적 프로그래밍)
• 피보나치 수열에서 i번째 요소 찾기
  • 루프를 사용하여
  • 재귀를 사용하여
  • 행렬 곱셈 사용
  • Binet의 공식을 이용하여
• 시퀀스에 있는 모든 요소의 총계 찾기(산술 진행)
  • 루프를 사용하여
  • 삼각수를 사용하여
• 연속 하위 배열의 최대 합(Kadane 알고리즘)
• 가장 긴 회문 부분 수열(동적 계획법)

정렬

• 미국 국기 정렬
• 버블정렬
• 계산 정렬(정수만 해당)
• 힙 정렬
• 삽입 정렬
• 병합 정렬
• 빠른 정렬
• 기수 정렬(정수만 해당)
• 쉘 정렬

문자열 함수

문자열 함수

• 문자열의 역방향 문자
  • 추가 저장소(String 또는 StringBuilder) 사용
  • 내부 스왑 사용
  • 내부 XOR 사용
• 문자열의 단어 반전
  • 문자 교환 및 추가 저장소 사용(StringBuilder)
  • StringTokenizer 및 추가 (문자열) 사용
  • Split() 메서드 및 추가 저장소(StringBuilder 및 String[]) 사용
  • 내부 스왑 사용
• 회문인가
  • 추가 저장소 사용(StringBuilder)
  • 내부 대칭 요소 비교 사용
• 문자열의 문자 하위 집합
• 편집(Levenshtein) 두 문자열의 거리(재귀, 반복)

Manacher의 알고리즘(가장 긴 회문 찾기)

KMP(Knuth-Morris-Pratt) 알고리즘 - 각 접두사의 최대 접두사-접미사 길이

문자열 회전

• 사전순으로 최소 문자열 회전 찾기
• 사전순으로 최대 문자열 회전 찾기