力扣 (LeetCode)-栈,括号生成｜刷题打卡

谁践踏了优雅 2021-07-24 18:01 315阅读 0赞

Github来源：力扣 (LeetCode)｜刷题打卡 | 求星星 ✨ | 给个❤️关注，❤️点赞，❤️鼓励一下作者

> \[已开启\]任务一：刷题打卡 \* 10 篇

大家好，我是**魔王哪吒**，很高兴认识你~~

哪吒人生信条：**如果你所学的东西 处于喜欢 才会有强大的动力支撑**。

每天学习编程，让你离梦想更新一步，感谢不负每一份热爱编程的程序员，不论知识点多么奇葩，和我一起，让那一颗四处流荡的心定下来，一直走下去，加油，`2021`加油！欢迎关注加我`vx:xiaoda0423`，欢迎点赞、收藏和评论

**时间：3 月 1 日 ～ 3 月 13 日**

*  力扣 (LeetCode)-两数之和,有效的括号,两数相加｜刷题打卡-3月1日
 *  力扣 (LeetCode)-合并两个有序链表,删除排序数组中的重复项,JavaScript笔记｜刷题打卡-3月2日
 *  力扣 (LeetCode)-最大子序和,JavaScript数据结构与算法（数组）｜刷题打卡-3月3日
 *  针对CSS说一说｜技术点评-3月4日

## 前言 ##

如果这篇文章有帮助到你，给个❤️关注，❤️点赞，❤️鼓励一下作者，接收好挑战了吗？文章公众号首发，关注 **程序员哆啦A梦** 第一时间获取最新的文章

❤️笔芯❤️~

### 栈 ###

栈是一种 **后进先出** 的有序集合。新添加或待删除的元素都保存在栈的同一端，叫做栈顶，另外一端叫栈底。

> 创建栈

创建一个类来表示栈：(如何使用Stack类)

function Stack() {
     // 各种属性和方法的声明
    }

声明数组，保存栈里的元素：

let items = []

*  `push()`，添加一个或几个新元素到栈顶
 *  `pop()`，移除栈顶的元素，同时返回被移除的元素
 *  `peek()`，返回栈顶的元素，不对栈做任何修改
 *  `isEmpty()`，如果栈里没有任何元素就返回true，否则返回false
 *  `clear()`，移除栈里的所有元素
 *  `size()`，返回栈里的元素个数

> 向栈添加元素（往栈里添加新元素）

示例：

// 只添加元素到栈顶，也就是栈的末尾
    this.push = function(element) {
     items.push(element);
    });

> 从栈移除元素（移出的是最后添加进去的元素）

示例：

this.pop = function() {
     return items.pop();
    };

> 查看栈顶元素（用于想找到栈里面最后添加的元素是什么）

示例，返回栈顶的元素：

this.peek = function() {
     return items[items.length-1];
    };

> 检查栈是否为空

如果栈为空的话将返回true，否则就返回false。

示例：

this.isEmpty = function() {
     return items.length == 0;
    };

返回栈的长度：

this.size = function() {
     return items.length;
    };

> 清空和打印栈元素

`clear`方法用来移除栈里所有的元素，把栈清空。

this.clear = function() {
     items = [];
    };

把栈里的元素都输出来：

this.print = function() {
     console.log(item.toString());
    };

### 使用Stack类 ###

初始化Stack类：

let stack = new Stack(); 
    console.log(stack.isEmpty()); //输出为true

往栈里添加一些元素

stack.push(1); 
    stack.push(2);

如果调用peek方法，将会输出2

console.log(stack.peek()); //输出2

### 如何用ES6声明Stack类 ###

代码：

// 在类的构造函数constructor里声明, ES6的类是基于原型的。
    class Stack {
     constructor() {
      this.items = [];
     }
     push(element) {
      this.items.push(element);
     }
    }

> 基于原型的类比基于函数的类更节省内存，也更适合创建多个实例，却不能够声明私有属性或方法。

*  用`ES6`的限定作用域`Symbol`实现类

`ES6`新增了一种叫做`Symbol`的基本类型，它是不可变的，可以用作对象的属性。

示例：

// 声明了Symbol类型的变量_items，在类的constructor函数中初始化它的值
    let _items = Symbol();
    
    class Stack {
     constructor() {
      this[_items] = [];
     }
    }

使用`ES6`新增的`Object.getOwnPropertySymbols`方法能够取到类里面声明的所有`Symbols`属性。

let stack = new Stack(); 
    stack.push(2); 
    stack.push(3); 
    let objectSymbols = Object.getOwnPropertySymbols(stack); 
    console.log(objectSymbols.length); // 1 
    console.log(objectSymbols); // [Symbol()]  数组Symbols属性
    console.log(objectSymbols[0]); // Symbol() 
    stack[objectSymbols[0]].push(1); 
    stack.print(); //输出 2, 3, 1

> 访问`stack[objectSymbols[0]]`获得`_items`的，`_items`属性是一个数组，可以进行任意的数组操作。所以不该使用这种方法。

*  `ES6`中的`WeakMap`实现类

