면접 복습 - 안 드 로 이 드 엔지니어 의 알고리즘 기초

체인 테이블
1. 링크 의 데이터 구조

static class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

2. 링크 의 node 노드 삭제

/**
 *      node  
 *
 * @param head    
 * @param node node  
 * @return    
 */
static Node delete(Node head, Node node) {
    //   
    if (node.next == null) {
        while (head.next != node) {
            head = head.next;
        }
        head.next = null;
    }
    //   
    else if (head == node) {
        head = null;
    }
    //    
    else {
        Node q = node.next;
        node.next = q.next;
        node.data = q.data;
    }
    return head;
}

1. 방식 1: 링크 에서 지정 한 값 의 노드 를 삭제 합 니 다.

/**
 *    ：           
 *
 * @param head    
 * @param num     
 * @return    
 */
static Node delete(Node head, int num) {
    Stack stack = new Stack<>();
    //  
    while (head != null) {
        if (head.data != num) {
            stack.push(head);
        }
        head = head.next;
    }
    //     
    while (!stack.isEmpty()) {
        stack.peek().next = head;
        head = stack.pop();
    }
    return head;
}

2. 방식 2: 링크 에서 지정 한 값 의 노드 를 삭제 합 니 다.

/**
 *    ：           
 *
 * @param head    
 * @param num     
 * @return    
 */
static Node remove(Node head, int num) {
    //     
    while (head != null) {
        if (head.data != num) {
            break;
        }
        head = head.next;
    }
    //     
    Node pre = head;
    Node cur = head;
    //    ，        
    while (cur != null) {
        if (cur.data != num) {
            pre = cur;
        } else {
            pre.next = cur.next;
        }
        cur = cur.next;
    }
    return head;
}

3. 링크 에서 중복 되 지 않 는 값 삭제

/**
 *           
 *
 * @param head    
 * @return    
 */
static Node deleteDuplication(Node head) {
    //   
    if (head == null) {
        return null;
    }
    HashSet set = new HashSet<>();
    //          
    set.add(head.data);
    //     
    Node per = head;
    Node cur = head.next;
    //    ，        
    while (cur != null) {
        if (set.contains(cur.data)) {
            per.next = cur.next;
        } else {
            set.add(cur.data);
            per = cur;
        }
        cur = cur.next;
    }
    return head;
}

4. 두 개의 링크 를 더 하 다.

/**
 *      ， 1-5-8 + 3-5-1   ：5-0-9
 *
 * @param head1   1   
 * @param head2   2   
 * @return         
 */
static Node add(Node head1, Node head2) {
    Stack stack1 = new Stack<>();
    Stack stack2 = new Stack<>();
    while (head1 != null) {
        stack1.push(head1.data);
        head1 = head1.next;
    }
    while (head2 != null) {
        stack2.push(head2.data);
        head2 = head2.next;
    }
    int n1 = 0;//  1   
    int n2 = 0;//  2   
    int n = 0;//n = n1 + n2 + ca
    int ca = 0;//       

    Node node = null;//    
    Node pnode = null;//node       

    while (stack1.isEmpty() || stack2.isEmpty()) {
        n1 = stack1.isEmpty() ? 0 : stack1.pop();
        n2 = stack2.isEmpty() ? 0 : stack1.pop();
        n = n1 + n2 + ca;
        //     
        node = new Node(n % 10);
        node.next = pnode;
        pnode = node;
        //    
        ca = n / 10;
    }
    //        
    if (ca == 1) {
        pnode = node;
        node = new Node(n / 10);
        node.next = pnode;
    }
    return node;
}

5. 하나의 단일 체인 표 가 답문 구조 인지 판단 한다.

/**
 *               
 *
 * @param head    
 * @return
 */
static boolean isPalindrome(Node head) {
    if (head == null) {
        return false;
    }
    Stack stack = new Stack<>();
    Node cur = head;
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }
    while (head != null) {
        if (head.data != stack.pop().data) {
            return false;
        }
        head = head.next;
    }
    return true;
}

6. 단일 체인 테이블 의 마지막 K 번 째 노드 삭제

/**
 *         K   
 *
 * @param head    
 * @param k
 * @return
 */
static Node removeLastKthNdoe(Node head, int k) {
    if (k <= 0 || head == null) {
        return head;
    }
    //  k   
    Node p = head;
    for (int i = 0; i < k; i++) {
        if (p.next != null) {
            p = p.next;
        } else {
            //K     
            return head;
        }
    }
    //        
    Node q = head;
    while (p.next != null) {
        p = p.next;
        q = q.next;
    }
    //  
    q.next = q.next.next;
    return head;
}

