牛客网刷题篇

简介: 牛客网刷题篇

文章目录

表示数值的字符串

替换空格

斐波那契数列

 数字在升序数组中出现的次数

表示数值的字符串

思路:

先trim,去掉字符串开头结尾的空格

.只能出现一次,且只能在e前面出现

e只能出现一次,且出现时前面应有数字

  • -只能出现在开头或e后面

空格,用trim处理,中间有空格时直接当失败返回

用boolean来表示每一个情况是否出现,只写成功的情况

题解:

public boolean isNumeric (String str) {
 
    str = str.trim();
    //用boolean来表示每一个情况是否出现,是否出现一次(用!XXX来判断)
    boolean numFlag = false, dotFlag = false, eFlag = false, plusFlag = false;
    //只写成功的情况
    for(int i = 0; i < str.length(); i++){
        if(str.charAt(i) >= '0' && str.charAt(i) <= '9'){
            numFlag = true;
        }else if(str.charAt(i) == '.' && !dotFlag && !eFlag){
            dotFlag = true;
        }else if((str.charAt(i) == 'e' || str.charAt(i) == 'E') &&
                 !eFlag && numFlag){
            eFlag = true;
            //处理132e这种情况
            numFlag = false;
        }else if((str.charAt(i) == '+' || str.charAt(i) == '-') && 
                 (i == 0 || str.charAt(i-1) == 'e' || str.charAt(i-1) == 'E')){
            //什么也不干
        }else {
            return false;
        }
    }
    return numFlag;
}

替换空格

方法一

思路:先把字符串转换为单个字符

这里让求的是把字符串中的空格替换成%20,其中一种实现方式就是申请一个临时数组,然后再遍历这个字符串的每个字符,如果不是空格就把遍历的字符添加到临时数组中,如果是空格就添加3个字符'%','2','0'分别到临时数组中,最后再把临时数组转化为字符串即可。

public String replaceSpace(String s) {
    int length = s.length();
    char[] array = new char[length * 3];
    int index = 0;
    for (int i = 0; i < length; i++) {
        char c = s.charAt(i);
        if (c == ' ') {
            array[index++] = '%';
            array[index++] = '2';
            array[index++] = '0';
        } else {
            array[index++] = c;
        }
    }
    String newStr = new String(array, 0, index);
    return newStr;
}

时间复杂度:O(n),所有字符都遍历一遍
空间复杂度:O(n),需要一个n*3的数组 

方法二

思路:使用StringBuilder

把字符串中的每个字符一个个添加到StringBuilder中,如果遇到空格就把他换成%20

public String replaceSpace(String s) {
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == ' ')
            stringBuilder.append("%20");
        else
            stringBuilder.append(s.charAt(i));
    }
    return stringBuilder.toString();
}

时间复杂度:O(n),所有字符都遍历一遍
空间复杂度:O(n),StringBuilder需要的空间

斐波那契数列
大家都知道斐波那契数列,现在要求输入一个正整数 n ,请你输出斐波那契数列的第 n 项。

