第8周 位运算、布隆过滤器和LRU缓存、排序算法
2021-12-20
7分钟阅读时长
题目数量：12
第16课 | 位运算
1. 位运算基础及实战要点
参考链接
2. 位运算实战题目解析
参考链接
实战题目 / 课后作业
// 最优写法
func hammingWeight(num uint32) (cnt int) {
for num > 0 {
cnt++
num &= num - 1
}
return cnt
}
// O(n) n = 32
func hammingWeight(num uint32) (cnt int) {
for num > 0 {
cnt += int(num & 1)
num >>= 1
}
return cnt
}
func isPowerOfTwo(n int) bool {
return n > 0 && n & (n - 1) == 0
}
// 没有上面运行快
func isPowerOfTwo(n int) bool {
return n > 0 && n & -n == n
}
//方案二： 判断是否为最大 22 的幂的约数
func isPowerOfTwo(n int) bool {
const big = 1 << 30
return n > 0 && big%n == 0
}
// 写法一：
func reverseBits(n uint32) (ans uint32) {
pos := 31
for n > 0 {
if n & 1 == 1 {
ans |= 1 << pos
}
pos -= 1
n >>= 1
}
return ans
}
// 写法二：
func reverseBits1(n uint32) (ans uint32) {
for i := 0; i < 32; i++ {
ans |= (n & 1) << (31 - i)
n >>= 1
}
return ans
}
func solveNQueens(n int) (res [][]string) {
size := 1 << n - 1
var solve func(row, cols, pie, na int, queens []int)
solve = func(row, cols, pie, na int, queens []int) {
if row == n {
ans := make([]string, n)
for i := 0; i < n; i++ {
c := ""
for j := 0; j < n; j++ {
if queens[i] & (1 << j) > 0 {
c += "Q"
} else {
c += "."
}
}
ans[i] = c
}
res = append(res, ans)
return
}
bits := size & (^(cols | pie | na))
for bits > 0 {
p := bits & -bits
queens = append(queens, p)
solve(row + 1, cols | p, (pie | p) << 1, (na | p) >> 1, queens)
queens = queens[:len(queens) - 1]
bits &= bits - 1
}
}
solve(0, 0, 0, 0, []int{})
return res
}
func totalNQueens(n int) (cnt int) {
size := 1 << n - 1
var slove func(int, int, int, int)
slove = func(row, cols, pie, na int) {
if row == n {
cnt++
return
}
bits := size & (^(cols | pie | na))
for bits > 0 {
p := bits & (-bits)
bits &= bits - 1
slove(row + 1, cols | p, (pie | p) << 1, (na | p) >> 1)
}
}
slove(0 , 0, 0, 0)
return cnt
}
- 338. 比特位计数 重点练习记忆理解
// 方法一：Brian Kernighan 算法 等于暴力 计算每个数
// 方法二：动态规划——最高有效位
// 方法三：动态规划——最低有效位
func countBits(n int) []int {
bits := make([]int, n + 1)
for i := 1; i <= n; i++ {
bits[i] = bits[i >> 1] + (i & 1)
}
return bits
}
// 方法四：动态规划——最低设置位
func countBits(n int) []int {
bits := make([]int, n + 1)
for i := 1; i <= n; i++ {
bits[i] = bits[i & (i - 1)] + 1
}
return bits
}
第17课 | 布隆过滤器和LRU缓存
1. 布隆过滤器的实现及应用
参考链接
- 布隆过滤器的原理和实现
- 使用布隆过滤器解决缓存击穿、垃圾邮件识别、集合判重
- 布隆过滤器 Python 代码示例
- 布隆过滤器 Python 实现示例
- 高性能布隆过滤器 Python 实现示例
- 布隆过滤器 Java 实现示例 1
- 布隆过滤器 Java 实现示例 2
2. LRU Cache的实现、应用和题解
参考链接
实战题目 / 课后作业
- 146. LRU缓存机制 重点练习
func init() { debug.SetGCPercent(-1) } // 提升速度为 288ms， 没有开启之前为：516ms
type cacheNode struct {
key int
val int
pre *cacheNode
next *cacheNode
}
type LRUCache struct {
capacity int
mp map[int]*cacheNode
head *cacheNode
tail *cacheNode
}
func Constructor(capacity int) LRUCache {
lru := LRUCache{
capacity: capacity,
mp: make(map[int]*cacheNode, capacity),
head: &cacheNode{},
tail: &cacheNode{},
}
lru.head.next = lru.tail
lru.tail.pre = lru.head
return lru
}
func (this *LRUCache) Get(key int) int {
if node, ok := this.mp[key]; ok {
this.moveToTail(node, node.val)
return node.val
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
if node, ok := this.mp[key]; ok {
this.moveToTail(node, value)
} else {
if len(this.mp) == this.capacity {
delNode := this.head.next
this.deleteNode(delNode)
delete(this.mp, delNode.key)
}
node = &cacheNode{key:key, val:value}
this.addToTail(node)
this.mp[key] = node
}
}
func (this *LRUCache) moveToTail(node *cacheNode, value int) {
this.deleteNode(node)
node.val = value
this.addToTail(node)
}
func (this *LRUCache) deleteNode(node *cacheNode) {
node.next.pre = node.pre
node.pre.next = node.next
}
func (this *LRUCache) addToTail(node *cacheNode) {
this.tail.pre.next = node
node.next = this.tail
node.pre = this.tail.pre
this.tail.pre = node
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/
第8周 第18课 | 排序算法
1. 初级排序和高级排序的实现和特性
参考链接
课后作业
用自己熟悉的编程语言，手写各种初级排序代码，提交到第 8 周学习总结中。
2. 特殊排序及实战题目详解
参考链接
实战题目 / 课后作业
// 自定义排序 sort.Slice()
// 计数排序
func relativeSortArray(arr1 []int, arr2 []int) []int {
ans := make([]int, 0, len(arr1))
cnt := make([]int, 1001)
for _, n := range arr1 {
cnt[n]++
}
for _, n := range arr2 {
for cnt[n] > 0 {
ans = append(ans, n)
cnt[n]--
}
}
for i := 0; i < 1001; i++ {
for cnt[i] > 0 {
ans = append(ans, i)
cnt[i]--
}
}
return ans
}
// 方法一：对s, t进行排序比较
func isAnagram(s, t string) bool {
s1, s2 := []byte(s), []byte(t)
sort.Slice(s1, func(i, j int) bool { return s1[i] < s1[j] })
sort.Slice(s2, func(i, j int) bool { return s2[i] < s2[j] })
return string(s1) == string(s2)
}
// 方法二：hash计数
func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
mp := make([]int, 26)
for i, c := range s {
mp[c - 'a']++
mp[t[i] - 'a']--
}
for _, v := range mp {
if v != 0 {
return false
}
}
return true
}
https://hwchang0417.wordpress.com/2019/11/04/leetcode-1244-design-a-leaderboard/
func merge(intervals [][]int) (res [][]int) {
if len(intervals) < 2 {
return intervals
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
res = append(res, intervals[0])
for i, j := 1, 0; i < len(intervals); i++ {
if res[j][1] < intervals[i][0] {
j++
res = append(res, intervals[i])
} else {
res[j][1] = max(res[j][1], intervals[i][1])
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
- 493. 翻转对 重点练习
// 方法一：归并排序
func reversePairs(nums []int) int {
return mergeSort(nums, 0, len(nums) - 1)
}
func mergeSort(nums []int, left int, right int) int {
if left >= right {
return 0
}
mid := left + (right - left) >> 1
cnt := mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right)
// 计算翻转对，并归并
cache := make([]int, right - left + 1)
c, i, l := 0, left, left
for j := mid + 1; j <= right; j, c = j + 1, c + 1 {
for i <= mid && nums[i] <= nums[j] * 2 {
i++
}
for ; l <= mid && nums[l] < nums[j]; l, c = l + 1, c + 1 {
cache[c] = nums[l]
}
cache[c] = nums[j]
cnt += mid - i + 1 // l -> mid 是 ok 的
}
for ; l <= mid; l, c = l + 1, c + 1 {
cache[c] = nums[l]
}
// 合并
for i, n := 0, right - left + 1; i < n; i++ {
nums[left + i] = cache[i]
}
return cnt
}
// 方法二：树状数组
本周作业及下周预习
本周作业
简单
用自己熟悉的编程语言，手写各种初级排序代码，提交到第 8 周学习总结中。