终极一战：为了编程面试！

• 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—