力扣 (LeetCode)-两数之和,有效的括号,两数相加

缺乏、安全感 2021-07-24 12:35 316阅读 0赞

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

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

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

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

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

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

## 前言 ##

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

❤️笔芯❤️~

### 1. 两数之和 ###

一、题目描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
    输出：[0,1]
    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
    输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
    输出：[0,1]

二、思路分析：

![e9373af0c11aba0d3732ce7cefd35ac9.png][]

1.  可以遍历所有数字对，双重循环遍历当前值和另一个当前值与目标值是否相等，如果相等返回结果。

三、答案 代码：

输入数组，目标值

// 暴力搜索
    /**
    * @param {number[]} nums
    * @param {number} target
    * @return {number[]}
    */
    var twoSum = function(nums, target) {
     // 暴力枚举
     for (let i = 0; i < nums.length; i++) {
      for (let j = i + 1; j < nums.length; j++) {
       if (nums[i] + nums[j] === target) {
        return [i,j];
       }
      }
     }
    };

// 借助Object对象存储
    var twoSum = function(nums, target) {
     let maps = {};
     for(let i = 0; i < nums.length; i++) {
      var index = nums.indexOf(target-nums[i]
      if(index !== -1 && index !== i) {
       return [i,index]
      }
     }
    };

const twoSum = function(nums, target) {
      const map = new Map();
      for (let i = 0; i < nums.length; i++) {
       const diff = target - nums[i];
       if (map.has(diff)) {
        return [map.get(diff), i];
       }
       map.set(num[i], i);
      }
    }

### 20. 有效的括号 ###

一、题目描述:

给定一个只包括 `'('，')'，'{'，'}'，'['，']'` 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

示例 1：
    
    输入：s = "()"
    输出：true
    示例 2：
    
    输入：s = "()[]{}"
    输出：true
    示例 3：
    
    输入：s = "(]"
    输出：false
    示例 4：
    
    输入：s = "([)]"
    输出：false

二、思路分析

1.  遍历输入字符串
2.  如果当前字符为左半边括号时，则将其压入栈中
3.  如果遇到右半边括号时，分类讨论：

*  如栈不为空且为对应的左半边括号，则取出栈顶元素，继续循环
 *  若此时栈为空，则直接返回false
 *  若不为对应的左半边括号，反之返回false

使用数组来模拟，入为`push`，出为`pop`，即是栈。

入为`push`，出为`shift`，即是队列。

![87e8900013db462c79e2e743ffc981c3.png][] ![84fb2ecc6d3774da1b4e09bfd961e471.png][] ![9307553dd656b7bf87c981cfb8e87b69.png][] ![2341417c437de5238e92df7b0ce4de35.png][] ![d9a40ff33a0be30187f9e3c7c2d62b4d.png][] ![5ea10fbee53e1fed45bcd4b33c2aaa4a.png][]

三、答案代码

var isValid = function (s) {
      while (s.includes("[]") || s.includes("()") || s.includes("{}")) {
        s = s.replace("[]", "").replace("()", "").replace("{}", "");
      }
      s = s.replace("[]", "").replace("()", "").replace("{}", "");
      return s.length === 0;
    };

/**
     * @param {string} s
     * @return {boolean}
     */
    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;
    };

> 匹配的过程，就是出栈的过程

### 2. 两数相加 ###

一、题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：
    输入：l1 = [2,4,3], l2 = [5,6,4]
    输出：[7,0,8]
    解释：342 + 465 = 807.
    
    示例 2：
    输入：l1 = [0], l2 = [0]
    输出：[0]
    
    示例 3：
    输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
    输出：[8,9,9,9,0,0,0,1]

二、思路分析

设立一个表示进位的变量 carried，建立一个新链表，把输入的两个链表从头往后同时处理，每两个相加，将结果加上 carried 后的值作为一个新节点到新链表后面，并更新 carried 值即可。

*  链表这种数据结构的特点和使用
 *  用一个 carried 变量来实现进位的功能，每次相加之后计算 carried，并用于下一位的计算

使用变量跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。每个结点都包含一个数字，并且数字按位逆序存储。

首先取出`“+”`左右两边两个数的最低位，其次求出他们的和并作为输出结果的最低位，并考虑将进位加入代码中，如果值不存在时，将其设置为0，然后再进行相加即可。

let val1 = l1.val
    let val2 = l2.val

三、答案代码

