学会从后往前遍历，例 [LeetCode] Pascal's Triangle II，剑指Offer 题4

当我们需要改变数组的值时，如果从前往后遍历，有时会带来很多麻烦，比如需要插入值，导致数组平移，或者新的值覆盖了旧有的值，但旧有的值依然需要被使用。这种情况下，有时仅仅改变一下数组的遍历方向，就会避免这些困难。

最直观的一题是剑指Offer上的面试题 4

另外一道例题，就是LeetCode上的 Pascal's Triangle II

Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

class Solution {

public:

    vector<int> getRow(int rowIndex) {

    }

};

所谓Pascal's Triangle，就是如下面所示的结构。

[

     [1],

    [1,1],

   [1,2,1],

  [1,3,3,1],

 [1,4,6,4,1]

]

要求O(k)空间复杂度的情况下，思路很直观，就是先在vector<int> 存入 1，然后循环 k 次。伪代码如下：

for(i = ; i < k; ++i)

{

    v[] =

    for(j = ; j < k; ++j)

    {

        v[j] = v[j-] + v[j];

    }

}

然而很快我发现这样做是不对的，因为v[j]算出后，紧接着在j+1后的运算中会作为v[j-1]出现，也就是说，v[j-1]此时已经是新值了，不再是上一排的数，算出的结果将是错误的。

只要从v[1]开始往后遍历，都会遇到这个问题。

那么我们改为 v[j] = v[j] + v[j+1]，这样确实可以避免值覆盖问题，但是会出现不得不整体移动数组的麻烦，因为前面算出的值没法放了。

这个时候，如果转而从最后一个值开始算起，逐渐算到v[1]，就可以避开这个麻烦。

for(i = ; i < k; ++i)

{

    v[k] =

    for(j = k-; j > ; --j)

    {

        v[j] = v[j-] + v[j];

    }

    v[] = ;

}

代码：

class Solution {

public:

    vector<int> getRow(int rowIndex) {

        vector<int> v;

        if(rowIndex < ) return v;

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

            v.push_back();

        }

        for(int j = ; j <= rowIndex; ++j){

            v[rowIndex] = ;

            for(int k = rowIndex-; k > ; --k){

                v[k] = v[k] + v[k-];

            }

            v[] = ;

        }

        return v;

    }

};

Accepted 4ms

巴特西

学会从后往前遍历，例 [LeetCode] Pascal's Triangle II，剑指Offer 题4

最新文章

热门文章