剑指Offer专项突击版题解一
1.整数除法
思想:不能用除法、乘法、取余,那么可以用减法完成除法的操作,但是在减去被除数的时候,可以考虑被除数<<1扩大一倍在进行减少,加快减的速率。
2.二进制加法
思想:从末尾向前遍历,类似这种有长短不一的需要累计的时候,可以采用for i>0 || j > 0 {内部在进行判断该值是否有贡献}
3.前n个数二进制1的个数
这里隐藏着2的倍数和之间二进制1的个数的关系,2和4的二进制个数相等。
4.出现1次的数字其余都是三次
原版本是找出出现一次的数字,其余都是出现两次,这个只需要全部异或就能得出答案,但是出现三次的要进行过滤的话,需要从二进制的角度去考虑,某一位,数组中累积和事3的倍数的话,这一位置肯定是出现三次的,否则是一位中的。注意:go语言中int是变化的,在这个题目中需要指定int32,否则会出现溢出的情况。
5.单词长度最大的乘积
题目要求:两个字符串之间没有字符交集
暴力做法:在单词数组中,找出两个互补包含相同字符的串的乘积的最大值,思路是采用暴力双层遍历,先对数组按照字符串的长度进行降序排序,关键是如何快速判断两个字符串包含相同的字符,超时做法是:用一个map记录a,然后在判断b,取巧的方式是采用strings.indexByte内置的api。
二进制做法(位运算):因为字符串只包含小写的英文字母,那么判断两个字符串是否有相同的字符可以考虑将字符串转换成数字,通过a&b ==0 表示字符串没有共同字符。
6.排序数组中找出两个数之和等于target
方法一:直接采用二分查找去做,方法二:可以采用变循环边加入map,通过map[tar-val]判断是否存在,一遍就能找出答案。
7.找出数组中三数之和为零的数
先排序,然后可以用两层遍历+去重复判断(i != 0 && nums[i] != nums[i-1),最后一维可以采用二分查找来做。
8.找出最短的字数组的和大于等于target的长度
暴力法:先计算前缀和,然后通过暴力从短到长的进行判断。
滑动窗口:由小窗口在逐渐变大,达到目的值的时候在逐渐减少(数组都是正数)。
func numSubarrayProductLessThanK(nums []int, k int) int {res := 0left := 0right := 0cv := 1for right < len(nums){cv *= nums[right]for left <= right && cv >= k { // 如果当前的滑动窗口需要进行变化cv /= nums[left]left++}res = res + (right - left + 1) // 含义:以right结尾的所有满足条件字数组的情况right++}return res
}
前缀和+二分查找:由于本题目的前缀和是递增的,因此也可以考虑用二分查找需要的值
9.找出子数组中积少的target的个数
滑动窗口:(数组中都为正数)
func numSubarrayProductLessThanK(nums []int, k int) int {res := 0left := 0right := 0cv := 1for right < len(nums){cv *= nums[right]for left <= right && cv >= k { // 如果当前的滑动窗口需要进行变化cv /= nums[left]left++}res = res + (right - left + 1) // 含义:以right结尾的所有满足条件字数组的情况right++}return res
}
10.和为k的子数组
很容易根据上面题目联想到使用滑动窗口,但是这题目nums中包含非正数,这导致了滑动窗口不知道往哪边滑,因此不能采取。
暴力法:枚举出所有的情况,最后几个用例超时了(暴力写法纠正),纠正暴力写法之后通过。
动态规划法:让我想到了01背包问题,01背包包括是否重复选,但是这里又和01重复选背包不同,这里要求是连续数组。
可以采用前缀和+加map一层遍历解决,思想和找出数组中两数之和为tar的方法一样。
遍历+map写法,只要target确定,可以考虑这种写法
func subarraySum(nums []int, k int) int {count, pre := 0, 0m := map[int]int{}m[0] = 1for i := 0; i < len(nums); i++ {pre += nums[i]if _, ok := m[pre - k]; ok {count += m[pre - k]}m[pre] += 1}return count
}
暴力写法的纠正
// 通过写法
func subarraySum(nums []int, k int) int {preSum := make([]int , len(nums))cv := 0res := 0for i := 0 ; i < len(nums); i++{cv += nums[i]preSum[i] = cv}// fmt.Println(preSum)for i := 0 ; i < len(nums); i++{for j := i ; j < len(nums); j++{cv := preSum[j]if i != 0{cv -= preSum[i-1]}if cv == k{res ++}}}return res
}
// 超时写法,很好理解代码的思路,但是超时
func subarraySum(nums []int, k int) int {preSum := make([]int , len(nums))cv := 0res := 0for i := 0 ; i < len(nums); i++{cv += nums[i]preSum[i] = cv}// fmt.Println(preSum)for clen:= 1; clen <= len(nums); clen++{for i := 0 ; i <= len(nums) - clen; i++{j := i + clen - 1if j >= len(nums){break}cv := preSum[j]if i != 0{cv -= preSum[i-1]}if cv == k{res++}// fmt.Println(cv)}}return res
}
相关文章:
剑指Offer专项突击版题解一
1.整数除法 思想:不能用除法、乘法、取余,那么可以用减法完成除法的操作,但是在减去被除数的时候,可以考虑被除数<<1扩大一倍在进行减少,加快减的速率。 2.二进制加法 思想:从末尾向前遍历࿰…...

Django框架之模型
模型 当前项目的开发, 都是数据驱动的。 以下为书籍信息管理的数据关系:书籍和人物是 :一对多关系 要先分析出项目中所需要的数据, 然后设计数据库表. 书籍信息表 字段名字段类型字段说明idAutoField主键nameCharField书名 idname1西游记2三国演义…...

OSACN-Net:使用深度学习和Gabor心电图信号谱图进行睡眠呼吸暂停分类
这篇文章在之前读过一次,其主要的思路就是利用Gabor变换,将心电信号转变为光谱图进行识别研究,总体来讲,不同于其他的利用心电信号分类的算法,该论文将心电信号转换为光谱图,在此基础上,分类问题…...

使用开源实时监控系统 HertzBeat 5分钟搞定 Mysql 数据库监控告警
使用开源实时监控系统 HertzBeat 对 Mysql 数据库监控告警实践,5分钟搞定! Mysql 数据库介绍 MySQL是一个开源关系型数据库管理系统,由瑞典MySQL AB 公司开发,属于 Oracle 旗下产品。MySQL 是最流行的开源关系型数据库管理系统之…...

插件 sortablejs:HTML元素可拖动排序
插件 sortablejs 用于可重新排序拖放列表的JavaScript库;关键链接:npm 地址 Github 地址 安装 npm i sortablejs引入 import Sortable from "sortablejs"HTML <ul id"items"><li>item 1</li><li>item …...

libVLC 视频裁剪
作者: 一去、二三里 个人微信号: iwaleon 微信公众号: 高效程序员 裁剪是指去除图像的外部部分,也就是从图像的左,右,顶部和/或底部移除一些东西。通常在视频中,裁剪是一种通过剪切不需要的部分来改变宽高比的特殊方式。 尤其是在做视频墙时,往往需要处理多个 vlc 实例…...

LAMP架构介绍及配置
LAMP架构介绍及配置一、LAMP简介与概述1、LAMP平台概述2、LAMP各组件主要作用3、构建LAMP平台二、编译安装Apache htpd服务1、将所需软件包上传到/opt目录下2、解压以下文件3、移动两个文件并改名4、安装所需工具5、编译安装6、做软连接,使文件可执行7、优化配置文件…...

Android图形显示流程简介
注:本文缩写说明本文代码都是基于Android S一、概述本文将对从App画出一帧画面到这帧画面是如何到达屏幕并最终被人眼看到的这一过程进行简要分析,并将这其中涉及到的各个流程与其在systrace上的体现对应起来,期望最终能够让读者对Android系统…...

4.5.3 ArrayList
文章目录1.特点2. 练习:ArrayList测试3.ArrayList扩容1.特点 存在java.util包中内部是用数组结构存放数据,封装数组的操作,每个对象都有下标内部数组默认的初始容量是10,如果不够会以1.5倍的容量增长查询快,增删数据效率会低 2. 练习:ArrayList测试 package partThree;import…...

十二、Linux文件 - fseek函数讲解
目录 一、fseek函数讲解 二、fseek函数实战 一、fseek函数讲解 重定向文件内部的指针 注:光标 ---- 文件内部的指针 函数原型: int fseek(FILE *stream,long offset,int framewhere) 参数: stream:文件指针offset:…...

Python3.10新特性之match语句示例详解
这篇文章主要为大家介绍了Python3.10新特性之match语句示例详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪正文在Python 3.10发布之前,Python是没有类似于其他语言中switch语句的&…...

虎牙盈利能力得到改善,但监管风险对其收入产生负面影响
来源:猛兽财经 作者:猛兽财经 监管风险再次成为焦点 过去一段时间,与中概股相关的监管风险再次引起了投资者的注意,这也是正在考虑投资虎牙(HUYA)的投资者需要注意的问题。 例如,监管机构在2022…...
HBase 分布式搭建
前言: 请先确保 Hadoop 集群搭建完成。 Hadoop 完全分布式搭建(超详细)搭建环境介绍: 三台主机,一主两从,系统为 Centos 7.5。 相关组件版本信息如下: jdk1.8hadoop-3.1.3zookeeper-3.5.7hbase-2.2.3注意,以下安装教程中涉及到的路径请替换成自己的! ZooKeeper 安…...
【Python】修改枚举的取值及链式调用
author: jwensh date: 2023.02.11 文章目录枚举的取值及链式调用需求背景1. enum.key 即获取值(而不是 enum.key.value)2. 多级链式调用枚举的取值及链式调用 需求背景 测试过程中需要很多参数化的设置及编程规范要求,希望修改数据不修改代…...

复现篇--zi2zi
intro: 用GAN学习东亚语言字体。zi2zi(意思是从字符到字符)是最近流行的pix2pix模型在汉字上的应用和扩展。 article:https://kaonashi-tyc.github.io/2017/04/06/zi2zi.html code:https://github.com/kaonashi-tyc/zi2zi pytorch版本:https://github.com/EuphoriaYan/zi2…...

153、【动态规划】leetcode ——416. 分割等和子集:滚动数组(C++版本)
题目描述 原题链接:1049. 最后一块石头的重量 II 解题思路 本题要找的是最小重量,我们可以将石头划分成两个集合,当两个集合的重量越接近时,相减后,可达到的装量就会是最小,此时本题的思路其实就类似于 4…...

linux head命令(head指令)(获取文件或管道输出结果前n行,默认前10行)与sed命令区别
head命令是一个在Linux系统中常用的命令,用于读取文件的前几行(默认读取前10行) 文章目录使用方法读取文件的前10行:head filename读取文件的前n行:head -n行数 filename读取多个文件的前几行:head -n 行数…...

Mysql数据库09——分组聚合函数
类似pandas里面的groupby函数,SQL里面的GROUP BY子句也是可以达到分组聚合的效果。 常用的聚合函数有COUNT(),SUM(),AVG(),MAX(),MIN(),其用法看名字都看的出来,下面一一介绍 聚合函数 COUNT()计数 统计student表中计科系学生的人数。 SE…...
第43章 菜单实体及其约束规则的定义实现
1 Core.Domain.Security.Menu namespace Core.Domain.Security { /// <summary> /// 【菜单--类】 /// <remarks> /// 摘要: /// 通过该实体类及其属性成员,用于实现当前程序【Core】.【领域】.【安全】.【菜单】实体与“[ShopDemo].[…...

OpenAI最重要的模型【CLIP】
最近的 AI 突破 DALLE和 Stable Diffusion有什么共同点? 它们都使用 CLIP 架构的组件。 因此,如果你想掌握这些模型是如何工作的,了解 CLIP 是先决条件。 此外,CLIP 已被用于在 Unsplash 上索引照片。 但是 CLIP 做了什么&…...

业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...

cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...

五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...

python可视化:俄乌战争时间线关键节点与深层原因
俄乌战争时间线可视化分析:关键节点与深层原因 俄乌战争是21世纪欧洲最具影响力的地缘政治冲突之一,自2022年2月爆发以来已持续超过3年。 本文将通过Python可视化工具,系统分析这场战争的时间线、关键节点及其背后的深层原因,全面…...

Pycharm的终端无法使用Anaconda命令行问题详细解决教程
很多初学者在Windows系统上安装了Anaconda后,在PyCharm终端中运行Conda命令时,会遇到以下错误: conda : 无法将“conda”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。 请检查名称的拼写,如果包括路径,请确保…...