欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實現(xiàn)LeetCode(120.三角形)

 更新時間:2021年07月23日 17:11:43   作者:Grandyang  
這篇文章主要介紹了C++實現(xiàn)LeetCode(120.三角形),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下

[LeetCode] 120.Triangle 三角形

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

這道題給了我們一個二維數(shù)組組成的三角形,讓我們尋找一條自上而下的路徑,使得路徑和最短。那么那道題后還是先考慮下暴力破解,我們可以發(fā)現(xiàn)如果要遍歷所有的路徑的話,那可以是階乘級的時間復雜度啊,OJ必滅之,趁早斷了念想比較好。必須要優(yōu)化時間復雜度啊,題目中給的例子很容易把人帶偏,讓人誤以為貪婪算法可以解題,因為看題例子中的紅色數(shù)組,在根數(shù)字2的下方選小的數(shù)字3,在3的下方選小的數(shù)字5,在5的下方選小的數(shù)字1,每次只要選下一層相鄰的兩個數(shù)字中較小的一個,似乎就能得到答案了。其實是不對的,貪婪算法可以帶到了局部最小,但不能保證每次都帶到全局最小,很有可能在其他的分支的底層的數(shù)字突然變的超級小,但是貪婪算法已經(jīng)將其他所有分支剪掉了。所以為了保證我們能得到全局最小,動態(tài)規(guī)劃Dynamic Programming還是不二之選啊。其實這道題和 Dungeon Game 非常的類似,都是用DP來求解的問題。那么其實我們可以不新建dp數(shù)組,而是直接復用triangle數(shù)組,我們希望一層一層的累加下來,從而使得 triangle[i][j] 是從最頂層到 (i, j) 位置的最小路徑和,那么我們?nèi)绾蔚玫綘顟B(tài)轉移方程呢?其實也不難,因為每個結點能往下走的只有跟它相鄰的兩個數(shù)字,那么每個位置 (i, j) 也就只能從上層跟它相鄰的兩個位置過來,也就是 (i-1, j-1) 和 (i-1, j) 這兩個位置,那么狀態(tài)轉移方程為:

triangle[i][j] = min(triangle[i - 1][j - 1], triangle[i - 1][j])

我們從第二行開始更新,注意兩邊的數(shù)字直接賦值上一行的邊界值,那么最終我們只要在最底層找出值最小的數(shù)字,就是全局最小的路徑和啦,代碼如下:

解法一:

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        for (int i = 1; i < triangle.size(); ++i) {
            for (int j = 0; j < triangle[i].size(); ++j) {
                if (j == 0) {
                    triangle[i][j] += triangle[i - 1][j];
                } else if (j == triangle[i].size() - 1) {
                    triangle[i][j] += triangle[i - 1][j - 1];
                } else {
                    triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
                }
            }
        }
        return *min_element(triangle.back().begin(), triangle.back().end());
    }
};

這種方法可以通過OJ,但是畢竟修改了原始數(shù)組triangle,并不是很理想的方法。在網(wǎng)上搜到一種更好的DP方法,這種方法復制了三角形最后一行,作為用來更新的一位數(shù)組。然后逐個遍歷這個DP數(shù)組,對于每個數(shù)字,和它之后的元素比較選擇較小的再加上面一行相鄰位置的元素做為新的元素,然后一層一層的向上掃描,整個過程和冒泡排序的原理差不多,最后最小的元素都冒到前面,第一個元素即為所求。代碼如下:

解法二: 

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp(triangle.back());
        for (int i = (int)triangle.size() - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
            }
        }
        return dp[0];
    }
};

下面我們來看一個例子,對于輸入數(shù)組:

     -1

    2   3

  1  -1  -3

5   3   -1   2

下面我們來看DP數(shù)組的變換過程(紅色數(shù)字為每次dp數(shù)組中值改變的位置):

DP:5  3  -1  2

