闯关leetcode——118. Pascal‘s Triangle

大纲

题目
- 地址
- 内容
解题
- 代码地址

题目

地址

https://leetcode.com/problems/pascals-triangle/description/

内容

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

在这里插入图片描述

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

1 <= numRows <= 30

解题

这题就是按照层数构造出一个帕斯卡三角。逻辑也很简单，就是两边都是1，中间元素都是由上一层元素两两相加而得。

#include <vector>
#include <numeric>
using namespace std;

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;
        result.push_back({1});
        for (int i = 2; i <= numRows; i++) {
            vector<int> row(i, 1);
            adjacent_difference(result[i-2].begin(), result[i-2].end(), row.begin(), plus<int>());
            result.push_back(row);
        }
        return result;
    }
};

这儿我们使用到C++17引入的std::adjacent_difference。它可以使用自定义的运算符计算区间内（__first，__last）相邻的两个元素，然后将其结果保存在另外一个迭代器（__result）的下一个位置。


  /**
   *  @brief  Return differences between adjacent values.
   *
   *  Computes the difference between adjacent values in the range
   *  [__first,__last) using the function object @p __binary_op and writes the
   *  result to @p __result.
   *
   *  @param  __first  Start of input range.
   *  @param  __last  End of input range.
   *  @param  __result  Output sum.
   *  @param  __binary_op Function object.
   *  @return  Iterator pointing just beyond the values written to result.
   */
  // _GLIBCXX_RESOLVE_LIB_DEFECTS
  // DR 539. partial_sum and adjacent_difference should mention requirements
  template<typename _InputIterator, typename _OutputIterator,
	   typename _BinaryOperation>
    _GLIBCXX20_CONSTEXPR
    _OutputIterator
    adjacent_difference(_InputIterator __first, _InputIterator __last,
			_OutputIterator __result, _BinaryOperation __binary_op)
    {
      typedef typename iterator_traits<_InputIterator>::value_type _ValueType;

      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
				                         _ValueType>)
      __glibcxx_requires_valid_range(__first, __last);

      if (__first == __last)
	return __result;
      _ValueType __value = *__first;
      *__result = __value;
      while (++__first != __last)
	{
	  _ValueType __tmp = *__first;
	  *++__result = __binary_op(__tmp, _GLIBCXX_MOVE_IF_20(__value));
	  __value = _GLIBCXX_MOVE(__tmp);
	}
      return ++__result;
    }