《剑指offer》(5)搜索算法、位运算、模拟

方法一:

class Solution:

    def GetNumberOfK(self , nums: List[int], k: int) -> int:

        #从两边开始找,找到之后记录当前位置

        left = 0

        right = len(nums) - 1

        if k not in nums:

            return 0

        start = len(nums) - 1

        end = 0

        while left <= right:

            if nums[left] < k:

                left += 1

            if nums[left] == k:

                start = min(left,start)

                left += 1

            if nums[right] > k :

                right -= 1

            if nums[right] == k:

                end = max(right,end)

                right -= 1

        return end - start + 1

方法二:

class Solution:

    def divice(self,nums,k):

        left = 0

        right = len(nums) - 1

        while left <= right:

            mid = (right + left)//2

            if nums[mid] < k:

                left = mid + 1

            elif nums[mid] > k:

                right = mid - 1

        return left

    def GetNumberOfK(self , nums: List[int], k: int) -> int:

        #二分法查找k+0.5和k-0.5的位置,中间部分就是k

        return self.divice(nums,k+0.5) - self.divice(nums,k-0.5)

#线性搜索:首先从数组左下角搜索,如果当前数字大于target,那么查找往上移一位,如果当前数字小于target,那么查找往右移一位。查找到target,返回true; 如果越界,返回false; 

class Solution:

    def Find(self , target: int, array: List[List[int]]) -> bool:

        if len(array) == 0:

            return False

        row = len(array)

        col = len(array[0])

        c,r = 0,row - 1 #从左下角开始搜索

        while c < col and r >= 0:

            temp = array[r][c]

            if temp < target:#往右移动

                c += 1

            if temp > target: #往上移动

                r -= 1

            if temp == target:

                return True

        return False

# 旋转之后,前半段和后半段都是升序,所以要确定最小值在后半段

#二分法,如果mid比right大,那mid在前半段中,让left = mid+1;如果mid比right小,mid在后半段,让right=mid,如果等无法判断是前半段还是后半段,right-=1,缩小判断范围。

class Solution:

    def minNumberInRotateArray(self , nums: List[int]) -> int:

        left = 0

        right = len(nums) - 1

        if len(nums) == 0:

            return 0

        while left < right:

            mid = (right+left)//2

            if nums[mid] > nums[right]:

                left = mid + 1

            elif nums[mid] < nums[right]:

                right = mid

            elif nums[mid] == nums[right]:

                right -= 1

        return nums[left]

全排列,递归回溯,每次将递归的层数和字符串下传,在[h,size-1]中的元素互换,然后递归,递归回来恢复现场

class Solution:

    def Permutation(self , s: str) -> List[str]:

        ans = []

        s = list(s)

        def dfs(h,string):

            if h == len(s) - 1:

                nonlocal ans

                ans.append(''.join(s))

                return

            for i in range(h,len(s)):

                s[i],s[h] = s[h],s[i]

                dfs(h+1,s)

                s[i],s[h] = s[h],s[i] #恢复现场

        dfs(0,s)

        ans = list(set(ans)) #因为没有在递归的时候拦住相等的元素重排列, 所以最后要去重

        return ans

class Solution:

    def findNthDigit(self , n: int) -> int:

        #1~9 9*1=9个数字

        #10~99 9*10*2=180个数字

        #100~999 9*100*3=2700个数字

        weishu = 1 #当前数字一共有多少位

        start = 1 #当前数字起始区间的一个数字是多少

        Sum = 9 #该区间一共多少个数字

        while n > Sum:

            n -= Sum

            weishu += 1

            start *= 10

            Sum = 9*weishu*start

        num = start+(n-1)//weishu #确定是哪个数字

        index = (n-1)%weishu #确定数字在哪一位

        return int(str(num)[index])

class Solution:

    def add(self, a: int, b: int) -> int:

        #要考虑负数的情况,python是用补码存储

        x = 0xffffffff

        a,b = a & x,b & x #获取补码

        while b != 0:

            a,b = a ^ b, (a & b)<<1 & x #可能超32位的也要补码

        return a if a <= 0x7fffffff else ~(a^x) #按位取反后将整个数字取反

class Solution:

    def NumberOf1(self , n: int) -> int:

        #考虑移位运算,每次移动一位;遍历二进制的32位,通过移位0-31次实现

        #将移位后的1与数字进行位与运算,结果为1就记录一次。

        res = 0

        for i in range(32):

            if n & (1 << i) != 0:

                res += 1

        return res

 用递归来累加

class Solution:

    def Sum_Solution(self, n):

        if n == 1:

            return 1

        return self.Sum_Solution(n-1)+n

方法一:使用哈希表,遍历数组,如果数组中的元素在key中,就删除掉这个元素。如果不在key中,就将其值置为1.最后排序一下哈希表,输出key。

