自学内容网 自学内容网

力扣刷题笔记——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)!