OCI 面试经验分享：合并K个排序链表与括号平衡检测 | 面试代面, OA代做, 面试辅导

OCI 面试经验分享：合并K个排序链表与括号平衡检测 | 面试代面, OA代做, 面试辅导

在这次OCI的面试中，考官提出了两道编程题目，分别是合并K个排序链表和检测括号的平衡性。这些题目主要考察考生对数据结构的理解和操作能力，包括堆、链表、栈等基础结构。应对这些问题需要良好的逻辑思维和编程技巧。

如果你希望在类似的面试中取得优异表现，我们的代面服务可以帮助你提升算法理解和编程能力，确保你能够自信应对各类挑战，成功获得心仪的offer。

想要了解更多或获取我们的服务，欢迎添加微信 leetcode-king。

---

题目一：合并K个排序链表

Problem Description:

Given an array of k linked lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.

Example:

- Input: lists = [[1,4,5],[1,3,4],[2,6]]
- Output: [1,1,2,3,4,4,5,6]

Code:

import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class MergeKSortedLists {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);

        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (!minHeap.isEmpty()) {
            ListNode minNode = minHeap.poll();
            tail.next = minNode;
            tail = minNode;

            if (minNode.next != null) {
                minHeap.offer(minNode.next);
            }
        }

        return dummy.next;
    }

    public static void main(String[] args) {
        // Example usage
        ListNode[] lists = new ListNode[3];
        lists[0] = new ListNode(1);
        lists[0].next = new ListNode(4);
        lists[0].next.next = new ListNode(5);

        lists[1] = new ListNode(1);
        lists[1].next = new ListNode(3);
        lists[1].next.next = new ListNode(4);

        lists[2] = new ListNode(2);
        lists[2].next = new ListNode(6);

        MergeKSortedLists solution = new MergeKSortedLists();
        ListNode result = solution.mergeKLists(lists);

        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

---

题目二：检测括号平衡性

Problem Description:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example:

- Input: "([)]" -> Output: false
- Input: "({[]})" -> Output: true

Code:

import java.util.Stack;

public class ParenthesesBalance {

    public boolean isBalanced(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if (c == ')' && top != '(') return false;
                if (c == '}' && top != '{') return false;
                if (c == ']' && top != '[') return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        ParenthesesBalance solution = new ParenthesesBalance();
        System.out.println(solution.isBalanced("([)]")); // false
        System.out.println(solution.isBalanced("({[]})")); // true
    }
}