有效的括號數據結構oj題(力口20)

目錄

目錄

題目描述

題目分析解析

解決代碼

寫題感悟:


題目描述

還有實例

題目分析解析

對于這個題目,我們首先有效字符串需要滿足什么,第一個左右括號使用相同類型的括號,這好理解,無非就是小括號和小括號大括號和大括號一起匹配。其次第二個就是左括號必須以正確順序來匹配注意了是順序,大家以為就是左括號(小括號)遇到左括號(中括號)然后遇到了右括號(小括號)和右括號(中括號),然而恰恰相反,而是小括號(左)、中括號(右)和中括號(右)小括號(右)相依匹配大致就是遇到第一個右括號時,然后與自己最近的左括號進行匹配,假設匹配成功消除,第二個右括號繼續匹配最近的括號)。最后就是第三個和我們將的第一個差不多,就是和對應的左括號匹配,但是這里主要是限制只有右括號的情況

接下來就是如何解決問題了。

這里我們根據第二個要求,可以知道當遇到右括號時,需要找到與之最近的左括號匹配,通過這個我們就能想到,當遇到右括號時把后進的左括號與之對比看是否滿足相同類型括號。這個后進先出就和我們學過的數據結構棧有關系,所以我們這里需要數據結構棧來寫。將遇到的左括號存入棧中,直到遇到右括號(這里還得考慮是否右括號),判斷是否匹配成功,只要有一個匹配失敗,就說明這個字符串不符合有效字符,以上都符合后,最后判斷棧是否還有左括號,如果沒有則符號題目要求。

解決代碼

//棧結構
typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;
//初始化
void StackInit(ST* Stack)
{Stack->arr = NULL;Stack->capacity = Stack->top = 0;
}//入棧
void StackPush(ST* Stack, STDataType x)
{assert(Stack);//空間不夠if (Stack->capacity == Stack->top){//擴容int newcapacity = Stack->capacity == 0 ? 4 : 2 * Stack->capacity;STDataType* tmp = (STDataType*)realloc(Stack->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc");exit(1);}Stack->arr = tmp;Stack->capacity = newcapacity;}//空間夠Stack->arr[Stack->top++] = x;
}//判斷
bool StackEmpty(ST* Stack)
{assert(Stack);return Stack->arr==NULL;
}//出棧
void StackPop(ST* Stack)
{assert(!StackEmpty(Stack));--Stack->top;
}//獲取棧中元素
STDataType StackTop(ST* Stack)
{assert(!StackEmpty(Stack));return Stack->arr[Stack->top - 1];
}//獲取棧中元素個數
int StackSize(ST* Stack)
{assert(!StackEmpty(Stack));return Stack->top;
}//銷毀棧
void StackDestory(ST* Stack)
{if (Stack->arr)free(Stack->arr);Stack->arr = NULL;Stack->capacity = Stack->top = 0;
}bool isValid(char* s) {ST st;
StackInit(&st);
char* cur = s;
while (*cur != '\0')
{//遇到左括號存入棧if (*cur == '('|| *cur == '['|| *cur == '{'){StackPush(&st, *cur);}//遇到右括號取棧頂元素進行對比else{//內部棧為空時(只有右括號時)if(st.top == 0){return false; }char top = StackTop(&st);if (*cur == ')' && top != '('|| *cur == ']' && top != '['|| *cur == '}' && top != '{'){StackDestory(&st);return false;}StackPop(&st);}cur++;
}
if (!StackSize(&st))
{return true;
}
else
{return false;
}
}

寫題感悟

????????這道題對于初學者的我很難想到盡然會用到數據結構棧,這說明數據結構在刷題過程中發揮著不可磨滅的作用。因此我覺得思路和知識都很重要,當然知識是的重要占大頭,沒有知識就沒有這個思路,就算給你一個思路,也很難實現。我覺得在前期的刷題過程需要刻意取練習,到后面就需要綜合去刷,利用自己學到的知識去解決問題,這個題目告訴我如果遇到先進后出或者后進需要先出類似的題目,首先可以考慮棧。

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

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

