文和906

题解

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

/ 注册

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

题解 | #大数加法#

使用大数加法的常规解法，模拟笔算加法的过程。从字符串末尾开始相加，将相加的结果入栈。计算完后将栈中元素逐次出栈，并添加到结果字符串末端即可。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 ...

C++ 栈

2021-09-29

0 421

题解 | #买卖股票的最好时机#

比较简单的动态规划。用一个变量保存最小值，另一个变量保存最大收益。遍历数组：1.当该数比最小值小时，将其赋给最小值。2.将该数与最小值相减得到该数所能得到的最大收益，若该收益比最大收益大，将其赋给最大收益最终即得最大收益。 class Solution { public: /** ...

C++ 动态规划

2021-09-29

0 318

题解 | #两个链表生成相加链表#

最开始的想法十分简单，读取两个链表，将链表保存的数据转为用int存储，然后相加，再存入结果链表中。代码如下。题目中给出的两个测试用例轻松通过。在我自信满满的点下提交后，第一个用例就没通过。事实证明我还是想的太简单了。 /** * Definition for singly-linked list....

C++ 栈链表

2021-09-29

0 305

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

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

C++ 深度优先搜索

2021-09-28

0 400

题解 | #表达式求值#

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

C++ 栈

2021-09-28

8 669

题解 | #最长回文子串#

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

C++ 动态规划字符串

2021-09-27

0 435

题解 | #反转字符串#

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

C++ 字符串

2021-09-27

0 357

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

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

C++ 动态规划分治

2021-09-26

0 337

题解 | #寻找第K大#

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

C++ 快速排序

2021-09-26

0 368

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

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

C++

2021-09-26

0 387