終極一戰：為了編程面試！

• 2019 年 10 月 10 日
• 筆記

前言

我是如何在一份全職工作中每天練習12個以上的編程問題的？

我不是在解決編程問題，而是練習把問題映射到我已經解決的問題上。

過去常常讀一個問題，然後花幾分鐘把它映射到我以前見過的類似問題上。如果我可以映射它，我將只關注這個問題與父問題相比有哪些不同約束。如果這是一個新問題，那麼我會嘗試解決它。隨着時間的推移，我開發了一組問題模式，這些模式幫助我快速地將問題映射到一個已知的問題。

今天，公眾號帶領大家掌握這種思路和方法，會讓你更加得心應手，遊刃有餘！

二分法檢索樣本問題

二分法檢索（binary search）又稱折半檢索，二分法檢索的基本思想是設字典中的元素從小到大有序地存放在數組（array）中。

▍問題陳述：

查找給定Bitonic數組中的最大值。如果數組是單調遞增然後單調遞減的，則認為它是雙調的。單調遞增或遞減意味着對於數組中的任何索引 i，arr[i] != arr[i+1]。

▍解決方法：

Bitonic數組是一個排序數組，唯一的區別是它的第一部分按升序排序，第二部分按降序排序。我們可以用二分法檢索的變體來解決這個問題。記住，在二分法檢索中，我們有 start，end 和 middle，在每個步驟中，我們通過移動 start 或 end 來減少搜索空間。由於沒有兩個連續的數字是相同的（因為數組是單調遞增或遞減的），所以當我們計算二分法檢索的 middle 索引時，我們可以將索引 middle 和 middle+1 所指出的數字進行比較，以確定我們是在升序還是降序部分。所以：

1、如果 arr[middle] > arr[middle + 1]，處於bitonic數組的第二（降序）部分。因此，我們需要的數字可以在middle指出，也可以在middle之前指出。這意味着我們要做 end = middle。

2、如果 arr[middle] <= arr[middle + 1]，處於bitonic數組的第一個（升序）部分。因此，所需的數字將在middle之後。這意味着 start = middle + 1。

我們可以在 start == end 時中斷。由於上述兩點，start和end都指向bitonic數組的最大個數。

下面是解決這個問題的Java代碼：

