CroMarmot

题解

未归档(12) 题解总结(4)

/ 注册

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

题解 | #最长上升子序列(一)#

最长上升子序列(一) 题意给定一个正整数数组，求它的最长上升子序列的长度方法深搜(TLE) 分析选一个位置开始，作为上升序列的起点，从这个位置向后找比它大的数。以此递归，每次记录长度，并记录所有方案中的最大长度，就是要求的值。变成伪代码就是 dfs(当前位置i,当前上升序列长度cnt):...

C++ 动态规划

2022-02-21

0 340

题解 | #二分查找-II#

二分查找-II（二分）题意在有序数组中,找目标值首次出现的位置. 思路分析找大于等于目标值的值而数组是有序的,可以二分找大于等于目标值的值对于找大于等于目标值的值,可以用lower_bound 找准确的值既然能通过二分找到首个大于等于目标值的值那么如果这个值和目标值相等,则输出下标如...

C++ 二分查找

2022-02-05

0 397

题解 | #丑数#

丑数（广搜）题意找第n个丑数,丑数:只包含2,3,5质因子的数思路分析考虑合法值因为只是2,3,5的倍数,所以合法的值表示为2p23p35p52^{p_2}3^{p_3}5^{p_5}2p23p35p5 从小到大维护从第一个找到第n个,每一次需要找还未找到过的最小值通过set或小...

C++ 广搜广度优先搜索

2022-02-05

0 356

题解 | #矩阵元素查找#

矩阵元素查找（二分）题意给一个二维数组,行列分别有序,在数组中找给定的值的位置思路分析考虑一维数组如果数组是一维的,那么有序可以直接二分控制查找的左右坐标对于二维数组考虑考虑把一维的左右坐标,变成二维数组中一个矩形范围的4个坐标不幸的是,一个子的二位数组,从数值上,并不满足是一段连续...

C++ 二分查找

2022-02-05

0 338

题解 | #在转动过的有序数组中寻找目标值#

在转动过的有序数组中寻找目标值（二分）题意求一个转动过的有序数组中, 找到值的索引思路分析转动的分界点性质因为数组转动过,所以转动的位置一定是左侧大于右侧,而剩余的部分依然保持单调有序分治因为这样的分界点至多有一个考虑这个分界点的位置, [l...m][m+1...r] 如果分界点在左...

C++ 二分查找

2022-02-05

0 431

题解 | #二分查找#

二分查找（二分）题意求一个单调递增数组中,首个出现的大于等于给定值v的位置.下标是1-index 思路分析 C++库函数有库函数直接可以实现 return (lower_bound(a.begin(),a.end(),v) - a.begin()) + 1 ; 数组上单调性质对于数组来说,...

C++ 二分查找

2022-02-05

0 342

题解 | #求平方根#

求平方根（二分）题意求一个整数的平方根,向下取整思路分析题意转换要求x的平方根n向下取整换句话说就是找到n2≤x<(n+1)2n^2 \leq x < (n+1)^2n2≤x<(n+1)2 整数上单调性质对于整数从000到n2n^2n2, 单调递增, 与x的大小关系,...

二分查找 C++

2022-02-05

1 357

题解 | #丢棋子问题#

丢棋子问题（动态规划）题意 n+1层楼,k个棋子,每次扔一个,如果坏了不能重复使用,没有坏可以重复使用,找到最高德不会摔坏层数问最坏情况需要几次思路分析 1个棋子的情况只有一个棋子,摔坏了就没得猜了,只能从低到高反复用 f(i,1) = i; 2个棋子的情况假设选取从j层丢第一个棋子 ...

C++ 动态规划

2022-02-04

0 484

题解 | #子数组的最大累加和问题#

子数组的最大累加和问题（贪心）题意给一个数字数组，求子数组和的最大值思路分析对于长度大于1的任意答案，考虑能否从这个答案眼花出更优的答案如果答案选择数组两端有负数那么把负数去掉，会得到更大的答案，所以两端一定都不是负数如果答案两端外还有正数那么包含这些正数，会得到更大的答案，所以...

C++ 贪心

2022-02-04

0 410

题解 | #买卖股票的最好时机(三)#

买卖股票的最好时机(三)（动态规划）题意数值数组,最多两次买卖,两次买卖不重叠,问最大收益思路分析状态设计主要有数组遍历下标和买卖状态所以不妨设状态为[下标][买的次数][卖的次数]=当前最大收益递推关系注意到两次买卖不重叠,所以卖的次数+1>=买的次数>=卖的次数, 同...

C++ 动态规划

2022-02-04

0 400