[leetcode #201] Bitwise AND of Numbers Range

1425 ワード
アルゴリズム#アルゴリズム# leetcode algorithm 道しるべ テキストリンク

Problem


Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.
Example 1:
Input: left = 5, right = 7
Output: 4
Example 2:
Input: left = 0, right = 0
Output: 0
Example 3:
Input: left = 1, right = 2147483647
Output: 0
Constraints:
・ 0 <= left <= right <= 2³¹ - 1

Idea


コードは短いですが、なかなか答えが出ません.長いこと考えたあげく,最後は人の解答しか見なかった.🥲
左と右を与え,左と右を含む範囲総数AND演算時の値を求める.コアは範囲内の数を考慮せず,両端値だけで答えを求めることができる.
左と右がシフトし、数が何回シフトしたかを数えます.ライトシフト中に左と右が同じになった場合、シフトを停止し、同じ数字を左シフトして値を求めます.
上記の方法が可能なのは、right shiftに同じ数の2つのビットが含まれているからである.残りのビットは、範囲内の数の0を含む可能性があります.したがって、0のみです.したがって、2つの数が同じ場合はshiftキーを押して左に移動するだけでよい.

Solution

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while(left != right){
            left = left >> 1;
            right = right >> 1;
            shift++;
        }

        return right << shift;
    }
}

Reference


https://leetcode.com/problems/bitwise-and-of-numbers-range/
[アルゴリズム]LeatCode-Course計画II
React component ライフサイクル図