class Solution:

    def FindNumsAppearOnce(self , nums: List[int]) -> List[int]:

        #第一种,使用哈希表

        dict_data = {}

        for i in nums:

            if i not in dict_data:

                dict_data[i] = 1

            else:

                dict_data.pop(i)

        res = [i for i in sorted(dict_data.keys())]

        return res

#第二种,位运算

class Solution:

    def FindNumsAppearOnce(self , nums: List[int]) -> List[int]:       

 #先将全部进行异或运算,得到的是两个不同的数的异或结果

        temp = 0

        for i in nums:

            temp ^= i

        #分组,每组求出一个异或结果;从最低位开始找到这两个数不同的那个二进制1

        mask = 1

        while temp & mask == 0:

            mask = mask << 1

        #根据mask的分组结果,将两组数据进行异或

        a = 0

        b = 0

        for i in nums:

            if i & mask == 0:

                a ^= i

            else:

                b ^= i

        return [a,b] if a < b else [b,a]

class Solution:

    def Power(self , base: float, exponent: int) -> float:

        #如果两个通时是0就判错返回

        if base == 0 and exponent == 0:

            return False

        #特别处理负次幂

        if exponent < 0:

            base = 1/base

            exponent = -exponent

        #根据幂指数累乘

        res = 1

        for i in range(exponent):

            res *= base

        return res

class Solution:

    def printMatrix(self, matrix):

        #顺时针就是先向右移动,到底后向下,然后向左,再向上。设置四个边界,每次遍历之后就更新边界,遇到边界后退出。

        res = []

        if len(matrix) == 0:

            return []

        left,right,down,up = 0, len(matrix[0]) - 1, len(matrix) - 1, 0

        #直到边界重合

        while left <= right and up <= down:

            #先从左到右

            for i in range(left,right+1):

                res.append(matrix[up][i])

            up += 1 #重置行数

            if up > down: #重置之后要判断当前是否已经没有剩余行了

                break

            #从上到下

            for i in range(up,down+1):

                res.append(matrix[i][right])

            right -= 1 #重置列

            if right < left: #重置之后查看当前是否已经没有剩余列了

                break

            #从右往左

            for i in range(right,left-1,-1):

                res.append(matrix[down][i])

            down -= 1 #重置行

            #从下往上

            for i in range(down,up-1,-1):

                res.append(matrix[i][left])

            left += 1 #重置列

        return res

给数组排序, 然后计算0的个数,找到第一个不是0的数,计算两两之间的差值;如果出现了两个相同的不为0的数,就一定不是顺子;0的个数大于累加和就是顺子。

class Solution:

    def IsContinuous(self , numbers: List[int]) -> bool:

        #将数组排序,计算0的个数,超过4就返回FALSE,找到第一个不为0的数,计算两两差值,累加和0比较。

        num_0 = 0

        sum_0 = 0

        numbers = sorted(numbers)

        for i in range(len(numbers)-1):

            if numbers[i] == 0:

                num_0 += 1

            else:

                sum_0 += numbers[i+1] - numbers[i] - 1 if numbers[i+1] > numbers[i] else 1000 #保证sum_0在不是顺子的时候大于num_0.

        if num_0 > 4:

            return False

        else:

            if num_0 >= sum_0:

                return True

            else:

                return False

class Solution:

    def StrToInt(self , s: str) -> int:

        #首先去掉字符串的首位空格,然后判断数字的符号位,然后开始遍历字符串,遇到非数字就跳过,最后做范围判断

        #去空格

        s = s.strip()

        #长度判断

        if len(s) == 0:

            return 0

        #确定符号位后去掉符号位

        sign = -1 if s[0] == '-' else 1

        s = s[1:] if s[0] == '+' or s[0] == '-' else s

        #拼接res,如果去掉符号位后是空,那最后也能返回0,首字符是0不影响结果

        res = ['0']

        for i in range(len(s)):

            j = i

            while j < len(s) and '0' <= s[j] <= '9':

                res.append(s[j])

                j += 1

            break #出循环之后就直接break

        # 确定边界值

        MAX = 2**31 - 1

        MIN = -2**31

        #计算整数,并根据边界值输出

        ans = sign*int(''.join(res))

        if MIN <= ans <= MAX:

            return ans

        if ans < MIN:

            return MIN

        if ans > MAX:

            return MAX

