首页 > 代码库 > leetcode-triangle

leetcode-triangle

2024-07-25 03:03:30   217人阅读

虽说题目很简单，也没有优化。但是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


联系
我们