海南省海口市网站建设,怎么评价网站做的好坏,有什么网站可以做试题,触屏网站meta标签⭐作者#xff1a;别动我的饭 ⭐专栏#xff1a;菜鸟刷题 ⭐标语#xff1a;悟已往之不谏#xff0c;知来者之可追 一.一维数组的动态和#xff1a;1480. 一维数组的动态和 - 力扣#xff08;LeetCode#xff09;
描述
给你一个数组 nums 。数组「动态和」的计算公式… ⭐作者别动我的饭 ⭐专栏菜鸟刷题 ⭐标语悟已往之不谏知来者之可追 一.一维数组的动态和1480. 一维数组的动态和 - 力扣LeetCode
描述
给你一个数组 nums 。数组「动态和」的计算公式为runningSum[i] sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。
示例
输入nums [1,2,3,4]
输出[1,3,6,10]
解释动态和计算过程为 [1, 12, 123, 1234] 。解题思路
1.通过观察示例可以发现其实runningSum[0]和nums[0]相等runningSum[1]runningSum[0]nums[1];所以我们可以得到这样一个结论当 i 0时runningSum[i]runningSum[i-1]nums[i];
我可以新开辟一个数组大小和nums一样大将累加的结果存放到这个新开的数组中再返回这个新开辟的数组。
int* runningSum(int* nums, int numsSize, int* returnSize)
{ int*tmp(int*)malloc(sizeof(int)*numsSize);tmp[0]nums[0];for(int i1;inumsSize;i){tmp[i]tmp[i-1]nums[i];}*returnSizenumsSize;return tmp;
}2.直接在原地改变除了第一项不用改变以外后面的每一项元素都是前面元素累加的结果。
int* runningSum(int* nums, int numsSize, int* returnSize)
{for(int i1;inumSize;i){nums[i]nums[i-1];}*returnSizenumsSize;return nums;
}二.搜索插入位置35. 搜索插入位置 - 力扣LeetCode
描述
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。 解题思路
看到说时间复杂度位Olog n就让人想起二分查找算法二分查找虽然强大但是有一个很大的缺陷就是要求被查找的数据必须要有序。正好题目说了是一个排序数组那还不二分走起
int searchInsert(int* nums, int numsSize, int target)
{int begin0;int endnumsSize-1;int mid0;while(beginend){mid(beginend)/2;if(nums[mid]target){beginmid1;}else if(nums[mid]target){endmid-1;}else//相等{return mid;}}return begin;
}关于最后的返回值位于begin左边的数一定小于目标值而在end右边的数一定是大于end的也就是说目标值要么在begin和end的中间要么就在begin和end之间的某个位置插入而最后的结束条件是beginend也就是说这中间只有begin是一直在改变的因此如果最后在数组中找不到这个元素那么它的插位置一定是begin位置 三.搜索旋转排序数组33. 搜索旋转排序数组 - 力扣LeetCode
描述
整数数组 nums 按升序排列数组中的值 互不相同 。
在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]下标 从 0 开始 计数。例如 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target 如果 nums 中存在这个目标值 target 则返回它的下标否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 解题思路
首先映入眼帘的还是O(log n)那么用二分查找吗一看是升序排序数组但是这里又说了会在某个位置旋转一下。好像不能用二分
但是我知道你在等但是在k位置旋转以后仍然是局部有序的。如果中间的数小于最右边的数则右半段是有序的若中间数大于最右边数则左半段是有序的我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内这样就可以确定保留哪一半了
这里只要通过控制下标就可以实现在一个数组内分割出两个数组的目的
int search(int* nums, int numsSize, int target)
{//核心在于只是局部有序int begin0,endnumsSize-1;while(beginend){int mid(beginend)/2;if(nums[mid]target)return mid;//二分查找只能在有序数列中进行所以要判断有序范围一定是局部有序if(nums[mid]nums[end])//说明右边数组有序{//判断一下目标值是否在右边数组中,既然在右边数组那么就要重新调整一下mid的值if(nums[mid]targetnums[end]target)beginmid1;elseendmid-1; }else{//左边数组有序,还要判断一下是否在左边数组中if(nums[mid]targetnums[begin]target)endmid-1;elsebeginmid1;}}//到这里就是找不到return -1;
}四.二进制链表转整数1290. 二进制链表转整数 - 力扣LeetCode
描述
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的 十进制值 链表不为空; 链表的结点总数不超过 30; 每个结点的值不是0就是 1
示例
输入head [1,0,1]
输出5
解释二进制数 (101) 转化为十进制数 (5解题思路
1.建立一个数组然后遍历链表将链表中的值存取到数组中将数组的内容转换成十进制在size-1位置的反而是于二的零次方相乘所以可以得到如下代码 int getDecimalValue(struct ListNode* head){int arr[31];int i0;int flag0;//做标记如果数组中没有1无论链表多长结果都是0while(head!NULL){arr[i]head-val;i;if(head-val1){flag1;}headhead-next;}//将链表中的数值全部提取到数组中,必须要拿到数组的有效长度int sum0;int szi;if(flag0)return 0;else{for(i0;isz;i){if(arr[i]!0){sumpow(2,sz-1-i);}}}return sum;
}2.此外还可以利用位运算第一次就从链表中拿到的那个数其实是二的size-1次方而左移一位就有乘二的效果
int getDecimalValue(struct ListNode* head)
{int sum0;while(head!NULL){sum(sum1)head-val;headhead-next;}return sum;
}人们总是高估短期努力能带来的提升而忽略长期坚持带来的改变。今天是第五天也是第二十题了你还在坚持吗
