帕斯卡三角形第k行求职面试的解决方案

问题：

给定索引\ $ k \ $，返回Pascal三角形的\ $ k ^ {th} \ $行。

例如，假设\ $ k = 3 \ $，则返回\ $ [1,3,3,1] \ $。使用\ $ O（k）\ $空间的奖励积分。

是否可以使用这种方式或其他方式进一步优化？

class Solution {
   public:
    long long C(int n, int r) {
       if(r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
       long long ans = 1;
       int i;

       for(i = 1; i <= r; i++) {
           ans *= n - r + i;
           ans /= i;
       }

       return ans;
   }

       vector<int> getRow(int rowIndex) {
           vector<int> v;
           long long sol;
           for(int i=0;i<=rowIndex;i++)
           {sol=C(rowIndex,i);
           v.push_back(sol);}

          return v; 
       }
   };

如果这是一次采访，我将一目了然。这意味着以这样一种方式编写代码，使代码的格式非常漂亮，并有注释说明了方法论和对您实现的复杂性的描述。

我对所有这些人都感到困惑，他们试图猜测在面试中可能会面临哪些挑战。提出此类问题的面试官并不希望您当场编写出完美的代码或炫耀您对语言的完全掌握。他们正在寻找的是洞悉您如何思考问题并解决问题的方法。微观优化是在您编写代码之后发生的，而微观优化是在您解决问题之后发生的。能够讨论您为什么选择了特定的方法或算法，才是更有益的。

我会使用Boost或其他lib，或者至少先问这个。不仅表明您知道现有的解决方案，而且不打算尝试重新发明轮子。但是，这是代码审查。

@TorbjornDiderholm：O（k）空间很小。您只需在三角形中保持两行。这是O（2k）=> O（k）。仅使用两行编写算法很简单，因为您可以在当前行中使用一个，而在下一行中使用，然后可以迭代求解。

考虑在最后一个for循环中摆脱那种可怕的括号样式。

#1 楼

您至少可以进行两种优化。

首先，您要对为r计算的每个r值执行C(k,r)乘法和r < k/2除法。
您最多只需要您要计算的C(k,r)的每个值一乘除一
，因为在您要
计算C(k,r)时，您已经计算并存储了C(k, r-1)的值。
请使用C(k,r) == C(k, r-1) * (k-r+1) / r的事实：

$$ \ begin {align *}
\ frac {C（k，r）} {C（k，r-1）}＆= \ frac {\ frac {k ！} {r！（k-r）！}} {\ frac {k！} {（r-1）！（k-r + 1）！}} = \ frac {（r-1）！（k-r + 1）！} {r！（k-r）！} = \ frac {k-r + 1} {r} \\
\\
C（k，r）＆= \ frac {k-r + 1} { r} C（k，r-1）
\ end {align *} $$

这会将所需的算术运算次数从O（k2）减少到O（k），
，我认为这是一个相当不错的优化。

第二个优化是由于C(k, r) == C(k, k - r)的事实。
您使用此公式减少了计算所需的运算数量
/> C(k,r)对应r > k/2，但实际上，您不必对Pascal三角形中的任何这些条目执行任何操作，因为您已经
计算并存储了答案。只需复制这些结果即可填充向量的其余部分。
（但是，当n为偶数时，当然不要复制C(k, k/2)。）

第二个优化将运算次数减少了近一半。

应用这些优化的结果是，实现像C(int n, int r)这样的函数不再有意义。但是据我所知，实现该功能并不是您的要求的一部分。

#2 楼

一方面，与空格使用和花括号放置的不一致可能表明对细节缺乏关注。在解决实际问题之前，请确保您的代码编写干净。

此：

for(int i=0;i<=rowIndex;i++)

应该使用一些空格：

for (int i = 0; i <= rowIndex; i++)

您已经在其他地方执行过此操作，并且应该在任何地方都应执行。

此外，此操作：

for(int i=0;i<=rowIndex;i++)
{sol=C(rowIndex,i);
v.push_back(sol);}

看起来有点草率，很难阅读。同样，使用更多的空格，还可以将循环主体与花括号分开。

for (int i = 0; i <= rowIndex; i++) {
    sol = C(rowIndex, i);
    v.push_back(sol);
}

\ $ \ begingroup \ $
这看似微不足道，但您可以教技能。懒惰很难被淘汰出局。与初级开发人员的次优算法相比，草率格式化对我来说是一个更大的危险信号。
\ $ \ endgroup \ $
– David Harkness
2014年5月30日下午3:26

\ $ \ begingroup \ $
@DavidHarkness：有趣。这是否表明如果OP不愿意采用它们，我的回答可能并没有太大帮助，或者恰恰相反？
\ $ \ endgroup \ $
– Jamal♦
2014年5月30日下午3:39

\ $ \ begingroup \ $
无论OP是否遵循您的建议，您的回答都将非常有用。如果他们不这样做，希望其他人会读它，这样我每天就可以减少清理格式不正确的代码的时间。
\ $ \ endgroup \ $
– David Harkness
2014年5月30日下午4:11

\ $ \ begingroup \ $
@DavidHarkness：感谢您的澄清。这实际上是受到温斯顿·埃沃特（Winston Ewert）的最高答案的启发，该答案严重批评了OP的采访代码。我想这是刚从大学刚毕业的申请人那里得到的期望，他至少应该能够关注细节。
\ $ \ endgroup \ $
– Jamal♦
2014年5月30日下午4:14

\ $ \ begingroup \ $
我坚持使用一些与拼写检查学期论文相同的格式。如果您不愿意采取这一基本步骤，那么这向我表明您并不真正在乎同行。当然，您可能会在乎，就像离开脏盘子并不能证明您对室友的照顾不足一样，但这是一个很好的领先指标。为什么不花2分钟来正确格式化您的代码以删除红旗呢？ CR并不是“每一分钟都很重要”的采访（顺便说一句，在采访中甚至不适用），因此没有任何借口可以使代码保持未格式化的状态。
\ $ \ endgroup \ $
– David Harkness
2014年5月30日下午4:27

#3 楼

类型在C ++中非常重要。

您对类型的使用很草率。

