Day 26: LeetCode Hard+Medium

LeetCode 212. Word Search II

Source

https://leetcode.com/problems/word-search-ii/

作法:

先clone Word Search的写法，再稍作更动，并加速一下。

Level:`Hard`

技术支援

@JohnTing

加速法: 加上filter
如果word当中的character不在board里，就不用找那个word了!

LeetCode 201. Bitwise AND of Numbers Range

Source

https://leetcode.com/problems/bitwise-and-of-numbers-range/

Discuss[1]

Observe

Ex: [5,8]

    101 <- len = 3
    110
&   111
   1000 <- len = 4
-------
   0000

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        
        if len(bin(left)) != len(bin(right)):
            return 0
        for i in range(left+1,right+1):
            left = left & i
        return left

YT[2]

Bitwise AND of Numbers Range

跟我一样的疑惑!

Observe

Ex: [5,7]

idx 210
-------
    101
    110
&   111
-------
    100
    -

作法

找出Out非1的位置，以[5,7]为例，则为index是2的情况，
index 2左边(包含2)保留，index 2右边舍弃。

以右移方式(/2)来找Out非1的位置，
右移直到m,n相同就停止，右移同时使用counter记录移了几次
PS: 右移 (>>1)
再由m左移counter(m/n<<counter)即所得。
PS: m/n == m或n

程序码

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        '''
        >> -> /2
        << -> *2
           421
        ------         
        5: 101
        6: 110
        7: 111
        -------
           100
           OXX  O: the same X: diffirent
        可移掉右边清为空留下左边
        移掉右边 -> 最後成00
        留下左边 -> 不动
        
        op1: >> also means drop right bit
        do (>> 1) + counter until m == n
        
        op2: << counter
        '''
        
        cnt = 0
        while left!=right:
            left >>= 1
            right >>= 1
            cnt+=1
        return right << cnt