wordpress 替换图片,优化seo网站西安,产品外包装设计,网站各个阶段推广今日题目#xff1a; 24. 两两交换链表中的节点
题目#xff1a;给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题#xff08;即#xff0c;只能进行节点交换#xff09;
思路…今日题目 24. 两两交换链表中的节点
题目给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换
思路
看了例子考虑一下三个的情况下最后一个是否交换,看这个栗子的情况最后一个不用管那就简单了。 直接for循环i一步走两个凉凉交换即可
图解
代码
class Solution {
public:void swap_node(ListNode* pre, ListNode* p, ListNode* pnext) {ListNode* pnext_next pnext-next;pre-next pnext;pnext-next p;p-next pnext_next;}ListNode* swapPairs(ListNode* head) {if (!head || !head-next)return head;ListNode* dummy (ListNode*)malloc(sizeof(ListNode));dummy-next head;ListNode* pre dummy;ListNode* p head;while (p p-next ) {ListNode* pnext p-next;ListNode* p_next p-next-next;swap_node(pre, p, pnext);pre p;p p_next;}head dummy-next;return head;}
}; 写代码的时候犯了个sb错误代码中使用了 malloc 来分配内存应该使用 free 来释放内存而不是 delete
在 C 中建议尽量避免使用 malloc 和 free而是使用 new 和 delete 运算符来进行内存分配和释放。 本题over 70. 爬楼梯
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
思路
每次你可以爬 1 或 2 个台阶。看到这个就想到了动态规划。
想一下起始条件 一开始没有楼梯1种方法试一下n0结果,expected n to have value from 1 to 45 only如果只有一层n1,此时结果也为1所以两个起始条件n0ans1n1;ans1;
中间过程 假设跳上n级台阶有 ans(n) 种跳法。在所有跳法中最后一步只有两种情况 跳上 1 级或 2 级台阶。 当为 1 级台阶 剩 n−1 个台阶此情况共有 ans(n-1) 种跳法。 当为 2 级台阶 剩 n−2 个台阶此情况共有 ans(n-2) 种跳法。 即 ans(n)为以上两种情况之和即 ans(n) ans(n-1) ans(n-2). 所以代码如下
class Solution {
public:int climbStairs(int n) {vectorintans(n1);ans[0]ans[1]1;for(int i2;in;i){ans[i]ans[i-1]ans[i-2];}return ans[n];}
};
注意
一开始我是按照下面的写法写的结果报错 vectorintans;ans[0]ans[1]1;Line 1037: Char 34: runtime error: applying non-zero offset 4 to null pointer (stl_vector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c/11/bits/stl_vector.h:1046:34
这个问题就是。在使用 vectorint ans; 声明向量后你直接尝试访问 ans[0] 和 ans[1] 来给这两个位置赋值这是不正确的。因为在声明向量后它是空的没有任何元素所以不能直接通过下标访问元素。
为了解决这个问题可以使用 push_back 函数向向量中添加元素或者在声明向量时指定大小。
改正如下 vectorintans(n1);ans[0]ans[1]1; 又over一道题 53. 最大子数组和
题目
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。
思考
首先想到动态规划的方法找转移方程因为需要找连续子数组如果用dp[i]表示i开头的话不如表示结尾这样dp[i]存储的就是连续的和这样dp[i](dp[i-1]nums[i],dp[i]);最后返回最大值.
class Solution {
public:int maxSubArray(vectorint nums) {int nnums.size();vectorint dp(n);dp[0]nums[0];for(int i1;in;i){dp[i]max(dp[i-1]nums[i],nums[i]);}sort(dp.begin(), dp.end());return dp[n-1];}
};
改进
反正都是返回最大值不如直接一个常量max函数搞定。用dp的话开数组排序消耗太大。
首先我们定义一个变量 maxSum 用于存储全局最大子序和另一个变量 currentSum 用于存储当前子序和初始值都设为数组中的第一个元素。
接下来我们遍历数组对于每个元素我们更新 currentSum 为 max(currentSum nums[i], nums[i])这代表着以当前元素结尾的子序列的最大和。然后我们将 maxSum 更新为 max(maxSum, currentSum)这样我们就能不断更新全局最大子序和。
class Solution {
public:int maxSubArray(vectorint nums) {int maxSumnums[0];int currentSum nums[0];for(int i1;inums.size();i){currentSummax(nums[i],currentSumnums[i]);maxSummax(currentSum,maxSum);}return maxSum;}
}; 以上三道题over
