给出一个值numRows,生成杨辉三角的前numRows行
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> generate(int numRows) { ArrayList<ArrayList<Integer>> list = new ArrayList<>(numRows); for(int i=0; i<numRows; i++){ ArrayList<Integer> l = new ArrayList<>(i+1); l.add(1); for(int j=1; j<=i; j++){ if(i==j) { l.add(1); break; } l.add(list.get(i-1).get(j-1)+list.get(i-1).get(j)); } list.add(l); } return list; } }
Leetcode#118. Pascal's Triangle(杨辉三角)
package Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* 118\. Pascal's Triangle(杨辉三角)
* 给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
*/
public class Solution118 {
public static void main(String[] args) {
Solution118 solution118 = new Solution118();
int numRows = 1;
List> res = solution118.generate(numRows);
System.out.println(res);
}
/**
* 对任意的n>0有
* f(1, n)=1,(n>0)
* f(1, 2)=1,(n=2)
* f(i,j) = f(i-1, j-1)+f(i, j-1),i>2,j>2
*
* @param numRows
* [@return](/profile/547241) */
public List> generate(int numRows) {
if (numRows == 0) {
return Collections.emptyList();
}
List> res = new ArrayList();
for (int i = 0; i < numRows; i++) {
List sub = new ArrayList();
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
sub.add(1);
} else {
List upSub = res.get(i - 1);
sub.add(upSub.get(j - 1) + upSub.get(j));
}
}
res.add(sub);
}
return res;
}
}
public ArrayList<ArrayList<Integer>> generate(int numRows) { ArrayList<ArrayList<Integer>> row = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> temp = new ArrayList<Integer>(); if(numRows<=0) return row; temp.add(1); row.add(temp); for (int i = 1; i < numRows; i++) { temp = new ArrayList<Integer>(); temp.add(1); for (int j = 1; j < i ; j++) { temp.add(row.get(i-1).get(j-1)+row.get(i-1).get(j)); } temp.add(1); row.add(temp); } return row; }
class Solution { public: vector<vector<int> > generate(int numRows) { vector<vector<int>> vRes; if(numRows == 0) return vRes; vector<int> v; v.push_back(1); vRes.push_back(v); for(int i=1;i<numRows;i++) { vector<int> vTmp; for(int j=0;j<=i;j++) { if(j-1>=0 && j<vRes[i-1].size()) vTmp.push_back(vRes[i-1][j-1]+vRes[i-1][j]); else vTmp.push_back(1); } vRes.push_back(vTmp); } return vRes; } };
vector<vector<int> > generate(int numRows) { vector<vector<int>> res; if(numRows==0) return res; vector<int> first; first.push_back(1); res.push_back(first); if(numRows==1) return res; for(int i=1; i<numRows; i++) { vector<int> tmp; tmp.push_back(1); for(int j=i-1; j>=1; j--) tmp.push_back(res[i-1][j]+res[i-1][j-1]); tmp.push_back(1); res.push_back(tmp); } return res; }
class Solution { public: vector<vector<int> > generate(int numRows) { vector<vector<int> >res; if(numRows <= 0) return res; generate(0,numRows,res); return res; } void generate(int row ,int rows, vector<vector<int> >&res){ vector<int>v; if(row == 0 && row < rows){ v.push_back(1); res.push_back(v); generate(row+1, rows, res); } else if(row == 1 && row < rows){ v.push_back(1); v.push_back(1); res.push_back(v); generate(row+1, rows, res); } else if( row > 1 && row < rows){ v = vector<int>(row+1 ,1); for(int i = 1; i < v.size()-1; ++i) v.at(i) = res.at(row-1).at(i-1) + res.at(row-1).at(i); res.push_back(v); generate(row+1, rows, res); } else return ; } };
class Solution { public: vector<vector<int> > generate(int numRows) { vector<vector<int> > res; for(int i=0;i<numRows;i++) { vector<int> v; for(int j=0;j<=i;j++) { if(j==0 || j==i) v.push_back(1); else if(i != 0) v.push_back(res[i-1][j-1]+res[i-1][j]); } res.push_back(v); } return res; } };
/**
* 118.Pascal's Triangle
* 杨辉三角
* 给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
* 在杨辉三角中,每个数是它左上方和右上方的数的和。 示例: 输入: 5 输出:
* [
* [1],
* [1,1],
* [1,2,1],
* [1,3,3,1],
* [1,4,6,4,1]
* ]
*/
public class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
List<List<Integer>> result = solution.generate(5);
System.out.println(result.toArray());
}
public List<List<Integer>> generate(int numRows) {
if (numRows < 0) {
return null;
}
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> eachRow = new ArrayList<>();
eachRow.add(1);
for (int j = 1; j < i; j++) {
if (i - 1 >= 0) {
List<Integer> lastRow = result.get(i - 1);
int num = lastRow.get(j - 1) + lastRow.get(j);
eachRow.add(j, num);
}
}
if (i > 0) {
eachRow.add(i, 1);
}
result.add(i, eachRow);
}
return result;
}
}
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> generate(int numRows) { ArrayList<ArrayList<Integer>> list = new ArrayList<>(); for (int i = 0; i < numRows; i ++) { ArrayList<Integer> temp = new ArrayList<>(); for (int j = 0; j <= i; j ++) { if(j == 0 || j == i) temp.add(1); else temp.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j)); } list.add(temp); } return list; } }
/* 思路:动态规划 第i行的杨辉三角基于第i-1行求得 状态定义: F[i][j]:第i行第j列的值 从第三行开始,不算左右两端,F[i][j] = F[i-1][j]+F[i-1][j-1]; 状态转移方程: F[i][j] = F[i-1][j]+F[i-1][j-1]; */ class Solution { public: /** * * @param numRows int整型 * @return int整型vector<vector<>> */ vector<vector<int> > generate(int numRows) { if(numRows <= 0){ return vector<vector<int>>(); } vector<vector<int>> results; //循环创建数组每一行 for(int i=0;i<numRows;i++){ vector<int> temp(i+1,1); results.push_back(temp); } //填充元素 for(int i=2;i<results.size();i++){ for(int j=1;j<results[i].size()-1;j++){ results[i][j] = results[i-1][j]+results[i-1][j-1]; } } return results; } };
Erlang动态规划
解题思路
沿着题目思路写,首先构建第一轮的元素,后面每一轮的元素由上一轮元素决定,于是构建Map用于存储上一轮的数据方便取值(取不到的数据为0,符合题意)
该题属于动态规划里面明确指出前后关系的了,有些题需要自己去挖掘这个前后关系~
代码
-spec generate(NumRows :: integer()) -> [[integer()]]. generate(NumRows) -> do_generate(1, _LastMap = #{}, _Args = #{rows => NumRows, nums => []}). do_generate(1, _, Args) -> do_generate(2, #{1 => 1}, Args#{nums := [[1]]}); do_generate(N, LastMap, Args = #{rows := NumRows, nums := Nums}) when N = Fun = fun(Index, Acc) -> L = maps:get(Index - 1, LastMap, 0), R = maps:get(Index, LastMap, 0), Num = L + R, [Num | Acc] end, SeqNums = lists:seq(1, N), RowNums = lists:foldl(Fun, [], SeqNums), Map = maps:from_list(lists:zip(SeqNums, RowNums)), NewRowNums = lists:reverse(RowNums), do_generate(N + 1, Map, Args#{nums := [NewRowNums | Nums]}); do_generate(_, _, _Args = #{nums := Nums}) -> lists:reverse(Nums).
利用对称性简化:
// // Created by jt on 2020/9/2. // #include <vector> using namespace std; class Solution { public: /** * * @param numRows int整型 * @return int整型vector<vector<>> */ vector<vector<int> > generate(int numRows) { // write code here vector<vector<int> > res; for (int i = 1; i <= numRows; ++i) { vector<int> vec(i, 1); for (int j = (i-1) / 2; j > 0; --j) { vec[j] = res[i-2][j] + res[i-2][j-1]; vec[(i-1)-j] = vec[j]; } res.push_back(vec); } return res; } };
class Solution: # dp python2.7 def generate(self , numRows ): # write code here res = [] dp = [1] if numRows == 0: return res res.append(dp[:]) for _ in range(numRows-1): l = len(dp) for j in range(l-1,0,-1): dp[j] = dp[j] + dp[j-1] dp.append(1) res.append(dp[:]) return res