CroMarmot

分类

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

/ 注册

全部文章（共10篇）

二分用法总结（一）

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

C++ 二分查找题解

2022-02-05

0 468

题解 | #二分查找-II#

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

C++ 二分查找

2022-02-05

0 397

题解 | #矩阵元素查找#

矩阵元素查找（二分）题意给一个二维数组,行列分别有序,在数组中找给定的值的位置思路分析考虑一维数组如果数组是一维的,那么有序可以直接二分控制查找的左右坐标对于二维数组考虑考虑把一维的左右坐标,变成二维数组中一个矩形范围的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

题解 | #长度最小的连续子数组#

题意正值数组中,求最短的连续区间,使其区间上值的和大于等于给定值. 限制: 数组长度不大于10510^5105 数组中值不大于10410^4104 方法二分法首先,因为数组元素全为正,那么长度为i的所有区间的和的最大值,一定小于长度为i+1的区间和的最大值. 因此,随着区间长度上升,其区间和最...

C++ 数组二分查找

2022-01-03

0 491

题解 | #求解立方根#

题意不用库,自己实现一个立方根函数限制: 传入的数的绝对值不大于20320^3203 方法二分注意到,一个数的三次方是单调递增函数.单调性的函数可以使用二分每次把猜测的区间二分, 根据其中点三次方的值和要求的值的大小关系,来判断要求的值是在左区间还是右区间以题目的样例数据216为例 ...

C++ 数学二分查找

2021-11-26

0 355

题解 | #Redraiment的走法#

题意给定数组,求其最长严格单调递增子序列的长度限制: 数组长度不大于200 方法计数我们,用一个数组来记录到当前位置的最大长度. 那么更新一个位置时,就是在他之前的所有值小于它的长度中找最长的 len[i]=max{len[j]+1,j<i,val[j]<val[i]}len[i...

C++ 数组二分查找

2021-11-26

0 360

题解 | #合唱队#

题意给定一个数列,问最少删除多少个数,使得数列为先严格单调递增后严格单调递减的数列. 限制:有多组数据,每组数列个数不大于3000 方法双重循环要删除的人最少,就是要留下的人最多,所以我们以要留下的人最多的来思考一个严格单调递增,再严格单调递减的序列,不妨把它拆分成两部分处理. 如果我们能计...

C++ 动态规划数组二分查找

2021-10-24

1 551