CroMarmot

分类

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

/ 注册

全部文章（共154篇）

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

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

C++ 动态规划

2022-02-21

0 388

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

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

C++ 动态规划

2022-02-21

0 350

二分用法总结（一）

二分用法总结（一）二分是一个加速搜索的工具，对于有序的内容,可以通过二分来改善遍历的低效率,而有序的内容不限定是数字,可以是任何有序的. 二分最常见的解法思路步骤是转化题意发掘其中有序的部分建立顺序标识运算函数f 二分查找有序部分输出结果在更复杂的竞赛中,二分只会是整个题目的一小部分...

C++ 二分查找题解

2022-02-05

0 468

题解 | #二分查找-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

动态规划用法总结（三）

动态规划用法总结（三）动态规划是一个相对高级的工具，有些本身是动态规划的题可以用动态规划以外，当你无法一眼看穿最优解法时，你可以考虑直接使用动态规划。动态规划最常见的解法思路步骤是设计状态设计转移方程对转移方程时间空间优化大多数可以改写为递推边界处理实现优点是，基于状态和状态转...

动态规划题解

2022-02-04

0 391