C语言leetcode刷题笔记2

C语言leetcode刷题笔记2

  • 第4题：283.移动零
    • 互换
    • 直接移动
  • 第5题：122.买卖股票的最佳时机‖
    • 递归（超时）
    • 动态规划
    • 贪心算法
  • 第6题：49.字母异位词分组
    • 优化

第4题：283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

互换

void moveZeroes(int* nums, int numsSize) {
    int i,j,temp;
    int count=0;
    while(true){
        count=0;
        for(i=0;i<numsSize-1;i++)
         {
            if(nums[i]==0&&nums[i+1]!=0)
            {
                count++;
                temp =nums[i];
                nums[i]=nums[i+1];
                nums[i+1]=temp;
                

            }

         }
         if(count==0)break;

    }
    
    
}

在这里插入图片描述

void moveZeroes(int* nums, int numsSize) {
    int i,j,temp;
    for(j=1;j<numsSize;j++)
    {
        for(i=0;i<numsSize-1;i++)
         {
            if(nums[i]==0&&nums[i+1]!=0)
            {
                temp =nums[i];
                nums[i]=nums[i+1];
                nums[i+1]=temp;

            }

         }

    }
    
    
}

在这里插入图片描述

直接移动

//建立新数组，把不是0的先放进去，剩下的都是0，再赋值回去
//优化：直接在原来数组上操作
void moveZeroes(int* nums, int numsSize) {
    int count=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]!=0){
            nums[count++]=nums[i];
            
        }
    }
    for(int i=count;i<numsSize;i++)
    {
        nums[count++]=0;

    }
    
}

第5题：122.买卖股票的最佳时机‖

一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

递归（超时）

int maxProfit(int* prices, int pricesSize) {
    int res=0;
    int profit=0;
    if(pricesSize==1)return 0;
//[7,1,5,3,6,4]
    //假设最后一天不卖
    profit=maxProfit(prices, pricesSize-1);
    res=profit>res?profit:res;

    //假设最后一天卖
    //maxProfit([7,1,5,3,6])+4-4
    //maxProfit([7,1,5,3])+4-6
    //...
    //maxProfit([7])+4-1
    for(int i=1;i<pricesSize;i++)
    {
        profit=maxProfit(prices, i)+prices[pricesSize-1]-prices[i-1];
        res=profit>res?profit:res;

    }
    return res;
    
}

在这里插入图片描述
递归次数过多导致超时，建立数组存储数据

动态规划

int maxProfit(int* prices, int pricesSize) {
    if(pricesSize==1)return 0;
    int profits[pricesSize+1];//profits[i]=maxProfit(prices,i);
    profits[1]=0;
    for(int k=2;k<=pricesSize;k++)
    {
        int res=0;
        int profit=0;
        
    //[7,1,5,3,6,4]
        //假设最后一天不卖
        profit=profits[k-1];//maxProfit(prices, pricesSize-1);
        res=profit>res?profit:res;

        //假设最后一天卖
        //maxProfit([7,1,5,3,6])+4-4
        //maxProfit([7,1,5,3])+4-6
        //...
        //maxProfit([7])+4-1
        for(int i=1;i<k;i++)
        {
            profit=profits[i]+prices[k-1]-prices[i-1];
            res=profit>res?profit:res;

        }
        profits[k]=res;
    }
    return profits[pricesSize];
    
}

在这里插入图片描述

贪心算法

//贪心算法 只要涨了就卖
int maxProfit(int* prices, int pricesSize) {
    int to=0;
    for(int i=1;i<pricesSize;i++)
    {
        if(prices[i]>prices[i-1])to+=prices[i]-prices[i-1];

    }
    return to;
    
}

