专栏首页量化投资与机器学习终极一战:为了编程面试!

终极一战:为了编程面试!

前言

我是如何在一份全职工作中每天练习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—

本文分享自微信公众号 - 量化投资与机器学习(Lhtz_Jqxx),作者:QIML编辑部

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 另类Alpha:基于供应链数据的量化因子挖掘

    在量化交易中,如何获取适当的数据用于开发和测试交易策略,往往是投资者面临的难题。随着技术的发展,获取大数据的成本不断降低,但历史价格等传统数据已完全无法满足投资...

    量化投资与机器学习微信公众号
  • 【量化精品】通过LSTM神经网络进行时序预测针对股票市场(附Python源码)

    阅读原文 Neural Networks these days are the “go to” thing when talking about new fad...

    量化投资与机器学习微信公众号
  • 从金融时序到图像识别:基于深度CNN的股票量化策略(附代码)

    本文基于一篇题为《Algorithmic Financial Trading with Deep Convolutional Neural Networks: ...

    量化投资与机器学习微信公众号
  • Code Forces 650 C Table Compression(并查集)

    C. Table Compression time limit per test4 seconds memory limit per test256 m...

    ShenduCC
  • ZOJ 3607 Lazier Salesgirl (枚举)

    Lazier Salesgirl Time Limit: 2 Seconds Memory Limit: 65536 KB Kochiya S...

    ShenduCC
  • 2017 Multi-University Training Contest - Team 9 1001&&HDU 6161 Big binary tree【树形dp+hash】

    Big binary tree Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65...

    Angel_Kitty
  • Codeforces Round #536 (Div. 2) D. Lunar New Year and a Wander(bfs)

    题目链接:http://codeforces.com/contest/1106/problem/D

    Ch_Zaqdt
  • 1250 Fibonacci数列

    时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 定义:f0=...

    attack
  • 贪心算法总结贪心算法基本思路算法实现实例分析参考

    贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。...

    致Great
  • 06-图2 Saving James Bond - Easy Version

    题目来源:http://pta.patest.cn/pta/test/18/exam/4/question/625 This time let us consi...

    llhthinker

扫码关注云+社区

领取腾讯云代金券