Day1 25/2/14 FRI

【一周刷爆LeetCode,算法大神左神(左程云)耗时100天打造算法与数据结构基础到高级全家桶教程,直击BTAJ等一线大厂必问算法面试题真题详解(马士兵)】https://www.bilibili.com/video/BV13g41157hK?p=3&vd_source=04ee94ad3f2168d7d5252c857a2bf358

目录

1、认识复杂度和简单排序算法

1.1 常数时间操作 & 时间复杂度

1.2 基础排序算法

1.2.1 选择排序

1.2.2 冒泡排序

补充:异或运算

1.2.3 插入排序

1.3 二分查找

1.4 对数器

1.5 master公式


笔记:

1、认识复杂度和简单排序算法

1.1 常数时间操作 & 时间复杂度

常数时间的操作:与数据量无关的操作,每次都是固定时间完成

数组查数是,链表不是?

数组是记录在案的,有目录可供直接取用,与数据量无关;而链表没有记录在案的目录,只能一个个查找,因此与数据量有关

时间复杂度:忽略最低项后只要最高项,且忽略掉系数。

忽略系数的原因,当数据量N足够大的时候,它的系数对它造不成影响。

评估一个算法流程的好坏,先比较时间复杂度指标,当指标相同时再实际运行去测哪个算法更好。

1.2 基础排序算法

选择排序&冒泡排序:都是O(N^2),实现方式不同但本质没区别

1.2.1 选择排序

选择排序:从i=0开始++,每加一次,从arr[i]开始遍历到arr[n-1]并把最小值交换到arr[i]上。

(遍历:0到n-1、1到n-1、2到n-1等等)

1.2.2 冒泡排序

冒泡排序:两个位置间比较,慢慢把数字升序或降序

从i=0开始++,如果arr[i]大于arr[i+1],它俩交换。这个方法每次遍历后,右边的数都是前面最大的。

(遍历:0到n-1、0到n-2、0到n-3等等)

补充:异或运算

可以理解为无进位相加,二进制中:0^0=0;1^0=0^1=1;1^1=0

N进制中:N^0=0^N=N;N^N=0

异或运算满足交换律、结合律

//使用前提:a和b各自指向的内存空间必须不同(a和b的数值可以一样,但a的地址不能等于b的地址,否则异或运算就会把a和b都抹为0)int a= 某个值;int b= 某个值;a=a^b; //(a=a^b, b=b)b=a^b; //(a=a^b, b=a^b^b=a^(b^b)=a^0=a)a=a^b; //(a=a^b^a=b, b=a)

【异或运算】例题:

(1)136. 只出现一次的数字 - 力扣(LeetCode)

描述:只有一个数字出现奇数次,找出它。

思路:用“异或 a^a=0”消除所有偶数次的数。

(2)描述:有两个数a和b都出现奇数次,找出它们两个。

思路?:先边遍历边异或得到targets=a^b,再将targets再和整个数组异或一遍,得到其中一个奇数次的数a。然后a和targets再异或得到b。

1.2.3 插入排序

插入排序:简而言之就像打扑克,按数字顺序整理好手中的牌,抽新牌后插入到对应位置上。

由于在数组中插入一个位置时,后面的数都要整体往后移,所以干脆在比较的同时就交换了位置,因此看着像冒泡排序。

从int i=1开始,因为再i=0上已经做到了有序。

数据状况不同,会导致算法流程的时间复杂度不同。

时间复杂度是按最差情况估计算法表现。

1.3 二分查找

时间复杂度:O(logN)

无论数组是否有序,都可以二分

例题:

(1)在有序数组中,找某数是否存在

(2)在有序数组中,找≥某数的最左侧位置

(3)在无序数组中,找局部最小值问题

1.4 对数器

原理:利用随机样本产生器去测试方法a和方法b,检查二者的输出和性能。修改样本大小和随机程度之后多测几次。

方法a:想测的方法

方法b:好实现但性能不太好的方法

java实现:

​Math.random()是等概率返回[0,1)区间内的一个小数。

而(int)Math.random() * N则是等概率返回[0, N-1]区间内的一个整数。

// 数组长度随机int[] arr = new int[ (maxSize+1) * (int)Math.random() ];// 数组数值随机,使用相减来概率得到负数for(int i=0; i<arr.length; i++){arr[i] = (int) ( (maxValue+1) * Math.random() - (int) ( maxValue * Math.random() );}

