首页 > 编程语言 >每天一算法,脑子不生锈(真押韵)

每天一算法,脑子不生锈(真押韵)

时间:2023-10-11 13:07:09浏览次数:41  
标签:index 押韵 const target nums item 算法 let 生锈


前言

看算法确实会让编码思路有所不同,看完好的方案,就会觉得自己的很low。今年开始尽量每天一道算法题,卷死自己,长期更新

Question

给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。 有效字符串需满足:

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

示例:

示例 1:
输入:s = "()"
输出:true

示例 2:
输入:s = "()[]{}"
输出:true

示例 3:
输入:s = "(]"
输出:false

示例 4:
输入:s = "([)]"
输出:false

示例 5:
输入:s = "{[]}"
输出:true

Answer

思路:对称性符合栈后入先出特性

// const s = '{[()]}'
const s = '()[]{}'
const arr = s.split('')
const obj = {
  "(": ")",
  "[": "]",
  "{": "}"
}
const stack = []
const valdate = data => {
  if (!data || data.length % 2 !== 0) return false
  let isRight = true
  data.split('').forEach(item => {
    if (obj[item]) {
      stack.push(item)
    } else {
      if (!stack.length || obj[stack.pop()] !== item) {
        isRight = false
      }
    }
  })
  if (stack.length) isRight = false
  return isRight
}
console.log(valdate(s)) // true

2023-02-02

Question

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

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

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

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

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

进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?

Answer

const nums = [2, 7, 11, 15], target = 9;
  // const nums = [3, 2, 4], target = 6
  // const nums = [3, 3], target = 6
  // const twoSum = function(nums, target) {
  //   let i = 0
  //   let next
  //   let isFind = false
  //   while(i < nums.length - 1 && !next) {
  //     const current = nums[i]
  //     if (current >= 9) {
  //       i++
  //     } else {
  //       nums.forEach((item, index) => {
  //         if (i !== index && item + current === target) {
  //           next = index
  //         }
  //       })
  //       if (!next) i++
  //     }
  //   }
  //   if (next) {
  //     return [i, next]
  //   }
  // }
  // console.log(twoSum(nums, target))
  // 减少一层循环(时间复杂度)
  var twoSum = function(nums, target) {
    const map = new Map();
    for(let i = 0, len = nums.length;i < len;i++) {
      if(map.has(target - nums[i])) {
          return [map.get(target - nums[i]), i];
      }
      map.set(nums[i], i);
    }
    return [];
  };
  console.log(twoSum(nums, target))

2023-02-03

Question

给定一个字符串 s ,请你找出其中不含有重复字符的 最长连续子字符串 的长度。

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子字符串是 "abc",所以其长度为 3。

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子字符串是 "b",所以其长度为 1。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

输入: s = ""
输出: 0

Answer

// 方便参考,输出连带字符串结果
const s = 'abcabcbb'
// const s = "bbbbb"
// const s = "pwwkew"
// const s = ''
const lengthOfLongestSubstring = (s) => {
  let str = ''
  let index = 0
  let obj = { len: index, str }
  if (!s) return obj
  s.split('').forEach(item => {
    if(str.includes(item)) {
      const { len } = obj
      if (index > len) obj = { len: index, str }
      index = 1
      str = item
    } else {
      str += item
      index++
    }
  })
  return obj
}
const { len, str } = lengthOfLongestSubstring(s)
console.log(len, str)

Question

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

输入:nums = [0]
输出:[[],[0]]

Answer

const nums = [1, 2, 3]
// const subsets = nums => {
//   if (nums.length === 0) return [[]];
//   let resArr = [];
//   backtrack(nums, 0, [], resArr);
//   return resArr;
// };
// function backtrack(nums, index, subArr, resArr) {
//   if (Array.isArray(subArr)) {
//     resArr.push(subArr.slice());
//   }
//   if (index === nums.length) {
//     return;
//   } 
//   for (let i = index; i < nums.length; i++) {
//     subArr.push(nums[i]);
//     backtrack(nums, i + 1, subArr, resArr);
//     subArr.pop();
//   }
// }
// subsets(nums)
const getAllSubsets = nums => nums.reduce(
  (subsets, value) => subsets.concat(
    subsets.map(set => [value,...set])
  ),
[[]]);

console.log(getAllSubsets(nums));

Question

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

输入:strs = ["flower","flow","flight"]
输出:"fl"

输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。

Answer

