首页 > 代码库 > leetcode-triangle
leetcode-triangle
虽说题目很简单，也没有优化。但是depend on myself & 一遍就AC还是很让人开心的。。
之前二维vector不熟，通过这个题熟了很多。
时间复杂度O(n^2),空间复杂度O(n^2). 优化之后可以做到空间复杂度O(1), 见代码2.
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 using namespace std; 5 6 class Solution { 7 public: 8 int minimumTotal(vector<vector<int> > &triangle) { 9 if (triangle.empty())10 return 0;11 vector<vector<int>> d;12 for (int i = 0; i < triangle.size(); i++)13 {14 d.push_back(vector<int>(triangle[i].size(), INT_MAX));15 }16 d.at(0).at(0) = (triangle.at(0).at(0));17 for (int i = 1; i < triangle.size(); i++)18 {19 for (int j = 0; j < triangle[i].size(); j++)20 {21 if (j == 0)22 {23 d.at(i).at(j) = triangle.at(i).at(j) + d.at(i - 1).at(j);24 }25 else if (j == int(triangle.at(i).size()) - 1)26 {27 d.at(i).at(j) = triangle.at(i).at(j) + d.at(i - 1).at(j - 1);28 }29 else30 {31 d.at(i).at(j) = triangle.at(i).at(j) + min(d.at(i - 1).at(j - 1), d.at(i - 1).at(j));32 }33 }34 }35 int minv = d.at(int(d.size()) - 1).at(0);36 for (int i = 1; i < int(d.at(int(d.size())-1).size()); i++)37 {38 if (d.at(d.size()-1).at(i)<minv)39 {40 minv = d.at(d.size() - 1).at(i);41 }42 }43 return minv;44 }45 };46 47 int main()48 {49 Solution s;50 vector<vector<int>> tri;51 int a1[] = { 2 };52 int a2[] = { 3, 4 };53 int a3[] = { 6, 5, 7 };54 int a4[] = { 4, 1, 8, 3 };55 //tri.push_back(vector<int>(a1,a1+1));56 //tri[0].push_back(1); tri[0].push_back(9);57 tri.push_back(vector<int>(a1, a1 + 1));58 tri.push_back(vector<int>(a2, a2 + 2));59 tri.push_back(vector<int>(a3, a3 + 3));60 tri.push_back(vector<int>(a4, a4 + 4));61 cout<<s.minimumTotal(tri)<<endl;62 return 0;63 }
以下为优化后：空间复杂度变为O(1)。
1 class Solution { 2 public: 3 int minimumTotal(vector<vector<int> > &triangle) { 4 if (triangle.empty()) 5 return 0; 6 for (int i = triangle.size() - 2; i >= 0; i--) 7 { 8 for (int j = 0; j < i + 1; j++) 9 {10 triangle[i][j] += min(triangle[i+1][j],triangle[i+1][j+1]);11 }12 }13 return triangle[0][0];14 }15 };
leetcode-triangle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。