算法刷题第二天(跑路人笔记)<双指针>

简介: 算法刷题第二天(跑路人笔记)<双指针>

第二天(双指针)

有序数组的平方

977. 有序数组的平方 - 力扣(LeetCode)


image.png


两种方法:第一种暴力=.=没得讲.


第二种:


其实我们把负数进行了平方后负数部分就是降序排列我们的正数部分是升序排列不过怎样都是有序的,我们可以使用类似于归并排序的思想.不过归并排序的思想要求我们两部分都应该是升序或者降序的所以我们将负数部分倒着读取就可以完成归并排序的一次过程了.

int* sortedSquares(int* nums, int numsSize, int* returnSize)
{
    int lin = -1;
    for(int i = 0;i<numsSize;i++)
    {
        if(nums[i] < 0)
        {
            lin = i;
        }
        nums[i] = nums[i]*nums[i];
    }
    int* ret = (int*)malloc(sizeof(int)*numsSize);
    *returnSize = numsSize;
    //用lin分成两部分
    //lin<0时直接nums内全为正确排序
    if(lin<0)
    {
        for(int i = 0;i<numsSize;i++)
        {
            ret[i] = nums[i];
        }
        return ret;
    }
    //lin>=0是用归并排序即可
    int begin1 = 0;
    int end1 = lin;
    int begin2 = lin+1;
    int end2 = numsSize-1;
    int i = 0;
    while(begin1 <= end1 && begin2<=end2)
    {
        if(nums[end1]>nums[begin2])
        {
            ret[i] = nums[begin2];
            begin2++;
            i++;
        }
        else if(nums[end1]<=nums[begin2])
        {
            ret[i] = nums[end1];
            end1--;
            i++;
        }
    }
    while(begin1<=end1)
    {
        ret[i] = nums[end1];
        end1--;
        i++;
    }
    while(begin2<=end2)
    {
        ret[i] = nums[begin2];
        begin2++;
        i++;
    }
    return ret;
}

轮转数组

次次做次次不会=.= 不过这样的题比较偏背一些=.=


既然次次做次次不会,那我就把这道题的两个思路都顺一遍.


189. 轮转数组 - 力扣(LeetCode)


image.png


方法一

再次之前我们可以先将k %= n;因为当k>n的时候轮转其实都是循环.


此方法是经验所得,所以可以背一背=.=


逆置 0~(n-k-1)之间的元素

逆置(n-k)~(n-1)的位置

逆置所有元素.

(记忆法: 只需记住第一步0~(n-k-1)然后逆序第一步没有逆序到的部分再逆序所有即可)


即可使数组向右轮转k个位置.


代码如下图

void reverse(int* nums,int left,int right)
{
  while (left < right)
  {
    int ret = nums[left];
    nums[left] = nums[right];
    nums[right] = ret;
    left++;
    right--;
  }
}
void rotate(int* nums, int numsSize, int k)
{
  k %= numsSize;
    reverse(nums,0,numsSize-k-1);
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);
}

方法二(使用额外数组)

这种方法就很好理解了.


我们将数组向右轮转的时候其实每个元素轮转后的下标都是与k有关的都是(i+k)%(n)—其中i是元素下标


非常好理解,i+k本身就是轮转后的下标位置但是有可能会超出数组空间所以我们要加以限制及%n使用n的原因是因为我们的得到的下标值最大应该是n-1所以%n即可.


代码如下:

void rotate(int* nums, int numsSize, int k)
{
    k%=numsSize;
    int* tmp = (int*)malloc(sizeof(int)*numsSize);
    assert(tmp);
    for(int i =0;i<numsSize;i++)
    {
        tmp[(i+k)%numsSize] = nums[i];
    }
    for(int i =0;i<numsSize;i++)
    {
        nums[i] = tmp [i];
    }
    free(tmp);
}


相关文章
|
1月前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
33 1
|
1月前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
58 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
1月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
13 0
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
31 0
|
5月前
|
C语言
指针进阶(C语言终)
指针进阶(C语言终)
|
1月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
22 0
|
2月前
|
存储 人工智能 C语言
C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
本文详细讲解了C语言中的指针,包括指针变量的定义与引用、指向数组及字符串的指针变量等。首先介绍了指针变量的基本概念和定义格式,随后通过多个示例展示了如何使用指针变量来操作普通变量、数组和字符串。文章还深入探讨了指向函数的指针变量以及指针数组的概念,并解释了空指针的意义和使用场景。通过丰富的代码示例和图形化展示,帮助读者更好地理解和掌握C语言中的指针知识。
|
3月前
|
C语言
【C初阶——指针5】鹏哥C语言系列文章,基本语法知识全面讲解——指针(5)
【C初阶——指针5】鹏哥C语言系列文章,基本语法知识全面讲解——指针(5)
|
3月前
|
C语言
【C初阶——指针4】鹏哥C语言系列文章,基本语法知识全面讲解——指针(4)
【C初阶——指针4】鹏哥C语言系列文章,基本语法知识全面讲解——指针(4)
|
3月前
|
存储 编译器 C语言
【C初阶——指针3】鹏哥C语言系列文章,基本语法知识全面讲解——指针(3)
【C初阶——指针3】鹏哥C语言系列文章,基本语法知识全面讲解——指针(3)