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

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

第二天(双指针)

有序数组的平方

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);
}


相关文章
|
25天前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
30 1
|
25天前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
46 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
26天前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
12 0
|
27天前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
29 0
|
15天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
2天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。
|
1天前
|
机器学习/深度学习 算法 芯片
基于GSP工具箱的NILM算法matlab仿真
基于GSP工具箱的NILM算法Matlab仿真,利用图信号处理技术解析家庭或建筑内各电器的独立功耗。GSPBox通过图的节点、边和权重矩阵表示电气系统,实现对未知数据的有效分类。系统使用MATLAB2022a版本,通过滤波或分解技术从全局能耗信号中提取子设备的功耗信息。
|
1天前
|
机器学习/深度学习 算法 5G
基于MIMO系统的SDR-AltMin混合预编码算法matlab性能仿真
基于MIMO系统的SDR-AltMin混合预编码算法通过结合半定松弛和交替最小化技术,优化大规模MIMO系统的预编码矩阵,提高信号质量。Matlab 2022a仿真结果显示,该算法能有效提升系统性能并降低计算复杂度。核心程序包括预编码和接收矩阵的设计,以及不同信噪比下的性能评估。
10 3
|
12天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。