力扣刷题笔记——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;
}

【本文参考了代码随想录】