Saturday, August 8, 2015

LeetCode OJ - Pascal's Triangle II

Problem:

Please find the problem here.

Solution:

Note the recurrence $ _nC_r = \frac{n!}{r!(n-r)!} = \frac{n!(n-r+1)}{r(r-1)!(n-r+1)!} = \frac{n-r+1}{r}\frac{n!}{(r-1)!(n-r+1)!} = \frac{n-r+1}{r}\frac{n!}{(r-1)!(n-(r-1))!} = \frac{n-r+1}{r}_nC_{(r-1)} $.

With that, we can simply compute the values one by one from left to right!

Code:

#include "stdafx.h"

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

#include "LEET_PASCALS_TRIANGLE_II.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_PASCALS_TRIANGLE_II
{
    class Solution
    {
    public:
        vector<int> getRow(int rowIndex)
        {
            vector<int> result;
            result.resize(rowIndex + 1);
            result[0] = 1;
            for (int i = 1; i <= rowIndex; i++)
            {
                long long temp = result[i - 1];
                temp = temp * (rowIndex + 1 - i) / i;
                result[i] = (int)temp;
            }
            return result;
        }
    };
};

using namespace _LEET_PASCALS_TRIANGLE_II;

int LEET_PASCALS_TRIANGLE_II()
{
    Solution solution;
    for (int i = 1; i <= 10; i++)
    {
        vector<int> result = solution.getRow(i);
        for (unsigned int j = 0; j < result.size(); j++)
        {
            cout << result[j] << " ";
        }
        cout << endl;
    }
    return 0;
}

No comments :

Post a Comment