Brian Kernighan 算法：求解《191. 位1的个数》《338. 比特位计数》《266. 回文排列》和《面试题 01.04. 回文排列》

Brian Kernighan 算法：用数组、哈希表、哈希集合 3 种数据结构求解《191. 位1的个数》《338. 比特位计数》《266. 回文排列》和《面试题 01.04. 回文排列》

Brian Kernighan 算法

• 对于数 n，n & n - 1 可删除其二进制比特位最右侧的 1
• 常用于某数比特位统计 1 的个数

Golang 中的 Set

• 用 map 实现 set，用 _, ok := map[key] 检查元素是否可用
• 将 value 设为空结构体 struct{}，空结构体不占用内存空间

  type void struct{}
  var vaule void
  set := make(map[string]void) // Create Empty Set
  set['key'] = vaule // Add
  for key := range set { fmt.Println(key) } // Loop
  delete(set, 'key') // Delete
  size := len(set) // Size
  _, ok :=  set['key']  // Check

例题

191. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。 提示： 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

答案

Brian Kernighan 算法

var hammingWeight = function(n) {
  let r = 0
  while (n) {
    n &= n - 1
    r++
  }
  return r
};

func hammingWeight(num uint32) int {
  r := 0
  for num > 0 {
    num &= num - 1
    r++
  }
  return r
}

338. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

答案

Brian Kernighan 算法

var countBits = function(n) {
  const r = new Uint32Array(n + 1)
  for (let i = 0; i <= n; i++) {
    r[i] = countOne(i)
  }
  return r
};
const countOne = n => {
  let r = 0
  while (n) {
    n &= n - 1
    r++
  }
  return r
}

func countBits(n int) []int {
  r := make([]int, n + 1)
  for i := 0; i <= n; i++ {
    r[i] = countOne(i)
  }
  return r
}
func countOne(n int) (r int) {
  for n > 0 {
    n &= n - 1
    r++
  }
  return
}

动态规划

var countBits = function(n) {
  const r = new Uint32Array(n + 1)
  for (let i = 1; i <= n; i++) {
    r[i] = r[i & i - 1] + 1
  }
  return r
};

func countBits(n int) []int {
  r := make([]int, n + 1)
  for i := 1; i <= n; i++ {
    r[i] = r[i & (i - 1)] + 1 // 括号不可省略
  }
  return r
}

266. 回文排列

面试题 01.04. 回文排列

给定一个字符串，判断该字符串中是否可以通过重新排列组合，形成一个回文字符串。

答案

数组

var canPermutePalindrome = function(s) {
  const h = new Uint32Array(128), n = s.length
  let odd = 0
  for (let i = 0; i < n; i++) {
    ++h[s.charCodeAt(i)] % 2 === 0 ? odd-- : odd++
  }
  return odd <= 1
};

func canPermutePalindrome(s string) bool {
  h, odd := make([]int, 128), 0
  for _, v := range s {
    h[v]++
    if h[v] % 2 == 0 {
      odd--
    } else {
      odd++
    }
  }
  return odd <= 1
}

集合

var canPermutePalindrome = function(s) {
  const h = new Set, n = s.length
  for (let i = 0; i < n; i++) {
    h.has(s[i]) ? h.delete(s[i]) : h.add(s[i])
  }
  return h.size <= 1
};

func canPermutePalindrome(s string) bool {
  type void struct{}
  var value void
  set := make(map[byte]void) 
  n := len(s)
  for i := 0; i < n; i++ {
    _, ok := set[s[i]]
    if ok {
      delete(set, s[i])
    } else {
      set[s[i]] = value
    }
  }
  return len(set) <= 1
}

位图 / 位比特图

• s[i]的范围是[0, 128) 用 BigInt （任意大的整数）扩大位比特图范围
• 使用 Brian Kernighan 算法 统计比特图中 1 的个数

var canPermutePalindrome = function(s) {
  const bit = new Bit, n = s.length
  for (let i = 0; i < n; i++) bit.add(s.charCodeAt(i))
  return bit.countOne() <= 1
};

class Bit {
  constructor () {
    this.bit = 0n
  }
  add (i) {
    this.bit ^= (1n << BigInt(i))
  }
  countOne () {
    let i = 0
    while (this.bit) {
      this.bit &= this.bit - 1n
      i++
    }
    return i
  }
}