然后创建两个空数组分别存储调用方法a和b之后的结果,比较结果是否相同。

1.5 master公式

master公式:T(N) = a*T(N/b) + O(N^d)

log(b,a) > d,复杂度为O( N^log(b,a) )

log(b,a) = d,复杂度为O( N^d * logN )

log(b,a) < d,复杂度为O( N^d )

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Windows环境管理多个node版本

前言 在实际工作中&#xff0c;如果我们基于Windows系统开发&#xff0c;同时需要维护老项目&#xff0c;又要开发新项目&#xff0c;且不同项目依赖的node版本又不同时&#xff0c;那么就需要根据项目切换不同的版本。本文使用Node Version Manager&#xff08;nvm&#xff0…

前端包管理器的发展以及Npm、Yarn和Pnpm对比

在现代前端开发中&#xff0c;包管理器是不可或缺的核心工具。随着 JavaScript 生态的快速发展&#xff0c;开发者经历了从 npm 一统天下到 Yarn 挑战格局&#xff0c;再到 pnpm 创新突破的技术演进。这里将对三种主流包管理器&#xff08;npm/Yarn/pnpm&#xff09;进行全方位…

leetcode 2915. 和为目标值的最长子序列的长度

题目如下 数据范围 本题就是典型的背包问题target就是容量&#xff0c;nums[i]就是第i个物品的重量。其实就是选最多的物品使得背包刚好装满。 令f(i,j)为当考虑到i - 1物品时刚好装到j重量的物品数。 当j > nums[j]时 有f(i,j) max(f(i - 1,j - nums[i - 1]) 1,f(i -…

ASP.NET Core 面试宝典【刷题系列】

文章目录 引言1、什么是 dot net core 的 startup class?2、什么是中间件?3、application builder 的 use 和 run 方法有什么区别?4、dot net core 管道里面的map拓展有什么作用?5、dot net core 里面的路径是如何处理的?6、如何在 dot net core 中激活 session 功能?7、…

BFS 走迷宫

#include<bits/stdc.h> using namespace std; int a[100][100],v[100][100];//访问数组 n,m<100 struct point {int x;int y;int step; }; queue<point> r;//申请队列 int dx[4]{0,1,0,-1};//四个方向 右下左上 int dy[4]{1,0,-1,0}; int main() { /* 5 4 1 …

给压缩文件加密码的5种方法(win/mac/手机/网页端)

把文件加密压缩&#xff0c;一方面能有效保护个人隐私与敏感信息&#xff0c;防止数据在传输或存储过程中被窃取、篡改。另一方面&#xff0c;压缩文件可减少存储空间占用&#xff0c;提升传输速度&#xff0c;方便数据的存储与分享。以下为你介绍5种常见的加密压缩方法。 一、…

IoTDB 导入数据时提示内存不足如何处理

问题现象 IoTDB 导入数据时提示内存不足&#xff0c;该如何处理&#xff1f; 解决方案 数据导入脚本会在触发内存不足的时候主动进行重试。当遇到此问题时&#xff0c;用户不用做任何操作&#xff0c;脚本也可以正确进行处理。如果想从根源减少此类提示&#xff0c;可以按照下…

自有证书的rancher集群使用rke部署k8s集群异常

rancher使用自签域名&#xff0c;或者商业证书容易踩到的坑。 最开始的报错&#xff1a; docker logs kubelet‘s id E0214 13:04:14.590268 9614 pod_workers.go:1300] "Error syncing pod, skipping" err"failed to \"StartContainer\" for …

计算机网络结课设计:通过思科Cisco进行中小型校园网搭建

上学期计算机网络课程的结课设计是使用思科模拟器搭建一个中小型校园网&#xff0c;当时花了几天时间查阅相关博客总算是做出来了&#xff0c;在验收后一直没管&#xff0c;在寒假想起来了简单分享一下&#xff0c;希望可以给有需求的小伙伴一些帮助 目录 一、设计要求 二、…

【漫话机器学习系列】091.置信区间(Confidence Intervals)

置信区间&#xff08;Confidence Intervals&#xff09;详解 1. 引言 在统计学和数据分析中&#xff0c;我们通常希望通过样本数据来估计总体参数。然而&#xff0c;由于抽样的随机性&#xff0c;我们不可能得到精确的总体参数&#xff0c;而只能通过估计值&#xff08;如均值…

