讲道理的豹子说这不是bug

分类

/ 注册

TA的专栏 99篇文章 6人订阅

刷题题解（c++）

96篇文章 900人学习

算法知识总结

3篇文章 859人学习

全部文章（共100篇）

题解 | #寻找峰值# 来自专栏

方法：二分法首先根据题目的条件2和条件3，可以得出一个结论：数组一定能找到峰值。因为数组相邻的元素不会相等，所以相邻的元素一定是有递增或者递减的趋势。如果数组是一个递增数组和递减数组，根据条件2也可以得到：递增数组的峰值是最后一个元素；递减数组的峰值是第一个元素。步骤：1、找到数组的中间元素mid；...

2023-07-06

1 321

题解 | #二维数组中的查找# 来自专栏

方法：线性搜索通过观察二维数组可以发现，左下角的元素是所在列最大的值，是所在行最小的值；右上角的元素是所在列最小的值，是所在行最大的值。如果从左下角或者右上角进行搜索，则一次搜索可以排除一行或者一列的元素。下列以右上角进行搜索：时间复杂度：0(n+m)空间复杂度：o(1) class Solutio...

2023-07-06

1 330

题解 | #旋转数组的最小数字# 来自专栏

方法：二分法题设中的条件：非降序的数组进行旋转。非降序说明数组是升序数组且可能有重复元素。通过观察可以得到：对于一个非降序的数组，取数组的中间元素与数组最右边的元素进行比较，如果中间元素大于最右边元素，最小值一定在中点右侧（不包括中点）；如果中间元素小于最右边元素，最小值一定在中点左侧（包括中点）；...

2023-07-06

1 342

题解 | #二分查找-I# 来自专栏

方法：二分法题设是一个升序且无重复元素的数组，利用二分法能很容易的查找元素。1、获取数组的中间元素，会有三种情况：如果目标值等于中间元素即找到；如果目标值小于中间元素，则目标值在左侧；如果目标值大于中间元素，则目标值在右侧；2、不断的缩小范围，直到最终只剩一个元素，若仍...

2023-07-06

1 345

题解 | #合并k个已排序的链表# 来自专栏

方法一：归并排序利用双指针和分治（递归）的思想来求解可以将问题分解为两个有序链表的合并的小问题，并且不断地向上递归，最终就可以将K个链表按顺序合并到一起。时间复杂度：o(nlogk)；递归有logk层，n为所有链表的总结点数，复杂度为o(nlogk)。空间复杂度：o(logk)，需要logk的递归栈...

2023-07-06

1 387

题解 | #删除有序链表中重复的元素-II# 来自专栏

方法一：双指针求解1、设置一个指针cur指向表头（为了解决表头就是重复元素的情况）；2、若cur->next与cur->next->next是重复元素，将cur->next向后移动直到指向不等于该元素的结点。时间复杂度：o(n)空间复杂度：o(1) class Solutio...

2023-07-02

3 335

题解 | #链表的奇偶重排# 来自专栏

方法一：双指针1、设置两个指针，奇数指针和偶数指针；2、将奇数指针的下一结点为偶数指针的下一个结点；奇数指针移动到下一个结点后，此时将偶数指针的下一个结点设置为奇数指针的下一个结点，移动偶数指针。时间复杂度：o(n)空间复杂度：o(1)，不需要辅助空间 class Solution { publ...

2023-07-02

1 0

题解 | #单链表的排序# 来自专栏

方法一：归并排序1、利用归并排序将链表分而治之，不断地将链表从中间结点拆解为两个链表；2、拆解至单个结点后进行排序，将问题转化为两个排序好的链表融合为一个链表的问题；自下而上递归将两个链表进行融合，最终得到排序后的链表。利用快慢指针得到链表的中间结点时间复杂度：o(nlog2n)，每级划分最坏需要...

2023-07-02

1 251

题解 | #链表相加(二)# 来自专栏

1、将两个链表翻转，方便相加；2、需要考虑相加时的进位问题，以及链表移动到尾部时的情况；3、两个链表都移动到尾部后，还需要考虑最后是否有进位的问题，如果有进位则需要多增加一个结点，若无则不需要增加。时间复杂度：o(n)空间复杂度：o(n) class Solution { public: ...

2023-07-01

1 278

题解 | #链表中的节点每k个一组翻转# 来自专栏

1、遍历链表得到链表的长度length；2、得到链表的长度是为了获取链表翻转的次数（length / k），循环翻转链表即可。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: ListNode* reverseKGroup(ListNode* h...

2023-06-29

1 267