class MaxInBitonicArray {      public static int findMax(int[] arr) {      int start = 0, end = arr.length - 1;      while (start < end) {        int mid = start + (end - start) / 2;        if (arr[mid] > arr[mid + 1]) {          end = mid;        } else {          start = mid + 1;        }      }        // at the end of the while loop, 'start == end'      return arr[start];    }      public static void main(String[] args) {      System.out.println(MaxInBitonicArray.findMax(new int[] { 1, 3, 8, 12, 4, 2 }));      System.out.println(MaxInBitonicArray.findMax(new int[] { 3, 8, 3, 1 }));      System.out.println(MaxInBitonicArray.findMax(new int[] { 1, 3, 8, 12 }));      System.out.println(MaxInBitonicArray.findMax(new int[] { 10, 9, 8 }));    }  }

雙指針（Two Pointers）問題

▍問題陳述：

給定一個有序數組和一個目標值，在數組中找到一對和等於給定目標的數組。編寫一個函數來返回這兩個數字的索引，使它們加起來等於給定的目標值。

▍解決方法：

由於給定的數組已經排序，一個蠻力解決方案可能是遍曆數組，每次取一個數字，然後通過二分法檢索查找第二個數字。該算法的時間複雜度為O(N*logN)，我們能做得更好嗎?

我們可以遵循雙指針（Two Pointers）的方法。從一個指向數組開頭的指針和另一個指向數組末尾的指針開始。在每一步中，我們都將看到兩個指針所指向的數字加起來是否等於目標和。如果他們找到了，那我們也就得到了這個數。否則，我們將做兩件事之的一件：

1、如果兩個指針所指向的兩個數的和大於目標和，那麼我們需要一對和小的數。所以，為了嘗試更多的對，我們可以減少末端指針。

2、如果兩個指針所指向的兩個數字的和小於目標和，這意味着我們需要一個和更大的對。所以，為了嘗試更多對，我們可以增加開始指針。

下圖是對這個算法的可視化：

代碼如下：

class PairWithTargetSum {      public static int[] search(int[] arr, int targetSum) {      int left = 0, right = arr.length - 1;      while (left < right) {        // comparing the sum of two numbers to the 'targetSum' can cause integer overflow        // so, we will try to find a target difference instead        int targetDiff = targetSum - arr[left];        if (targetDiff == arr[right])          return new int[] { left, right }; // found the pair          if (targetDiff > arr[right])          left++; // we need a pair with a bigger sum        else          right--; // we need a pair with a smaller sum      }      return new int[] { -1, -1 };    }      public static void main(String[] args) {      int[] result = PairWithTargetSum.search(new int[] { 1, 2, 3, 4, 6 }, 6);      System.out.println("Pair with target sum: [" + result[0] + ", " + result[1] + "]");      result = PairWithTargetSum.search(new int[] { 2, 5, 9, 11 }, 11);      System.out.println("Pair with target sum: [" + result[0] + ", " + result[1] + "]");    }  }

樣本問題

▍問題陳述：

給定一個二維平面上的點數組，找出離原點最近的K點。

▍解決方法：

點 P(x,y) 到原點的歐氏距離可由下式計算：

我們可以使用最大堆（Max Heap）來找到離原點最近的K點。我們可以從堆中的K點開始。在遍歷其餘點時，如果一個點（比如P）比Max Heap的頂點更接近原點，那麼我們將從堆中刪除頂點，並添加P，始終保持堆中最近的點。

代碼如下：

import java.util.*;    class Point {    int x;    int y;      public Point(int x, int y) {      this.x = x;      this.y = y;    }      public int distFromOrigin() {      // ignoring sqrt      return (x * x) + (y * y);    }  }    class KClosestPointsToOrigin {      public static List<Point> findClosestPoints(Point[] points, int k) {      PriorityQueue<Point> maxHeap = new PriorityQueue<>(                (p1, p2) -> p2.distFromOrigin() - p1.distFromOrigin());      // put first 'k' points in the max heap      for (int i = 0; i < k; i++)        maxHeap.add(points[i]);        // go through the remaining points of the input array, if a point is closer to      // the origin than the top point of the max-heap, remove the top point from      // heap and add the point from the input array      for (int i = k; i < points.length; i++) {        if (points[i].distFromOrigin() < maxHeap.peek().distFromOrigin()) {          maxHeap.poll();          maxHeap.add(points[i]);        }      }        // the heap has 'k' points closest to the origin, return them in a list      return new ArrayList<>(maxHeap);    }      public static void main(String[] args) {      Point[] points = new Point[] { new Point(1, 3), new Point(3, 4), new Point(2, -1) };      List<Point> result = KClosestPointsToOrigin.findClosestPoints(points, 2);      System.out.print("Here are the k points closest the origin: ");      for (Point p : result)        System.out.print("[" + p.x + " , " + p.y + "] ");    }  }

▍問題陳述：

給定一個具有不同元素的集合，找到它所有不同的子集。

要生成給定集合的所有子集，可以使用廣度優先搜索（Breadth-First Search ）方法。我們可以從一個空集開始，逐一遍歷所有數字，然後將它們添加到現有集中，創建新的子集。

廣度優先搜索（BFS）類似於二叉樹的層序遍歷算法，它的基本思想是：首先訪問起始頂點v，然後由v出發，依次訪問v的各個未被訪問過的鄰接頂點w1,w2,w3….wn，然後再依次訪問w1，w2,…,wi的所有未被訪問過的鄰接頂點，再從這些訪問過的頂點出發，再訪問它們所有未被訪問過的鄰接頂點….以此類推，直到途中所有的頂點都被訪問過為止。

▍解決方法：

讓我們用上面的例子來看看算法的每個步驟：

給定集合：[1,5,3]

1、從空集開始：[[]]；

2、將第一個數字(1)添加到所有現有子集，以創建新的子集：[[]，[1]]；

3、將第二個數字(5)添加到所有現有子集：[[]，[1]，[5]，[1,5]]；

4、將第三個數(3)添加到所有現有的子集：[[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]]。

以下是上述步驟的可視化表示：

代碼如下：

import java.util.*;    class Subsets {      public static List<List<Integer>> findSubsets(int[] nums) {      List<List<Integer>> subsets = new ArrayList<>();      // start by adding the empty subset      subsets.add(new ArrayList<>());      for (int currentNumber : nums) {        // we will take all existing subsets and insert the current number in them to        // create new subsets        int n = subsets.size();        for (int i = 0; i < n; i++) {          // create a new subset from the existing subset and          // insert the current element to it          List<Integer> set = new ArrayList<>(subsets.get(i));          set.add(currentNumber);          subsets.add(set);        }      }      return subsets;    }      public static void main(String[] args) {      List<List<Integer>> result = Subsets.findSubsets(new int[] { 1, 3 });      System.out.println("Here is the list of subsets: " + result);        result = Subsets.findSubsets(new int[] { 1, 5, 3 });      System.out.println("Here is the list of subsets: " + result);    }  }

▍問題陳述：

給定一個二叉樹和一個數字s，找出該樹是否有一個從根到葉的路徑，使得該路徑的所有節點值之和等於s。

當我們試圖搜索根到葉的路徑時，我們可以使用深度優先搜索（Depth First Search ）技術來解決這個問題。

要以DFS的方式遞歸遍歷二叉樹，我們可以從根開始，在每個步驟中執行兩個遞歸調用，一個用於左邊，一個用於右邊。

以下是解決二叉樹路徑和問題的步驟：

1、從樹的根開始DFS。

2、如果當前節點不是葉節點，做兩件事：

• a. 從給定的數字中減去當前節點的值，得到一個新的 S = S – node.value。
• b. 對當前節點的兩個子節點進行兩次遞歸調用，使用上一步計算的新編號。

3、在每一步中，查看當前被訪問的節點是否為葉節點，以及它的值是否等於給定數字 S。

4、如果當前節點是一個葉節點，但它的值不等於給定的數字S，則返回false。

代碼如下：

class TreeNode {    int val;    TreeNode left;    TreeNode right;      TreeNode(int x) {      val = x;    }  };    class TreePathSum {    public static boolean hasPath(TreeNode root, int sum) {      if (root == null)        return false;        // if current node is a leaf and its value is equal to the sum, we've found a path      if (root.val == sum && root.left == null && root.right == null)        return true;        // recursively call to traverse the left and right sub-tree      // return true if any of the two recursive call return true      return hasPath(root.left, sum - root.val) || hasPath(root.right, sum - root.val);    }      public static void main(String[] args) {      TreeNode root = new TreeNode(12);      root.left = new TreeNode(7);      root.right = new TreeNode(1);      root.left.left = new TreeNode(9);      root.right.left = new TreeNode(10);      root.right.right = new TreeNode(5);      System.out.println("Tree has path: " + TreePathSum.hasPath(root, 23));      System.out.println("Tree has path: " + TreePathSum.hasPath(root, 16));    }  }

遵循這些模式可以極大地幫助我節省編碼面試準備的時間！

—End—