斐波那契数列是一个满足 fib(x)=\left{ \begin{array}{rcl} 1 & {x=1,2}\\ fib(x-1)+fib(x-2) &{x>2}\\ \end{array} \right.fib(x)={1fib(x−1)+fib(x−2)​x=1,2x>2​ 的数列

数据范围:1\leq n\leq 401≤n≤40

要求:空间复杂度 O(1)O(1),时间复杂度 O(n)O(n) ,本题也有时间复杂度 O(logn)O(logn) 的解法

输入描述:

一个正整数n

返回值描述:

输出一个正整数。

方法一

思路:迭代相加(推荐使用)

动态规划算法的基本思想是:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

斐波那契数列初始化第1项与第2项都是1,则根据公式第0项为0,可以按照斐波那契公式累加到第nnn项

具体做法:

1:低于2项的数列,直接返回n

2:初始化第0项,与第1项分别为0,1

3:从第2项开始,逐渐按照公式累加,并更新相加数始终为下一项的前两项

public class Solution {

public int Fibonacci(int n) {
    //从0开始,第0项是0,第一项是1
    if(n <= 1)    
         return n;
     int res = 0;
     int a = 0;
     int b = 1;
     //因n=2时也为1,初始化的时候把a=0,b=1
     for (int i = 2; i <= n; i++){
     //第三项开始是前两项的和,然后保留最新的两项,更新数据相加
         res = (a + b);
         a = b;
         b = res;
     }
    return res;
}

}
方法二

思路:递归

1、当 n < 2时,直接返回 n

2、递归算法:Fibonacci(n-1) + Fibonacci(n-2);

优点,代码简单好写,缺点:慢,会超时 时间复杂度:O(2^n) 空间复杂度:递归栈的空间

public class Solution {

public int Fibonacci(int n) {
    if (n < 2){
        return n;
    }
    
    return Fibonacci(n-1) + Fibonacci(n-2);
}

}
 数字在升序数组中出现的次数
给定一个长度为 n 的非降序数组和一个非负数整数 k ,要求统计 k 在数组中出现的次数

数据范围:0 \le n \le 1000 , 0 \le k \le 1000≤n≤1000,0≤k≤100,数组中每个元素的值满足 0 \le val \le 1000≤val≤100
要求:空间复杂度 O(1)O(1),时间复杂度 O(logn)O(logn)

方法:二分法(推荐使用)

分治即“分而治之”,“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题,子问题继续按照这样划分,直到问题可以被轻易解决;“治”指的是将子问题单独进行处理。经过分治后的子问题,需要将解进行合并才能得到原问题的解,因此整个分治过程经常用递归来实现。

思路:

因为data是一个非降序数组,它是有序的,这种时候我们可能会想到用二分查找。但是一个数组可能有多个k,而且我们要查找的并非常规二分法中k出现的位置,而是k出现的左界和k出现的右界。要是能刚好找到恰好小于k的数字位置和恰好大于k的数字的位置就好了

再有因为数组中全是整数,因此我们可以考虑,用二分查找找到k+0.5k+0.5k+0.5应该出现的位置和k−0.5k-0.5k−0.5应该出现的位置,二者相减就是k出现的次数

具体做法:

1:写一个二分查找的函数在数组中找到某个元素出现的位置。每次检查区间中点值,根据与中点的大小比较,确定下一次的区间

2:分别使用二分查找,找到k+0.5和k-0.5应该出现的位置,中间的部分就全是k,相减计算次数就可以了

public class Solution {

//二分查找
private int bisearch(int[] data, double k){ 
    int left = 0;
    int right = data.length - 1;
    //二分左右界
    while(left <= right){ 
        int mid = (left + right) / 2;
        if(data[mid] < k)
            left = mid + 1;
        else if(data[mid] > k)
            right = mid - 1;
    }
    return left;
}
public int GetNumberOfK(int [] array , int k) {
    //分别查找k+0.5和k-0.5应该出现的位置,中间的部分就全是k
    return bisearch(array, k + 0.5) - bisearch(array, k - 0.5);
}

}
时间复杂度:O(log2n)O(log_2n)O(log2​n),其中nnn为数组长度,两次二分查找,二分查找复杂度为O(log2n)O(log_2n)O(log2​n)

空间复杂度:O(1)O(1)O(1),常数级变量,无额外辅助空间

相关文章
|
19天前
|
存储 人工智能 测试技术
小鱼深度评测 | 通义灵码2.0,不仅可跨语言编码,自动生成单元测试,更炸裂的是集成DeepSeek模型且免费使用,太炸裂了。
小鱼深度评测 | 通义灵码2.0,不仅可跨语言编码,自动生成单元测试,更炸裂的是集成DeepSeek模型且免费使用,太炸裂了。
141060 20
小鱼深度评测 | 通义灵码2.0,不仅可跨语言编码,自动生成单元测试,更炸裂的是集成DeepSeek模型且免费使用,太炸裂了。
|
19天前
|
人工智能 运维 前端开发
基于阿里百炼的DeepSeek-R1满血版模型调用【零门槛保姆级2084小游戏开发实战】
本文介绍基于阿里百炼的DeepSeek-R1满血版模型调用,提供零门槛保姆级2048小游戏开发实战。文章分为三部分:定位与核心优势、实战部署操作指南、辅助实战开发。通过详细步骤和案例展示,帮助开发者高效利用DeepSeek-R1的强大推理能力,优化游戏逻辑与视觉效果,解决官网响应延迟问题,提升开发效率和用户体验。适合企业开发者、教育行业及多模态探索者使用。
70895 17
基于阿里百炼的DeepSeek-R1满血版模型调用【零门槛保姆级2084小游戏开发实战】
|
27天前
|
人工智能 自然语言处理 Shell
深度评测 | 仅用3分钟,百炼调用满血版 Deepseek-r1 API,百万Token免费用,简直不要太爽。
仅用3分钟,百炼调用满血版Deepseek-r1 API,享受百万免费Token。阿里云提供零门槛、快速部署的解决方案,支持云控制台和Cloud Shell两种方式,操作简便。Deepseek-r1满血版在推理能力上表现出色,尤其擅长数学、代码和自然语言处理任务,使用过程中无卡顿,体验丝滑。结合Chatbox工具,用户可轻松掌控模型,提升工作效率。阿里云大模型服务平台百炼不仅速度快,还确保数据安全,值得信赖。
358007 62
深度评测 | 仅用3分钟,百炼调用满血版 Deepseek-r1 API,百万Token免费用,简直不要太爽。
|
23天前
|
人工智能 自然语言处理 API
快速使用 DeepSeek-R1 满血版
DeepSeek是一款基于Transformer架构的先进大语言模型,以其强大的自然语言处理能力和高效的推理速度著称。近年来,DeepSeek不断迭代,从DeepSeek-V2到参数达6710亿的DeepSeek-V3,再到性能比肩GPT-4的DeepSeek-R1,每次都带来重大技术突破。其开源策略降低了AI应用门槛,推动了AI普惠化。通过阿里云百炼调用满血版API,用户可以快速部署DeepSeek,享受高效、低成本的云端服务,最快10分钟完成部署,且提供免费token,极大简化了开发流程。
191000 23
快速使用 DeepSeek-R1 满血版
|
8天前
|
人工智能 搜索推荐 数据可视化
Manus:或将成为AI Agent领域的标杆
随着人工智能技术的飞速发展,AI Agent(智能体)作为人工智能领域的重要分支,正逐渐从概念走向现实,并在各行各业展现出巨大的应用潜力。在众多AI Agent产品中,Manus以其独特的技术优势和市场表现,有望成为该领域的标杆。作为资深AI工程师,本文将深入探讨Manus的背景知识、主要业务场景、底层原理、功能的优缺点,并尝试使用Java搭建一个属于自己的Manus助手,以期为AI Agent技术的发展和应用提供参考。
11058 13
|
8天前
|
机器学习/深度学习 人工智能 测试技术
阿里云百炼已上线超强推理开源模型QwQ-32B,尺寸更小,性能比肩DeepSeek满血版
通义千问团队推出了320亿参数的QwQ-32B模型,通过大规模强化学习和多阶段训练,在数学、编程及通用能力上达到或超越了DeepSeek-R1等先进模型。QwQ-32B模型已在阿里云百炼上线,支持API调用,用户可通过官方文档了解详细使用方法。未来,团队将继续探索智能体与RL集成,推动人工通用智能的发展。
|
25天前
|
机器学习/深度学习 人工智能 自然语言处理
快来零门槛、即刻拥有 DeepSeek-R1 满血版
随着人工智能技术的发展,DeepSeek作为一款新兴推理模型,凭借强大的技术实力和广泛的应用场景崭露头角。本文基于阿里云提供的零门槛解决方案,评测DeepSeek的部署与使用。该方案支持多模态任务,涵盖文本生成、代码补全等,融合NLP、IR和ML技术,提供快速实现AI应用的便利。用户无需编码,最快5分钟、最低0元即可部署DeepSeek模型。阿里云还提供100万免费Token,适合预算有限的个人或小型团队试用。通过Chatbox客户端配置API,用户可轻松体验智能交互功能,如数学提问和代码书写等。
37602 5
|
19天前
|
人工智能 编解码 算法
DeepSeek加持的通义灵码2.0 AI程序员实战案例:助力嵌入式开发中的算法生成革新
本文介绍了通义灵码2.0 AI程序员在嵌入式开发中的实战应用。通过安装VS Code插件并登录阿里云账号,用户可切换至DeepSeek V3模型,利用其强大的代码生成能力。实战案例中,AI程序员根据自然语言描述快速生成了C语言的base64编解码算法,包括源代码、头文件、测试代码和CMake编译脚本。即使在编译错误和需求迭代的情况下,AI程序员也能迅速分析问题并修复代码,最终成功实现功能。作者认为,通义灵码2.0显著提升了开发效率,打破了编程语言限制,是AI编程从辅助工具向工程级协同开发转变的重要标志,值得开发者广泛使用。
7905 68
DeepSeek加持的通义灵码2.0 AI程序员实战案例:助力嵌入式开发中的算法生成革新
|
7天前
|
机器学习/深度学习 弹性计算 搜索推荐
真正的0代码,0脚本,0门槛,QwQ-32B一键部署!
阿里云最新发布的QwQ-32B模型通过强化学习显著提升了推理能力,在多个核心指标上达到DeepSeek-R1满血版水平,超越了DeepSeek-R1-Distill-Qwen-32B。用户可通过阿里云系统运维管理(OOS)的公共扩展功能,一键部署OpenWebUI+Ollama至ECS,轻松运行QwQ-32B模型。该方案支持本地部署和连接阿里云百炼在线模型,无需编写代码,操作简便,适合新手尝试。具体步骤包括:在阿里云控制台安装OpenWebUI扩展、选择ECS实例并创建、等待几分钟后获取URL链接,即可开始使用。此外,还提供了详细的配置指南和高级玩法介绍,帮助用户更好地利用该模型。
|
10天前
|
开发者 异构计算
高效部署通义万相Wan2.1:ComfyUI文生/图生视频实战,工作流直取!
通义万相Wan2.1开源不到一周,已登顶HuggingFace Model 和 Space 榜双榜首,在HuggingFace和ModelScope平台的累计下载量突破100万次,社区热度持续攀升!为响应小伙伴们对ComfyUI工作流运行Wan2.1的强烈需求,社区开发者整理了实战教程👇
1243 21
高效部署通义万相Wan2.1:ComfyUI文生/图生视频实战,工作流直取!