[HackerRank]Java位元集合(Java BitSet)

題目描述

Java的BitSet類別實作出位元數值的動態陣列，允許我們輕易地使用以位元為單位來最佳化記憶體空間。一個位元值為1的元素稱為一個設定位元(set bit)。

給定B₁和B₂兩個BitSet物件，和集合的位元數量N，每個位元一開始都設定為0，要進行M次的連續操作。在每一次的操作完成之後，分別印出兩個BitSet物件所包含的設定位元數量，使用空格字元隔開。

原題網址

輸入格式

第1行包含兩個使用空格隔開的整數N和M，N的範圍在1到1000之間(包含1和1000)，M的範圍在1到10000之間(包含1和10000)。接下來的M行每行代表每次的操作，格式如下：

「set」可為「1」或是「2」。「1」表示B₁；「2」表示B₂。「index」是一個整數，對應到「set」所代表的BitSet物件指定索引位置的位元。

AND、OR、XOR這些二元運算子會由左計算到右，並且將結果存回第一個運算元中，也就是「set₁」。舉例來說：

B₂是左邊的運算元，B₁，所以會把「B₂ AND B₁」的結果存回B₂。

輸出格式

在每一次的操作完成之後，分別印出兩個BitSet物件所包含的設定位元數量，使用空格字元隔開。

範例輸入

範例輸出

額外解釋

一開始N=5，M=4，所以B₁=[0, 0, 0, 0, 0]，B₂=[0, 0, 0, 0, 0]。

執行「AND 1 2」操作：

此時B₁=[0, 0, 0, 0, 0]，B₂=[0, 0, 0, 0, 0]。

執行「SET 1 4」操作，此時B₁=[0, 0, 0, 0, 1]，B₂=[0, 0, 0, 0, 0]。

執行「FLIP 2 2」操作，此時B₁=[0, 0, 0, 0, 1]，B₂=[0, 0, 1, 0, 0]。

執行「OR 2 1」操作：

此時B₁=[0, 0, 0, 0, 1]，B₂=[0, 0, 1, 0, 1]。

解題概念

直接使用Java的BitSet物件所提供的「and」、「or」、「xor」、「flip」、「set」方法來完成操作。

至於設定位元的數量可以藉由計算串流元素數量的方式來取得，這是因為BitSet物件儲存設定位元的方式其實是使用一個長整數陣列來存放設定位元的索引位置。舉例來說，「00101」這個BitSet物件，在記憶體中儲存的方式為[2, 4]；「11100」這個BitSet物件，在記憶體中儲存的方式為[0, 1, 2]。由此可知，設定位元索引位置的數量就是設定位元的數量。

參考答案

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        final int N = sc.nextInt();
        final int M = sc.nextInt();

        final BitSet[] B = {new BitSet(N), new BitSet(N)};
        final StringBuilder sb = new StringBuilder();

        for (int i = 0; i < M; ++i) {
            final String operator = sc.next();
            final int o1 = sc.nextInt();
            final int o2 = sc.nextInt();
            switch (operator) {
                case "AND":
                    B[o1 - 1].and(B[o2 - 1]);
                    break;
                case "OR":
                    B[o1 - 1].or(B[o2 - 1]);
                    break;
                case "XOR":
                    B[o1 - 1].xor(B[o2 - 1]);
                    break;
                case "FLIP":
                    B[o1 - 1].flip(o2);
                    break;
                case "SET":
                    B[o1 - 1].set(o2);
                    break;
            }
            sb.append(B[0].stream().count()).append(" ").append(B[1].stream().count()).append("\n");
        }
        System.out.println(sb.toString().trim());
    }
}