119 pascal tam giác ii java

Vấn đề

Cho chỉ số k không âm trong đó k ≤ 33, trả về hàng chỉ số thứ k của tam giác Pascal

Lưu ý rằng chỉ số hàng bắt đầu từ 0

Trong tam giác Pascal, mỗi số bằng tổng của hai số ngay phía trên nó

Ví dụ

Input: 3
Output: [1,3,3,1]

Theo sát

Bạn có thể tối ưu hóa thuật toán của mình để chỉ sử dụng không gian thừa O(k) không?

Giải pháp 1

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
  var res = [];
  var i = 0;
  var j = 0;
  for (i = 0; i <= rowIndex; i++) {
    res.unshift(1);
    for (j = 1; j < i; j++) {
      res[j] += res[j + 1];
    }
  }
  return res;
};

Giải thích

không

phức tạp

• Độ phức tạp về thời gian. O(n^2)
• Độ phức tạp của không gian. Trên)

Giải pháp 2

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
  var res = Array(rowIndex + 1);
  var i = 0;
  var j = 0;
  for (i = rowIndex; i >= 0; i--) {
    res[i] = 1;
    for (j = i + 1; j < rowIndex; j++) {
      res[j] += res[j + 1];
    }
  }
  return res;
};

Giải thích

không

phức tạp

• Độ phức tạp về thời gian. O(n^2)
• Độ phức tạp của không gian. Trên)

Giải pháp 3

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
  var res = Array(rowIndex + 1);
  res[0] = 1;
  for (var i = 1; i <= rowIndex; i++) {
    res[i] = res[i - 1] * ((rowIndex - i + 1) / i);
  }
  return res;
};

Giải thích

在第 k 行，第 i 个元素，

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
  var res = [];
  var i = 0;
  var j = 0;
  for (i = 0; i <= rowIndex; i++) {
    res.unshift(1);
    for (j = 1; j < i; j++) {
      res[j] += res[j + 1];
    }
  }
  return res;
};

phức tạp

• Độ phức tạp về thời gian. Trên)
• Độ phức tạp của không gian. Trên)

Trong bài giải Leetcode Pascal's Triangle II này, chúng ta có một số nguyên rowIndex, trả về hàng rowIndexth (0-indexed) của tam giác Pascal. Trong tam giác Pascal, mỗi số bằng tổng của hai số ngay phía trên nó

Giải pháp vấn đề trong Python

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0: 
            return [1]
        if rowIndex == 1: 
            return [1, 1]
        if rowIndex == 2: 
            return [1, 2, 1]
        
        ans = [1] * (rowIndex + 1)
        prev = [1, 2, 1]
        
        for i in range(3, rowIndex + 1):
            for j in range(1, i):
                ans[j] = prev[j] + prev[j - 1]
            prev = ans[:]
            
        return ans

Giải pháp vấn đề trong Java

public List<Integer> getRow(int rowIndex) {      
        List<Integer> result = new ArrayList<>();
        result.add(1);
        
        if(rowIndex==0) return result;
        
        List<Integer> prev = getRow(rowIndex-1);        
        for(int i=0; i<prev.size()-1;i++){
            result.add(prev.get(i)+prev.get(i+1));
        }
        result.add(1);
        
        return result;
    }

Giải pháp vấn đề trong C++

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        ++rowIndex;
        std::vector<int> res(rowIndex, 1);
        for(int i{1}; i < rowIndex; ++i) res[i] = (int64_t) res[i-1] * (rowIndex-i) / i;
        return res;
    }
};

Giải quyết vấn đề trong C

int* getRow(int rowIndex, int* returnSize) {
    int *result = malloc((rowIndex + 1) * sizeof(int));
    int i, j, new, old = 1;
    
    *returnSize = rowIndex + 1;
    
    for (i = 0; i <= rowIndex; i++) {
        result[i] = 1;
        for (j = 1; j < i; j++) {
            new = result[j];
            result[j] += old;
            old = new;
        }
    }
    
    return result;
}

Hàng 7 của tam giác Pascal là gì?

3 mẫu trong tam giác Pascal là gì?

Giá trị của số hạng t6 2 trong Tam giác Pascal là bao nhiêu?

Hàng 4 của tam giác Pascal là gì?