DP:4  3  -1  2

DP:4  -2  -1  2

DP:4  -2  -4  2

DP:0  -2  -4  2

DP:0  -1  -4  2

DP:-2  -1  -4  2

參考資料:

https://leetcode.com/problems/triangle/

https://leetcode.com/problems/triangle/discuss/38730/DP-Solution-for-Triangle

https://leetcode.com/problems/triangle/discuss/38918/C%2B%2B-top-down-and-bottom-up-solutions.

到此這篇關于C++實現(xiàn)LeetCode(120.三角形)的文章就介紹到這了,更多相關C++實現(xiàn)三角形內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • 如何使用visual studio2019創(chuàng)建簡單的MFC窗口(使用C++)

    如何使用visual studio2019創(chuàng)建簡單的MFC窗口(使用C++)

    這篇文章主要介紹了如何使用visual studio2019創(chuàng)建簡單的MFC窗口(使用C++),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-03-03
  • 詳解c++中的類型識別

    詳解c++中的類型識別

    這篇文章主要介紹了 詳解c++中的類型識別,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-06-06
  • C++利用Socket實現(xiàn)主機間的UDP/TCP通信

    C++利用Socket實現(xiàn)主機間的UDP/TCP通信

    這篇文章主要為大家詳細介紹了C++如何利用Socket實現(xiàn)主機間的UDP/TCP通信功能,文中的示例代碼講解詳細,感興趣的小伙伴可以了解一下
    2023-01-01
  • 利用C++實現(xiàn)通訊錄管理系統(tǒng)的完整代碼

    利用C++實現(xiàn)通訊錄管理系統(tǒng)的完整代碼

    通訊錄是一個可以記錄親人、好友信息的工具,下面這篇文章主要給大家介紹了關于利用C++實現(xiàn)通訊錄管理系統(tǒng)的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
    2022-06-06
  • 深入解析C++編程中線程池的使用

    深入解析C++編程中線程池的使用

    這篇文章主要介紹了深入解析C++編程中線程池的使用,包括線程池的封裝實現(xiàn)等內(nèi)容,需要的朋友可以參考下
    2015-11-11
  • C++中抽象類和接口的區(qū)別介紹

    C++中抽象類和接口的區(qū)別介紹

    抽象類(abstract class)和接口(interface)的概念是面向對象設計中常用的概念, 也是比較容易混淆的概念. 在這里, 我提出一種區(qū)分它們的思路
    2013-04-04
  • C++命名空間5種常見用法實例解析

    C++命名空間5種常見用法實例解析

    這篇文章主要介紹了C++命名空間5種常見用法實例解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-06-06
  • C語言 完整游戲項目推箱子詳細代碼

    C語言 完整游戲項目推箱子詳細代碼

    經(jīng)典的推箱子是一個的古老游戲,目的是在訓練你的邏輯思考能力。在一個狹小的倉庫中,要求把木箱放到指定的位置,稍不小心就會出現(xiàn)箱子無法移動或者通道被堵住的情況,所以需要巧妙的利用有限的空間和通道,合理安排移動的次序和位置,才能順利的完成任務
    2021-11-11
  • C++缺省參數(shù)的具體使用

    C++缺省參數(shù)的具體使用

    缺省參數(shù)是聲明或定義函數(shù)時為函數(shù)的參數(shù)指定一個默認值。本文就詳細的介紹了一下C++缺省參數(shù)的具體使用,具有一定的參考價值,感興趣的可以了解一下
    2022-01-01
  • C++?多維數(shù)組詳解

    C++?多維數(shù)組詳解

    這篇文章主要介紹了C++?獲取數(shù)組大小、多維數(shù)組操作詳解,其實C++中沒有什么多維數(shù)組,所說的多維數(shù)組其實就是數(shù)組的數(shù)組,本文給大家介紹的非常詳細,需要的朋友可以參考下
    2024-04-04

最新評論