전단 면접 에서 흔히 볼 수 있 는 데이터 구조 문제
4585 단어 막 이의 면접
1. 링크 에 고리 가 있 는 지 없 는 지 어떻게 판단 합 니까?
사고: 빠 르 고 느 린 지침, 하 나 는 빨리 가 고 하 나 는 느리게 간다. 그러면 몇 걸음 후에 빠 르 고 느 린 지침 이 만 날 것 이다.
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
var hasCycle = function(head) {
if( head == null || head.next == null ){
return false;
}
var slow = head; //slow pointer moves one step forward
var fast = head; //fast pointer moves two steps forward
while( true ){
if( fast.next == null || fast.next.next == null ){
return false;
}
slow = slow.next;
fast = fast.next.next;
if( fast === slow ){
return true;
}
}
};
2. 링크 의 반전 (재 귀 법)
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if(head == null || head.next == null )
return head;
var nextNode = head.next;
var newHead = reverseList(nextNode);
nextNode.next = head;
head.next = null;
return newHead;
};
3. 링크 의 특정한 노드 삭제
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
if (head == null) return null;
var node = head;
while(node != null && node.next != null){
if(node.next.val == val){
node.next = node.next.next;
}
else{
node = node.next;
}
}
return head.val == val ? head.next : head;
};
2. 창고 와 대열
1. 두 개의 스 택 으로 하나의 대기 열 을 실현 합 니 다.
우 리 는 현재 두 개의 스 택 이 있 는데, 하나의 직관 적 인 생각 은 데 이 터 를 두 개의 스 택 사이 에서 이동 시 켜 선진 적 인 목적 을 달성 할 수 있 도록 하 는 것 이다.이 두 스 택 이 스 택 A 와 스 택 B 라 고 가정 하면 스 택 A 는 enqueue 의 데 이 터 를 받 고 스 택 B 는 dequeue 데 이 터 를 사용 하 며 구체 적 인 알고리즘 은:
enqueue: (1) 스 택 A 에 데 이 터 를 직접 압축 합 니 다.
dequeue: (1) 스 택 B 가 비어 있 지 않 으 면 스 택 B 상단 의 데 이 터 를 팝 업 (2) 스 택 B 가 비어 있 으 면 스 택 A 의 모든 데 이 터 를 팝 업 하고 스 택 B 에 눌 러 서 스 택 B 상단 의 데 이 터 를 팝 업 합 니 다.
2. 두 개의 대기 열 로 스 택 실현
만약 에 우리 가 현재 대기 열 A 와 대기 열 B 가 있다 고 가정 하면 직관 적 이기 때문에 직접 알고리즘 에 올 라 갑 니 다.
push: (1) 요 소 를 대기 열 A 에 추가 합 니 다.
pop: (1) 대기 열 A 의 size 를 1 보다 클 때, 반복 적 으로 대기 열 A 의 요 소 를 대기 열 B (2) 로 이동 시 켜 대기 열 A 의 마지막 남 은 요 소 를 대기 열 에서 나 오고 결과 로 되 돌려 줍 니 다 (3) 대기 열 A 와 대기 열 B 의 이름 을 교환 합 니 다.