class Solution:

    #判断是否是整数(带符号)

    def isInt(self,num):

        if len(num) == 0 or (len(num) == 1 and num[0] in ['+','-']):

            return False

        ans = [i for i in num if not '0' <= i <= '9']

        return len(ans) == 0 or (len(ans) == 1 and num[0] in ['+','-'])

    #判断是否是小数(带符号)

    def isFloat(self,num):

        if len(num) == 0 or '.' not in num :

            return False

        #去掉符号位

        num = num[1:] if num[0] in ['+','-'] else num

        #获得小数点的下标

        ind = num.index('.')

        #判断是否是小数

        a = self.isInt(num[:ind]) #前半段可以是带符号整数

        b = self.isInt(num[ind+1:]) and '+' not in num[ind+1:] and '-' not in num[ind+1:] #后半段不可以带符号

        if len(num[:ind]) == 0 : return b #如果前半段为空,后边必须成立

        elif len(num[ind+1:]) == 0 : return a #如果后半段是空,前面必须成立

        else: return a and b #都不空的时候,都得成立

#判断字符串

    def isNumeric(self , s ):

        #去空格

        s = s.strip()

        #判断长度

        if len(s) == 0:

            return False

        #分类判断

        for i in range(len(s)):

            if '0' <= s[i] <= '9':

                continue #数字就跳过

            elif s[i] in ['e','E']: #遇到e之后,判断两段

                a = self.isFloat(s[:i]) or self.isInt(s[:i]) #前半段整数或小数

                b = self.isInt(s[i+1:]) #后半段必须整数

                return a and b

            elif s[i] == '.': #遇到.

                if 'e' in s or 'E' in s: #如果有e,就先跳过

                    continue

                else: #否则判断是否是小数

                    return self.isFloat(s)

            elif s[i] in ['+','-']: #遇到符号位如果是最开始或者e后面,跳过

                if i == 0 or s[i-1] in ['e','E']:

                    continue

                else: #否则就是错误的

                    return False

            else: #遇到其他字符直接报错

                return False

        return '0' <= s[-1] <= '9' #出循环后要保证最后跳过的是数字

 

 

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Vue2源码分析-day1

初始化数据 vue中最核心的我们都知道那就是响应式数据&#xff0c;数据的变化视图自动更新。那么我们来new一个我们自己的vue 在index.html文件下加入如下代码&#xff0c;这也是vue最常见的基本结构。data已经有了下面我们来获取data的数据 <script src"./vue.js&qu…

[openCV]基于拟合中线的智能车巡线方案V3

import cv2 as cv import os import numpy as np# 遍历文件夹函数 def getFileList(dir, Filelist, extNone):"""获取文件夹及其子文件夹中文件列表输入 dir&#xff1a;文件夹根目录输入 ext: 扩展名返回&#xff1a; 文件路径列表"""newDir d…

『Samba』在Linux中实现高效访问和管理共享文件夹的基本操作与实践

&#x1f4e3;读完这篇文章里你能收获到 Samba 的安装和配置&#xff1a;详细介绍了如何在 Linux 操作系统上安装和配置 Samba 服务器共享文件夹的设置&#xff1a;指导如何选择要共享的文件夹&#xff0c;并为其设置共享名称、路径以及访问权限Samba 用户的创建&#xff1a;提…

C# App.config和Web.config加密

步骤1&#xff1a;创建加密命令 使用ASP.NET提供的命令工具aspnet_regiis来创建加密命令。 1、打开控制台窗口&#xff0c;在命令行中输入以下命令&#xff1a; cd C:\Windows\Microsoft.NET\Framework\v4.xxxxx aspnet_regiis.exe -pef connectionStrings "C:\MyAppFo…

搭建 elasticsearch8.8.2 伪集群 windows

下载windows 版本 elasticsearch8.8.2 以下链接为es 历史版本下载地址&#xff1a; Past Releases of Elastic Stack Software | Elastic windows 单节点建立方案&#xff1a; 下载安装包 elasticsearch-8.8.2-windows-x86_64.zip https://artifacts.elastic.co/download…

代码随想录算法训练营第51天|动态规划part09|198.打家劫舍、213.打家劫舍II、337.打家劫舍III

代码随想录算法训练营第51天&#xff5c;动态规划part09&#xff5c;198.打家劫舍、213.打家劫舍II、337.打家劫舍III 198.打家劫舍 198.打家劫舍 思路&#xff1a; 仔细一想&#xff0c;当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。 所以这里就更感觉到&a…

机器学习鱼书笔记(自用更新)

零、预知识 1.Numpy 使用 介绍&#xff1a;高效的操作多维数组的函数库。 安装&#xff1a;&#xff08;前提已经安装了python&#xff09; pip install numpy导入 import numpy as np创建数组 Numpy最重要的数据结构是多维数组&#xff08;ndarray&#xff09;。通过Numpy&…

农商行基于分类分级的数据安全管控建设实践

《数据安全法》颁布实施以来&#xff0c;以分类分级为基础&#xff0c;对数据进行差异化管理和防护&#xff0c;成为行业共识。 金融行业作为数据密集的高地&#xff0c;安全是重中之重&#xff0c;而鉴于金融数据种类和内容庞杂&#xff0c;面临规模化用数、普惠用数、跨机构共…

分布式协议与算法——Paxos算法