使用`WeakMap`确保属性是私有的，`WeakMap`可以存储键值对，其中键是对象，值可以是任意数据类型。

示例：

// 声明了一个WeakMap类型的变量items
    const items = new WeakMap(); // 谁都可以改动它
    
    class Stack { 
     constructor () { 
     // 在constructor中，以this为键，把代表栈的数组存入items
     items.set(this, []);
     } 
     push(element) { 
     // 从WeakMap中取出值，即以this为键从items中取值
     let s = items.get(this);
     s.push(element); 
     } 
     pop() { 
     let s = items.get(this); 
     let r = s.pop(); 
     return r; 
     } 
     //其他方法
    }

> `itmes`在`Stack`类里是真正的所有属性了。

使用闭包：

// 当Stack函数里的构造函数被调用时，会返回Stack类的一个实例
    let Stack = (function () { 
     const items = new WeakMap(); 
     class Stack { 
       constructor () { 
        items.set(this, []); 
       } 
       //其他方法
      }
      return Stack; //当被调用时，会返回Stack类的一个实例
    })();
    // 使用这种方法，扩展类无法继承私有属性

### 十进制转二进制问题算法 ###

示例：

function divideBy2(decNumber){ 
     var remStack = new Stack(), 
     rem, 
     binaryString = ''; 
     while (decNumber > 0){ 
       rem = Math.floor(decNumber % 2);  
       remStack.push(rem); 
       decNumber = Math.floor(decNumber / 2); 
     } 
     while (!remStack.isEmpty()){ 
       binaryString += remStack.pop().toString(); 
     } 
     return binaryString; 
    }

### 十进制转换成任何进制 ###

示例：

function baseConverter(decNumber, base){ 
     var remStack = new Stack(), 
     rem, 
     baseString = '', 
     // 多了digits
     digits = '0123456789ABCDEF'; 
     // 基数
     while (decNumber > 0){ 
     rem = Math.floor(decNumber % base); 
     remStack.push(rem); 
     decNumber = Math.floor(decNumber / base); 
     } 
     
     while (!remStack.isEmpty()){ 
     baseString += digits[remStack.pop()]; 
     } 
     return baseString; 
    }

### 两数之和 ###

解题思路：

*  暴力法
 *  哈希表法

![fce894403790fc6094c89c6491a23ec6.png][]

示例伪代码：

func(nums,target) -> []
    result = []; [0,1] 长度为2
    for i in [0, len(nums)]; // 不动
    for j in [i+1, len(nums)]; // 移动
    sum = nums[i]+nums[j];
    if sm == target;
    result[0] = i
    result[1] = j
    result result

![d4dc7061b93e6bf9b83ac6321a2d99c6.png][]

伪代码：

func(nums, target) -> [];
    result = []
    map = HashTable()
    
    for i in [0, len(nums)];
     map.add(nums[i], i);
    
    for j in [0, len(nums)];
     diff = target - nums[j]
     if(map.containskey(diff) and map.get(diff) != j)
      result[0] = j
      result[1] = map.get(diff)
      return result

### 两数相加 ###

*  迭代法
 *  递归法

![f0bdda568b91da302ef292b658289dce.png][] ![4c0a89c0eff8006011a3c0dad3e0ace4.png][]

伪代码：

func (l1, l2) -> Listnode
    total = 0 // 两个相加的和是多少
    next1 = 0 // 下一个进位
    
    result = ListNode()
    cur = result
    
    while (l1 != null and l2 != null);
    total = l1.val + l2.vale + next1
    
    cur.next = ListNode(total%10)
    next1 = total / 10
    
    l1 = l1.next
    l2 = l2.next
    cur = cur.next
    
    while l1 != null
     total = l1.val + next1
     cur.next = ListNode(total%10)
     nextl = total / 10
     l1 = l1.next
     cur = cur.next
     
    while l2 != null
     total = l2.val + next1
     cur.next = ListNode(total%10)
     next1 = total / 10
     l2 = l2.next
     cur = cur.next
     
    if next1 ! = 0
     cur.next = ListNode(next1)
     return reult.next

递归法：

![6ae32061c5e85a29a4238c053cb55cf0.png][]

伪代码：

func (l1, l2) -> ListNode
     total = l1.val + l2.val
     next1 = total / 10
     res = ListNode(total % 10)
     if( l1.next != null or l2.next != null or next1 != 0 )
      if(l1.next ! = null)
       l1 = l1.next
      else
       l2 = ListNode(0)
       
      if(l2.next != null)
       l2 = l2.next
      else
       l2 = ListNode(0)
       
      l1.val = l1.val + next1
      res.next = fun(l1,l2)
     return res

### 有效的括号 ###

栈的解法：

![1e016cb52f157d8c5d38d63d1dd98423.png][]

var isValid = function (s) {
      let valid = true;
      const stack = [];
      const mapper = {
        "{": "}",
        "[": "]",
        "(": ")",
      };
    
      for (let i in s) {
        const v = s[i];
        if (["(", "[", "{"].indexOf(v) > -1) {
          stack.push(v);
        } else {
          const peak = stack.pop();
          if (v !== mapper[peak]) {
            return false;
          }
        }
      }
    
      if (stack.length > 0) return false;
    
      return valid;
    };