var addTwoNumbers = function (l1, l2) {
      if (l1 === null || l2 === null) return null;
    
      // 使用dummyHead可以简化对链表的处理，dummyHead.next指向新链表
      let dummyHead = new ListNode(0);
      let cur1 = l1;
      let cur2 = l2;
      let cur = dummyHead; // cur用于计算新链表
      let carry = 0; // 进位标志
    
      while (cur1 !== null || cur2 !== null) {
        let val1 = cur1 !== null ? cur1.val : 0;
        let val2 = cur2 !== null ? cur2.val : 0;
        let sum = val1 + val2 + carry;
        let newNode = new ListNode(sum % 10); // sum%10取模结果范围为0~9，即为当前节点的值
        carry = sum >= 10 ? 1 : 0; // sum>=10，carry=1，表示有进位
        cur.next = newNode;
        cur = cur.next;
    
        if (cur1 !== null) {
          cur1 = cur1.next;
        }
    
        if (cur2 !== null) {
          cur2 = cur2.next;
        }
      }
    
      if (carry > 0) {
        // 如果最后还有进位，新加一个节点
        cur.next = new ListNode(carry);
      }
    
      return dummyHead.next;
    };

* @param {ListNode} l1
     * @param {ListNode} l2
     * @return {ListNode}
     */
    var addTwoNumbers = function(l1, l2) {
        let addOne = 0
        let sum = new ListNode('0')
        let head = sum
        while (addOne || l1 || l2) {
            let val1 = l1 !== null ? l1.val : 0
            let val2 = l2 !== null ? l2.val : 0
            let r1 = val1 + val2 + addOne
            addOne = r1 >= 10 ? 1 : 0
            sum.next = new ListNode(r1 % 10)
            sum = sum.next 
            if (l1) l1 = l1.next 
            if (l2) l2 = l2.next 
        }
        return head.next
    };

四、总结：

> 两数之和,有效的括号,两数相加-题解！

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

*  一个合格的初级前端工程师需要掌握的模块笔记
 *  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

关注数：**10亿+** 文章数：**10亿+**  
粉丝量：**10亿+** 点击量：**10亿+**  
 ![44392abc02077a3abd4b9ca3070d2e08.png][]

--------------------

微信群管理员请扫描这里

![fa6035b0b62180c4be61933311d329ee.png][]

微信群管理员请扫描这里

![73806ce0c32f3ca05840f5a2586bc2f9.png][]

喜欢本文的朋友，欢迎关注公众号 **程序员哆啦A梦**，收看更多精彩内容

![98f5bc03bff30a64b8cf596d405cec01.png][]

点个[在看]，是对小达最大的支持！

**如果觉得这篇文章还不错，来个【分享、点赞、在看】三连吧，让更多的人也看到**

[e9373af0c11aba0d3732ce7cefd35ac9.png]: /images/20210724/b58fa02b0c8d4af28ad251a78872427c.png
[87e8900013db462c79e2e743ffc981c3.png]: https://img-blog.csdnimg.cn/img_convert/87e8900013db462c79e2e743ffc981c3.png
[84fb2ecc6d3774da1b4e09bfd961e471.png]: https://img-blog.csdnimg.cn/img_convert/84fb2ecc6d3774da1b4e09bfd961e471.png
[9307553dd656b7bf87c981cfb8e87b69.png]: https://img-blog.csdnimg.cn/img_convert/9307553dd656b7bf87c981cfb8e87b69.png
[2341417c437de5238e92df7b0ce4de35.png]: https://img-blog.csdnimg.cn/img_convert/2341417c437de5238e92df7b0ce4de35.png
[d9a40ff33a0be30187f9e3c7c2d62b4d.png]: https://img-blog.csdnimg.cn/img_convert/d9a40ff33a0be30187f9e3c7c2d62b4d.png
[5ea10fbee53e1fed45bcd4b33c2aaa4a.png]: /images/20210724/1bb9948360124fe598c9ff248a260c57.png
[44392abc02077a3abd4b9ca3070d2e08.png]: /images/20210724/2d6e0a481a7340d28845f11f4cff1e7c.png
[fa6035b0b62180c4be61933311d329ee.png]: /images/20210724/54cd5ceed5cb48b38ca22ca635df0c0a.png
[73806ce0c32f3ca05840f5a2586bc2f9.png]: /images/20210724/7a1ef35bcc9c44afbe7c202022c6866c.png
[98f5bc03bff30a64b8cf596d405cec01.png]: /images/20210724/4a0a4e15519a4ea4bb2ffb097c2dc4e5.png