程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Pascal's Triangle II

leetcode筆記:Pascal's Triangle II

編輯:C++入門知識

leetcode筆記: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?

二. 題目分析

關於帕斯卡三角形的定義,可參考:http://baike.baidu.com/link?url=qk_-urYQnO4v6v3P4BuMtCa0tMNUqJUk4lmbkb1aqbqikBU-ndiMlTF20fq2QUjTTFTeTohZ72KFxgBnz4sJha

該題要求只輸出第k行的元素值,並且要求空間復雜度為O(k),因此,采用的方法是只使用一個定長的數組,用於存放每一行的元素值,對於每個新的行,可對原先存放的行從後往前掃描,主要分為以下三種情況:

最後一個元素,直接等於1; 對於下標為i的中間元素,有:result[i] = result[i-1] + result[i]; 第一個元素,直接等於1;

這樣,就只需要O(k)的空間。

三. 示例代碼

class Solution {
public:
    vector getRow(int rowIndex) 
    {
        vector result(rowIndex + 1);
        result[0] = 1;
        if (rowIndex < 1) return result;

        for(int i = 1; i <= rowIndex; ++i)
            for(int j = i; j >= 0; --j)
                if (j == i || j == 0)
                    result[j] = 1;
                else
                    result[j] = result[j-1] + result[j];

        return result;                    
    }
};

四. 小結

若不要求O(k)的空間復雜度,該題的難度更低,但這樣也沒什麼技巧可言了。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved