LeetCode 力扣官方題解 - 1614. 括號(hào)的最大嵌套深度

題目描述

成都創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供若羌網(wǎng)站建設(shè)、若羌做網(wǎng)站、若羌網(wǎng)站設(shè)計(jì)、若羌網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、若羌企業(yè)網(wǎng)站模板建站服務(wù)，十年若羌做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

如果字符串滿足以下條件之一，則可以稱之為 有效括號(hào)字符串（valid parentheses string ，可以簡(jiǎn)寫為 VPS ）：

類似地，可以定義任何有效括號(hào)字符串 S 的 嵌套深度 depth(S)：

例如：""、"()()"、"()(()())" 都是 有效括號(hào)字符串 （嵌套深度分別為 0、1、2），而 ")(" 、"(()" 都不是 有效括號(hào)字符串 。

給你一個(gè) 有效括號(hào)字符串 s，返回該字符串的 s 嵌套深度 。

示例 1：

示例 2：

提示：

解決方案

對(duì)于括號(hào)計(jì)算類題目，我們往往可以用棧來思考。

遍歷字符串 s，如果遇到了一個(gè)左括號(hào)，那么就將其入棧；如果遇到了一個(gè)右括號(hào)，那么就彈出棧頂?shù)淖罄ㄌ?hào)，與該右括號(hào)匹配。這一過程中的棧的大小的最大值，即為 s 的嵌套深度。

代碼實(shí)現(xiàn)時(shí)，由于我們只需要考慮棧的大小，我們可以用一個(gè)變量 size 表示棧的大小，當(dāng)遇到左括號(hào)時(shí)就將其加一，遇到右括號(hào)時(shí)就將其減一，從而表示棧中元素的變化。這一過程中 size 的最大值即為 s 的嵌套深度

代碼

Python3

C++

Java

Golang

C#

C

JavaScript

復(fù)雜度分析

BY /

本文作者：力扣

Go切片數(shù)組深度解析

Go 中的分片數(shù)組，實(shí)際上有點(diǎn)類似于Java中的ArrayList,是一個(gè)可以擴(kuò)展的數(shù)組，但是Go中的切片由比較靈活，它和數(shù)組很像，也是基于數(shù)組，所以在了解Go切片前我們先了解下數(shù)組。

數(shù)組簡(jiǎn)單描述就由相同類型元素組成的數(shù)據(jù)結(jié)構(gòu), 在創(chuàng)建初期就確定了長(zhǎng)度，是不可變的。

但是Go的數(shù)組類型又和C與Java的數(shù)組類型不一樣， NewArray 用于創(chuàng)建一個(gè)數(shù)組，從源碼中可以看出最后返回的是 Array{}的指針，并不是第一個(gè)元素的指針，在Go中數(shù)組屬于值類型，在進(jìn)行傳遞時(shí)，采取的是值傳遞，通過拷貝整個(gè)數(shù)組。Go語(yǔ)言的數(shù)組是一種有序的struct。

Go 語(yǔ)言的數(shù)組有兩種不同的創(chuàng)建方式，一種是顯示的初始化，一種是隱式的初始化。

注意一定是使用 [...]T 進(jìn)行創(chuàng)建，使用三個(gè)點(diǎn)的隱式創(chuàng)建，編譯器會(huì)對(duì)數(shù)組的大小進(jìn)行推導(dǎo)，只是Go提供的一種語(yǔ)法糖。

其次，Go中數(shù)組的類型，是由數(shù)值類型和長(zhǎng)度兩個(gè)一起確定的。[2]int 和 [3]int 不是同一個(gè)類型，不能進(jìn)行傳參和比較，把數(shù)組理解為類型和長(zhǎng)度兩個(gè)屬性的結(jié)構(gòu)體，其實(shí)就一目了然了。

Go中的數(shù)組屬于值類型，通常應(yīng)該存儲(chǔ)于棧中，局部變量依然會(huì)根據(jù)逃逸分析確定存儲(chǔ)棧還是堆中。

編譯器對(duì)數(shù)組函數(shù)中做兩種不同的優(yōu)化：

在靜態(tài)區(qū)完成賦值后復(fù)制到棧中。