目录 Paxos算法Basic Paxos算法三种角色如何达成共识&#xff08;协商过程&#xff09;小结&#xff1a; Multi-Paxos算法关于 Multi-Paxos 的思考领导者优化Basic PaxosChubby 的 Multi-Paxos 实现小结 参考 Paxos算法 Paxos论文 Paxos Made Simple 、author&#xff1a;Lesli…

wireshark 安装和使用

wireshark&#xff0c;世界上最受欢迎的网络协议分析器。是一个网络流量分析器&#xff0c;或“嗅探器”&#xff0c;适用于Linux、macOS、*BSD和其他Unix和类Unix操作系统以及Windows。它使用图形用户界面库Qt以及libpcap和npcap作为数据包捕获和过滤库。 wireshark&#xff…

Flamingo

基于已有的图像模型和文本模型构建多模态模型。输入是图像、视频和文本&#xff0c;输出是文本。 Vision encoder来自预训练的NormalizerFree ResNet (NFNet)&#xff0c;之后经过图文对比损失学习。图片经过图像模型的输出是2D grid&#xff0c;视频按1FPS的频率采样后经过图…

【2种方法,jmeter用一个正则提取器提取多个值!】

jmeter中&#xff0c;用json提取器&#xff0c;一次提取多个值&#xff0c;这个很多人都会。但是&#xff0c;用正则提取器一次提取多个&#xff0c;是否可以呢&#xff1f; 肯定&#xff0c;很多人都自信满满的说&#xff0c;可以&#xff01;形如&#xff1a;token":&q…

Python入门【​编辑、组合、设计模式_工厂模式实现 、设计模式_单例模式实现、工厂和单例模式结合、异常是什么?异常的解决思路 】(十七)

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱敲代码的小王&#xff0c;CSDN博客博主,Python小白 &#x1f4d5;系列专栏&#xff1a;python入门到实战、Python爬虫开发、Python办公自动化、Python数据分析、Python前后端开发 &#x1f4e7;如果文章知识点有错误…

matlab使用教程(10)—脚本和函数

1.概述 MATLAB 提供了一个强大的编程语言和交互式计算环境。您可以使用此语言在 MATLAB 命令行中一次输入一个命令&#xff0c;也可以向某个文件写入一系列命令&#xff0c;按照执行任何 MATLAB 函数的相同方式来执行这些命令。使用 MATLAB 编辑器或任何其他文件编辑器可以创建…

使用HTTP隧道时如何应对目标网站的反爬虫监测?

在进行网络抓取时&#xff0c;我们常常会遇到目标网站对反爬虫的监测和封禁。为了规避这些风险&#xff0c;使用代理IP成为一种常见的方法。然而&#xff0c;如何应对目标网站的反爬虫监测&#xff0c;既能保证数据的稳定性&#xff0c;又能确保抓取过程的安全性呢&#xff1f;…

Gartner发布《2023年全球RPA魔力象限》:90%RPA厂商,将提供生成式AI自动化

8月3日&#xff0c;全球著名咨询调查机构Gartner发布了《2023年全球RPA魔力象限》&#xff0c;通过产品能力、技术创新、市场影响力等维度&#xff0c;对全球16家卓越RPA厂商进行了深度评估。 弘玑Cyclone&#xff08;Cyclone Robotics&#xff09;、来也&#xff08;Laiye&am…

Visual Studio Code中对打开的脚本格式统一

什么是Language Server Protocol (LSP)? Language Server Protocol&#xff08;语言服务器协议&#xff0c;简称LSP&#xff09;是微软在2016年提出的一套统一的通讯协议方案。LSP定义了一套编辑器或者IDE与语言服务器&#xff08;Language Server&#xff09;之间使用的协议&…

【笔记】移动光猫改桥接

1. 登录后台 移动光猫的超管和密码&#xff08;百度的&#xff09; 账号&#xff1a;CMCCAdmin 密码&#xff1a;aDm8H%MdA 浏览器访问 192.168.1.1 并登录 2. 选择连接 点击“网络”&#xff0c;在“连接名称”下拉框选择 INTENET_R_VID 字样的连接&#xff0c;并截图备…

构建Docker容器监控系统(Cadvisor +InfluxDB+Grafana)

目录 案例概述 Cadvisor InfluxDBGrafana 1.1、 Cadvisor 1.2、InfluxDB 1.3、Grafana 1.4、监控组件架构 1.5、开始部署 安装docker-ce 阿里云镜像加速器 创建自定义网络 创建influxdb容器 案例概述 Docker作为目前十分出色的容器管理技术&#xff0c;得到大量企业…

CTF流量题解http1.pcapng

使用Wireshark工具打开流量文件http1.pcapng&#xff0c;如下图所示。 在过滤检索栏输入http&#xff0c;wireshark自动进行过滤。
最新文章