第6题：49.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
 struct pair{
    char * s1;
    char * s1_qsort;
 };
 typedef struct pair Pair;
 int cmp(void *a,void *b)
 {
    return (*(char *)a -  *(char *)b);
    //return ( *(int*)a - *(int*)b );
 }
 int paircmp(void *a,void *b)
 {
    Pair * Pa=(Pair*)a;
    Pair * Pb=(Pair*)b;
    return strcmp(Pa->s1_qsort,Pb->s1_qsort);
 }
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize=0;
    * returnColumnSizes=NULL;
    char***res=NULL;
    Pair * pairs=(Pair *)malloc(sizeof(Pair)*strsSize);

    for(int i=0;i<strsSize;i++)
    {
        pairs[i].s1=strs[i];
        pairs[i].s1_qsort=(char*)malloc(sizeof(char)*(strlen(strs[i])+1));
        strcpy(pairs[i].s1_qsort,pairs[i].s1);
        qsort(pairs[i].s1_qsort,strlen(strs[i]),sizeof(char),cmp);
        
    }
    qsort(pairs,strsSize,sizeof(Pair),paircmp);
    int group=0;//记录最后组坐标
    int index=0;//记录组内坐标
    for(int i=0;i<strsSize;i++)
    {
        if(i==0)
        {
            group=0;
            index=0;
            *returnSize=group+1;//1zu
     
            *returnColumnSizes=(int*)malloc(sizeof(int)*1);
            (*returnColumnSizes)[group]=index+1;
            res=(char***)malloc(sizeof(char**)*(*returnSize));
            res[group]=(char**)malloc(sizeof(char*)*((*returnColumnSizes)[group]));
            res[group][index]=(char*)malloc(sizeof(char)*(strlen(pairs[i].s1)+1));
            strcpy(res[group][index],pairs[i].s1);
            

        }
        else
        {
            if(strcmp(pairs[i-1].s1_qsort,pairs[i].s1_qsort)!=0)//no equal
            {
                group++;
                index=0;
                *returnSize=group+1;//group++
        
                *returnColumnSizes=(int*)realloc(*returnColumnSizes,sizeof(int)*(group+1));
                (*returnColumnSizes)[group]=index+1;
                res=(char***)realloc(res,sizeof(char**)*(group+1));
                res[group]=(char**)malloc(sizeof(char*)*(index+1));
                res[group][index]=(char*)malloc(sizeof(char)*(strlen(pairs[i].s1)+1));
                

            }
            else//equal
            {
                index++;
                (*returnColumnSizes)[group]=index+1;
                res[group]=(char**)realloc(res[group],sizeof(char*)*(index+1));
                res[group][index]=(char*)malloc(sizeof(char)*(strlen(pairs[i].s1)+1));              

            }
            strcpy(res[group][index],pairs[i].s1);

        }
        
        
        
    }


    return res;
}

优化

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
 struct pair{
    char * s1;
    char * s1_qsort;
 };
 typedef struct pair Pair;
 int cmp(void *a,void *b)
 {
    return (*(char *)a -  *(char *)b);
    //return ( *(int*)a - *(int*)b );
 }
 int paircmp(void *a,void *b)
 {
    Pair * Pa=(Pair*)a;
    Pair * Pb=(Pair*)b;
    return strcmp(Pa->s1_qsort,Pb->s1_qsort);
 }
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    int NofG[10000]={0};//记录每组总个数
    int Gs=0,Gc=0;
    *returnSize=0;
    * returnColumnSizes=NULL;
    char***res=NULL;
    Pair * pairs=(Pair *)malloc(sizeof(Pair)*strsSize);

    for(int i=0;i<strsSize;i++)
    {
        pairs[i].s1=strs[i];
        pairs[i].s1_qsort=(char*)malloc(sizeof(char)*(strlen(strs[i])+1));
        strcpy(pairs[i].s1_qsort,pairs[i].s1);
        qsort(pairs[i].s1_qsort,strlen(strs[i]),sizeof(char),cmp);
        
    }
    qsort(pairs,strsSize,sizeof(Pair),paircmp);
    for(int i=0;i<strsSize;i++)
    {
        
        if(i==0)//no equal
        {
            Gc=1;
            
        }
        else
        {
            if(strcmp(pairs[i-1].s1_qsort,pairs[i].s1_qsort)!=0)//no equal
            {
                
                NofG[Gs]=Gc;
                //printf("%d NofG[Gs]=%d\n",i,NofG[Gs]);
                Gc=1;
                Gs++;

            }
            else
            {
                Gc++;

            }
            
            
        }


    }
    NofG[Gs++]=Gc;
    res=(char***)malloc(sizeof(char**)*Gs);
    *returnColumnSizes=(int*)malloc(sizeof(int)*(Gs));
    *returnSize=Gs;
    for(int i=0;i<Gs;i++)
    {
        res[i]=(char**)malloc(sizeof(char*)*(NofG[i]));
        (*returnColumnSizes)[i]=NofG[i];

    }
    
    int group=-1;//记录最后组坐标
    int index=0;//记录组内坐标

    for(int i=0;i<strsSize;i++)
    {
        
            if(i==0||strcmp(pairs[i-1].s1_qsort,pairs[i].s1_qsort)!=0)//no equal
            {
                group++;
                index=0;
            }
            else//equal
            {
                index++;
              
            }
             res[group][index]=(char*)malloc(sizeof(char)*(strlen(pairs[i].s1)+1));  
            strcpy(res[group][index],pairs[i].s1);               
    }
    return res;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/607928.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

分布式事务Seata使用

分布式事务Seata使用

