算法刷题 week4

这篇具有很好参考价值的文章主要介绍了算法刷题 week4。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.斐波那契数列

题目

算法刷题 week4,算法笔记,算法,java,开发语言,笔记

题解
(递推 + 滚动变量) O(n)

这题的数据范围很小,我们直接模拟即可。
当数据范围很大时,就需要采用其他方式了,可以参考 求解斐波那契数列的若干方法 。

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

用两个变量滚动式得往后计算,a 表示第 n−1 项,b 表示第 n 项。
则令 c=a+b 表示第 n+1 项,然后让 a, b 顺次往后移一位。

时间复杂度分析

总共需要计算 n 次,所以时间复杂度是 O(n) ,但空间复杂度变成了 O(1)。

class Solution {
public:
    const int MOD = 1e9 + 7;    //1000000007
    int Fibonacci(int n) {
        int a = 0, b = 1;
        while (n--)  
        {
            int c = (a + b) % MOD;  //取模优先级比加减高,比乘数低
            a = b, b = c;   //逗号运算符,从左到右计算
        }
        return a;
    }
};  
//  	 0 1 1 2 3 5
//第几项  0 1 2 3 4 5 

剑指offer 10 - II 青蛙跳台阶问题

题目

算法刷题 week4,算法笔记,算法,java,开发语言,笔记

题解

此类求 多少种可能性 的题目一般都有 递推性质 ,即 f(n) 和 f(n-1)…f(1) 之间是有联系的。

算法刷题 week4,算法笔记,算法,java,开发语言,笔记

算法刷题 week4,算法笔记,算法,java,开发语言,笔记

计算 f(n) 需循环 n 次,每轮循环内计算操作使用 O(1) ,所以时间复杂度是 O(n) 。

几个标志变量使用常数大小的额外空间,空间复杂度为 O(1)。

class Solution {
public:
    const int MOD = 1e9 + 7;    //1000000007
    int numWays(int n) {
        int a = 1, b = 1;   //只有起始条件不同,其它都与上题相同
        while (n--)  
        {
            int c = (a + b) % MOD;  //取模优先级比加减高,比乘数低
            a = b, b = c;   //逗号运算符,从左到右计算
        }
        return a;
    }
};

10.旋转数组的最小数字

题目

算法刷题 week4,算法笔记,算法,java,开发语言,笔记

题解
(二分) O(n)

为了便于分析,我们先将数组中的数画在二维坐标系中,横坐标表示数组下标,纵坐标表示数值, 图中水平的实线段表示相同元素。如下所示:

我们发现除了最后水平的一段(黑色水平那段)之外,其余部分满足二分性质:竖直虚线左边的数满足 nums[i]≥nums[0];而竖直虚线右边的数不满足这个条件。

二分是二分性而不是单调性。只要满足可以找到一个值一半满足一半不满足即可,而不用满足单调性。

分界点就是整个数组的最小值,所以我们先将最后水平的一段删除即可。

另外,不要忘记处理数组完全单调的特殊情况:

当我们删除最后水平的一段之后,如果剩下的最后一个数大于等于第一个数,则说明数组完全单调。

时间复杂度分析

二分的时间复杂度是 O(logn),删除最后水平一段的时间复杂度最坏是 O(n),所以总时间复杂度是 O(n)。文章来源地址https://www.toymoban.com/news/detail-733106.html

class Solution
{
public:
    int findMin(vector<int>& nums)
    {
        int n = nums.size() - 1;
        if(n < 0) return -1;
        
        while (n > 0 && nums[n] == nums[0]) n--; //删除最后水平的一段,当n=0时,只有一个数,也要退出循环
        if (nums[n] >= nums[0]) return nums[0]; //当没有元素旋转时,则出现这种情况
        
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r >> 1;  //[l, mid], [mid + 1, r]
		  	if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};

到了这里,关于算法刷题 week4的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 0xGame week4-WEB wp

    完结撒花!!!学到了很多很多,算是我这个WEB菜鸡过渡期的一个见证吧。 0xGame虽然也没做出来几道(大嘘),但是 一步步跟着复现也学了很多好玩的知识点和思路,希望下次能进化成WEBak哥hhhhhh~~~~ 来看最后一周,全是java框架,麻了。 整体不难,hint把解题方法基本写脸上

