写点什么

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

用户头像
魔王哪吒
关注
发布于: 2021 年 03 月 02 日
力扣 (LeetCode)-两数之和,有效的括号,两数相加

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


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


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


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


前言


如果这篇文章有帮助到你,给个❤️关注,❤️点赞,❤️鼓励一下作者,接收好挑战了吗?文章公众号首发,关注 程序员哆啦 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]
复制代码


二、思路分析:



  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,即是队列。








三、答案代码


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.vallet 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};
复制代码


四、总结:


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


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


点赞、收藏和评论


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


我们下期见!


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


github收录,欢迎Starhttps://github.com/webVueBlog/WebFamily


发布于: 2021 年 03 月 02 日阅读数: 16
用户头像

魔王哪吒

关注

微信搜:程序员哆啦A梦 2018.05.08 加入

面向JavaScript爱好人员提供:Web前端最新资讯、原创内容、JavaScript、HTML5、Ajax、jQuery、Node.js、Vue.js、React、Angular等一系列教程和经验分享。 博客首发:http://www.dadaqianduan.cn/#/

评论

发布
暂无评论
力扣 (LeetCode)-两数之和,有效的括号,两数相加