python-leetcode 48.括號生成

題目:

數字n代表生成括號的對數,設計一個函數,用于生成所有可能并且有效的括號組合。


方法一:回溯

可以生成所有?2**2n?個?‘(’?和?‘)’?字符構成的序列,然后檢查每一個是否有效即可

為了生成所有序列,我們可以使用遞歸。長度為?n?的序列就是在長度為?n?1?的序列前加一個?‘(’?或?‘)’。

為了檢查序列是否有效,遍歷這個序列,并使用一個變量 balance 表示左括號的數量減去右括號的數量。如果在遍歷過程中 balance 的值小于零,或者結束時 balance 的值不為零,那么該序列就是無效的,否則它是有效的。

可以只在序列仍然保持有效時才添加?‘(’?或?‘)’,通過跟蹤到目前為止放置的左括號和右括號的數目來做到這一點,如果左括號數量不大于?n,我們可以放一個左括號。如果右括號數量小于左括號的數量,我們可以放一個右括號。

class Solution(object):def generateParenthesis(self, n):""":type n: int:rtype: List[str]"""ans=[] #列表,用于存儲所有有效的括號組合def backtrack(S,left,right):  #遞歸回溯函數,當前構造的括號序列,當前左括號的數目,當前右括號的數目if len(S)==2*n:  #長度達到合法括號的序列ans.append(''.join(S))#列表 S 變成字符串,加入列表中returnif left<n:  #當左括號數目不達標時S.append("(")backtrack(S,left+1,right)  #加入左括號后繼續構造S.pop()#遞歸返回后,將最后添加的 ( 移除,恢復原狀(回溯)if right<left:  #只有 right < left 時,才能添加 ),確保括號序列合法S.append(")") #加了一個 ) 之后繼續嘗試構造backtrack(S,left,right+1)S.pop() # 將最后添加的 ) 移除,恢復原狀backtrack([],0,0)return ans

時間復雜度:O(?4*n/n**1/2?),在回溯過程中,每個答案需要?O(n)?的時間復制到答案數組中

空間復雜度:O(n)


方法二:按括號序列的長度遞歸

