风中的聂鲁达

题解

/ 注册

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

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

动态规划参考题解通过 pos[i] = max(nums[i],max(nums[i]*pos[i-1], nums[i]*neg[i-1])); neg[i] = min(nums[i],min(nums[i]*pos[i-1], nums[i]*neg[i-1])); 可以把数组中负值...

C++ 动态规划

2022-03-13

0 491

题解 | #集合的所有子集(一)#

递归求解求子集时可以先规定一个quota，从1开始直到集合长度，每次只把quota数量的元素压入向量中。代码如下： class Solution { public: vector<vector<int> > subsets(vector<int> &a...

C++ 递归

2022-03-01

0 434

题解 | #括号生成#

递归求解此题想法就是从空字符串开始先填一个 "("，然后下一个可以是 "(" 或者 ")"，当然每有一个 "(" 时，后面都需要对应一个 ")" ，依次往后填充即可。 // 这一句就是限制有一个"("时，后面必然会填充一个")" if(left<right) dfs(str+")",left...

C++ 深度优先搜索递归

2022-03-01

0 374

题解 | #数字字符串转化成IP地址#

递归求解看题解的时候发现的一个容易理解的代码，标记一下，用递归来解决每一次找小于255的数。参考来源 class Solution { public: /** * * @param s string字符串 * @return string字符串vecto...

C++ 递归

2022-02-28

0 484

题解 | #最小花费爬楼梯#

动态规划到达楼顶花费的最小值可以想成从楼顶往下2层或者从楼顶往下1层上来花费的最小值，由此递推，可设dp[i]为从第i楼往上走花费的最小值，则dp[i]的递推式为： dp[i]=min{dp[i−1],dp[i−2]}+cost[i]dp[i] = min \{ dp[i-1],dp[i-2]\}...

C++ 动态规划

2022-02-21

3 559

题解 | #兑换零钱(一)#

动态规划设dp[i]为目标为i时需要的最少货币数，则dp的转移方程为dp[j] = min(dp[j], dp[j-arr[i]]+1)。意思就是说比较当前目标值需要的货币数与当前目标值减去一个货币之后所需货币数加一（因为要达到这个目标值还需要加上这个被减去的货币）。显然目标值为0时，需要的货...

C++ 动态规划

2022-02-14

0 372

题解 | #判断t1树中是否有与t2树完全相同的子树#

递归判断很简单的想法，若root1和root2的值相同，判断root1的左子树和root2的左子树是否一致，以及他们的右子树是否一致；若root1的值和root2的值不一致，判断root1的左子树是否含有root2，或者root1的右子树是否含有root2。代码如下： /** * struct...

C++ 二叉树递归

2022-02-12

0 340

题解 | #判断一个链表是否为回文结构#

用字符串来比较在遍历链表的同时，分别采用头插和尾插的方法构造2个字符串，然后比较这两个字符串是否相等即可。代码如下： /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution ...

C++ 链表字符串

2022-02-12

18 775

题解 | #找到搜索二叉树中两个错误的节点#

C++ 中序遍历因为是一颗搜索二叉树，所以使用中序遍历的话就是对这些数进行从小到大的遍历，其中发生错误的两个点就是一个大的数换到了前面，一个小的数换到了后面。故而，要找出这两个数，思路就是先找到中序遍历中当前节点值小于前一个节点值的节点（类似线索二叉树），它的前一个节点值就是我们要找的换到前面的...

C++ 二叉树

2022-02-10

0 482

题解 | #求平方根#

根据题目要求时间复杂度O(logn)可以知道使用二分法，然后递归是最容易想到的，每次对x都除2，然后根据中点和x的大小关系来判断该往中点下方继续除还是从中点上方除，直到：中点的平方与x相等中点的平方小于x但中点加一的值的平方大于x 既此中点就是x的平方根。需要注意的是中点的平方很大，需要用...

C++ 二分查找

2022-01-29

0 372