相關文章

Mock 單元測試

作者:小凱 沉淀、分享、成長,讓自己和他人都能有所收獲! 本文的宗旨在于通過簡單干凈實踐的方式教會讀者,如何使用 Mock (opens new window)進行工程的單元測試,以便于驗證系統中的獨立模塊功能的健壯性。 從整個工程所…

MySQL 深度性能優化配置實戰指南

?? 一、硬件與系統層優化:夯實性能基石 ??硬件選型策略?? ??CPU??:讀密集型場景選擇多核CPU(如32核);寫密集型場景選擇高主頻CPU(如3.5GHz+)。 ??內存??:建議≥64GB,??緩沖池命中率≥99%?? 是性能關鍵指標。 ??存儲??:??必用NVMe SSD??,I…

Visual Studio Code(VSCode)中設置中文界面

在VS Code中設置中文界面主要有兩種方法:通過擴展市場安裝中文語言包或通過命令面板直接切換語言。?方法一:通過擴展市場安裝中文語言包?打開VS Code,點擊左側活動欄的"擴展"圖標(或按CtrlShiftX)。在搜索…

叉車機器人如何實現托盤精準定位?這項核心技術的原理和應用是什么?

隨著智慧物流和智能制造的加速發展,智能化轉型成為提升效率、降低成本的關鍵路徑,叉車機器人(AGV/AMR叉車)在倉儲、制造、零售等行業中的應用日益廣泛。 其中,托盤定位技術是實現其高效、穩定作業的核心環節之一&…

NO.6數據結構樹|二叉樹|滿二叉樹|完全二叉樹|順序存儲|鏈式存儲|先序|中序|后序|層序遍歷

樹與二叉樹的基本知識 樹的術語結點: 樹中的每個元素都稱為結點, 例如上圖中的 A,B,C…根結點: 位于樹頂部的結點, 它沒有父結點,比如 A 結點。父結點: 若一個結點有子結點, 那么這個結點就稱為其子結點的父…

數據集下載網站

名稱簡介鏈接Kaggle世界上最大的數據科學競賽平臺之一,有大量結構化、圖像、文本等數據集可直接下載?支持一鍵下載、APIPapers with Code可按任務(如圖像分類、文本生成等)查找模型與數據集,標注 SOTA?與論文強關聯Hugging Face…

Tomcat 生產 40 條軍規:容量規劃、調優、故障演練與安全加固

(一)容量規劃 6 條 軍規 1:線程池公式 maxThreads ((并發峰值 平均 RT) / 1000) 冗余 20 %; 踩坑:壓測 2000 QPS、RT 200 ms,理論 maxThreads500,線上卻設 150 導致排隊。軍規 2:…

深入解析 Amazon Q:AWS 推出的企業級生成式 AI 助手

在人工智能助手競爭激烈的當下,AWS 重磅推出的 Amazon Q 憑借其強大的企業級整合能力,正成為開發者提升生產力的新利器。隨著生成式 AI 技術席卷全球,各大云廠商紛紛布局智能助手領域。在 2023 年 re:Invent 大會上,AWS 正式推出了…

物流自動化WMS和WCS技術文檔

導語大家好,我是社長,老K。專注分享智能制造和智能倉儲物流等內容。歡迎大家使用我們的倉儲物流技術AI智能體。新書《智能物流系統構成與技術實踐》新書《智能倉儲項目出海-英語手冊,必備!》完整版文件和更多學習資料,…

Web3.0 實戰項目、簡歷打造、精準投遞+面試準備

目錄 一、獲取真實企業級 Web3.0 項目的 5 種方式 1. 參與開源項目(推薦指數:?????) 2. 參與黑客松(Hackathon) 3. 遠程實習 & DAO 協作項目(兼職也可) 4. Web3 Startup 實戰項目合…

pymongo庫:簡易方式存取數據