總結(jié)起來，在不考慮逃逸分析的情況下，如果數(shù)組中元素的個(gè)數(shù)小于或者等于 4 個(gè)，那么所有的變量會(huì)直接在棧上初始化，如果數(shù)組元素大于 4 個(gè)，變量就會(huì)在靜態(tài)存儲(chǔ)區(qū)初始化然后拷貝到棧上。

由于數(shù)組是值類型，那么賦值和函數(shù)傳參操作都會(huì)復(fù)制整個(gè)數(shù)組數(shù)據(jù)。

不管是賦值或函數(shù)傳參，地址都不一致，發(fā)生了拷貝。如果數(shù)組的數(shù)據(jù)較大，則會(huì)消耗掉大量?jī)?nèi)存。那么為了減少拷貝我們可以主動(dòng)的傳遞指針呀。

地址是一樣的，不過傳指針會(huì)有一個(gè)弊端，從打印結(jié)果可以看到，指針地址都是同一個(gè)，萬一原數(shù)組的指針指向更改了，那么函數(shù)里面的指針指向都會(huì)跟著更改。

同樣的我們將數(shù)組轉(zhuǎn)換為切片，通過傳遞切片，地址是不一樣的，數(shù)組值相同。

切片是引用傳遞，所以它們不需要使用額外的內(nèi)存并且比使用數(shù)組更有效率。

所以，切片屬于引用類型。

通過這種方式可以將數(shù)組轉(zhuǎn)換為切片。

中間不加三個(gè)點(diǎn)就是切片,使用這種方式創(chuàng)建切片，實(shí)際上是先創(chuàng)建數(shù)組，然后再通過第一種方式創(chuàng)建。

使用make創(chuàng)建切片，就不光編譯期了，make創(chuàng)建切片會(huì)涉及到運(yùn)行期。1. 切片的大小和容量是否足夠??；

切片是否發(fā)生了逃逸，最終在堆上初始化。如果切片小的話會(huì)先在?；蜢o態(tài)區(qū)進(jìn)行創(chuàng)建。

切片有一個(gè)數(shù)組的指針，len是指切片的長(zhǎng)度, cap指的是切片的容量。

cap是在初始化切片是生成的容量。

發(fā)現(xiàn)切片的結(jié)構(gòu)體是數(shù)組的地址指針array unsafe.Pointer，而Go中數(shù)組的地址代表數(shù)組結(jié)構(gòu)體的地址。

slice 中得到一塊內(nèi)存地址，array[0]或者unsafe.Pointer(array[0])。

也可以通過地址構(gòu)造切片

nil切片：指的unsafe.Pointer 為nil

空切片：

創(chuàng)建的指針不為空，len和cap為空

當(dāng)一個(gè)切片的容量滿了，就需要擴(kuò)容了。怎么擴(kuò)，策略是什么？

如果原來數(shù)組切片的容量已經(jīng)達(dá)到了最大值，再想擴(kuò)容， Go 默認(rèn)會(huì)先開一片內(nèi)存區(qū)域，把原來的值拷貝過來，然后再執(zhí)行 append() 操作。這種情況對(duì)現(xiàn)數(shù)組的地址和原數(shù)組地址不相同。

從上面結(jié)果我們可以看到，如果用 range 的方式去遍歷一個(gè)切片，拿到的 Value 其實(shí)是切片里面的值拷貝,即淺拷貝。所以每次打印 Value 的地址都不變。

由于 Value 是值拷貝的，并非引用傳遞，所以直接改 Value 是達(dá)不到更改原切片值的目的的，需要通過 slice[index] 獲取真實(shí)的地址。

Go語(yǔ)言web框架Martini怎么輸出嵌套的json數(shù)據(jù)

arshal函數(shù)只有在轉(zhuǎn)換成功的時(shí)候才會(huì)返回?cái)?shù)據(jù)，在轉(zhuǎn)換的過程中我們需要注意幾點(diǎn)：

JSON對(duì)象只支持string作為key，所以要編碼一個(gè)map，那么必須是map[string]T這種類型(T是Go語(yǔ)言中任意的類型)

Channel, complex和function是不能被編碼成JSON的

嵌套的數(shù)據(jù)是不能編碼的，不然會(huì)讓JSON編碼進(jìn)入死循環(huán)

指針在編碼的時(shí)候會(huì)輸出指針指向的內(nèi)容，而空指針會(huì)輸出null