DSA/arrays/generate.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.\n",
    "\n",
    "\n",
    "In Pascal's triangle, each number is the sum of the two numbers directly above it.\n",
    "\n",
    "Example:\n",
    "\n",
    "    Input: 5\n",
    "    Output:\n",
    "    [\n",
    "         [1],\n",
    "        [1,1],\n",
    "       [1,2,1],\n",
    "      [1,3,3,1],\n",
    "     [1,4,6,4,1]\n",
    "    ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Solution:\n",
    "    def generate(self, numRows):\n",
    "        '''\n",
    "        numRows: int\n",
    "        rtype: List[List[int]]\n",
    "        '''\n",
    "        f = [[1]*(i+1) for i in range(numRows)]\n",
    "        for i in range(numRows):\n",
    "            for j in range(1,i):\n",
    "                f[i][j] = f[i-1][j-1] + f[i-1][j]\n",
    "        return f\n",
    "\n",
    "# test\n",
    "numRows = 5\n",
    "Solution().generate(numRows)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}