文和906

题解

未归档(4) 项目笔记(5)

/ 注册

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

题解 | #合并两个有序的数组#

由于题目未对复杂度做要求，所以采取简单粗暴的直接法，将B数组的值赋给A数据，然后对A数组进行冒泡排序。若要进一步追求高效，则应采用归并排序。 class Solution { public: vector<int> GetLeastNumbers_Solution(vector&...

C++

2021-09-24

0 379

题解 | #最小的K个数#

比较简单粗暴的解法，先将input数组排序，然后直接返回排序后数组的前k位。关于时间复杂度，由于这里用的是冒泡排序所以时间复杂度为O(n^2+k)，n为input长度。而若使用时间复杂度更低的排序方法，如快速排序，则可以达到O(nlogn+k)。此处空间复杂度则小于题目要求，仅为O(k)。 clas...

C++ 归并排序

2021-09-23

0 421

题解 | #在二叉树中找到两个节点的最近公共祖先#

基本思路是通过递归来获取从根结点到目标结点的路径，两个结点的最近公共祖先就是其从根结点开始的路径上最后一个相同的结点。具体实现是用两个栈来记录路径，从根结点开始向下递归，每次都将路径上的结点压栈。最后得到两个保存有路径的栈，对两个栈的栈顶进行比较，相同则记录该结点，并同时进行出栈操作，不同则返回上一...

C++

2021-09-17

0 473

题解 | #最长无重复子数组#

最开始没有使用哈希表，而是直接使用一个变量存储目前子数组的头部位置来记录信息，但是这种做法虽然五个测试用例都能通过，切在提交后也能通过8个用例，但唯独第九个用例无法通过，原因目前仍未确定，尝试修改一些细节，但都无解，希望看出来的大佬可以告知我。有问题的初版代码如下： class Solution {...

C++

2021-09-17

0 395

题解 | #跳台阶#

本题的关键在于对题目信息的提取。青蛙每次跳1阶或2阶，设f(n)表示n阶台阶时青蛙总共可以选择的不同跳法。青蛙第一跳可以选择跳1阶或跳2阶，当青蛙跳1阶时，剩余的情况为f(n-1)，当青蛙跳2阶时，剩余情况为f(n-2)，所以有f(n)=f(n-1)+f(n-2)。这与斐波那契数列的递推式完全一致，...

C++

2021-09-16

0 424

题解 | #求二叉树的层序遍历#

使用递归方法，声明一个全局二维数组来保存遍历结果，以根结点为第0层，每次递归都使层数++，并在对应层数插入结点值。由于结果集最初为空，需要随着层数的加深不断向其中加入新数组。由于使用层数进行插入，所以只需让层数与size进行比较，两者相等则说明层数越界，要想结果集中加入新数组。这里有个小坑，算是...

C++ 广度优先搜索二叉树

2021-09-15

6 845

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

为了满足时间复杂度低于O(n+m)，观察数据结构，发现该数据结构所构成的矩阵，从左下角的点起，右侧的点大于该点，上方的点小于该点，可以通过逐次移动该点来查找目标点。这种做法的时间复杂度最大为O(n+m)。具体实现如下，通过引入两个变量来进行越界检测，引入另外两个变量进行游标控制。 class Sol...

C++ 设计

2021-09-15

0 388

题解 | #二分查找-II#

二分查找，最开始做的时候遇到的一个坑。按照常规解法使用left与right来标志查找位置，当left与right相等时退出查找。查找结点的位置为left+(right-left)/2，当left+(right-left)/2>target时，说明要查找的值在数轴左侧，要使right左移，反之当...

2021-09-13

0 401

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

使用最简单的思路，用一个栈作为输入栈，保存输入数据，另一个栈作为删除栈，在删除时将输入栈的数据依次放入删除栈中，之后删除输入栈的栈底元素，最后还原输入栈。代码如下。 class Solution { public: void push(int node) { stack1.p...

2021-09-13

0 358

题解 | #单链表的排序#

单链表排序，采用最简单的方法，建立一个数组，遍历链表，将每个结点的值存入数组，对数组排序，再将排序后的数组的值依次赋值给每个结点。完整代码如下。 class Solution { public: /** * * @param head ListNode类 the hea...

2021-09-11

0 352