三月第四周

leetcode

关于便利mxn矩阵对角线的模板：核心是矩阵同一对角线的元素满足 i-j + n = k，其中 k 为常数属于【1，m+n-1】

class Solution:
  def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
      m, n = len(grid), len(grid[0])
      # 第一排在右上，最后一排在左下
      # 每排从左上到右下
      # 令 k=i-j+n，那么右上角 k=1，左下角 k=m+n-1
      for k in range(1, m + n):
          # 核心：计算 j 的最小值和最大值
          min_j = max(n - k, 0)  # i=0 的时候，j=n-k，但不能是负数
          max_j = min(m + n - 1 - k, n - 1)  # i=m-1 的时候，j=m+n-1-k，但不能超过 n-1
          a = [grid[k + j - n][j] for j in range(min_j, max_j + 1)]  # 根据 k 的定义得 i=k+j-n
          a.sort(reverse=min_j == 0)
          for j, val in zip(range(min_j, max_j + 1), a):
              grid[k + j - n][j] = val
      return grid

滴滴笔试和

滴滴算法笔试题目编程题

照明灯安装问题：给定一个整数数组表示一排位置，以及一个整数 k，表示要安装的照明灯数量。要求在这些位置上放置 k 个照明灯，使得任意两个照明灯之间的最小距离尽可能大，输出这个最大的最小距离。
黑白块路径问题：给定一个由 0 和 1 组成的二维网格，0 表示白色块，1 表示黑色块。从左上角 (0,0) 走到右下角 (n - 1, m - 1)，每次只能向右或向下移动，求经过黑色块数量最少的路径中黑色块的数量。
小青蛙走迷宫：给定一个迷宫地图，用二维数组表示，其中 0 表示可通行的路径，1 表示障碍物。小青蛙位于迷宫的起点，要走到终点，求小青蛙能否走出迷宫，如果能，输出最短路径长度；如果不能，输出 - 11。
末尾 0 的个数：给定一个正整数 n，计算 n!（n 的阶乘）结果中末尾 0 的个数1。

数据结构题

实现一个函数，计算二叉树中某一层的节点个数。
给定一个整数数组，使用快速排序算法对其进行排序。
设计一个数据结构，实现对字符串的插入、查找和删除操作，要求时间复杂度尽可能低。
描述并实现 Dijkstra 算法，用于计算图中从一个顶点到其他所有顶点的最短路径。

概率

10 个人相互握手，每个人都与其他人握一遍，总共握手多少次？
A、B 打乒乓球五局三胜，A 赢得每局概率为 0.6，B 赢的概率为 0.4，A 已经赢了前 2 局，问 A 最终获胜的概率是多少？
有 12 个黑球和若干个白球，随机取球，数到 13 时取出的为白球的取法有多少种？

业务

假设你负责优化滴滴的某一地区的派单算法，你会从哪些方面入手？请详细阐述思路和可能用到的算法。
滴滴的订单数据中包含出发地、目的地、订单时间等信息，设计一个算法，根据历史订单数据预测某个区域在未来一段时间内的订单需求趋势。
考虑到滴滴司机和乘客的位置分布、车辆类型、路况等因素，设计一个算法来计算最优的拼车方案，以提高拼车成功率和乘客满意度。

滴滴面试

阿里面试

先问项目和八股，八股里有两个没答好：

简要说明stacking和bagging的区别和联系答案是bagging并行训练N个同构的分类器然后进行加权投票；Stacking算是bagging的升级，算法分为2层，第一层是用不同的算法形成T个弱分类器，同时产生一个与原数据集大小相同的新数据集，利用这个新数据集和一个新算法构成第二层的分类器。
- 补充：Boosting是另外一种集成学习方法，它是串行训练N个同构的分类器，每个分类器都在尝试修正前一个分类器的错误，具体为提高错误分类样本的权重，boosting的代表算法是Adaboost和Xgboost。
说说常见的torch里的优化器有哪些，他们的区别是什么只说了一个adam，没说出来其他的，其实还有SGD，RMSprop，Adadelta，Adamax，Adagrad，AdamW，Momentum等等，他们的区别在于更新参数的方式不同。Adam是SGD的变种，它在SGD的基础上加入了动量和自适应学习率，Adam的优点是收敛速度快，但是可能会过拟合，所以在训练的时候需要调整学习率。

Stacking 就像是 Bagging的升级版，Bagging中的融合各个基础分类器是相同权重，而Stacking中则不同,Stacking中第二层学习的过程就是为了寻找合适的权重或者合适的组合方式。周四阿里面试，除了八股和项目之外，问了如下四个问题：

在圆中随机取一个点，到圆心的距离的期望是多少？（贝特郎悖论）
解决方法：正常做法：记半径为r，取点到圆心的距离为随机变量X，那么X的分布函数$F(x)=P(X<=x)=x^2/r^2$，求导得到概率密度函数$f(x)=2x/r^2$，然后求期望$E(X)=\int_0^r2x^2/r^2dx=2r/3$。我回答：随机取点等于随机取一个角度和一个距离，这两个是独立的，所以是0.5r。经过提醒我算出了2/3r。
一个均匀的六面骰子，如何用它模拟一个均匀的七面骰子？
解决方法，投两次，去掉[6，6]的情况，剩余35种情况分配到7个面上。
N盏灯，第一次开关全部打开，第二次每两盏灯关掉一盏，第三次每三盏灯开关一次，以此类推，第N次每N盏灯开关一次，问最后有多少盏灯是开着的？
解决方法：每盏灯的操作次数是它的因子个数，只有平方数的因子个数是奇数个，所以最后开着的灯是平方数的个数。 leetcode319. 灯泡开关

1，5，11元的银币进行支付，问支付n元有多少种方法？
解决方法：动态规划,这是leetcode322，零钱兑换问题。

class Solution:
 def coinChange(self, coins: List[int], amount: int) -> int:
     f = [0] + [inf] * amount
     for x in coins:
         for c in range(x, amount + 1):
             f[c] = min(f[c], f[c - x] + 1)
     ans = f[amount]
     return ans if ans < inf else -1

两道编程都没写出来，第一道找到了灯开关次数是因子个数，但是没想到是平方数，第二道一眼动态规划，被压力就写不出了。吃完饭看果然被挂。