任何一個括號序列都一定是由?‘(’?開頭,并且第一個?‘(’?一定有一個唯一與之對應的?‘)’,每一個括號序列可以用?(a)b?來表示,其中?a?與?b?分別是一個合法的括號序列(可以為空)。

生成所有長度為?2n?的括號序列,我們定義一個函數?generate(n)?來返回所有可能的括號序列。那么在函數?generate(n)?的過程中:

需要枚舉與第一個?‘(’?對應的?‘)’?的位置?2i+1

遞歸調用?generate(i)?即可計算?a?的所有可能性

遞歸調用?generate(n?i?1)?即可計算?b?的所有可能性

遍歷?a?與?b?的所有可能性并拼接,即可得到所有長度為?2n?的括號序列

為了節省計算時間,在每次?generate(i)?函數返回之前,把返回值存儲起來,下次再調

用?generate(i)?時可以直接返回,不需要再遞歸計算

class Solution(object):def generateParenthesis(self, n):""":type n: int:rtype: List[str]"""if n==0:  #沒有括號對return [""]ans=[]for c in range(n): #讓c在0到n-1之間遍歷,表示把 n 對括號分成兩部分,左部分:c 對括號;右部分n - 1 - c 對括號for left in self.generateParenthesis(c):#遞歸調用自己,求出 c 對括號的所有可能組合,并把結果賦值給 left,相當于生成左部分括號的所有可能情況for right in self.generateParenthesis(n - 1 - c):#生成右部分括號的所有可能情況ans.append('({}){}'.format(left,right)) #負責把 left 和 right 組合return ans

時間復雜度:O(?4*n/n**1/2?)

空間復雜度:O(?4*n/n**1/2?)此方法除答案數組外,中間過程中會存儲與答案數組同樣數量級的臨時數組,是所需要的空間復雜度。

源自力扣官方題解

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/72704.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/72704.shtml
英文地址,請注明出處:http://en.pswp.cn/web/72704.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

TDE透明加密技術:免改造實現華為云ECS中數據庫和文件加密存儲

在數字經濟與云計算深度融合的今天&#xff0c;華為云ECS&#xff08;彈性云服務器&#xff09;已成為企業數字化轉型的核心載體&#xff0c;承載著數據庫、文件存儲、AI訓練等關鍵業務。然而&#xff0c;云上數據安全形勢日益嚴峻&#xff1a;2024年全球云環境勒索攻擊同比激增…

3D點云數據處理中的聚類算法總結

1.歐式聚類&#xff1a; 基于點的空間距離&#xff08;歐幾里得距離&#xff09;來分割點云&#xff0c;將距離較近的點歸為同一簇。 歐式聚類需要的參數&#xff1a;鄰域半徑R,簇的最小點閾值minPts&#xff0c;最大點數閾值maxPts。 實現效率&#xff1a; O(n * log n) 實現…

PCL--點云可視化

用于單個顯示、多個顯示的頭文件<visual_.h> visual_.h #pragma once #include <iostream> #include <thread> #include <pcl/visualization/pcl_visualizer.h>using namespace std::chrono_literals;/********************************************…

火星探測發展概述2025.3.20

一.火星探測歷程 1.1 探索啟蒙 火星探測的啟蒙階段可追溯至20世紀60年代,標志著人類對這顆神秘行星的科學探索正式拉開帷幕。這一時期的標志性事件包括: 1960年10月至1964年11月間,蘇聯和美國進行了6次火星探測嘗試,但均以失敗告終。 1964年11月28日,美國成功發射“水手…

DAPO:一個開源的大規模大型語言模型LLM強化學習系統

推斷擴展賦予了大型語言模型前所未有的推理能力,強化學習作為激發復雜推理的核心技術,清華大學聯合字節提出了解耦片段與動態采樣策略優化(DAPO)算法,并全面開源了一個最先進的大規模強化學習系統,該系統使用Qwen2.5-32B基礎模型在AIME 2024上取得了50分的高分。還開源了…

力扣刷題46. 全排列

46. 全排列 - 力扣&#xff08;LeetCode&#xff09; 使用dfs搜索&#xff0c;查找所有的情況&#xff0c;首先定義所有的鏈表集合list&#xff0c;在定義每一種情況的鏈表res&#xff0c;在主函數中遍歷所有的初始元素&#xff0c;首先初始化res&#xff0c;并且添加到res中&…

Metasploit Framework(MSF)使用教程與命令詳解

Metasploit Framework&#xff08;簡稱MSF&#xff09;是一款功能強大的開源滲透測試工具&#xff0c;廣泛應用于網絡安全領域。它集成了大量的漏洞利用模塊&#xff08;exploits&#xff09;、輔助模塊&#xff08;auxiliary&#xff09;和載荷&#xff08;payloads&#xff0…

【Netty】客戶端功能完善

超時控制 public class RequestTimeoutManager {private final HashedWheelTimer timer new HashedWheelTimer();private final ConcurrentMap<Long, Timeout> pendingRequests new ConcurrentHashMap<>();public void addRequest(long requestId, long timeout…

【鴻蒙開發】Hi3861學習筆記- DS18B20溫度傳感器

00. 目錄 文章目錄 00. 目錄01. DS18B20簡介02. DS18B20引腳及電路03. DS18B20內部結構框圖04. DS18B20內存映射05. 硬件設計06. 軟件設計07. 實驗現象08. 附錄 01. DS18B20簡介 DS18B20 是常用的數字溫度傳感器&#xff0c;其輸出的是數字信號&#xff0c;具有體積小&#xf…

跨境大文件傳輸如何突破延遲與丟包雙重困局

一、行業痛點&#xff1a;跨國傳輸的挑戰 在全球化業務場景中&#xff0c;跨境大文件傳輸常面臨網絡延遲高、丟包率頻發等問題。傳統TCP協議因其“先建聯再傳輸”的機制&#xff0c;在高時延、高丟包環境下效率驟降&#xff0c;導致跨國協作、影視渲染、科研數據共享等場景中傳…

uni-app——計時器和界面交互API

API 基本概要 概念說明 API&#xff08;應用程序接口&#xff09;是預先定義的方法集合&#xff0c;用于實現特定功能。在 uni-app 中&#xff0c;通過全局對象 uni 調用 API&#xff0c;例如 uni.getSystemInfoSync 獲取設備信息。 API 分類與調用規則 事件監聽型 以 on 開…

Dify 升級攻略:從0.15.3邁向1.1.0,元數據管理全攻略!

嘿&#xff0c;小伙伴們&#xff01;今天給大家帶來一個超實用的干貨分享——Dify從0.15.3升級到1.1.0版本的詳細攻略。這次升級不僅帶來了功能上的更新&#xff0c;還特別強化了元數據管理。相信很多小伙伴和我一樣&#xff0c;一直在使用Dify來提升工作效率&#xff0c;但每次…

15.三數之和-力扣(python)

給你一個整數數組 nums &#xff0c;判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i ! j、i ! k 且 j ! k &#xff0c;同時還滿足 nums[i] nums[j] nums[k] 0 。請你返回所有和為 0 且不重復的三元組。 注意&#xff1a;答案中不可以包含重復的三元組。 示例 1&a…

numpy學習筆記14:模擬隨機游走過程

numpy學習筆記14&#xff1a;模擬隨機游走過程 隨機游走是一種數學統計模型&#xff0c;其中的每一步方向和大小都是隨機的。下面使用 NumPy 模擬一維和二維的隨機游走過程&#xff1a; 1.代碼示例 import numpy as np import matplotlib.pyplot as plt plt.rcParams[font.s…

YOLOv11 目標檢測

本文章不再贅述anaconda的下載以及虛擬環境的配置&#xff0c;博主使用的python版本為3.8 1.獲取YOLOv11的源工程文件 鏈接&#xff1a;GitHub - ultralytics/ultralytics: Ultralytics YOLO11 &#x1f680; 直接下載解壓 2.需要自己準備的文件 文件結構如下&#xff1a;紅…

dijkstra算法——47. 參加科學大會

卡碼網:47. 參加科學大會https://kamacoder.com/problempage.php?pid=1047 題目描述 小明是一位科學家,他需要參加一場重要的國際科學大會,以展示自己的最新研究成果。 小明的起點是第一個車站,終點是最后一個車站。然而,途中的各個車站之間的道路狀況、交通擁堵程度以…

Rust語言介紹和猜數字游戲的實現

文章目錄 Rust語言介紹和猜數字游戲的實現cargo是什么使用Rust編寫猜數字 Rust語言介紹和猜數字游戲的實現 Rust語言是一種系統編程語言&#xff0c;核心強調安全性、并發性以及高性能&#xff0c;由類似于C/C的底層控制能力&#xff0c;性能也非常接近&#xff0c;Rust有一些…

Ubuntu下Docker部署Misskey:打造你的去中心化社交平臺

引言 在信息爆炸的時代&#xff0c;人們對于社交平臺的需求日益增長&#xff0c;同時也更加注重數據的隱私和自由。Misskey作為一個開源的去中心化社交平臺&#xff0c;為用戶提供了一個全新的選擇。本文將詳細介紹如何在Ubuntu Linux環境下&#xff0c;利用Docker快速部署Mis…

DeepSeek Chat 自動化交互技術分析

本文將對 DeepSeek Chat 自動化交互腳本進行技術分析&#xff0c;包括代碼結構、實現原理以及關鍵技術點。該腳本使用 Selenium 實現了對 DeepSeek Chat 平臺的自動化登錄和問答功能。 1. 代碼結構概覽 該腳本主要由以下幾個部分組成&#xff1a; 環境準備與依賴導入&#x…

128. Longest Consecutive Sequence

如果n-1存在于數組中&#xff0c;則以n開頭的連續序列可以忽略掉&#xff0c;因為以n-1開頭的連續序列的長度肯定至少比以n開頭的連續序列長1個元素。這是本題的關鍵。然后利用哈希表查詢元素是否在數組中。 class Solution { public:int longestConsecutive(vector<int>…