leetcode 201 数字范围按位与

数字化生活方式正在全球范围内普及 #生活知识# #生活感悟# #科技生活变迁# #数字化生活方式#

记一次失败的解题经历，想跑捷径，最后发现还是最初的起点比较快

题目如下

201. 数字范围按位与

难度中等112收藏分享切换为英文关注反馈

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例 1: 

输入: [5,7]

输出: 4

示例 2:

输入: [0,1]

输出: 0

解题优化程度远不如官方，想学习优化算法可以看官方题解

此处记录思路过程，以及总结经验

解题代码如下

class Solution:

def change(self,m:int) -> int:

temp = bin(m)[2:]

temp= [i for i in str(temp)]

change = False

for i in range(len(temp)-1,-1,-1):

if temp[i] == '1':

temp[i] = '0'

change = True

elif change:

temp[i] = '1'

break

temp = ''.join(temp)

if int(temp) == 0:

temp = '1' + temp

return int(temp, 2)

def rangeBitwiseAnd(self, m: int, n: int) -> int:

if m == 0:

return 0

temp = m

result = m

while temp <= n:

result = result & temp

if result == 0:

return 0

temp = self.change(temp)

return result

        思路过程如下

        # 思路1（失败），首先把所有数字按照题目要求，暴力法进行按位与，看起来似乎是个可行操作，但是经过测试在使用range()时，内存超标

【第一个想法明显是会超标的，只是初始化试试，并且写一个demo，用于以后测试其他算法结果是否一致】
        # 思路2（失败），百度按位与的逻辑后，可以轻松得出一个规律，就是0与任何数按位与结果都为0，所以最最初始的思路就是，按位与所有数，如果有一次结果为0，则直接返回0，这个算法结果是超时

【第二个想法只是测试一下单纯快速短路算法能否解决，结果也不行】
        # 思路3(失败)，上述思路失败后，可以得知，如果正常方法是只会超时的，因此如果想解决，发现其中规律，此时整理一下手中，在不便利所有字符 情况下，能获取到的条件
        能获取到的是，起始字符m，结束字符n,以及中间会遍历的位数m-n+1,思路步骤第三步，思路2的函数并没有错误，只是会超时，那么用思路2的函数进行输出结果来查看是否有规律
        从结果可以得出是有规律的，在中间相同数字的按位与结果往往有较多重复,随后我随机以一个数字174为起点，遍历输出结果，得到(174,174到175)结果为174,(174,176到191)结果为160，(174,192到255)结果为128，(174,256以及后面)结果都为0
        然后可以看出，174到175为2个数,176到191为16个数，192到255为64个数，然后计算174的二进制结果为"10101110",160二进制为10100000（正好消除的位数到2^4=16）,128二进制为10000000（消除到2^6=64）
        从而联想，是否可以这么计算，m和n按位与，首先，计算m的二进制，以上述的174为例，首先计算174的二进制为10101110，随后174与174+1进行按位与，随后结果持续2^(174-174=0)位，随后把上次的结果174按位与174+1+2^(174-174，结果取最高二进制为0)得到结果160
        随后结果持续2^(174-160=14，结果取最高二进制为4),随后把上次的结果160按位与174+1+2^(174-174，结果取最高二进制为0)+2^4得到结果128....（超时，中间部分逻辑错误，跳跃幅度不够）

【第三个想法，认真查看了结果，通过重复数字次数较多得知必然有规律，但是逆推规律依旧比较难，中间漏了许多要素，也难以优化】
        # 思路4，从上述结果，得知从结果推算规律虽然有可能，但是依旧十分困难，所以就不通过结果推算规律了，直接从按位与的逻辑推算规律，首先按位与只有同时为1的情况结果会为0，
        # 那么依旧从上面的174进行假设，二进制为10101110,希望改变多出个0的话，下一个结果促使改变的结果应该为10110000即176【即把倒数第一个1变成0，但是因为数字只会上升不会下降，因此向前进1位】
        # 这个结果恰好与思路3里遍历出的结果相同，176后一个促使变化的数为后面步骤相同11000000即192，从而得知结果正确

【第四个想法成功解决了问题，但是这个直接从按位与逻辑推算规律的东西，我在第二个想法的时候有思考过，但是感觉可能逆推比较容易就放弃了，最后发现这个规律推算并不难，反而第三个想法里逆推规律用来一个小时推算了一个错误规律，第四个想法反而只花了20分钟不到，虽然里面也有第三个想法推算时，已经总结到一些关键的缘故，但依然是个错误】

总结

在未知算法原理时，推算规律时，可以尝试用暴力法做个demo，遍历一批答案，查看结果是否有序，获取有什么规律【如重复数字，奇数偶数。2的n次方加一，等差数列】。但是在已知算法原理的情况下，建议从原理推算算法各个步骤需要进行的变化。

网址：leetcode 201 数字范围按位与 https://www.yuejiaxmz.com/news/view/355919

相关内容

9.回文数
201不锈钢餐具安全吗 201不锈钢会生锈吗 201不锈钢优缺点
数字体温计使用方法 数字体温价格
提升全民数字素养与技能，共享美好数字生活
201不锈钢餐具安全吗
全方位构建数字安全
提升全民数字素养与技能
数字化转型：数字化的组织方案
数字生活在此徐徐展开……浦东启动全民数字素养与技能提升月
《地铁噪声与振动控制规范》（DB11

随便看看