Swift 3.0

//
//  E_118_Pascal'sTriangle.swift
//  AlgorithmLeetCode
//
//  Created by okerivy on 2017/3/8.
//  Copyright ? 2017年 okerivy. All rights reserved.
//  https://leetcode.com/problems/pascals-triangle

import Foundation




// MARK: - 題目名稱(chēng): 118. Pascal's Triangle

/* MARK: - 所屬類(lèi)別:
 標(biāo)簽: Array
 
 相關(guān)題目:
  (E) Pascal's Triangle II
 
 */

/* MARK: - 題目英文:
 Given numRows, generate the first numRows of Pascal's triangle.
 
 For example, given numRows = 5,
 Return
 
 [
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
 ]
 
 */


/* MARK: - 題目翻譯:
 給定一個(gè)數(shù)字,生成一個(gè)帕斯卡三角形（楊輝三角）
 例如給定一個(gè)數(shù)字5 ,返回下面的數(shù)組
 [
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
 ]
 
 */



/* MARK: - 解題思路:
 
 要得到一個(gè)帕斯卡三角维蒙，我們只需要找到規(guī)律即可择份。
 
 第k層有k個(gè)元素
 每層第一個(gè)以及最后一個(gè)元素值為1
 對(duì)于第k（k > 2）層第n（n > 1 && n < k）個(gè)元素A[k][n]，A[k][n] = A[k-1][n-1] + A[k-1][n]
 知道了上面的規(guī)律衣陶，就很好做了镀迂，我們使用一個(gè)二維數(shù)組來(lái)存儲(chǔ)整個(gè)三角
 
 */


/* MARK: - 復(fù)雜度分析:
 時(shí)間復(fù)雜度 O(n^2), 空間復(fù)雜度在最后一位有進(jìn)位時(shí)惡化為 O(n)
 
 */


// MARK: - 代碼:
private class Solution {
    func generate(_ numRows: Int) -> [[Int]] {
        
        // 初始化一個(gè)二維數(shù)組
        var arrays = [[Int]]()
        
        //大于等于1 進(jìn)行數(shù)組的遍歷
        if numRows >= 1 {
            // 二維數(shù)組 拼接第一個(gè)元素(長(zhǎng)度為1的,元素為1 一維數(shù)組)
            arrays.append([Int](repeating: 1, count: 1))
        
            for i in 1 ..< numRows {
                // 二維數(shù)組 拼接其余的元素(長(zhǎng)度為i+1的 初始值 為0 的一維數(shù)組)
                arrays.append([Int](repeating: 0, count: i+1))
                // 第一個(gè)元素設(shè)置為1
                arrays[i][0] = 1
                // 最后一個(gè)元素設(shè)置為1
                arrays[i][i] = 1
                for j in 1 ..< i {
                    // 中間元素 根據(jù)規(guī)則 進(jìn)行計(jì)算
                    arrays[i][j] = arrays[i - 1][j - 1] + arrays[i - 1][j];
                }
            }
        }

        return arrays
    }
    
    // 遞歸算法
    // 求楊輝三角中第i行第j列的值
    private func calcTriVal(_ dwRow: Int, _ dwCol: Int) -> Int {
        if 0 == dwCol || dwCol == dwRow {
            return 1
        } else {
            return calcTriVal(dwRow - 1, dwCol - 1) + calcTriVal(dwRow - 1, dwCol)
        }
        
    }
    
    func generate2(_ numRows: Int) -> [[Int]] {
        
        // 初始化一個(gè)二維數(shù)組
        var arrays = [[Int]]()
        for dwRow in 0 ..< numRows {
            arrays.append([Int](repeating: 0, count: dwRow+1))
            for dwCol in 0 ... dwRow {
                // 對(duì)數(shù)組進(jìn)行賦值
                arrays[dwRow][dwCol] =  calcTriVal(dwRow, dwCol)
            }
        }
        
        return arrays
    }
}



// MARK: - 測(cè)試代碼:

func pascalsTriangle()  {
    
    let numRows = 6
    var arrays = Solution().generate(numRows)
    
    // 按照要求 打印輸出 非代碼的部分
    print("[")
    for i in 0..<numRows {
        var output = ""
        
        // 拼接空格的個(gè)數(shù)
        for _ in 0..<numRows-i-1 {
            output.append(" ")
        }
        
        // 拼接數(shù)組的其實(shí)標(biāo)志
        output.append("[")
        // 打印不換行
        print("\(output)" ,terminator:"")
        for j in 0...i {
            if j == 0 {
                // 第一個(gè)元素打印
                print("\(arrays[i][j])" ,terminator:"")
            } else {
                // 其余元素打印, 前面加逗號(hào)
                print(",\(arrays[i][j])" ,terminator:"")
            }
            
        }
        // 打印數(shù)組末尾, 換行
        print("]")
        
    }
    print("]")
}