朝天椒USB服务器:解决加密狗远程连接

本文探讨朝天椒USB服务器用Usb Over Network技术&#xff0c;解决加密狗在虚拟机、云主机甚至异地的远程连接问题。 在企业数字化转型的浪潮中&#xff0c;加密狗作为防止软件盗版的重要手段&#xff0c;广泛应用于各类软件授权场景。然而&#xff0c;随着企业超融合进程不断加…

Linux 配置 MySQL 定时自动备份到另一台服务器

Linux 配置 MySQL 定时自动备份到另一台服务器 前言1、配置服务器通信1.1&#xff1a;配置过程 2、编写自动备份sh脚本文件3&#xff1a;设置定时自动执行 前言 此方案可使一台服务器上的 MySQL 中的所有数据库每天 0 点自动转储为 .sql 文件&#xff0c;然后将文件同步到另一…

【网络编程】之Udp网络通信步骤

【网络编程】之Udp网络通信步骤 TCP网络通信TCP网络通信的步骤对于服务器端对于客户端 TCP实现echo功能代码实现服务器端getsockname函数介绍 客户端效果展示 对比两组函数 TCP网络通信 TCP网络通信的步骤 对于服务器端 创建监听套接字。&#xff08;调用socket函数&#xff…

RV1126解码(1)

比如我们现在要拉一个流&#xff0c; 拉一个rtmp或者拉一个rtsp的流&#xff0c;让它显示到显示屏上面去&#xff0c;此时就要用到我们这个解码模块了&#xff0c;把它个解出来并且发到其他模块去。 主要功能是通过FFMPEG的API读取每一帧的音视频数据&#xff0c;并通过RV1126的…

js实现点击音频实现播放功能

目录 1. HTML 部分&#xff1a;音频播放控件 2. CSS 部分&#xff1a;样式设置 3. JavaScript 部分&#xff1a;音频控制 播放和暂停音频&#xff1a; 倒计时更新&#xff1a; 播放结束后自动暂停&#xff1a; 4. 总结&#xff1a; 完整代码&#xff1a; 今天通过 HTML…

kotlin标准库里面也有很多java类

Kotlin 标准库中确实存在许多与 Java 类直接关联或基于 Java 类封装的结构&#xff0c;但这并不是“问题”&#xff0c;而是 Kotlin 与 JVM 生态深度兼容和互操作性的体现。以下从技术原理和设计哲学的角度详细解释&#xff1a; 一、Kotlin 与 JVM 的底层关系 Kotlin 代码最终…

【DeepSeek】从文本摘要到对话生成:DeepSeek 在 NLP 任务中的实战指南

网罗开发 &#xff08;小红书、快手、视频号同名&#xff09; 大家好&#xff0c;我是 展菲&#xff0c;目前在上市企业从事人工智能项目研发管理工作&#xff0c;平时热衷于分享各种编程领域的软硬技能知识以及前沿技术&#xff0c;包括iOS、前端、Harmony OS、Java、Python等…

亚博microros小车-原生ubuntu支持系列 27、手掌控制小车运动

背景知识 本节跟上一个测试类似&#xff1a;亚博microros小车-原生ubuntu支持系列&#xff1a;26手势控制小车基础运动-CSDN博客 都是基于MediaPipe hands做手掌、手指识别的。 为了方便理解&#xff0c;在贴一下手指关键点分布。手掌位置就是靠第9点来识别的。 2、程序说明…

2025-02-13 学习记录--C/C++-PTA 7-17 爬动的蠕虫

一、题目描述 ⭐️ 二、代码&#xff08;C语言&#xff09;⭐️ #include <stdio.h>int main() {int N, U, D; // N: 井的总高度&#xff0c;U: 每分钟向上爬的高度&#xff0c;D: 每分钟滑下的高度int height 0; // 蠕虫当前的高度int minute 0; // 蠕虫爬行的时间sc…

多模态识别和自然语言处理有什么区别

在科技飞速发展的当下&#xff0c;人工智能&#xff08;AI&#xff09;已经渗透到我们生活的方方面面。不知道大家有没有这样的经历&#xff1a;早上醒来&#xff0c;对着智能音箱说 “播放今天的新闻”&#xff0c;音箱不仅能识别你的语音&#xff0c;还能在播放新闻的同时&am…