ARTS004

ARTS004

ARTS是什么？
Algorithm：每周至少做一个 leetcode 的算法题
Review：阅读并点评至少一篇英文技术文章
Tip：学习至少一个技术技巧
Share：分享一篇有观点和思考的技术文章

Algorithm

LC 杨辉三角 II

解法1：先构造整个杨辉三角，然后返回第k行。

class Solution {
public:vector<int> getRow(int rowIndex) {vector<vector<int>> nums(rowIndex+1);for(int i=0; i<=rowIndex; ++i){vector<int> v(i+1);v[0]=v[i]=1; // 首尾为1for(int j=1; j<i; ++j){v[j]=nums[i-1][j-1]+nums[i-1][j];}nums[i]=v;}return nums[rowIndex];}
};

解法2：采用滚动数组，因为计算第k行的杨辉三角只需根据第k-1行即可。

class Solution {
public:vector<int> getRow(int rowIndex) {vector<int> pre, cur;for(int i=0; i<=rowIndex; ++i){size(i+1);cur[0]=cur[i]=1; // 首尾为1for(int j=1; j<i; ++j){cur[j]=pre[j-1]+pre[j];}pre=cur;}return pre;}
};

Review

Find with Custom Returns
本文讲了如何定制std::find的返回值。Arno Schödl在演讲中分享了std::find算法如何对返回值进行灵活的处理。标准的find算法，如果找到搜索的值，那么返回指向这个值的迭代器iterator，否则返回入参的最后一个迭代器end。现在find的实现如下：

template<typename InputRange, typename Value>
decltype(auto) find(InputRange&& range, Value const& value)
{auto itEnd = end(range);for(auto it = begin(range); it != itEnd; ++it){if (*it == value) return it;}return itEnd;
}

如果我们想让它返回更复杂的返回类型和值，我们在find中就需要引入了一个自定义点。

template<typename ReturnPolicy, typename InputRange, typename Value>
decltype(auto) find(InputRange&& range, Value const& value)
{for(auto it = begin(range); it != end(range); ++it){if (*it == value) return ReturnPolicy::onFound(it, range);}return ReturnPolicy::onNotFound(range);
}

有了这种间接方式后，我们现在可以使find返回其他结果，而无需更改算法本身的代码，可以直接重新修改自定义点IteratorOrEnd就可以了。

struct IteratorOrEnd
{template<typename Iterator, typename Range>static auto onFound(Iterator&& iterator, Range&&){return iterator;}template<typename Range>static auto onNotFound(Range&& range){return end(range);}
};auto position42 = find<IteratorOrEnd>(v, 42);
if (position42 != end(v))
{// code using *position42 ...

Tip

C++函数如何返回多个值？

• 方法1：将返回值用引入参数传入，返回值只作为状态，根据状态再输出具体的返回值。
• 方法2：采用tuple，struct，pair等数据结构来实现多个返回值。
• 方法3：std::optional，C++17引入的。

Share

KK给年轻人的建议