您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

LeetCode 高頻面試題總結：Top 10 經典演算法解析

編輯：關於C++

找實習一段時間，總結 LeetCode 上面試出現頻率較高的題目，持續更新中。

一、Two Sum

給無序陣列，輸出和為 k 的兩個數。
解題思路：先排序，再用雙指標分別指向頭尾，計算頭尾和 s，與 k 比較：s < k 頭指標後移，s > k 尾指標前移，直到找到。若頭尾相遇仍未找到則不存在。

public static void printK(int[] array, int k) {
    if (array == null || array.length <= 0) return;
    Arrays.sort(array);
    int start = 0, end = array.length - 1;
    while (start < end) {
        while (start < end && array[start] == array[start+1]) start++;
        while (start < end && array[end] == array[end-1]) end--;
        if (array[start] + array[end] == k) {
            System.out.println(start + " " + end);
            start++;
        } else if (array[start] + array[end] < k) {
            start++;
        } else {
            end--;
        }
    }
}

二、3Sum

從陣列找三個數使和為 0，輸出所有可能。
思路：排序後從第一位遍歷，如第一位為 1，在剩餘陣列中找和為 -1 的兩數（用 Two Sum 思路）。

public static void print3Num(int[] array, int k) {
    Arrays.sort(array);
    int length = array.length;
    for (int i = 0; i < length; i++) {
        if (i < length-1 && array[i] == array[i+1]) continue;
        int target = k - array[i];
        int start = i+1, end = length-1;
        while (start < end) {
            if (array[start] + array[end] == target) {
                System.out.println(array[i] + " " + array[start] + " " + array[end]);
                start++; end--;
                while (start < end && array[start] == array[start-1]) start++;
                while (start < end && array[end] == array[end+1]) end--;
            } else if (array[start] + array[end] < target) start++;
            else end--;
        }
    }
}

三、Climbing Stairs

n 級樓梯，一次爬 1 或 2 級，問爬法總數。典型費波那契數列。
思路：f(n) = f(n-1) + f(n-2)。

// 遞迴
public static int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return climbStairs(n-1) + climbStairs(n-2);
}
// 非遞迴
public static int climbStair(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int num1 = 1, num2 = 2, sum = 0;
    for (int i = 2; i < n; i++) {
        sum = num1 + num2;
        num1 = num2;
        num2 = sum;
    }
    return sum;
}

四、Merge Two Sorted Lists

合併兩個已排序鏈結串列。
思路：選較小節點作為新鏈表頭，比較兩鏈表節點值，較小者接在新鏈表尾，對應鏈表前移，直到一條遍歷完，將另一條剩餘部分接上。

public static ListNode merge(ListNode head1, ListNode head2) {
    if (head1 == null) return head2;
    if (head2 == null) return head1;
    ListNode head = null, tail = null;
    if (head1.val < head2.val) { head = tail = head1; head1 = head1.next; }
    else { head = tail = head2; head2 = head2.next; }
    while (head1 != null && head2 != null) {
        if (head1.val < head2.val) { tail.next = head1; head1 = head1.next; }
        else { tail.next = head2; head2 = head2.next; }
        tail = tail.next;
    }
    tail.next = (head1 != null) ? head1 : head2;
    return head;
}

五、Merge Sorted Array

將 nums2 合併到 nums1，nums1 長度 ≥ m+n。
思路：從尾部開始比較，大的放到 nums1 最後，對應指標前移，自然完成排序。

public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int index = m + n - 1, i = m - 1, j = n - 1;
    while (i >= 0 && j >= 0) {
        nums1[index--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
    }
    while (j >= 0) nums1[index--] = nums2[j--];
}

六、Valid Palindrome

驗證字串是否為回文，只看字母數字，忽略大小寫。
思路：雙指標頭尾向中間掃描，跳過非字母數字，比較字元（忽略大小寫）。

public static boolean isPalindrome(String s) {
    s = s.toLowerCase();
    int start = 0, end = s.length() - 1;
    while (start < end) {
        while (start < end && !Character.isLetterOrDigit(s.charAt(start))) start++;
        while (start < end && !Character.isLetterOrDigit(s.charAt(end))) end--;
        if (s.charAt(start) != s.charAt(end)) return false;
        start++; end--;
    }
    return true;
}

七、Valid Parentheses

驗證括號是否正常閉合。
思路：用堆疊，左括號入堆，右括號出堆比對，最後堆疊為空且無誤配則正確。

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

八、Pow(x, n)

實現 Pow(x, n) 乘方函式。
思路：處理負數指數與負數底數，利用已計算值減少運算（快速冪）。

public static double pow(double x, int n) {
    if (n == 0) return 1;
    if (n < 0) { x = 1/x; n = -n; }
    double result = 1;
    while (n > 0) {
        if ((n & 1) == 1) result *= x;
        x *= x;
        n >>= 1;
    }
    return result;
}

九、Generate Parentheses

給整數 n，輸出 n 對括號所有合法組合。
思路：遞迴生成，left 為剩餘左括號數，right 為右括號數。若 left > 0 可加左括號；若 right > left 可加右括號。

public static List generateParenthesis(int n) {
    List res = new ArrayList<>();
    if (n <= 0) return res;
    backtrack(res, "", n, n);
    return res;
}
private static void backtrack(List res, String cur, int left, int right) {
    if (left == 0 && right == 0) { res.add(cur); return; }
    if (left > 0) backtrack(res, cur + "(", left-1, right);
    if (right > left) backtrack(res, cur + ")", left, right-1);
}

十、Validate Binary Search Tree

判斷二元樹是否為 BST。
思路一：中序遍歷，若非遞增則非 BST。
思路二：遞迴傳遞上下界，左子樹上界為根值，右子樹下界為根值。

// 思路二
public static boolean isValidBST(TreeNode root) {
    return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private static boolean valid(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return valid(node.left, min, node.val) && valid(node.right, node.val, max);
}

整理好累，其實 LeetCode 刷了不少，但常見筆試面試題就那幾類，個人覺得不會出太難。