php7.3能装wordpress/windows优化大师靠谱吗
目录
1.排序数组
2.数组中的第K个最大元素
3.最小k个数
4.排序数组(归并)
5.数组中的逆序对
6.计算右侧小于当前元素的个数
7. 翻转对
1.排序数组
快排的写法有很多,这里我采取了相对快的三路划分加随机基准值。
三路划分,是将一段区间划成了【小于基准值】【等于基准值】【大于基准值】的三段区间。递归遍历的时候只需要递归【小于基准值】【大于基准值】的区间,中间区间就可以看作已经完成了排序,这也与二路划分的快排有很大区别,相比之下遇到极端情况(整个区间都是同一个数字)时间复杂度会更小。
考虑到三路划分本身不是很难,但是这边还是有基础题的。
75. 颜色分类 - 力扣(LeetCode)
class Solution { public:void sortColors(vector<int>& nums) {int n=nums.size();int left=-1,right=n;int index=0;while(index<right){if(nums[index]==0){swap(nums[++left],nums[index++]);}else if(nums[index]==1)index++;else if(nums[index]==2){swap(nums[--right],nums[index]);}}}};
283. 移动零 - 力扣(LeetCode)//这题是二路的,但是思想跟三路很像,主要是学会怎么划分,具体是几路要看题目要求
void moveZeroes(int* nums, int numsSize) {int dest=-1,cur=0;while(cur<numsSize){if(nums[cur]!=0){dest++;int tmp=nums[dest];nums[dest]=nums[cur];nums[cur]=tmp;}cur++;} }
912. 排序数组 - 力扣(LeetCode)
class Solution { public: //返回随机基准值int rad(vector<int>&nums,int left,int right){int r=rand();return nums[r%(right-left+1)+left];} //快排本身void fastsort(vector<int>&nums,int left,int right){if(left>=right)return;//递归出口int mid=rad(nums,left,right);//获取基准值int l=left-1,r=right+1,index =left;//设定三指针,方便划分3路while(index<r){if(nums[index]<mid)swap(nums[index++],nums[++l]);else if(nums[index]==mid)index++;else if(nums[index]>mid)swap(nums[index],nums[--r]);}fastsort(nums,left,l);fastsort(nums,r,right);}vector<int> sortArray(vector<int>& nums) {int n=nums.size();srand(time(0));fastsort(nums,0,n-1); return nums;} };
2.数组中的第K个最大元素
215. 数组中的第K个最大元素 - 力扣(LeetCode)
class Solution { public: //返回随机基准值int rad(vector<int>&nums,int left,int right){int r=rand();return nums[r%(right-left+1)+left];} //快排int qsort(vector<int>&nums,int left,int right,int k){ //结合最下面的条件判断,我们会发现,我们只会进入,至少有一个元素的区间, //所以最多就是left==right,我们在寻找最有可能的区间中,一直找,找到只有 //一个元素,说明正好就是他了if(left==right)return nums[left]; //三路划分int mid=rad(nums,left,right);int index=left,l=left-1,r=right+1;while(index<r){if(nums[index]<mid)swap(nums[index++],nums[++l]);else if(nums[index]==mid)index++;else swap(nums[index],nums[--r]);} //a是【小于基准值】的个数,b是【等于基准值】的个数,c是【大于基准值】的个数int a=l-left+1,b=r-l-1,c=right-r+1; //c>=k,说明第k大的数一定在【大于基准值】区间里,所以只需要递归这个区间即可if(c>=k){return qsort(nums,r,right,k);} //在不满足c>=k的情况,b+c>=k,说明我们要找的第k大数,正好就是当前的基准值 //直接返回基准值即可else if(b+c>=k)return mid; //在不满足上面条件的情况下,因为k肯定是小于整个区间大小的,那么b+c<k,说明a+b+c>=k, //那么此时第k大的数就在【小于基准值】区间内,注意了,前面两个条件,k都是原始的k //那是因为可以确定【等于基准值】区间元素个数+【大于基准值】区间元素个数大于k个或 //【大于基准值】区间元素个数大于k个,所以k一定是在left-right区间内的 //但这里不同,虽然我们可以判断第k大数在【小于基准值】区间内, //但是这个区间元素不一定大于等于k个,所以,我们传参的时候,是在 //【小于基准值】区间内找第k-b-c大的数else{return qsort(nums,left,l,k-b-c);}}int findKthLargest(vector<int>& nums, int k) {int n=nums.size();srand(time(NULL));return qsort(nums,0,n-1,k);} };
3.最小k个数
面试题 17.14. 最小K个数 - 力扣(LeetCode)
class Solution { public:int rad(vector<int>& arr,int l,int r){return arr[rand()%(r-l+1)+l];}void dfs(vector<int>& arr,int l,int r,int k){if(l>=r)return ;int key=rad(arr,l,r);int left=l-1,right=r+1,index=l;while(index<right){if(arr[index]<key)swap(arr[index++],arr[++left]);else if(arr[index]==key)index++;else swap(arr[index],arr[--right]);}int a=left-l+1,b=right-1-left,c=r-right+1; //a>k,说明,最小k个数一定在【小于基准值】的区间里。所以要继续递归a的区间 //然后三路划分a区间,重复操作,直到满足第二个条件。 //如果满足a+b>=k,那么不管是a==k,还是a+b==k,都说明此时数组前k个数已经是最小的k个数了 //直接返回即可 //如果前两个条件都不满足,说明这k个数是包含了a和b,包含了部分c,所以要继续递归c的区间 //然后三路划分c区间,重复操作,直到满足第二个条件。if(a>k)dfs(arr,l,left,k);else if(a+b>=k)return ;else dfs(arr,right,r,k-a-b);}vector<int> smallestK(vector<int>& arr, int k) {srand(time(NULL));dfs(arr,0,arr.size()-1,k);vector<int>res(k);for(int i=0;i<k;i++)res[i]=arr[i];return res;} };
4.排序数组(归并)
912. 排序数组 - 力扣(LeetCode)
class Solution { public:void merge(vector<int>&num,int l,int r){if(l>=r)return;int mid=l+(r-l)/2;merge(num,l,mid);merge(num,mid+1,r);int i1=l,i2=mid+1;int i3=0;while(i1<=mid&&i2<=r){if(num[i1]<num[i2]){tmp[i3++]=num[i1++];}else tmp[i3++]=num[i2++];}while(i1<=mid)tmp[i3++]=num[i1++];while(i2<=r)tmp[i3++]=num[i2++];for(int i=l;i<=r;i++)num[i]=tmp[i-l];return ;}vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());merge(nums,0,nums.size()-1);return nums;}vector<int>tmp; };
5.数组中的逆序对
数组中的逆序对_牛客题霸_牛客网 (nowcoder.com)
思路依旧是归并。
整个数组,我们可以这样思考。一段区间的逆序对,如果以中间划分,可以分为【左部分】的逆序对个数+【右部分】的逆序对个数+【左部分挑一个,右部分挑一个】的逆序对个数
由此,我们可以以分治的思路,一路切割。
注意,【左部分挑一个,右部分挑一个】这部分必须要依靠排序来快速挑选,否则,时间复杂度依旧是On2。
也就是说可以分为【左部分】的逆序对个数&&排序+【右部分】的逆序对个数&&排序+【左部分挑一个,右部分挑一个】的逆序对个数&&排序。
#include <cstdio> class Solution { public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param nums int整型vector * @return int整型*/int tmp[100010]={0};int _InversePairs(vector<int>& nums,int l,int r){if(l>=r)return 0;//说明当前区间只有1或0个数字,没有逆序对,返回0int mid=l+(r-l)/2;int res=0;res+=_InversePairs(nums,l , mid);//加左部分res+=_InversePairs(nums, mid+1, r);//加右部分res%=1000000007;//题目数据要求,必须mod,不然有个样例会溢出int cur1=l,cur2=mid+1;int i=l;while(cur1<=mid&&cur2<=r)//排序和找逆序对,同时进行{if(nums[cur1]>nums[cur2])//说明自cur2坐标上起的数字,都是比cur1坐标上的值小{res+=(r-cur2+1);tmp[i++]=nums[cur1++];}else {tmp[i++]=nums[cur2++];}}//sort(nums.begin()+l,nums.begin()+r+1,greater<int>()); //注意,偷懒可以直接sort,但是时间复杂度很高,因为sort是Nlogn,而我们自己写 //有序数组合并,可以做到Onwhile(cur1<=mid)tmp[i++]=nums[cur1++];while(cur2<=r)tmp[i++]=nums[cur2++];for(int k=l;k<=r;k++)nums[k]=tmp[k];return res%1000000007;}int InversePairs(vector<int>& nums) {return _InversePairs(nums,0,nums.size()-1);}};
6.计算右侧小于当前元素的个数
315. 计算右侧小于当前元素的个数 - 力扣(LeetCode)
这题,跟上一题很像。
我们需要两个额外的数组,一个是用来记录数字在原数字中的下标,在排序时同步移动
,一个是用来记录答案的数组。利用第一个数组,即可下标访问,及时更新第二个数组
class Solution { public:void merge(vector<int>& nums,int l,int r,vector<int>&res){if(l>=r)return;int mid=l+(r-l)/2;merge(nums,l,mid,res);merge(nums,mid+1,r,res);int cur1=l,cur2=mid+1,index=l;while(cur1<=mid&&cur2<=r){if(nums[cur1]>nums[cur2]){res[ix[cur1]]+=(r-cur2+1);tmp[index]=nums[cur1];tmp1[index++]=ix[cur1++];}else{tmp[index]=nums[cur2];tmp1[index++]=ix[cur2++];}}while(cur1<=mid)tmp[index]=nums[cur1],tmp1[index++]=ix[cur1++];while(cur2<=r)tmp[index]=nums[cur2],tmp1[index++]=ix[cur2++];for(int i=l;i<=r;i++)nums[i]=tmp[i],ix[i]=tmp1[i];}vector<int> countSmaller(vector<int>& nums) {int n=nums.size();for(int i=0;i<n;i++)ix[i]=i;vector<int>res(n,0);merge(nums,0,n-1,res);return res;}int ix[100100]={0};int tmp[100100]={0};int tmp1[100100]={0}; };
7. 翻转对
493. 翻转对 - 力扣(LeetCode)
这题,跟上面逆序对的写法,几乎一模一样,只是要注意,排序必须单独写,不能在找逆序对里同时排序。还有条件是>2倍(虽然每个数都是int范围,但是*2可能会溢出,所以可以强转成更大的类型,比如long,或者判断条件可以是a>=b/2.0,注意c++/是整除,可能有余数,所以要加个2.0,这样就是浮点数了)
class Solution { public:int tmp[100010] = { 0 };int _InversePairs(vector<int>& nums, int l, int r){if (l >= r)return 0;//说明当前区间只有1或0个数字,没有逆序对,返回0int mid = l + (r - l) / 2;int res = 0;res += _InversePairs(nums, l, mid);//加左部分res += _InversePairs(nums, mid + 1, r);//加右部分int cur1 = l, cur2 = mid + 1;int i = l;while (cur1 <= mid && cur2 <= r)//排序和找逆序对,同时进行{if (nums[cur1] > 2*(long)nums[cur2])//说明自cur2坐标上起的数字,都是比cur1坐标上的值小{res += (r - cur2 + 1);cur1++;}else {cur2++;}}int l1=l,l2=mid+1;while(l1<=mid&&l2<=r){if(nums[l1]>nums[l2]){tmp[i++]=nums[l1++];}else{tmp[i++]=nums[l2++];}}while(l1<=mid)tmp[i++]=nums[l1++];while(l2<=r)tmp[i++]=nums[l2++];for(int k=l;k<=r;k++)nums[k]=tmp[k];return res;}int InversePairs(vector<int>& nums) {return _InversePairs(nums, 0, nums.size() - 1);}int reversePairs(vector<int>& nums) {return InversePairs(nums);} };
相关文章:

分支-快排/归并---1
目录 1.排序数组 2.数组中的第K个最大元素 3.最小k个数 4.排序数组(归并) 5.数组中的逆序对 6.计算右侧小于当前元素的个数 7. 翻转对 1.排序数组 快排的写法有很多,这里我采取了相对快的三路划分加随机基准值。 三路划分,是…...

代码随想录训练营 Day32打卡 动态规划 part01 理论基础 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯
代码随想录训练营 Day32打卡 动态规划 part01 一、 理论基础 动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的。 例如:有N件物品和一个最多能背重量为W 的背包…...

【智能流体力学】剖析ANSYS Fluent材料属性设定与边界条件
目录 一、材料属性设定**1. 材料属性的概述****功能****2. 材料属性的类型****标准材料库****多相流****燃烧模型****传热模型****辐射模型****3. 属性设置与函数****4. 自定义材料数据库****5. Granta数据库支持**二、边界条件**1. 通用边界条件****Pressure Inlet (压力-入口…...

微信小程序反编译工具
目录 介绍 工程结构还原 微信开发者工具运行 如何查看当前运行版本? 开启小程序F12 重新打包运行 效果示例 安装 用法 参数说明 获取微信小程序AppID 文件夹名即为AppID 下载地址 介绍 纯Golang实现,一个用于自动化反编译微信小程序的工具,小程序安全利器, 自…...

线程基本概念
一、进程的结束 wait(阻塞) 一般不做额外的事情 wait(非阻塞) 逻辑不受影响(必须套在循环中) wait作用:1.获取子进程退出状态 2.回收资源 传参为指针:被调修改主调 获取退出状态值: WIFEXITED 判断是否…...

在SpringBoot中执行后台任务
在 Spring Boot 中执行后台任务通常涉及到使用线程池和定时任务。Spring Boot 提供了多种方式来实现后台任务,包括使用 Scheduled 注解、ThreadPoolTaskExecutor 和 ExecutorService。 下面我将详细介绍如何使用这些方法来实现后台任务。 使用 Scheduled 注解 Sp…...

【网络】UDP回显服务器和客户端的构造,以及连接流程
回显服务器(Echo Server) 最简单的客户端服务器程序,不涉及到业务流程,只是对与 API 的用法做演示 客户端发送什么样的请求,服务器就返回什么样的响应,没有任何业务逻辑,没有进行任何计算或者…...

【智能流体力学】ANSYS Fluent工作流程设置、求解和后处理详解
目录 一、设置阶段1. **模型****功能** :**详细说明及原理** :2. **材料****功能** :**详细说明及原理** :3. **单元区域条件****功能** :**详细说明及原理** :4. **边界条件****功能** :**详细说明及原理** :5. **网格交界面****功能** :**详细说明及原理** :6. **动…...

最新UI六零导航系统源码 | 多模版全开源
六零导航页 (LyLme Spage) 致力于简洁高效无广告的上网导航和搜索入口,支持后台添加链接、自定义搜索引擎,沉淀最具价值链接,全站无商业推广,简约而不简单。 使用PHPMySql,增加后台管理 多模板选择,支持在…...

K8S中使用英伟达GPU —— 筑梦之路
前提条件 根据不同的操作系统,安装好显卡驱动,并能正常识别出来显卡,比如如下截图: GPU容器创建流程 containerd --> containerd-shim--> nvidia-container-runtime --> nvidia-container-runtime-hook --> libnvid…...

2024-2025年最值得选的Java计算机毕业设计选题大全:800个热门选题
一、前言 博主介绍: ✌我是阿龙,一名专注于Java技术领域的程序员,全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师,我在计算机毕业设计开发方面积累了丰富的经验。同时,我也是掘金、华为云、阿里云、InfoQ…...

libnl教程(2):发送请求
文章目录 前言示例示例代码构造请求创建套接字发送请求 简化示例 前言 前置阅读要求:libnl教程(1):订阅内核的netlink广播通知 本文介绍,libnl如何向内核发送请求。这包含三个部分:构建请求;创建套接字;发送请求。 …...

【软件测试】功能测试理论基础
目录 项目的测试流程🏴 需求评审 评审形式 测试人员在需求评审中职责 测试计划与方案 测试计划 问题 测试方案🏴 测试计划与方案的对比 功能测试设计🏴 测试设计的步骤 项目的测试流程🏴 作用: 有序有效开展…...

玩机进阶教程-----回读 备份 导出分区来制作线刷包 回读分区的写入与否 修改xml脚本
很多工作室需要将修改好的系统导出来制作线刷包。前面分享过很多制作线刷包类的教程。那么一个机型中有很多分区。那些分区回读后要写入。那些分区不需要写入。强写有可能会导致不开机 不进系统的故障。首先要明白。就算机型全分区导出后在写回去 都不一定可以开机进系统。那么…...

MongoDB 插入文档
MongoDB 插入文档 MongoDB 是一个流行的 NoSQL 数据库,它使用文档存储数据。在 MongoDB 中,数据以 BSON(Binary JSON)格式存储,这是一种二进制表示的 JSON 格式。MongoDB 提供了灵活的数据模型,使得插入和查询文档变得非常简单。本文将详细介绍如何在 MongoDB 中插入文档…...

【内网】服务器升级nginx1.17.0
今天用rpm包升级内网nginx版本,上来就给我报错 警告:nginx-1.27.0-2.el7.ngx.x86_64.rpm: 头V4 RSA/SHA256 Signature, 密钥 ID 7bd9bf62: NOKEY 错误:依赖检测失败: libcrypto.so.10()(64bit) 被 nginx-1:1.27.0-2.el7.ngx.x…...

歌曲爬虫下载
本次编写一个程序要爬取歌曲音乐榜https://www.onenzb.com/ 里面歌曲。有帮到铁子的可以收藏和关注起来!!!废话不多说直接上代码。 1 必要的包 import requests from lxml import html,etree from bs4 import BeautifulSoup import re impo…...

transformer-explainer
安装和启动 找到这个项目,然后装好了。 这个项目的目的如名字。 https://github.com/poloclub/transformer-explainerTransformer Explained: Learn How LLM Transformer Models Work with Interactive Visualization - poloclub/transformer-explainerhttps:/…...

C#中的S7协议
S7协议-S7COMM S7COMM 进行写 CTOP->PDU type已知枚举值 0X0E连接请求0x0d连接确认0x08断开请求0x0c断开确认0x05拒绝访问0x01加急数据0x02加急数据确认0x04用户数据0x07TPDU错误0x0f数据传输 S7Header->ROSCTR已知枚举值 0X01JOB REQUEST。主站发送请求0x02Ack。从站…...

2024-08-16升级记录:使用Android RecyclerView控件显示列表型信息
在页面上使用RecyclerView实现一个列表型信息展示: 步骤如下: 一、在页面布局中添加RecyclerView控件 <TextViewandroid:id"id/txt_gnss_info"android:layout_width"match_parent"android:layout_height"wrap_content"…...

通义千问 ( 一 ) 基础实例
1.相关概念 1.1.模型与平台 1.1.1.通义千问 通义千问 : 是阿里云研发的大语言模型;用于理解和分析用户输入的自然语言,在不同领域和任务为用户提供服务和帮助。 具体应用场景如下: 文字创作:撰写故事、公文、邮件、剧本和诗歌…...

docker 修改数据目录
1.停止 Docker 服务 sudo systemctl stop docker sudo systemctl stop docker.socket2.复制数据目录 sudo cp -rp /var/lib/docker /data/ 或 # sudo rsync -aP /var/lib/docker/ /data/docker/3.修改 Docker 配置 编辑 Docker 的配置文件,设置新的数据目录&#…...

r4s软路由写入iStoreOS镜像
需要用到的工具: 1、r4s软路由 2、32G及以上的TF卡 3、TF卡读卡器 4、镜像写入软件(推荐Etcher,下载地址:https://github.com/balena-io/etcher/releases/download/v1.19.21/balenaEtcher-1.19.21.Setup.exe) 5、…...

[C++][opencv]基于opencv实现photoshop算法灰度化图像
测试环境】 vs2019 opencv4.8.0 【效果演示】 【核心实现代码】 BlackWhite.hpp #ifndef OPENCV2_PS_BLACKWHITE_HPP_ #define OPENCV2_PS_BLACKWHITE_HPP_#include "opencv2/core.hpp"namespace cv {class BlackWhite { public:float red; //红色的灰度系…...

Emacs23.x版本之重要特性及用法实例(一百五十六)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 新书发布:《Android系统多媒体进阶实战》🚀 优质专栏: Audio工程师进阶系列…...

机器学习 第11章-特征选择与稀疏学习
机器学习 第11章-特征选择与稀疏学习 11.1 子集搜索与评价 我们将属性称为“特征”(feature),对当前学习任务有用的属性称为“相关特征”(relevant feature)、没什么用的属性称为“无关特征”(irrelevant feature)。从给定的特征集合中选择出相关特征子集的过程&a…...

Grok 2携AI图片生成重生
埃隆马斯克(Elon Musk)的人工智能初创公司xAI推出其最新的AI助手Grok 2的测试版,添加了类似于OpenAI的DALL-E和Google的Gemini的图像生成工具,但对可以生成的图像类型的限制显然较少。<这是其中的一个“亮点”,一些…...

使用Nexus搭建Maven私服仓库
一、私服仓库简介 在Java的世界中,我们通常使用Maven的依赖体系来管理构件(artifact,又称为二方库或三方库)的依赖,Maven仓库用于存储这些构件。一般的远程仓库(比如Maven Central)只提供下载功…...

云计算day27
任务背景 公司的服务器越来越多, 维护⼀些简单的事情都会变得很繁琐。⽤ shell脚本来管理少量服务器效率还⾏, 服务器多了之后, shell脚本⽆ 法实现⾼效率运维。这种情况下,我们需要引⼊⾃动化运维⼯具, 对 多台服务器实现⾼效运维。 任务要求任务要求 通过管…...

关于HTTP HEAD介绍
一、HTTP HEAD介绍 HTTP HEAD 是一种 HTTP 请求方法,它用于请求服务器返回指定资源的元信息(metadata),而不包括响应体的内容。这种请求方式常用于客户端预先评估资源的大小、最后修改日期或其他头信息,而无需实际下载…...