当前位置: 首页 > news >正文

xampp wordpress教程安卓手机优化软件排名

xampp wordpress教程,安卓手机优化软件排名,小游戏网站怎么做,dede 网站打开慢题目描述 queries二维数组是nums数组待判断的索引区间(左闭右闭)。需要判断每个索引区间中的nums相邻元素奇偶性是否不同,如果都不同则该索引区间的搜索结果为True,否则为False。 暴力推演:也是我最开始的思路 遍历q…

题目描述

在这里插入图片描述
queries二维数组是nums数组待判断的索引区间(左闭右闭)。需要判断每个索引区间中的nums相邻元素奇偶性是否不同,如果都不同则该索引区间的搜索结果为True,否则为False。

暴力推演:也是我最开始的思路

遍历queries的索引区间,在每一个区间内再遍历相应的nums元素判断奇偶性是否不同。
那么,如何判断相邻元素的奇偶性不同呢?我想到的是:“奇数+偶数=奇数”而“奇数+奇数=偶数”、“偶数+偶数=偶数”,即判断相邻元素之和是否为奇数。

该思路代码如下:

class Solution:def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:# 相邻数字奇偶性不同:和为奇数。# 暴力搜索:遍历数组的每一个查询索引区间,依次判断。# 时间复杂度:O(M*N),其中M为queries的长度,N为nums的长度。answer = []for index_range in queries:result = True  # 首先假设区间符合要求for i in range(index_range[0], index_range[1]): if (nums[i] + nums[i + 1]) % 2 == 0:  # 检查和是否为偶数result = False  # 找到一对不符合要求的相邻数字break  # 找到后立即停止循环answer.append(result)return answer

在这里插入图片描述
这个思路时间复杂度过高。该如何优化呢?
我们发现这个思路再遍历queries每个区间时都要在nums中进行从头到尾的遍历,这一部分是不是可以优化呢?
比如可以先遍历nums中所有的元素,判断相邻元素奇偶性差异并在相应的位置做好标记,如果该位置与前一个元素的奇偶性不同,则该位置的标记与前一个位置的标记保持一致,否则+1,这样的话每次只需要判断区间首位位置的标记是否相同即可(时间复杂度即可变为O(M+N),如果相同则说明该区间所有的相邻元素奇偶性都不同,输出True,否则输出False。
看了题解,原来这个标记的思路其实可以用前缀和(之前很少用到,练练)来实现,而且判断两个元素奇偶性差异可以直接用位运算(也很少用到,正好练练)。

前缀和

前缀和是什么呢?
前缀和是一种在数组或序列中计算元素累积和的方法。具体来说,对于一个数组或序列中的元素,前缀和是指从第一个元素到当前元素(包括当前元素)的所有元素的和。

位运算是什么?
位运算是一种直接对整数的二进制位进行操作的运算方式。在计算机科学中,位运算是一种非常基础且高效的运算方式,它在底层硬件和编程语言中广泛使用。位运算主要包括以下几种类型:
1、AND(与)运算:符号为 &。两个位相与,只有两个位都是1时结果才是1,否则是0。
2、OR(或)运算:符号为 |。两个位相或,只要有一个位是1结果就是1,否则是0。
3、XOR(异或)运算:符号为 ^。两个位相异或,相同则结果为0,不同则结果为1。
4、NOT(非)运算:符号为 ~。对一个位取反,1变成0,0变成1。
5、左移(Left Shift)运算:符号为 <<。将一个数的所有位向左移动指定的位数,左边超出的位被丢弃,右边空出的位补0。
6、右移(Right Shift)运算:符号为 >>。将一个数的所有位向右移动指定的位数,右边超出的位被丢弃,左边空出的位补原数的符号位(算术右移)或补0(逻辑右移)。

位运算如何判断两个元素奇偶性差异?
对照上面的位运算类型,用异或!!
nums[i-1] ^ nums[i] == 1即为相邻元素奇偶性不同。

该思路代码如下:

class Solution:def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:# 前缀和:在数组或序列中计算元素累积和的方法,具体来说是指从第一个元素到当前元素(包括当前元素)的所有元素的和。# 快速计算某个范围内的元素总和的场景,可以帮助简化问题,提高算法效率。# 时间复杂度:O(M+N)n = len(nums)sum_array = [0] * nfor i in range(1, n):sum_array[i] = sum_array[i-1]if ((nums[i-1] ^ nums[i]) & 1) == 0: # 位运算判断,如果奇偶性相同条件则为真sum_array[i] += 1m = len(queries)answer = [False] * mfor i in range(m):index_range = queries[i]if sum_array[index_range[0]] == sum_array[index_range[1]]:  #若区间两端的标记一致,则说明区间内的相邻元素均满足奇偶性不同的条件。answer[i] = Truereturn answer

我试了试把位运算判断的条件改成:

if nums[i-1] ^ nums[i] == 0:

测试用例报错:
在这里插入图片描述
我觉得这两句效果一样,但输出结果就是不一样,也不知道为啥。。。留待后续!!

后续

用位运算判断两数的奇偶性差异:看二进制最后一位是否相同。而 nums[i-1] ^ nums[i] 会比较每一位是否相同,所以要 (nums[i-1] ^ nums[i]) & 1 ,因为只关注异或运算的最低位结果。

参考题解: 【预处理】前缀和 & 动态规划(详细思路+推导)

http://www.dt0577.cn/news/20596.html

相关文章:

  • 做mg动画赚钱网站厦门seo怎么做
  • 网页设计旅游哈尔滨代码关键词优化难度查询
  • b2c网站建设的网站收录量
  • 广州4a广告公司名单网站运营优化培训
  • 国外网页设计网站seo技术分享免费咨询
  • 精品网站建镇江网络
  • 贵阳做网站方舟网络广州疫情今天最新消息
  • 萧山网站制作公司北京网站优化经理
  • 广州广告网站建设seo范畴
  • 网站怎么做安全可靠免费发广告网站
  • 乌鲁木齐做网站深圳全网推广公司
  • 贵阳网站建设优化最新国际新闻热点事件
  • 重庆网站建设培训班网站统计代码
  • 长宁武汉阳网站建设semester什么意思
  • dw网站结构图怎么做成都网站快速优化排名
  • asp企业网站自助建站系统免费版超漂亮版绍兴百度推广优化排名
  • 网站的功能测试怎么做的水果网络营销策划书
  • 淄博网站建设优化在线bt磁力搜索
  • 网站建设那个网站好百度指数是什么意思
  • 湖北住房城乡建设厅网站站长工具推荐网站
  • 湘潭市政府采购网seo百度首页排名业务
  • 网站设计 原型图百度一下你就知道了百度一下
  • 做网站的图片要求大小郑州今日重大新闻
  • 广州联享网站建设公司怎么样发软文是什么意思
  • 旅游网站建设需求说明书收录优美的图片
  • 建设网站要在需求海口seo快速排名优化
  • 推进门户网站建设 用好用活廊坊seo排名优化
  • 海沧网站制作网上营销方法
  • 学校语言文字网站建设百度指数在哪里看
  • 东莞快速网站制作哪家强百度搜索竞价