창고.
1. 두 개의 스 택 시 뮬 레이 션 대기 열 을 사용 합 니 다.

/**
 *          
 */
class imitateQueue {

    Stack

2. 최소 함수 min () 을 포함 한 스 택 을 설계 합 니 다.

/**
 *        min()  
 */
class min {

    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    void push(int node) {
        stack.push(node);
        if (minStack.isEmpty() || node <= minStack.peek()) {
            minStack.push(node);
        }
    }

    void pop() {
        if (stack.isEmpty())
            return;
        int data = stack.peek();
        stack.pop();
        if (data == minStack.peek()) {
            minStack.pop();
        }
    }

    int min() {
        return minStack.peek();
    }
}

이 진 트 리
1. 이 진 트 리 의 데이터 구조

class TreeNode {
    TreeNode left;
    TreeNode right;
    int data;
}

2. 넓이 우선 옮 겨 다 니 기

/**
 *       
 *
 * @param root
 */
void levelTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    LinkedList queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode head = queue.removeFirst();
        System.out.print("data:" + head.data);
        if (head.left != null) {
            queue.add(head.left);
        }
        if (head.right != null) {
            queue.add(head.right);
        }
    }
}

3. 범위 우선 옮 겨 다 니 며 줄 번호 가 있 습 니 다.

/**
 *       ，     
 *
 * @param root
 * @return
 */
LinkedList levelTraversalWithLineNum(TreeNode root) {
    if (root == null) {
        return null;
    }
    LinkedList list = new LinkedList<>();
    Queue queue = new ArrayBlockingQueue<>(100);
    //            
    TreeNode last = root;
    //            
    TreeNode nLast = root;

    while (!queue.isEmpty()) {
        TreeNode cur = queue.poll();
        System.out.println("data:" + cur.data);
        //   
        list.add(cur);

        if (cur.left != null) {
            queue.add(cur.left);
            nLast = cur.left;
        }
        if (cur.right != null) {
            queue.add(cur.right);
            nLast = cur.right;
        }
        if (cur == last) {
            System.out.println("  ");
            last = nLast;
        }
    }
    return list;
}

4. 앞 순 서 를 옮 겨 다 닌 다.

/**
 *     （  ）
 *
 * @param root
 */
void preorderTraversalRec(TreeNode root) {
    if (root == null) {
        return;
    }
    System.out.println("data:" + root.data);
    preorderTraversal(root.left);
    preorderTraversal(root.right);
}

/**
 *     （  ）
 *
 * @param root
 */
void preorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack stack = new Stack<>();
    stack.add(root);

    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        System.out.print("data:" + cur.data);
        if (cur.right != null) {
            stack.add(cur.right);
        }
        if (cur.left != null) {
            stack.add(cur.left);
        }
    }
}

5. 중 서 를 옮 겨 다 닌 다.

/**
 *     （  ）
 *
 * @param root
 */
void inorderTraversalRec(TreeNode root) {
    if (root == null) {
        return;
    }
    preorderTraversal(root.left);
    System.out.println("data:" + root.data);
    preorderTraversal(root.right);
}

/**
 *     （  ）
 *
 * @param root
 */
void inorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack stack = new Stack<>();
    TreeNode cur = root;
    while (!stack.isEmpty() || cur != null) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            TreeNode node = stack.pop();
            System.out.println("data:" + node.data);
            cur = cur.right;
        }
    }
}

6. 후 서 를 옮 겨 다 닌 다.

/**
 *     （  ）
 *
 * @param root
 */
void postorderTraversalRec(TreeNode root) {
    if (root == null) {
        return;
    }
    preorderTraversal(root.left);
    preorderTraversal(root.right);
    System.out.println("data:" + root.data);
}

/**
 *     （  ）
 *
 * @param root
 */
void postorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack s = new Stack<>();
    Stack output = new Stack<>();
    s.push(root);

    while (!s.isEmpty()) {
        TreeNode cur = s.pop();
        output.push(cur);

        if (cur.left != null) {
            s.push(cur.left);
        }
        if (cur.right != null) {
            s.push(cur.right);
        }
    }

    while (!output.isEmpty()) {
        System.out.print("data:" + output.pop().data);
    }
}