我们要学习seata&#xff0c;首先需要具备如下技术储备&#xff1a; 数据库事务的基本知识&#xff1b;maven工具的使用&#xff1b;熟悉SpringCloudAlibaba技术栈&#xff1b;掌握SpringDataJPA简单使用&#xff1b; 一. Seata基本概念 1.seata是什么 Seata是阿里巴巴中间…
阅读更多...
C++ 动态内存管理

C++ 动态内存管理

例如&#xff1a;动态内存和释放单个数据的存储区 一 用new运算符初始化单个数据的存储区 举例
阅读更多...
pytest + yaml 框架 - 参数化读取文件路径优化

pytest + yaml 框架 - 参数化读取文件路径优化

针对小伙伴提出参数化时读取外部文件&#xff0c;在项目根路径运行没问题&#xff0c;但是进入到项目下子文件夹运行用例&#xff0c;就会找不到文件问题做了优化。 关于参数化读取外部文件相关内容参考前面这篇pytest yaml 框架 -25.参数化数据支持读取外部文件txt/csv/json/…
阅读更多...
LeetCode 257. 二叉树的所有路径

LeetCode 257. 二叉树的所有路径

LeetCode 257. 二叉树的所有路径 1、题目 题目链接&#xff1a;257. 二叉树的所有路径 给你一个二叉树的根节点 root &#xff0c;按 任意顺序 &#xff0c;返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点。 示例 1&#xff1a; 输入&#xff1a;root…
阅读更多...
C++:内存管理

C++:内存管理

C:内存管理 一、C/C内存分布二、C语言中动态内存管理方式&#xff1a;malloc/calloc/realloc/free三、C内存管理方式1.new/delete操作内置类型2.new和delete操作自定义类型 四、operator new与operator delete函数&#xff08;重点&#xff09;五、new和delete的实现原理1.内置…
阅读更多...
Unity曲线插件Dreamteck Splines生成曲线Mesh

Unity曲线插件Dreamteck Splines生成曲线Mesh

一、需求 脱离编辑器&#xff0c;运行时添加点&#xff0c;动态生成管道、线缆等曲线Mesh。 二、Dreamteck Splines简单运用 这方面资料不多&#xff0c;只有官方文档全英参考&#xff0c;而且又介绍得不详细。 2个重要组件介绍&#xff1a; SplineComputer&#xff1a; 最…
阅读更多...
系统运维（虚拟化）

系统运维（虚拟化）

1.VLAN VLAN&#xff08;Virtual Local Area Network&#xff09;即虚拟局域网&#xff0c;是将一个物理的LAN在逻辑上划分成多个广播域的通信技术。 每个VLAN是一个广播域&#xff0c;VLAN内的主机间可以直接通信&#xff0c;而VLAN间则不能直接互通。这样&#xff0c;广播报…
阅读更多...
987: 输出用先序遍历创建的二叉树是否为完全二叉树的判定结果

987: 输出用先序遍历创建的二叉树是否为完全二叉树的判定结果

解法&#xff1a; 一棵二叉树是完全二叉树的条件是&#xff1a; 对于任意一个结点&#xff0c;如果它有右子树而没有左子树&#xff0c;则这棵树不是完全二叉树。 如果一个结点有左子树但是没有右子树&#xff0c;则这个结点之后的所有结点都必须是叶子结点。 如果满足以上条…
阅读更多...
1010: 折半查找的实现

1010: 折半查找的实现

解法&#xff1a; #include<iostream> #include<vector> using namespace std; void solve() {int n;cin >> n;vector<int> vec(n);for (int& x : vec) cin >> x;int x;cin >> x;int l 0, r n-1, cnt 0;while (l < r) {cnt;int…
阅读更多...
Ubuntu22.04下安装kafka_2.12-2.6.0并运行简单实例

Ubuntu22.04下安装kafka_2.12-2.6.0并运行简单实例

目录 一、版本信息 二、安装Kafka 1. 将Kafka安装包移到下载目录中 2. 安装Kafka并确保hadoop用户对Kafka目录有操作权限 三、启动Kafka并测试Kafka是否正常工作 1. 启动Kafka 2. 测试Kafka是否正常工作 一、版本信息 虚拟机产品&#xff1a;VMware Workstation 17 Pro…
阅读更多...
一套C语言开发的 PACS影像系统源码 PACS系统的基本概念、系统业务流程

一套C语言开发的 PACS影像系统源码 PACS系统的基本概念、系统业务流程

PACS系统基本概念 PACS&#xff0c;全称 Picture Archiving and Communication Systems&#xff0c;中文意为影像归档和通信系统。它是应用于医院影像科室的一种系统&#xff0c;主要任务是把日常产生的各种医学影像&#xff08;包括核磁&#xff0c;CT&#xff0c;超声&#…
阅读更多...
Faststone Capture：高效屏幕捕获神器评测【AI写作】

