文章目录 题目描述 思路分析 完整代码 题目描述 给你一个字符串表达式s，请你实现一个基本计算器来计算并返回它的值。注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如eval（)。 示例1：输入：s=“1+1”输出：2 示例2：输入：s="2-1+2"输出：3 示例3：输入：s=“(1+(4+5+2)-3)+(6+8)”输出：23 思路分析 模拟！开始！ 例子：s=“(1+(4+5+2)-3)+(6+8)” 先设几个变量，别问为什么，先记就行。 1.变量res，记录当前括号里的内容总和。比如(4+5+2)那总和就是res=112.变量num，记录当前整体数字，因为要遍...

文章目录 题目描述 思路分析 完整代码 题目描述 给定一个数组A[0,1,…,n-1]，请构建一个数组B[0,1,…,n-1]，其中B[i]的值是数组A中除了下标i以外的元素的积,即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。 思路分析 将所有的数都乘起来得到一个总乘积，然后求第i位就直接除以i就行了，不过可惜了题目要求不能使用除法。 对于i位的数来讲，其值等于0到i-1的乘积，乘以i+1到末尾的乘积。看下图。 所以建立两个数组，一个left，一个right，分别存储每个位置的左边乘积和右边乘积(不包含该位置) 比如示例:[1...

文章目录 题目描述 思路分析 完整代码 题目描述 一个整型数组nums里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 思路分析 题目要求了时间和空间复杂度，就不能暴力和哈希表了。 之前有做个一个题，是在数组中找到仅仅出现了一次的数。那个题的思路是用异或。即A和A异或结果为0。ABABC五个数异或，则结果为C。 给忘了的同学提醒一下： 异或：相同为0，不同为1. 与：双1则1，否则0. 本题是一个数组里有两个只出现了一次的数，那么是否可以将整个数组分组，让两个只出现了一次的数分别在两个分组里？ 分组步...

文章目录 题目描述 思路分析 完整代码 题目描述 给定一个未排序的整数数组nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。 示例1：输入：nums=[100,4,200,1,3,2]输出：4解释：最长数字连续序列是[1,2,3,4]。它的长度为4。 示例2：输入：nums=[0,3,7,2,5,8,4,6,0,1]输出：9 思路分析 要我说，这种题就应该直接暴力，管他超不超时的呢。 正经 1.造哈希表hs，key存当前遍历的数值，value存连续区间的最大长度。2.遍历所给数组nums。 若当前值在哈希...

文章目录 题目描述 思路分析 完整代码 题目描述 给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。 示例1:输入:[“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”,“H”,“I”,“J”,“K”,“L”,“M”]输出:[“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”] 示例2:输入:[“A”,“A”]输出:[] 思路分析 将...

文章目录 题目描述 思路分析 完整代码 题目描述 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。 思路分析 搞什么这种题就很无语啊。 要不是做练习，这题我是做不出来，模拟又超时。 纯纯找规律，不说啥约瑟夫了。 直接上规律。 第一轮是[0,1,2,3,4]，所以是[0,1,2,3,4]这个数组的多个复制。这一轮2删除了。 第二轮...

文章目录 题目描述 思路分析 完整代码 题目描述 请定义一个队列并实现函数max_value得到队列里的最大值，要求函数max_value、push_back和pop_front的均摊时间复杂度都是O(1)。若队列为空，pop_front和max_value需要返回-1 思路分析 单调队列的练习题，主要是实现三个函数，读最大值，压数，取数。 题目要求了时间复杂度是o1，压数，取数都是o1没问题，问题就出在读取最大值这块，正常来讲每次读取最大值都需要扫描列表，时间复杂度肯定On了。 要换一种数据结构解决这个问题，这时候就得用单调队列了。、 直接举例秒懂：当前要操作的函数是[压数1，...

文章目录 题目描述 思路分析 完整代码 题目描述 给定一个数字，我们按照如下规则把它翻译为字符串：0翻译成“a”，1翻译成“b”，……，11翻译成“l”，……，25翻译成“z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。 思路分析 直接动态规划。 1.设置dp含义：dp[i]表示以i为结尾的字符串最多有多少种翻译。 2.看一下递推公式。 假设当前字符串nums=‘123’，那么当遍历到dp[2]时， 当最后两位23是可以翻译的数时：可以选择使用最后一位3来进行翻译，也可以使用最后两位的组合23来翻译.dp[i]=dp[i-1]+dp[i...

文章目录 题目描述 思路分析 完整代码 题目描述 我们把只包含质因子2、3和5的数称作丑数（UglyNumber）。求按从小到大的顺序的第n个丑数。 思路分析 这道题实际上是leetcode主站的丑数2。 暴力会超时啊，我试过了哈哈，测试用例都直接超时了。 动规开始！ 首先递推思想，某个丑数一定是由比他小的丑数乘以2或3或5得到的。且丑数需要从小到大排列，所以也就是说,当前丑数‘x‘乘以2或3或5中的最小值就是下一个丑数。 //下一个最小的丑数一定在n2,n3,n5中。 n2=dp[a]2 n3=dp[b]3 n5=dp[c]5 进而可得到递推公式：dp[i]=min(...

文章目录 题目描述 思路分析 完整代码 题目描述 在一个由‘0’和‘1’组成的二维矩阵内，找到只包含‘1’的最大正方形，并返回其面积。 输入：matrix=[[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]输出：4 思路分析 看了一圈题解，解释的都不太清楚。我来写一个。 这题动规。直接步骤开走。 1.确定dp下标含义： dp[i][j]表示为以i和j为右下角的格子可以组成的正方形的最长边长。 2.递推公式： dp[i][j]=min(dp[i−1]...

文章目录 题目描述 思路分析 完整代码 题目描述 给定一个数组，包含从1到N所有的整数，但其中缺了两个数字。你能在O(N)时间内只用O(1)的空间找到它们吗？以任意顺序返回这两个数字均可。 示例1:输入:[1]输出:[2,3] 示例2:输入:[2,3]输出:[1,4] 思路分析 用数学方法做这个题是最简单的。 根据题意，给定nums的长度为n,则补全之后的数组长度为m=n+2。 补全之后的数组和利用等差数列求和公式来做，((1+m)m)//2。 所以有补全之后的数组总和-未补全的数组总和=缺失的两个数字和。su=((1+m)m)//2-sum(nums) 我们找到缺失数组和的中间...

文章目录 题目描述 思路分析 完整代码 题目描述 给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。 示例：输入：[“cat”,“banana”,“dog”,“nana”,“walk”,“walker”,“dogwalker”]输出：“dogwalker”解释："dogwalker"可由"dog"和"walker"组成。 思路分析 首先上来就需要排序，因为题目要求找到其中最长的单词，所以按照长度进行排序，最长的在前面。长度相同则按照字典序排序。这样...

文章目录 题目描述 思路分析 完整代码 题目描述 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第i个元素代表这n个骰子所能掷出的点数集合中第i小的那个的概率。 思路分析 我读完这道题愣了一会。反应了半天才看懂题。 简单说一下题目，扔1次骰子，则可能的点数，1，2,3，4,5，6。每一种出现的概率就是1/6。所以当扔骰子数n=1时，应该返回[1/6,1/6,1/6,1/6,1/6,1/6] 当n=2的时候，看下面的表。 其实就是统计出投骰子的总和点数，计算出这些点数的出现概率: P(k)=k出...

文章目录 题目描述 思路分析 完整代码 题目描述 给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为1。 上面是由数组[0,1,0,2,1,0,1,3,2,1,2,1]表示的直方图，在这种情况下，可以接6个单位的水（蓝色部分表示水）。 示例:输入:[0,1,0,2,1,0,1,3,2,1,2,1]输出:6 思路分析 观察图片可知，总面积=黑色面积+蓝色面积。 黑色面积很好求，直接sum(所给数组)就行了。蓝色面积是答案。所以问题转化成求图中的总面积。 这个其实也很好处理，我们一层一层的去求就好了。 按照所给示例：height=...

题目在这​​:https://leetcode-cn.com/problems/nim-game/​​ 思路分析: 这是一道比较有意思的题。来简单分析一下，题目中要求，我先手，并且双方的每一步都是最优解。既只要找到一种我能赢的情况，就是我赢。当有1个石头的情况下，我直接拿走。赢。当有2个石头和3个石头的情况下，我直接全拿走，赢。当有4个石头的情况下，无论我拿走几个，对手都可以直接拿完，输。 当有5个石头的情况下，我拿1个，对手拿1个、2个、3个，我拿3个、2个、1个。赢。 当有6个石头的情况下:我拿2个，对手拿1个、2个、3个，我拿3个、2个、1个。赢。 当有7个石头的情况下:我拿3个，对手...