剑指 Offer第二版:1~n 整数中 1 出现的次数、51. 数组中的逆序对、56 - II. 数组中数字出现的次数 II
剑指 Offer第二版
- 43. 1~n 整数中 1 出现的次数
- 51. 数组中的逆序对
- 56 - II. 数组中数字出现的次数 II
43. 1~n 整数中 1 出现的次数
题目:输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。
例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。
示例 1:
输入:n = 12
输出:5
**思路分析:**将n的每一位数分别处理,计算出每个位数上1的个数,然后将所有位数上1的个数相加即可。具体来说,首先判断n是否为0,如果n为0,直接返回0。然后从低位到高位依次处理每一位数,计算当前位数上1的个数。如果当前位数的数字小于1,1的个数为高位数当前位数,即highbit;如果当前位数的数字等于1,1的个数为高位数当前位数+低位数+1,即highbit+low+1;如果当前位数的数字大于1,1的个数为(high+1)*bit,即高位数加一乘以当前位数。最后将所有位数上1的个数相加即为最终结果。
时间复杂度:需要处理n的每一位数,因此时间复杂度为 O ( log n ) O(\log n) O(logn)。
空间复杂度:只需要使用常量级别的额外空间,因此空间复杂度为 O ( 1 ) O(1) O(1)。
class Solution {public int countDigitOne(int n) {if (n == 0) { // 如果n为0,直接返回0return 0;}long bit = 1; // bit表示当前处理的位数long cur = n / bit % 10; // cur表示当前处理的数字long low = n % bit; // low表示当前位数以下的数字long high = n / bit / 10; // high表示当前位数以上的数字long res = 0; // res表示1的个数while (bit <= n) { // 当位数小于等于n的位数时,继续处理if (cur < 1) { // 如果当前位数的数字小于1,1的个数为high*bitres += high * bit;} else if (cur == 1) { // 如果当前位数的数字等于1,1的个数为high*bit+low+1res += high * bit + low + 1;} else { // 如果当前位数的数字大于1,1的个数为(high+1)*bitres += (high + 1) * bit;}bit *= 10; // 处理下一位数cur = n / bit % 10;low = n % bit;high = n / bit / 10;}return (int) res; // 返回1的个数}
}
51. 数组中的逆序对
题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
思路分析: 在归并排序的过程中,每次合并两个有序的子数组时,需要统计逆序对数量。具体实现时,在合并过程中,如果左半段的数大于等于右半段的数,则说明左半段中剩余的数都比右半段的数大,因此可以直接统计逆序对数量。
时间复杂度:归并排序的时间复杂度为O(nlogn),而在归并排序的过程中,每次合并两个有序的子数组时,需要遍历所有元素一次,因此合并的时间复杂度也是O(nlogn)。因此总的时间复杂度为O(nlogn)。
空间复杂度:归并排序需要使用一个临时数组来存储合并过程中的数据,因此空间复杂度为O(n)。
class Solution {int res = 0; // 记录逆序对数量public int reversePairs(int[] nums) {if (nums == null || nums.length == 0) {return 0;}mergeSort(nums, 0, nums.length - 1); // 归并排序return res; // 返回逆序对数量}private void mergeSort(int[] nums, int l, int r) {if (l >= r) {return;}int mid = (r - l) / 2 + l; // 计算中间位置mergeSort(nums, l, mid); // 对左半段进行归并排序mergeSort(nums, mid + 1, r); // 对右半段进行归并排序merge(nums, l, mid, r); // 合并左右两个有序的子数组}private void merge(int[] nums, int l, int mid, int r) {int i = l; // 左半段的起始位置int j = mid + 1; // 右半段的起始位置int[] temp = new int[r - l + 1]; // 用于存储合并过程中的数据int index = 0; // 临时数组的下标while (i <= mid && j <= r) { // 合并左右两个有序的子数组if (nums[i] <= nums[j]) { // 如果左半段的数小于右半段的数temp[index++] = nums[i++]; // 将左半段的数加入临时数组中} else { // 如果左半段的数大于等于右半段的数res += mid - i + 1; // 统计逆序对数量temp[index++] = nums[j++]; // 将右半段的数加入临时数组中}}// 将剩余的元素复制到临时数组中while (i <= mid) {temp[index++] = nums[i++];}while (j <= r) {temp[index++] = nums[j++];}// 将临时数组中的元素复制回原数组中index = 0;for (i = l; i <= r; i++) {nums[i] = temp[index++];}}
}
56 - II. 数组中数字出现的次数 II
题目:在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1:
输入:nums = [3,4,3,3]
输出:4
思路分析: 对于每一位,统计所有数字在该位上出现的次数,然后对3取模,得到出现1次的数字在该位上的值。最后将所有位的值合并起来,即得到最终结果。
时间复杂度为O(nk),其中n为数字数量,k为数字的二进制位数,因为需要遍历所有数字和所有位数。
空间复杂度为O(k),因为需要使用一个长度为k的数组来记录每个数字在每个位上出现的次数。
class Solution {public int singleNumber(int[] nums) {if(nums == null || nums.length == 0){return -1;}int res = 0; // 用于存储最终结果int bit = 1; // 用于表示当前位的值,从最低位开始int[] count = new int[32]; // 用于记录所有数字在当前位上出现的次数for(int i = 0; i < 32; i++){ // 遍历所有位for(int j = 0; j < nums.length; j++){ // 遍历所有数字if((nums[j] & bit) != 0){ // 如果当前数字在当前位上为1count[i]++; // 记录出现次数}}count[i] %= 3; // 对3取模,得到出现1次的数字在当前位上的值res += bit * count[i]; // 将当前位的值加入最终结果bit <<= 1; // 判断下一位}return res; // 返回最终结果}
}
相关文章:
剑指 Offer第二版:1~n 整数中 1 出现的次数、51. 数组中的逆序对、56 - II. 数组中数字出现的次数 II
剑指 Offer第二版 43. 1~n 整数中 1 出现的次数51. 数组中的逆序对56 - II. 数组中数字出现的次数 II 43. 1~n 整数中 1 出现的次数 题目:输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。 例如,…...
云原生-k8s核心概念(pod,deploy,service,ingress,configmap,volume)
Gitee-k8s学习 云原生实战-kubernetes核心实战 namespace Namespace是kubernetes系统中的一种非常重要资源,它的主要作用是用来实现多套环境的资源隔离或者多租户的资源隔离 Pod Pod可以认为是容器的封装,一个Pod中可以存在一个或者多个容器。 De…...
他工作10年,老板却让他走人
大家好,我是五月,一个编程街溜子。 二狗被裁了,他在公司待了快十年,他想留下来,老板却让他走。 我和他一样困惑。 他985毕业,工作中有从0开始一个项目直到日活过千万,也有过参与顶级产品核心…...
vpp怎么写node
VPP(Vector Packet Processing)是一个高性能的数据平面开源项目,用于构建网络功能虚拟化(NFV)和软件定义网络(SDN)解决方案。它由Cisco开发,并在Apache 2.0许可下发布。 在VPP中&am…...
【4. ROS的主要通讯方式:Topic话题与Message消息】
【4. ROS的主要通讯方式:Topic话题与Message消息】 1. 前言1.1 王者解释结点通讯:1.2 通讯小结 2. 灵活的Topic话题图解2.1 话题注意细节2.2 外延补充 3. Message消息图解3.1 消息类型3.2 查看标准消息类型std_msgs 4. 使用C实现Publisher发布者4.1 发布…...
【react全家桶学习】react中组件定义及state属性(超详/必看)
函数式组件定义及特点 定义(核心就是一个函数,返回虚拟dom): import React from reactexport default function index() {return <div>index</div> }特点: 1、适用于【简单组件】的定义2、是一个函数&a…...
如何以产品经理思维打造一所高品质学校?
学校的建设与管理真不是一件容易事。2023年03月17日,山东菏泽市曹县一家长投诉某中学课业繁重,孩子经常写作业到半夜;2023年4月4日,张先生在华龙网重庆网络问政平台投诉万州区某中学伙食差,指出“发灰的洋葱࿰…...
根治Spring中使用Mongo时报错InvalidMongoDbApiUsageException
文章目录 And Or迷惑原因 告别InvalidMongoDbApiUsageException问题简单解决根本解决修改源码 代码(省流,可以直接看这里) And Or 很多时候都需要进行逻辑的与或操作,但是spring当中自带的操作并不好用,于是做了相关的改进&#…...
【计算机组成原理】数据的表示和运算·进位计数制
🚩 本文已收录至专栏:计算机基础 我们可以通过显示屏看到各种形式的数据信息,但数据是如何在计算机中表示呢?运算器又是如何实现数据的算数、逻辑运算? 十进制数是最适合我们日常使用的一种计数方式,除此之…...
C++ Primer第五版_第十四章习题答案(21~30)
文章目录 练习14.21练习14.22头文件CPP文件 练习14.23头文件CPP文件 练习14.24头文件CPP文件 练习14.25练习14.26练习14.27练习14.28练习14.29练习14.30 练习14.21 编写 Sales_data 类的 和 运算符,使得 执行实际的加法操作而 调用。相比14.3节和14.4节对这两个运…...
服务器性能调优
硬件 如果是硬件瓶颈就换硬件 (包括CPU、内存、网卡) 软件 如果是方案架构设计有问题就换方案,比如mysql、redis方案有问题 建议先 top 看下软件瓶颈在哪,CPU、内存、网络(netstat),哪个进程占…...
带你深入学习k8s--(三) pod 管理
目录 一、简介 1、什么是pod 2、为什么要有pod 二、pod的分类 0、pod常用命令命令 1、准备镜像 2、自主式pod 3、控制器创建pod 4、扩容pod数量 5、通过service暴露pod(负载均衡,自动发起) 6、更新应用版本 三、编写yaml文件 四、Pod生命周期…...
前端系列11集-ES6 知识总结
ES Module 优点 静态分析 浏览器和 Node 都支持 浏览器的新 API 能用模块格式提供 不再需要对象作为命名空间 export 用于规定模块的对外接口 输出的接口与其对应的值是动态绑定关系可以取到模块内部实时的值 import 用于输入其他模块提供的功能 具有提升效果,会提升…...
连接分析工具箱 | 利用CATO进行结构和功能连接重建
导读 本研究描述了一个连接分析工具箱(CATO),用于基于扩散加权成像(DWI)和静息态功能磁共振成像(rs-fMRI)数据来重建大脑结构和功能连接。CATO是一个多模态软件包,使研究人员能够运行从MRI数据到结构和功能连接组图的端到端重建,定制其分析并…...
【目标检测论文阅读笔记】Detection of plane in remote sensing images using super-resolution
Abstract 由于大量的小目标、实例级噪声和云遮挡等因素,遥感图像的目标检测精度低,漏检率或误检率高。本文提出了一种新的基于SRGAN和YOLOV3的目标检测模型,称为SR-YOLO。解决了SRGAN网络 对超参数的敏感性和模态崩溃问题。同时,Y…...
外卖app开发流程全解析
外卖app开发是现代餐饮业的一个必备部分。在这个数字化时代,人们更愿意使用手机应用程序来订购食品。因此,为了满足客户需求,餐饮企业需要开发自己的外卖app。 第一步:确定目标受众 在开始外卖app的开发之前,需要确定…...
BUUCTF jarvisoj_level0
小白垃圾做题笔记而已,不建议阅读。。。 这道题感觉主要就是64位程序ebp8 题目中给出了shellcode 我们直接将返回地址覆盖就好。 在main函数中调用了vulnerable_function()函数。 vulnerable函数是一个漏洞函数:(存在缓溢出),我们只需要将…...
网络安全之入侵检测
目录 网络安全之入侵检测 入侵检测经典理论 经典检测模型 入侵检测作用与原理 意义 异常检测模型(Anomaly Detection) 误用检测模型(Misuse Detection) 经典特征案例 编辑自定义签名 编辑 签名检查过程 检测生命周期…...
元数据管理
1、业务元数据 描述 ”数据”背后的业务含义主题定义:每段 ETL、表背后的归属业务主题。业务描述:每段代码实现的具体业务逻辑。标准指标:类似于 BI 中的语义层、数仓中的一致性事实;将分析中的指标进行规范化。标准维度…...
C# WebService的开发以及客户端调用
目录 1、WebService简介 1.1 什么是XML? 1.2 什么是Soap? 1.3 什么是WSDL? 2、WebService与WebApi的区别与优缺点 2.1 WebService与WebApi的区别: 2.2 WebService的优缺点: 2.3 WebApi的优缺点: 3…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