Faststone Capture：高效屏幕捕获神器评测【AI写作】

首先&#xff0c;这篇文章是基于笔尖AI写作进行文章创作的&#xff0c;喜欢的宝子&#xff0c;也可以去体验下&#xff0c;解放双手&#xff0c;上班直接摸鱼~ 按照惯例&#xff0c;先介绍下这款笔尖AI写作&#xff0c;宝子也可以直接下滑跳过看正文~ 笔尖Ai写作&#xff1a;…
阅读更多...
Java毕设之基于SpringBoot的在线拍卖系统

Java毕设之基于SpringBoot的在线拍卖系统

运行环境 开发语言:java 框架:springboot&#xff0c;vue JDK版本:JDK1.8 数据库:mysql5.7(推荐5.7&#xff0c;8.0也可以) 数据库工具:Navicat11 开发软件:idea/eclipse(推荐idea) 系统详细设计 管理员功能模块 管理员登录&#xff0c;管理员通过输入用户名、密码、角色等信…
阅读更多...
AI日报：干翻AI PC!苹果M4芯片首发；GoEnhance可生成粘土风格视频；DeepSeek-V2模型已在魔搭社区开源

AI日报：干翻AI PC!苹果M4芯片首发；GoEnhance可生成粘土风格视频；DeepSeek-V2模型已在魔搭社区开源

欢迎来到【AI日报】栏目!这里是你每天探索人工智能世界的指南&#xff0c;每天我们为你呈现AI领域的热点内容&#xff0c;聚焦开发者&#xff0c;助你洞悉技术趋势、了解创新AI产品应用。 新鲜AI产品点击了解&#xff1a;AIbase - 智能匹配最适合您的AI产品和网站 1、干翻AI …
阅读更多...
Zip压缩归档库-libzip介绍

Zip压缩归档库-libzip介绍

1.简介 libzip是一个C库&#xff0c;用于读取、创建和修改zip格式的压缩文件。它支持从zip文件中读取、写入、添加和删除文件&#xff0c;还支持密码保护的zip文件。libzip是跨平台的&#xff0c;可以在多种操作系统上使用&#xff0c;包括Linux、Windows和macOS。 常用接口介…
阅读更多...
【Ping】Windows 网络延迟测试 ping 、telnet、tcping 工具

【Ping】Windows 网络延迟测试 ping 、telnet、tcping 工具

ping 命令 属于网络层的ICMP协议&#xff0c;只能检查 IP 的连通性或网络连接速度&#xff0c; 无法检测IP的端口状态。 telnet telnet命令&#xff0c;属于应用层的协议&#xff0c;用于远程登录&#xff0c;也可用于检测IP的端口状态。但是功能有限&#xff0c;只能检测一时…
阅读更多...
【OpenHarmony 实战开发】 做一个 loading加载动画

【OpenHarmony 实战开发】 做一个 loading加载动画

本篇文章介绍了如何实现一个简单的 loading 加载动画&#xff0c;并且在文末提供了一个 demo 工程供读者下载学习。作为一个 OpenHarmony 南向开发者&#xff0c;接触北向应用开发并不多。北向开发 ArkUI 老是改来改去&#xff0c;对笔者这样的入门选手来说学习成本其实非常大&…
阅读更多...
网页主题自动适配：网页跟随系统自动切换主题

网页主题自动适配：网页跟随系统自动切换主题

主题切换是网站设计中一个非常有趣的功能&#xff0c;它允许用户在多种预先设计的样式之间轻松切换&#xff0c;以改变网站的视觉表现。最常见的就是白天和黑夜主题的切换&#xff0c;用户可以根据自己的喜好进行设置。 除了让用户手动去切换主题外&#xff0c;如果能够让用户第…
阅读更多...
Vue从入门到实战Day03

Vue从入门到实战Day03

一、生命周期 1. 生命周期四个阶段 思考&#xff1a; ①什么时候可以发送初始化渲染请求&#xff1f; 答&#xff1a;越早越好&#xff0c;在创建阶段后 ②什么时候可以开始操作DOM&#xff1f; 答&#xff1a;至少DOM得渲染出来&#xff0c;在挂载阶段结束后。 Vue生命周…
阅读更多...
Python从0到POC编写--实用小脚本02

Python从0到POC编写--实用小脚本02

爆破脚本&#xff1a; 爆破脚本也是我们经常使用的东西 这里就简单讲讲后台爆破脚本的编写吧 在编写之前&#xff0c;我们先通过访问网站去看看情况 首先我们可以先登录看看 输入账号 admin &#xff0c;密码 12345 后 登录失败&#xff0c;提示 用户名或密码错误 在输入…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站