【戲玩算法】07-字典
theme: fancy highlight: atom-one-light
持續創作,加速成長!這是我參與「掘金日新計劃 · 6 月更文挑戰」的第11天,點擊查看活動詳情
Hi~,我是一碗周,如果寫的文章有幸可以得到你的青睞,萬分有幸~
🫐 寫在前面
在前面的幾篇文章中,我們學習了棧、隊列、鏈表以及集合,在這篇文章中學習一個新的數據結構——字典。
🍓 什麼是字典
説到字典,第一時間想到的應該就是新華字典,實際上,這跟編程中的字典類似,兩者都有一個特點,就是一一對應(yi yi dui ying),或者説是映射。
字典通常以**【鍵,值】** 對的形成存儲,因為是以鍵值對的形式存儲,更方便通過key
來獲取value
,比如存儲用户信息:
javascript
{
'username': '一碗周',
'age': 18
}
🍋 JavaScript中的字典
在JavaScript中,對象好像擁有字典的所有特點,但是在ES6中新增Map
,用來表示字典,這裏的map不是翻譯成地圖,而是映射。
示例代碼如下:
```javascript // 創建一個字典 const map = new Map()
// 往字典中存儲信息 map.set('username', '一碗周') map.set('age', 18)
console.log(map) // Map(2) { 'username' => '一碗周', 'age' => 18 }
```
🍊 字典的應用
在學習鏈表的時候我們做了一個算法題,是力扣中題號為20的一道題,它的題目:有效的括號,題目大意就是判斷給定字符串中的括號是否匹配,匹配返回true
,否則返回false
。
解題思路如下:
-
判斷字符串的長度是否為偶數,不為偶數直接返回
false
,因為括號都是成對出現的; -
新建一個棧;
-
遍歷字符串,遍歷到每一項時如果時左括號,將其壓入棧;如果是右括號,與棧頂對比,如果相匹配則出棧,不匹配則返回
false
。
我們原來的解法:
```javascript /* * @param {string} s * @return {boolean} / var isValid = function(s) { if (s.length % 2 !== 0) return false
const stack = []
for(let i = 0; i<s.length; i++) {
const c = s[i] // 記錄當前項
if (c === '(' || c === '[' || c==='{') {
stack.push(c)
} else {
const t = stack[stack.length - 1] // 獲取棧頂元素
if (
(t === '(' && c === ')') ||
(t === '[' && c === ']') ||
(t === '{' && c === '}')
) {
stack.pop()
} else {
return false
}
}
}
// 如果為0表示全部匹配,有剩餘則表示不匹配
return stack.length === 0
}; ```
在上面的代碼中,條件判斷中的判斷條件非常的長,這時我們就可以利用字典來優化這個寫法,實現代碼如下:
javascript
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
// 1. 判斷字符串的長度是否為偶數,不為偶數直接返回false,因為括號都是成對出現的;
if (s.length % 2 !== 0) return false
const stack = []
const map = new Map() // 將所有括號的對應關係存儲在字典中
map.set('(', ')')
map.set('[', ']')
map.set('{', '}')
for(let i = 0; i<s.length; i++) {
const c = s[i] // 記錄當前項
// 判斷是否存在 key 也就是左括號,如果存儲,將左括號存儲在棧中
if (map.has(c)) {
stack.push(c)
} else {
const t = stack[stack.length - 1] // 獲取棧頂元素
if (map.get(t) === c) { // 獲取最後一個左括號,判斷是否與右括號匹配
stack.pop() // 出棧
} else {
return false
}
}
}
// 如果為0表示全部匹配,有剩餘則表示不匹配
return stack.length === 0
};
在這個代碼中,我們優化了if
語句中的判斷條件。
🍉 寫在最後
本篇文章到這就結束了\~
本專欄採用JavaScript作為編程語言,從前端的角度去介紹數據結構與算法,如果對你所有幫助,可以點個關注支持一下啊\~
- 用ChatGPT學Nginx是一種什麼體驗
- 【好物分享】分享給前端開發的28個資源(網站、軟件、插件),簡直是提高效率必備
- Vite3.0都來了,你還捲動嗎?(Vite3.0新特性一覽)
- 【好物分享】在命令行讀Markdown,這個感覺太舒服了
- 從0開始使用pnpm構建一個Monorepo方式管理的demo
- 我畫了5張腦圖可以讓你快速入門TypeScript
- 我看着MDN文檔,手寫了幾個數組實例方法
- 淺談JavaScript中的特殊函數
- 如何通過SSH配合VSCode收穫超舒適的遠程開發體驗
- CSS的calc函數不會還有人沒有用吧
- 【戲玩算法】12-圖
- 誰説前端不能搞紅黑樹,用這55張圖拿JS一起手撕紅黑樹
- 簡單總結了10個JavaScript代碼優化小tips
- NaiveUI中看起來沒啥用的組件(文字漸變)實現原來這麼簡單
- 面試官讓我用Flex寫色子佈局,我直接給寫了6個
- Vue3 TS Vite NaiveUI搭建一個項目骨架
- 用一萬多字從頭到尾介紹【函數式編程】
- 這8張腦圖幾乎概括了所有的佈局方案,確定不看看嗎?
- 【戲玩算法】07-字典
- 還在console.log一把梭嗎?console還有其他騷操作