면접 알고리즘: 링크 에 고리 가 있 는 지 여 부 를 어떻게 판단 합 니까?
방법 1: 이중 순서 로 옮 겨 다 니 기
첫 번 째 노드 부터 한 번 에 하나의 체인 표를 옮 겨 다 니 는 모든 노드.새로운 노드 를 옮 겨 다 니 지 않 고 새로운 노드 이전의 모든 노드 를 처음부터 검사 하고 새로운 노드 와 이전의 모든 노드 를 한 번 에 비교 하면 이전의 특정한 노드 와 같다 는 것 을 발견 하면 이 노드 가 두 번 옮 겨 다 니 는 것 을 설명 하고 링 을 설명 한다.단점: 시간 복잡 도 O (n ^ 2) 가 너무 높 고 공간 복잡 도 O (1)
코드 는 다음 과 같다.
0
1
2
3
4
5
///Swift
public class Node {
var data: Int
var next: Node?
init(_ data: Int) {
self.data = data;
}
}
func nodeIsRing(_ node: Node) -> Bool {
var nextNode = node.next
while nextNode != nil {
var proNode = node
while (nextNode! !== proNode) {
if proNode === nextNode?.next {
return true // true
}
proNode = proNode.next!
}
nextNode = nextNode?.next//
}
return false;
}
방법 2: 이전의 옮 겨 다 니 는 결 과 를 저장 합 니 다.
앞 에 널 려 있 는 데 이 터 를 모두 저장 하고 새로운 노드 와 이전의 대 비 는 똑 같은 설명 이 있 으 면 고리 가 있다 는 것 이다.해시 표, 코드 약간... 시간 복잡 도: O (n) 공간 복잡 도 O (n)
방법 3: 링 트랙, 속도 가 같 지 않 으 면 두 사람 은 반드시 만 날 것 이다.
링 인 이상 우 리 는 두 개의 변 수 를 사용 하고 하 나 는 증가폭 이 1 이 며 하 나 는 증가폭 이 2 라면 두 개의 지침 은 반드시 만 날 것 이다.고리 가 아니 었 다 면 영원히 만 나 지 못 했 을 것 이다.
시간 복잡 도: O (n) 공간 복잡 도 역시 O (1)
코드
func isNodeSpeed(_ node: Node) -> Bool {
var fastNode: Node? = node
var slowNode: Node? = node
while true {
fastNode = fastNode?.next?.next
slowNode = slowNode?.next
if fastNode == nil && slowNode == nil {
return false //
}
if fastNode != nil && slowNode != nil && fastNode === slowNode {
return true //
}
}
}
확장: 어떻게 출입 환 점 을 구 합 니까?링 길이?
아래 댓 글 환영 합 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
View의 레이아웃 방법을 AutoLayout에서 따뜻한 손 계산으로 하면 성능이 9.26배로 된 이야기이 기사는 의 15 일째 기사입니다. 어제는 에서 이었습니다. 손 계산을 권하는 의도는 없고, 특수한 상황하에서 계측한 내용입니다 화면 높이의 10 배 정도의 contentView가있는 UIScrollView 레이아...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