 long long sol;      // big int object.

将其放入仅包含容纳int

 vector<int> v;       // Only takes int
 v.push_back(sol);    // push long long and thus truncate

\ $ \ begingroup \ $
oj.leetcode.com/problems/pascals-triangle-ii我不是故意使用它的，它的结构是一样的，但是在将数据类型作为int sol的int时，我认为可能会发生整数溢出。
\ $ \ endgroup \ $
– swapedoc
2014年5月29日18:52

\ $ \ begingroup \ $
如果有溢出的可能性，则向量也应使用long long。您可以将值保留在sol中，但是一旦将其放入向量中，该值就会被截断（因此您会丢失信息）。
\ $ \ endgroup \ $
–马丁·约克
2014年5月29日19:57

#4 楼

我很好奇为什么将Int变量从for循环中分离出来了？

    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

我认为只有在您希望变量位于外部时才这样做循环，但它是使循环功能起作用的变量，您不希望它的作用域是公开的，可能会出现某些问题并破坏您的循环（或使其无限循环）

它应该看起来像这样

    for(int i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

\ $ \ begingroup \ $
啊，我错过了。由于这是C ++，而不是C99之前的版本，因此没有理由将其置于循环之外。
\ $ \ endgroup \ $
– Jamal♦
2014年5月29日在18:47

\ $ \ begingroup \ $
是否有理由在循环外声明它？ C99进行了哪些更改以使其正常？老实说，我不了解足够的C / C ++内部结构来猜测原因，但是我确实很好奇。
\ $ \ endgroup \ $
– David Harkness
2014年5月30日，3：23

\ $ \ begingroup \ $
@DavidHarkness在C99（例如ANSI C）之前，在for构造内部声明循环变量是非法的。您必须在外部声明它，然后使用它。在作用域块开头以外的其他任何地方声明变量也是非法的。
\ $ \ endgroup \ $
–托马斯
2014年5月30日6:24

#5 楼

作为一名面试官，我会在实施过程中看到一个很大的危险信号。从头计算每个系数会导致很多不必要的重新计算。

使用递归：您已经知道\ $ \ binom {n} {r} \ $，所以\ $ \ binom {n} {r +1} \ $只是一个乘法和一个除法。

#6 楼

我建议您在代码中使用与挑战中相同的符号。从k切换到rowIndex到n只会引起混乱。

#7 楼

这是一个有趣的面试问题，因为它提出了一些您应该指出的问题。

解决方案的主要缺点不是缺乏优化。这是事实，由于溢出，即使对于早期的行它也会给出错误的结果。下降阶乘不是要走的路！大卫的答案可以解决这个问题，但是有一个更简单的解决方案：\ $ \ binom {n} {r} = \ binom {n-1} {r} + \ binom {n-1} {r-1} \ $。没有除法，没有乘法，先生。有时\ $ O（k ^ 2）\ $加法优于\ $ O（k）\ $乘法和除法。您不必选择：提出几种方法是值得赞赏的。

另外，由于强调了\ $ O（k）\ $空间，因此应该reserve(k)。夫人，有了本机类型，没有更多分配了。如果使用累加生成方法一次又一次遍历相同的向量，则具有更好的局部性。

我们还可以想象2个向量-仍然为\ $ O（k）\ $-一个用于奇数行，一个用于偶数行，允许安全并行化。您不必编写此解决方案，但只需调用它即可获得额外的奖励积分。

最后，您可以列出一些测试实现的方法（例如，将某些行与参考进行比较，或测试Pascal三角形的某些属性）。

\ $ \ begingroup \ $
实际上C（n，r）= C（n-1，r）+ C（n-1，r-1）给了我一个“超过时间限制”。
\ $ \ endgroup \ $
– swapedoc
2014年5月30日19:18

编程黑洞网