力扣刷题笔记——Day1
二分查找
题目描述:给定一个 n
个元素有序的(升序)整型数组 nums
和一个目标值 target
,写一个函数搜索 nums
中的 target
,如果目标值存在返回下标,否则返回 -1
。
eg1:输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4 【解释: 9 出现在 nums 中并且下标为 4】
eg2:输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1 【解释: 2 不存在 nums 中因此返回 -1】
本人做法(基于C语言):
int search(int* nums, int numsSize, int target)
{
int left=0;
int right=(numsSize-1);
int mid=(left+right)/2;
while(left<=right){
mid=(left+right)/2;
if(nums[mid]>target)
{
right=(mid-1);
}
if(nums[mid]==target)
{
return mid;
}
if(nums[mid]<target)
{
left=(mid+1);
}
}
return -1;
}
易错点:①忽略了没有找到target值的情况,即没有最后return -1;
②忽略了最开始的while(left<=right)这一句,这一句是必需的,当left>right的时候就说明已经扫描过一轮了
移除元素
给你一个数组 nums
和一个值 val
,你需要 原地 移除所有数值等于 val
的元素。元素的顺序可能发生改变。然后返回 nums
中与 val
不同的元素的数量。
假设 nums
中不等于 val
的元素数量为 k
,要通过此题,您需要执行以下操作:
- 更改
nums
数组,使nums
的前k
个元素包含不等于val
的元素。nums
的其余元素和nums
的大小并不重要。 - 返回
k
。
本人在暴力解法处卡住了,于是是用下面这种方法做的,就是把不和val相等的值传入nums[j]里面
int removeElement(int* nums, int numsSize, int val) {
int i=0;int j=0;
for(i=0;i<numsSize;i++){
if(nums[i]!=val)
{
nums[j]=nums[i];
j++;
}}
return j;
}
有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100]
- 解释:平方后,数组变为 [16,1,0,9,100],排序后,数组变为 [0,1,9,16,100]
示例 2:输入:nums = [-7,-3,2,3,11] 输出:[4,9,9,49,121]
一开始用的算法性能太差了,就是先把nums各个元素平方,之后冒泡排序处理,结果超时了,而且一开始忽略了要把在函数内部创建数组/指针是存放在临时的栈里的情况,函数结束之后栈就被释放了【返回值是通过复制返回值到调用方的寄存器或内存位置来实现的。对于指向局部变量的指针/引用/数组等情况,不能安全地返回局部变量,否则可能导致未定义行为】
这个是后面自己重新写的代码
int* sortedSquares(int* nums, int numsSize, int* returnSize){
int i=0,j=numsSize-1,k=0;
int* rusult = malloc(numsSize * sizeof(int));
for(k=(numsSize-1);k>=0;k--){
if(nums[i]*nums[i]<nums[j]*nums[j])
{
rusult[k]=nums[j]*nums[j];
j--;
}
else{
rusult[k]=nums[i]*nums[i];
i++;
}
}
*returnSize = numsSize;
return rusult;
}
【本文参考了代码随想录】
原文地址:https://blog.csdn.net/weixin_62514989/article/details/139086975
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!