// 如何减少遍历?这么搞打败不了对手啊
const strs = ["flower","flow","flight"]
// const strs = ["dog","racecar","car"]
// const strs = ["aab123v", 'aab123b', 'aba123a']
const longestCommonPrefix = strs => {
  strs.sort((a, b) => a.length - b.length)
  const [firtst, ...others] = strs
  let s = ''
  let isOver = false
  for(let i = 0; i < firtst.length; i++) {
    others.forEach(item => {
      if (item[i] !== firtst[i]) isOver = true
    })
    if (!isOver) {
      s += firtst[i]
    }
  }
  return s
};
longestCommonPrefix(strs)

感触

坚持是真难哦,工作、生活各种事情忙起来就各种没时间,话说也才搞了一周都坚持不起来了,惜败惜败

标签:index,押韵,const,target,nums,item,算法,let,生锈
From: https://blog.51cto.com/u_14627797/7809088

相关文章

  • 并查集的实现【学习算法】
    并查集的实现【学习算法】前言版权推荐并查集的实现最后前言2023-9-2614:38:02以下内容源自《【学习算法】》仅供学习交流使用版权禁止其他平台发布时删除以下此话本文首次发布于CSDN平台作者是CSDN@日星月云博客主页是禁止其他平台发布时删除以上此话推荐算法讲解056【必备】并......
  • 谈谈"求线段交点"的几种算法(js实现,完整版)
    谈谈"求线段交点"的几种算法(js实现,完整版)"求线段交点"是一种非常基础的几何计算,在很多游戏中都会被使用到. 下面我就现学现卖的把最近才学会的一些"求线段交点"的算法说一说,希望对大家有所帮助. 本文讲的内容都很初级,主要是面向和我一样的初学者,所以请各位算法帝......
  • Java算法之动态规划详解
    ①动态规划动态规划(DynamicProgramming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事......
  • 《算法学习专栏》——DP问题之线性DP
    2023年10月10日更新于2023年10月10日一、前言本栏,为线性DP,题目主要来源日常,目前主要来源于Acwing的提高课。希望以后做到线性DP的题目,也能加进来,不断完善。二、线性DP2.1目前的模型:数字三角形模型最长上升子序列模型2.2目前解决的问题:可以解决路径上的各种值。解决......
  • 基于Qlearning强化学习的路径规划算法matlab仿真
    1.算法运行效果图预览  2.算法运行软件版本MATLAB2022A  3.算法理论概述       路径规划在机器人、自动驾驶等领域中具有重要应用。Q-learning是一种经典的强化学习算法,可以用于解决路径规划问题。本文介绍了基于Q-learning的路径规划算法,该算法可以在未知......
  • 基于扩频的数字视频水印嵌入和检测算法matlab仿真
    1.算法运行效果图预览 2.算法运行软件版本matlab2022a 3.算法理论概述     在MPEG压缩标准中,数据流是以多路复合流的格式存储和传输的。多路复合流由音频流和视频流复合组成。多路复合流的基本单位时包,而一个包由三个组组成。组分为视频组和音频组,在此只介绍视......
  • 算法
    学习道路:通过第一学期的算法学习,顺利成为一名算法竞赛选手。学习目标:通过科学的方式学习算法,向ACM-ICPC(是计算机类竞赛最有含金量的比赛)奖牌冲锋在第二学期参加比赛,比赛中学习,学习中比赛,其中每年能够有多次外出比赛的机会参加的主要赛事(A类赛事或企业认可度高的赛......
  • 搜索算法:线性搜索、二分法
    搜索算法:1.线性搜索:循环遍历,判断是否等于目标值2.二分法:(需要有序)先定一个起点和终点left,right,当left<right时,取中间值mid,如果目标值小于mid,则right=mid-1,反之亦然#线性搜索defaction1(arr,target):foriinarr:ifi==target:print(arr.inde......
  • 浅析森林烟火AI检测算法的应用及场景使用说明
    一、方案背景现有的森林防火监测系统落后,以人工地面巡护、瞭望塔高点巡查为主,存在巡护范围有限、巡护效率低等问题,建立健全的森林防火风险预警体系,实现对森林、林场等场景的全天候智能自动监测、火情预警,及时发现森林火灾并辅助决策,是当前林业管理的重要任务。二、方案概述旭帆......
  • Lnton羚通视频分析算法开发平台建立工地人员入侵,构建工地实名制人员通道系统解决方案
    Lnton羚通的算法算力云平台是一款优秀的解决方案,具有突出的特点。它提供高性能、高可靠性、高可扩展性和低成本的特性,使用户能够高效地执行复杂计算任务。此外,平台还提供丰富的算法库和工具,并支持用户上传和部署自定义算法,提升了平台的灵活性和个性化能力。建筑工地的管理一直以来......