### 合并两个有序链表 ###

*  迭代法
 *  递归法

![f51ee5d0eb7aa8d93455af178ad2278d.png][] ![509bbb02fbd92300e254300aaaefacd7.png][]

/**
     * @param {ListNode} l1
     * @param {ListNode} l2
     * @return {ListNode}
     */
    const mergeTwoLists = function (l1, l2) {
      if (l1 === null) {
        return l2;
      }
      if (l2 === null) {
        return l1;
      }
      if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
      } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
      }
    };

### 22. 括号生成 ###

一、题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
    
    输入：n = 3
    输出：["((()))","(()())","(())()","()(())","()()()"]
    
    示例 2：
    
    输入：n = 1
    输出：["()"]
    
    提示：
    
    1 <= n <= 8

二、思路分析

*  回溯法

![9235567cd4c40d4af514467496cd3fe6.png][] ![169a342a06a64474ee12651aac121370.png][]

伪代码：

fun(n) -> []
     result = []
     backtracking(n,result,0,0, "")
     return result
     backtracking(n,result,left,right,str) -> void
     
     if right > left
     return
     if left == right == n
     result.add(str)
     return
     
     if left<n
     backtracking(n,result,left+1,right,str+"(")
     if right<left
     backtracking(n,result,left,right+1,str+")")

三、答案代码

示例：

/**
     * @param {number} n
     * @return {string[]}
     * @param l 左括号已经用了几个
     * @param r 右括号已经用了几个
     * @param str 当前递归得到的拼接字符串结果
     * @param res 结果集
     */
    const generateParenthesis = function (n) {
      const res = [];
    
      function dfs(l, r, str) {
        if (l == n && r == n) {
          return res.push(str);
        }
        // l 小于 r 时不满足条件 剪枝
        if (l < r) {
          return;
        }
        // l 小于 n 时可以插入左括号，最多可以插入 n 个
        if (l < n) {
          dfs(l + 1, r, str + "(");
        }
        // r < l 时 可以插入右括号
        if (r < l) {
          dfs(l, r + 1, str + ")");
        }
      }
      dfs(0, 0, "");
      return res;
    };

四、总结

> 栈,括号生成分析

### 回看笔者往期高赞文章，也许能收获更多喔！ ###

*  一个合格的初级前端工程师需要掌握的模块笔记
 *  Vue.js笔试题解决业务中常见问题
 *  【初级】个人分享Vue前端开发教程笔记
 *  长篇总结之JavaScript，巩固前端基础
 *  前端面试必备ES6全方位总结
 *  达达前端个人web分享92道JavaScript面试题附加回答
 *  【图文并茂，点赞收藏哦！】重学巩固你的Vuejs知识体系
 *  【思维导图】前端开发-巩固你的JavaScript知识体系
 *  14期-连肝7个晚上，总结了计算机网络的知识点！（共66条）

❤️关注+点赞+收藏+评论+转发❤️，原创不易，鼓励笔者创作更好的文章

### 点赞、收藏和评论 ###

我是`Jeskson`(达达前端)，感谢各位人才的：**点赞、收藏和评论**，我们下期见！(如本文内容有地方讲解有误，欢迎指出☞**谢谢，一起学习了**)

### 我们下期见！ ###

> 文章持续更新，可以微信搜一搜「 **程序员哆啦A梦** 」第一时间阅读，回复【资料】有我准备的一线大厂资料，本文 http://www.dadaqianduan.cn/\#/ 已经收录

> `github`收录，欢迎`Star`：https://github.com/webVueBlog/WebFamily

[fce894403790fc6094c89c6491a23ec6.png]: /images/20210724/aba8ce5d774d4efebaadef84d39dc966.png
[d4dc7061b93e6bf9b83ac6321a2d99c6.png]: /images/20210724/d5977417697342868f6cdee5ee2a5762.png
[f0bdda568b91da302ef292b658289dce.png]: https://img-blog.csdnimg.cn/img_convert/f0bdda568b91da302ef292b658289dce.png
[4c0a89c0eff8006011a3c0dad3e0ace4.png]: /images/20210724/bc2d114e05ed4c839879c2beba05b0b8.png
[6ae32061c5e85a29a4238c053cb55cf0.png]: /images/20210724/689538a15ffb40b4b615f81dff10e0e1.png
[1e016cb52f157d8c5d38d63d1dd98423.png]: /images/20210724/e7e1c4180a5844269fab335e8a334231.png
[f51ee5d0eb7aa8d93455af178ad2278d.png]: https://img-blog.csdnimg.cn/img_convert/f51ee5d0eb7aa8d93455af178ad2278d.png
[509bbb02fbd92300e254300aaaefacd7.png]: /images/20210724/d9132dd04f6a4e869b523aeecdeb474a.png
[9235567cd4c40d4af514467496cd3fe6.png]: https://img-blog.csdnimg.cn/img_convert/9235567cd4c40d4af514467496cd3fe6.png
[169a342a06a64474ee12651aac121370.png]: /images/20210724/1832e9c9a1e84afe8047740510e7408f.png