心空之上

分类

/ 注册

全部文章（共68篇）

题解 | #用两个栈实现队列#

基本思路在进队操作时用stack1接收进队元素，在出队操作时将栈中的元素全部推到stack2，实现元素的反序，这样stack2中栈顶弹出的元素就是最先进来的元素，但是有可能出现连续进队后中间有出队再进队的情况，例如stack1进队[2,3]，出队时stack2中元素为[3,2]，将2出队，此时如果没...

2023-08-16

0 357

题解 | #旋转数组的最小数字#

此题二分查找中间值应该和哪个值比较？此题旋转数组中的旋转点将数组分为两个有序部分，左有序部分的元素必然大于右有序部分的所有元素，且最小值在右有序部分。因此我们要将区间定位到右有序部分，并逐渐缩小区间找到最下值。由于右有序部分的最大值为右边界值，因此可以用中间值和右边界值比较，如果中间值大于右边界值，...

2023-05-03

0 223

题解 | #数组中的逆序对#

如何用分治思想统计数组中的逆序对？分治是将较大的问题规模分解成相同结构的规模较小的子问题，再合并子问题的解。此题可以利用归并排序的思想，将原始数组分割成由较小元素的子数组，并统计每个子数组中的逆序对，再统计合并后的数组的逆序对，而分割的两个数组是有序的，在合并时，前面一个数组的某个元素如果大于后面数...

2023-05-03

1 308

题解 | #寻找峰值#

二分查找的本质二分查找的本质是二段性，二分查找的过程本质是对可行区间的压缩，只要满足二段性的问题都可以用二分查找解决。此题的二段性体现在峰值的左边单调增，右边单调减。二分查找的分类左闭右开型：while循环中，left和right之间没有等号，中间值选取为mid=(left+right)/2，中间值...

2023-05-03

0 316

题解 | #二维数组中的查找#

分治思想分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。解法线性搜索：二维矩阵可以用...

2023-05-02

0 201

题解 | #三数之和#

如何用双指针解决三数之和问题？求三个数的和可以转换为两个数的和是否等于第三个数的问题，这样可以遍历数组的每个元素，再看能不能从后面的子数组中找两个元素相加等于这个数，这样就转换为两数之和的问题了。由于题目要求三元组非降序排列，所以可以先将数组排序好，然后再遍历元素，当遍历到某个元素时，设置两个指针指...

2023-05-02

0 282

题解 | #两数之和#

哈希表哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构，而这种直接访问意味着只要知道key就能在O(1)时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。此题如何跟哈希表联系起来？设计一个哈希表，键保存原数组中的值，值保存原数组中对应值的下标，将此题...

2023-05-02

0 243

题解 | #主持人调度（二）#

如何用贪心思想完成最少的主持人调度？利用贪心思想，如果当前活动的开始和结束时间和其他活动的开始结束时间不重合时，这个主持人就可以继续主持活动，如果两个活动时间有交叉则要增派主持人。但是题目给出的活动时间不一定是按时间顺序排列的，同一时间段可能有多个活动。因此需要自己整理好开始时间和结束时间的排序，如...

2023-04-30

1 299

题解 | #分糖果问题#

贪心思想贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。如何使用贪心思想解决分糖果问题利用贪心思想，初始时每个人都获得一个糖果，然后遍历每个人和相邻的人的分数进行比较，如果比周围人的分数高，则糖果数应...

2023-04-30

0 422

题解 | #接雨水问题#

如何用双指针处理接雨水问题？当前柱子能否盛水和桶的高度有关，而桶的高度又由左右两个边界的最少那个决定，因此需要双指针来指向数组的首尾边界。由于柱子能否盛水跟桶的高度有关，所以最短边界的那边才能盛水，因此如果确定了最短边界，就从最短边界那边遍历柱子来确定盛水量，但是如果柱子比边界大就无法盛水了，此时就...

2023-04-27

0 276