文和906

分类

未归档(4) 项目笔记(5) 题解(103)

/ 注册

全部文章（共113篇）

题解 | #二叉树根节点到叶子节点和为指定值的路径#

比较简单的bfs遍历，最开始写完之后卡在第13个用例没通过，看了半天代码没发现原因。最后去看了别人的代码，发现每次递归结束之后忘了pop_back()，这就很尴尬。因为在递归中是用同一个数组来记录路径的，所以在一次递归结束后必须要把该路径上的结点去除，才能用于记录另一路径。 /** * struc...

C++ 深度优先搜索

2021-09-28

0 411

题解 | #表达式求值#

经典的中缀表达式求值。常用思路，将其转为后缀表达式，边转边求值。后缀表达式的特点，遇到运算符则将前两个数拿出来运算，便于计算机计算。这里简单描述一下算法过程：遍历字符串，当读到的是数字时，直接将其压入数字栈。当读到的是运算符时，若符号栈为空，则直接将其压入符号栈；若符号栈非空，则判断符号栈栈顶的运算...

C++ 栈

2021-09-28

8 685

题解 | #最长回文子串#

比较经典的回文判断题型。由于题目要求时间复杂度为O(n^2)，故考虑较为直接的暴力解法。使用一个二重循环，第一重循环i从数组的第一个元素开始，第二重循环j从数组的最后一个元素开始，每趟循环都判断从i到j是否构成回文，若构成，则直接退出内层循环，在外层更新最大值。当i到j的字符串长度小于最大值时，直接...

C++ 动态规划字符串

2021-09-27

0 456

题解 | #反转字符串#

实际项目直接调用reverse()即可，这里就不偷懒模拟一下。从后向前遍历str即可。 class Solution { public: /** * 反转字符串 * @param str string字符串 * @return string字符串 *...

C++ 字符串

2021-09-27

0 367

题解 | #连续子数组的最大和#

动态规划。使用遍历array的同时，使用array自身来保存当前连续子数组的和，第i趟遍历时查看前i-1项中最大子数组的和，若其小于0，则将第i项的值作为前i项中最大子数组的和，否则将前i-1项最大子数组的和加上第i项的值作为前i项中最大子数组的和。前i项最大子数组的和保存在数组的第i项中。 cla...

C++ 动态规划分治

2021-09-26

0 347

题解 | #寻找第K大#

最开始的想法很简单，直接食用sort()将数组排序，然后直接通过序号取第K大的元素即可。sort()使用的是优化后的快速排序，所以时间复杂度平均为O(nlogn)，空间复杂度为O(logn)。不满足题目要求，此时注意到题目中还特意给出了数组大小n，可能需要用到别的解法才能达到题目要求。 class ...

C++ 快速排序

2021-09-26

0 379

题解 | #实现二叉树先序，中序和后序遍历#

使用递归法实现先序，中序，后序遍历。由于借助了3个辅助队列，空间复杂度为O(3n)，这里较为容易优化，直接在结果数组上修改的话可将空间复杂度降为O(1)。而对树进行了三次递归，所以时间复杂度为O(3n)，基本符合题目要求的O(n)。 class Solution { public: /**...

C++

2021-09-26

0 395

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

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

C++

2021-09-24

0 386

题解 | #最小的K个数#

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

C++ 归并排序

2021-09-23

0 429

Java 对象数据类型与基本数据类型的小坑

Java的数据类型在使用时也容易出现一些不容易被发现的坑。基本数据类型共有八种：int, double, float, long, byte, short, boolean, char。而与之对应的对象数据类型为：Integer, Float, Long, Byte, Short, Boolean,...

Java

2021-09-17

0 465