文檔 基礎使用 前提:開發機器已安裝mongo配置環境,已啟動服務。 macOS啟動服務:brew services start mongodb-community8.0 macOS停止服務:brew services stop mongodb-community8.0安裝:python3 -m pip install pym…

Java 線程池與多線程并發編程實戰全解析:從異步任務調度到設計模式落地,200 + 核心技巧、避坑指南與業務場景結合

多線程編程在現代軟件開發中扮演著至關重要的角色,它能夠顯著提升應用程序的性能和響應能力。通過合理利用異步線程、多線程以及線程池等技術,我們可以更高效地處理復雜任務,優化系統資源的使用。同時,在實際應用中,我…

gitee 分支切換

ssh-keygen -t rsa -C "pengchengzhangcplaser.com.cn" ssh -T gitgitee.comgit remote add origin 倉庫地址git config --global user.email "youexample.com"git config --global user.name "Your Name"# 1. 更新遠程信息 git fetch origin# …

Vue3生命周期函數

在 Vue 3 中,生命周期鉤子函數是指組件從創建到銷毀的整個過程中,Vue 自動調用的一些特定函數。它們讓你能夠在組件的不同階段執行一些自定義操作。Vue 3 提供了組合式 API 和選項式 API 兩種方式來定義生命周期鉤子。1. onBeforeMount (組合式 API)作用…

基于SEP3203微處理器的嵌入式最小硬件系統設計

目錄 1 引言 2 嵌入式最小硬件系統 3 SEP3202簡述 4 最小系統硬件的選擇和單元電路的設計 4.1 電源電路 4.2 晶振電路 4.3 復位及喚醒電路 4.5 存儲器 4.5.1 FLASH存儲 4.5.2 SDRAM 4.6 串行接口電路設計 4.7 JTAG模塊 4.8 擴展功能(LED) …

【開源軟件推薦】 SmartSub,一個可以快速識別視頻/音頻字幕的工具

背景介紹 我就說Github上面能找到好東西吧 事情是這樣的 我最近在用PC端的剪映剪輯視頻 需要用到它的語音轉字幕功能 轉完之后,導出的時候 發現 赫然有一項字幕識別的會員權益 我尋思看看什么價格 不貴的話就充了 好家伙,這不看不知道&#xff…

自動駕駛仿真領域常見開源工具

自動駕駛仿真領域常見開源工具1、目錄1.1 自動駕駛仿真領域常見開源2、地圖&場景2.1、場景播放器-Esmini4、被測對象-智駕軟件4.1、Autoware4.4、端到端模型-VAD4.5、端到端模型-UniAD4.6、端到端模型-ThinkTwice4.7、端到端模型-TCP5、評價方法5.1、Leaderboard5.2、Bench…

GPU算力租用平臺推薦,價格便宜且有羊毛薅,最低只要0.49/小時!

1.趨動云,這是我近期一直在用的,使用體驗還不錯,推薦給大家 網址:https://platform.virtaicloud.com/gemini_web/auth/register?inviteCode5f74065eac6d8867eac5c82194e2683a 是否選擇一個算力平臺我認為有幾點需要考慮&#xff…

python學智能算法(二十五)|SVM-拉格朗日乘數法理解

引言 前序學習進程中,已經對最佳超平面的求解有了一定認識。 剛好在此梳理一下: 函數距離 首先有函數距離F,也可以稱為函數間隔F: Fmin?i1...myi(w?xib)F \min_{i1...m}y_{i}(w \cdot x_{i}b)Fi1...mmin?yi?(w?xi?b) 幾何距離 然后…

vscode 源碼編譯

windows 環境 下載安裝 build tools Visual Studio Build Tools 勾選 C 因為安裝詳細信息里是 v143,所以單個組件里也要追加兩個 143 的勾選 點擊安裝,安裝好重啟下電腦 Electron 安裝失敗:connect ETIMEDOUT 20.205.243.166:443 為防Ele…