    2024年02月05日
    浏览(69)
  • NewStarCTF 2023 公开赛道 WEEK4|CRYPTO 部分WP

    1、题目信息 提示: \\\"Schmidt Samoa\\\" 附件信息 2、解题方法 学了一个新技巧,哈哈哈。 简介 : Schmidt-Samoa密码系统,像rabin加密一样,其安全性基于整数因式分解的难度。但 Rabin 解密时会得到四个解,而 Schmidt-Samor 得到的是唯一解。 密钥生成 1.选取两个大的质数p和q并进行计算

    2024年02月08日
    浏览(45)
  • [BUUCTF NewStarCTF 2023 公开赛道] week4 crypto/pwn

    再补完这个就基本上完了. Schmidt-Samoa密码系统看上去很像RSA,其中N=pqq, 给的e=N给了d NTRU又一个格的基本应用   当E.order() == p时   p-1光滑时的分解 此题先是p-1光滑分解,然后是e=3*0x10000先求3次根再用rabin求16次    求误差,虽然被分成3个数组,但本质上是一个,可以连到一起求解. 

    2024年02月07日
    浏览(38)
  • 剑指offer题解合集——Week4day2

    题目链接:二叉树中和为某一值的路径 AC代码 思路: 整体思路

    2024年01月15日
    浏览(46)
  • 前端架构师-week4-封装通用的npm包管理类Package

    目录 脚手架命令本地调试功能支持 动态执行库exec模块创建 创建 npm 模块通用类 Package Package 类的属性、方法定义及构造函数逻辑开发 Package 类获取入口文件路径功能开发(pkg-dir应用+解决不同操作系统路径兼容问题)  利用 npminstall 库安装 npm 模块 Package 类判断模块是否存在

    2024年02月03日
    浏览(42)
  • 【北邮国院大三下】Cybersecurity Law 网络安全法 Week4

    北邮国院大三电商在读,随课程进行整理知识点。仅整理PPT中相对重要的知识点,内容驳杂并不做期末突击复习用。个人认为相对不重要的细小的知识点不列在其中。如有错误请指出。转载请注明出处,祝您学习愉快。 编辑软件为Effie,如需要pdf/docx/effiesheet/markdown格式的文件

    2024年02月11日
    浏览(74)
  • NEUQ-acm第二期训练Week4——代码源div2

    RSA算法选择两个不同质数的积作为模数。现在有两个正整数 A,B,如果它们是不同的质数,则判定为 full credit;否则,如果A⋅B不是任意大于1的整数的平方的整数倍,则判定 partial credit;否则判定为no credit。 一行两个正整数 A,B。 full credit 或 partial credit 或 no credit。 数据规模

    2024年02月16日
    浏览(36)
  • NewStarCTF2023week4-midsql(利用二分查找实现时间盲注攻击)

    大致测试一下,发现空格被过滤了 使用内联注释/**/绕过,可行 使用%a0替代空格,也可以  再次测试发现等号也被过滤,我们使用 like 代替 (我最开始以为是and被过滤,并没有,如果是and或者or被过滤我们也可以使用 和 || 替代) 但是这里尝试了很多都只返回一个页面,没有

    2024年02月07日
    浏览(47)
  • Coursera自然语言处理专项课程04:Natural Language Processing with Attention Models笔记 Week02

    Course Certificate 本文是学习这门课 Natural Language Processing with Attention Models的学习笔记,如有侵权,请联系删除。 Compare RNNs and other sequential models to the more modern Transformer architecture, then create a tool that generates text summaries. Learning Objectives Describe the three basic types of attention Name the two ty

    2024年04月08日
    浏览(53)
  • Coursera自然语言处理专项课程04:Natural Language Processing with Attention Models笔记 Week01

    Course Certificate 本文是学习这门课 Natural Language Processing with Attention Models的学习笔记,如有侵权,请联系删除。 Discover some of the shortcomings of a traditional seq2seq model and how to solve for them by adding an attention mechanism, then build a Neural Machine Translation model with Attention that translates English sente

    2024年04月16日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包