牛客500979850号

题解

/ 注册

全部文章 / 题解（共33篇）

题解 | #单调栈#

题意：给定一个数组（可含重复值），找到每个元素左边和右边比它小且离它最近的数组位置。方法一：暴力解法解题思路：对于每个元素，都向左和向右找比它小的即可。代码如下： public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可...

C++

2021-10-07

3 337

题解 | #二分查找-I#

题意：给定数组和目标值，利用二分查找在数组中寻找目标值。方法一：解题思路：首先用left和right表示查找范围，用mid=(left+right)/2进行二分查找，如果nums[mid]==target，则直接返回mid；如果nums[mid]>target，则将right更新...

C++

2021-08-24

0 465

题解 | #二叉树的中序遍历#

题意：返回二叉树的中序遍历序列。方法一：递归解题思路：按照左子节点->根->右子节点的顺序，用递归的方式进行遍历。代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定...

2021-08-24

0 348

题解 | #数组中只出现一次的数（其它数出现k次）#

题意：给定一个整数数组和整数，其中数组中有一个数只出现一次，其他数都出现次，求这个只出现一次的数。方法一：解题思路：在为偶数时，将所有数异或就能得到答案，因为偶数个相同数异或结果为，最终只留下了要求的数，时间复杂度，空间复杂度。在为奇数时，若利用计数的方式来求答案，那么空间复杂度会来...

2021-08-12

0 419

题解 | #牛牛的数列#

题意：给定一个整数序列，取一个连续的子序列，要求满足：最多改变一个数，使该子序列严格上升。方法一：解题思路：遍历数组的元素，记为nums[i]，如果nums[i+1]>nums[i-1]+2的话，无论nums[i]为什么数，那么nums[i-1],nums[i],nums[i+1...

2021-08-06

2 514

题解 | #最长回文子序列#

题意：给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。方法一：动态规划解题思路：求解最长回文子序列，有明显的子问题重叠，使用动态规划，考虑以下最优子结构：（1）dp[i][j]-----序列s[i]-->s[j]的最长回文子序列的长度。（2）dp[i][i]=1（3...

2021-08-04

3 543

题解 | #信封嵌套问题#

题意：给 n 个信封的长度和宽度。如果信封 A 的长和宽都小于信封 B ，那么信封 A 可以放到信封 B 里，请求出信封最多可以嵌套多少层。方法一:动态规划如下方法二中的解题思路,不同之处是在于寻找dp中不小于letters[i][1]的最小值直接简单遍历寻找. class Soluti...

2021-08-04

0 738

题解 | #数的划分#

题意：将整数n划分成k份，每份不能为空，求划分的种数。方法一：回溯法解题思路：分析数划分的规律，n=7，k=3，如图：根据上图我们总结一下此种划分的规律：（1）右边的数大于等于左边的数（2）每一个位置都是从最小可能的数开始增加到最大可能的数。因此按照这种规律可以保证划分的唯一性和完...

2021-07-28

0 534

题解 | #股票(无限次交易)#

题意：给定一个数组代表股票每天价格，最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费），求最多可以赚多少钱。方法一：解题思路：参考题目NC134的解法，利用几个状态变量来记录遍历数组时的状态，动态求得股票的最大收益。定义四个状态变量，分别是firstBuy,...

2021-07-27

0 432

题解 | #股票(无限次交易)#

题意：给定一个数组代某一股票价格，不限股票交易次数，不计算手续费，求最多可以赚多少钱。方法一：贪心解题思路：由于是无限次数交易，因此贪心的策略是：如果后一天的价格高于前一天，就应当加上该差价；否则不变。代码：设置last为前一天的价格，起始值为101，因此股票价格范围是[1,100]...

2021-07-27

0 521