iT邦幫忙

2021 iThome 鐵人賽

DAY 26
0
自我挑戰組

FRIENDS系列 第 26

Day 26: LeetCode Hard+Medium

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    
            
        
        

Level:Medium


上一篇
Day 25: Mac M1 螢幕錄製 feat. GCP Lab demo
下一篇
Day 27: 暴力破解 WPA/WPA2 加密 wifi 密碼
系列文
FRIENDS30

尚未有邦友留言

立即登入留言