Một tập hợp số nguyên không âm được xây dựng bằng mảng bit với các phương thức sau:
- `func (s *NumSet) Contains(val int) bool`: Kiểm tra sự tồn tại của phần tử.
- `func (s *NumSet) Insert(val int)`: Thêm phần tử vào tập hợp.
- `func (s *NumSet) Size() int`: Trả về kích thước của tập hợp.
- `func (s *NumSet) Delete(val int)`: Xóa phần tử khỏi tập hợp.
- `func (s *NumSet) Reset()`: Xóa tất cả các phần tử trong tập hợp.
- `func (s *NumSet) Clone() *NumSet`: Tạo bản sao của tập hợp.
- `func (s *NumSet) Union(other *NumSet)`: Thực hiện phép hợp.
- `func (s *NumSet) Intersection(other *NumSet)`: Thực hiện phép giao.
- `func (s *NumSet) Difference(other *NumSet)`: Thực hiện phép hiệu.
- `func (s *NumSet) SymmetricDifference(other *NumSet)`: Thực hiện phép hiệu đối xứng.
Mã nguồn `numset.go`:
package numset
import (
"bytes"
"fmt"
"log"
)
var popCount [256]byte
func init() {
for i := range popCount {
popCount[i] = popCount[i>>1] + byte(i&1)
}
}
type NumSet struct {
bits []uint64
}
func (s *NumSet) Contains(val int) bool {
index := val / 64
bit := val % 64
return index < len(s.bits) && s.bits[index]&(1<= len(s.bits) {
s.bits = append(s.bits, 0)
}
s.bits[index] |= 1 << bit
}
func (s *NumSet) Union(other *NumSet) {
for i, otherBit := range other.bits {
if i < len(s.bits) {
s.bits[i] |= otherBit
} else {
s.bits = append(s.bits, otherBit)
}
}
}
func (s *NumSet) Intersection(other *NumSet) {
minLen := len(s.bits)
if len(other.bits) < minLen {
minLen = len(other.bits)
}
for i := 0; i < minLen; i++ {
s.bits[i] &= other.bits[i]
}
for i := minLen; i < len(s.bits); i++ {
s.bits[i] = 0
}
}
func (s *NumSet) Difference(other *NumSet) {
for i, otherBit := range other.bits {
if i < len(s.bits) {
s.bits[i] &^= otherBit
}
}
}
func (s *NumSet) SymmetricDifference(other *NumSet) {
temp := other.Clone()
temp.Difference(s)
s.Difference(other)
s.Union(temp)
}
func countOnes(x uint64) int {
return int(popCount[byte(x>>(0*8))] +
popCount[byte(x>>(1*8))] +
popCount[byte(x>>(2*8))] +
popCount[byte(x>>(3*8))] +
popCount[byte(x>>(4*8))] +
popCount[byte(x>>(5*8))] +
popCount[byte(x>>(6*8))] +
popCount[byte(x>>(7*8))])
}
func (s *NumSet) Size() int {
count := 0
for _, bit := range s.bits {
if bit == 0 {
continue
}
count += countOnes(bit)
}
return count
}
func (s *NumSet) Delete(val int) {
index, bit := val/64, uint(val%64)
if index >= len(s.bits) {
log.Printf("Phần tử không tồn tại: %d\n", val)
return
}
s.bits[index] &^= 1 << bit
}
func (s *NumSet) Reset() {
s.bits = []uint64{}
}
func (s *NumSet) Clone() *NumSet {
clone := &NumSet{}
clone.bits = make([]uint64, len(s.bits))
copy(clone.bits, s.bits)
return clone
}
func (s *NumSet) String() string {
var buffer bytes.Buffer
buffer.WriteByte('{')
for i, bit := range s.bits {
if bit == 0 {
continue
}
for j := 0; j < 64; j++ {
if bit&(1< 1 {
buffer.WriteByte(' ')
}
fmt.Fprintf(&buffer, "%d", 64*i+j)
}
}
}
buffer.WriteByte('}')
return buffer.String()
}
package numset
import (
"fmt"
"testing"
)
func TestNumSet(t *testing.T) {
var set1, set2 NumSet
set1.Insert(1)
set1.Insert(144)
set1.Insert(9)
fmt.Println(set1.String()) // "{1 9 144}"
set2.Insert(9)
set2.Insert(42)
fmt.Println(set2.String()) // "{9 42}"
set1.Union(&set2)
fmt.Println(set1.String()) // "{1 9 42 144}"
fmt.Println(set1.Contains(9), set1.Contains(123)) // "true false"
}
var testSet NumSet
func TestNumSet2(t *testing.T) {
testSet.Insert(1)
testSet.Insert(144)
testSet.Insert(9)
fmt.Println(testSet.Size())
fmt.Println(testSet.String())
testSet.Delete(10)
fmt.Println(testSet.String())
copySet := testSet.Clone()
fmt.Println("testSet.Clone()", copySet.String())
fmt.Println("testSet", testSet.String())
testSet.Reset()
fmt.Println("testSet.Reset()", testSet.String())
}