第8周
2021-11-20
9分钟阅读时长
第8周 第16课 | 位运算
1. 位运算基础及实战要点
参考链接
如何从十进制转换为二进制
2. 位运算实战题目解析
参考链接
N 皇后位运算代码示例
def totalNQueens(self, n):
if n < 1: return []
self.count = 0
self.DFS(n, 0, 0, 0, 0)
return self.count
def DFS(self, n, row, cols, pie, na):
# recursion terminator
if row >= n:
self.count += 1
return
bits = (~(cols | pie | na)) & ((1 << n) — 1) # 得到当前所有的空位
while bits:
p = bits & —bits # 取到最低位的1
bits = bits & (bits — 1) # 表示在p位置上放入皇后
self.DFS(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1)
# 不需要revert cols, pie, na 的状态
class Solution {
private int size;
private int count;
private void solve(int row, int ld, int rd) {
if (row == size) {
count++;
return;
}
int pos = size & (~(row | ld | rd));
while (pos != 0) {
int p = pos & (-pos);
pos -= p; // pos &= pos - 1;
solve(row | p, (ld | p) << 1, (rd | p) >> 1);
}
}
public int totalNQueens(int n) {
count = 0;
size = (1 << n) - 1;
solve(0, 0, 0);
return count;
}
}
def solveNQueens(self, n):
def DFS(queens, xy_dif, xy_sum):
p = len(queens)
if p==n:
result.append(queens)
return None
for q in range(n):
if q not in queens and p-q not in xy_dif and \
p+q not in xy_sum:
DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
result = []
DFS([],[],[])
return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]
实战题目 / 课后作业
191. 位1的个数
class Solution {
/**
* 位运算
* @param Integer $n
* @return Integer
*/
function hammingWeight($n) {
$cnt = 0;
while ($n > 0) {
$cnt++;
$n &= $n - 1;
}
return $cnt;
}
function hammingWeight($n) {
$cnt = 0;
while ($n > 0) {
$cnt += $n & 1;
$n = $n >> 1;
}
return $cnt;
}
function hammingWeight($n) {
$count = 0;
$mask = 1;
for($i=0; $i<32; $i++) {
if ($n & $mask) {
$count ++;
}
$mask = $mask << 1;
}
return $count;
}
}
231. 2的幂
class Solution {
/**
* @param Integer $n
* @return Boolean
*/
function isPowerOfTwo($n) {
return $n > 0 && ($n & ($n - 1)) == 0;
//return ($n > 0) && ($n & -$n) == $n;
}
}
190. 颠倒二进制位
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function reverseBits($n) {
$ret = 0;
$power = 31;
while ($ret > 0) {
$ret += ($n & 1) << $power;
$n = $n >> 1;
$power -= 1;
}
return $res;
}
}
51. N皇后
class Solution {
private $res = [];
private $count = 0;
/**
* @param Integer $n
* @return String[][]
*/
function solveNQueens($n) {
if ($n < 1) return 0;
$this->dfs($n, 0, 0, 0, 0, []);
return $this->res;
}
function dfs($n, $row, $cols, $pie, $na, $curr_state) {
if ($n <= $row) {
$res = [];
foreach ($curr_state as $col) {
for ($j = 0; $j < $n; $j++) {
if ($col & (1 << $j)) {
$col = $j;
break;
}
}
$res[] = str_pad('', $col, '.') . 'Q' . str_pad('', $n - $col - 1, '.');
}
$this->res[] = $res;
$this->count++;
return;
}
$bits = (~($cols | $pie | $na)) & ((1 << $n) - 1);
while ($bits) {
$p = $bits & -$bits;
$curr_state[] = $p; //这里存在bug， 请大佬指出哪里，应该怎么写
$this->dfs($n, $row + 1, $cols | $p, ($pie | $p) << 1, ($na | $p) >> 1, $curr_state);
array_pop($curr_state);
$bits = $bits & ($bits - 1);
}
}
}
52. N皇后 II
class Solution {
private $count = 0;
/**
* @param Integer $n
* @return Integer
*/
function totalNQueens($n) {
if ($n < 1) return 0;
$this->dfs($n, 0, 0, 0, 0);
return $this->count;
}
function dfs($n, $row, $col, $pie, $na) {
if ($n == $row) {
$this->count++;
return;
}
$bits = (~($col | $pie | $na)) & ((1 << $n)) - 1);//得到所有的空位
while ($bits) {
$p = $bits & -$bits; //获取最后一位1
$bits &= ($bits - 1);
$this->dfs($n, $row + 1, $col | $p, ($pie | $p) << 1, ($na | $p) >> 1);
}
}
}
338. 比特位计数
class Solution {
/**
* @param Integer $num
* @return Integer[]
*/
function countBits($num) {
$dp = array_fill(0, $num + 1; 0);
for ($i = 1; $i <= $num; $i++) {
$dp[$i] = $dp[$i & ($i - 1)] + 1;
}
return $dp;
}
}
// $dp[$i] = $dp[$i >> 1] + ($i&1);
第8周 第17课 | 布隆过滤器和LRU缓存
1. 布隆过滤器的实现及应用
参考链接
布隆过滤器的原理和实现
使用布隆过滤器解决缓存击穿、垃圾邮件识别、集合判重
布隆过滤器 Python 代码示例
布隆过滤器 Python 实现示例
高性能布隆过滤器 Python 实现示例
布隆过滤器 Java 实现示例 1
布隆过滤器 Java 实现示例 2
2. LRU Cache的实现、应用和题解
参考链接
Understanding the Meltdown exploit
替换算法总揽
LRU Cache Python 代码示例
class LRUCache(object):
def __init__(self, capacity):
self.dic = collections.OrderedDict()
self.remain = capacity
def get(self, key):
if key not in self.dic:
return -1
v = self.dic.pop(key)
self.dic[key] = v # key as the newest one
return v
def put(self, key, value):
if key in self.dic:
self.dic.pop(key)
else:
if self.remain > 0:
self.remain -= 1
else: # self.dic is full
self.dic.popitem(last=False)
self.dic[key] = value
实战题目 / 课后作业
146. LRU缓存机制
class LRUCache {
private $capacity;
private $map = [];
private $head = null;
private $tail = null;
/**
* @param Integer $capacity
*/
function __construct($capacity) {
$this->capacity = $capacity;
$this->head = new DictNode('head',0);
$this->tail = new DictNode('end',0);
$this->head->next = $this->tail;
$this->tail->pre = $this->head;
}
/**
* @param Integer $key
* @return Integer
*/
function get($key) {
$result = -1;
if (array_key_exists($key,$this->map)){
$node = $this->map[$key];
$result = $node->value;
$this->move_node_to_head($node);
}
return $result;
}
/**
* @param Integer $key
* @param Integer $value
* @return NULL
*/
function put($key, $value) {
if (array_key_exists($key,$this->map)){
$node = $this->map[$key];
$node->value = $value;
$this->move_node_to_head($node);
} else {
$node = new DictNode($key,$value);
$this->map[$key] = $node;
$firstNode = $this->head->next;
$firstNode->pre = $node;
$this->head->next = $node;
$node->next = $firstNode;
$node->pre = $this->head;
}
if (count($this->map) > $this->capacity){
$lastNode = $this->tail->pre;
$lastSecondNode = $this->tail->pre->pre;
$this->tail->pre = $lastSecondNode;
$lastSecondNode->next = $this->tail;
unset($this->map[$lastNode->key]);
}
}
function move_node_to_head($node){
$preNode = $node->pre;
$nextNode = $node->next;
$preNode->next = $nextNode;
$nextNode->pre = $preNode;
$firstNode = $this->head->next;
$firstNode->pre = $node;
$this->head->next = $node;
$node->next = $firstNode;
$node->pre = $this->head;
}
}
class DictNode {
public $value;
public $key;
public $pre = null;
public $next = null;
public function __construct($key,$value)
{
$this->key = $key;
$this->value = $value;
}
}
第8周 第18课 | 排序算法
1. 初级排序和高级排序的实现和特性
参考链接
十大经典排序算法
快速排序代码示例
归并排序代码示例
堆排序代码示例
课后作业
用自己熟悉的编程语言，手写各种初级排序代码
2. 特殊排序及实战题目详解
参考链接
十大经典排序算法
9 种经典排序算法可视化动画
6 分钟看完 15 种排序算法动画展示
实战题目 / 课后作业
1122. 数组的相对排序
class Solution {
/**
* 方法一:计数排序
* @param Integer[] $arr1
* @param Integer[] $arr2
* @return Integer[]
*/
function relativeSortArray1($arr1, $arr2) {
$arr = array_fill(0, 1001, 0);
foreach ($arr1 as $num) {
$arr[$num]++;
}
$res = [];
foreach ($arr2 as $num) {
while ($arr[$num]) {
$res[] = $num;
$arr[$num]--;
}
}
for ($i = 0; $i <= 1001; $i++) {
while ($arr[$i]) {
$res[] = $i;
$arr[$i]--;
}
}
return $res;
}
//方法二
function relativeSortArray($arr1, $arr2) {
$arr = array_count_values($arr1);
$res = [];
foreach ($arr2 as $num) {
while ($arr[$num]) {
$res[] = $num;
$arr[$num]--;
}
unset($arr[$num]);
}
ksort($arr);
foreach ($arr as $num => $count) {
while ($count) {
$res[] = $num;
$count--;
}
}
return $res;
}
}
242. 有效的字母异位词
class Solution {
/**
* 方法一：哈希表
* @param String $s
* @param String $t
* @return Boolean
*/
function isAnagram1($s, $t) {
$len = strlen($s);
if ($len != strlen($t)) return false;
$map = [];
for ($i = 0; $i < $len; $i++) {
if (!isset($map[$s[$i]])) $map[$s[$i]] = 0;
if (!isset($map[$t[$i]])) $map[$t[$i]] = 0;
$map[$s[$i]]++;
$map[$t[$i]]--;
}
foreach ($map as $c) {
if ($c) return false;
}
return true;
}
//方法二：统计字母出现的次数比较
function isAnagram2($s, $t) {
return count_chars($s, 1) == count_chars($t, 1);
}
/**
* 方法三：排序比较
* @param String $s
* @param String $t
* @return Boolean
*/
function isAnagram($s, $t) {
$s = str_split($s);
$t = str_split($t);
sort($s);
sort($t);
return $s == $t;
}
}
1244. Design A Leaderboard 解题思路分析
https://hwchang0417.wordpress.com/2019/11/04/leetcode-1244-design-a-leaderboard/
class Leaderboard {
public:
map<int, int> m;
Leaderboard() {}
void addScore(int playerId, int score) {
m[playerId] += score;
}
int top(int K) {
int sum = 0;
priority_queue<int, std::vector<int>, std::greater<int>> pq;
for(pair<int, int> p : m){
sum += p.second;
pq.push(p.second);
if(pq.size() > K){
sum -= pq.top();
pq.pop();
}
}
return sum;
}
void reset(int playerId) {
m.erase(m.find(playerId));
}
};
56. 合并区间
class Solution {
/**
* @param Integer[][] $intervals
* @return Integer[][]
*/
function merge($intervals) {
//排序
array_multisort(array_column($intervals, 0), $intervals);
$res = [];
$i = -1;
foreach ($intervals as $interval) {
if ($i == -1 || $res[$i][1] < $interval[0]) {
$res[++$i] = $interval;
} else {
$res[$i][1] = max($res[$i][1], $interval[1]);
}
}
return $res;
}
}
493. 翻转对
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function reversePairs($nums) {
return $this->mergesort($nums, 0, count($nums) - 1);
return $this->mergesort_and_count($nums, 0, count($nums) - 1);
}
/**
* 参考链接
* https://leetcode.com/problems/reverse-pairs/discuss/97306
* @param [type] $nums
* @param [type] $start
* @param [type] $end
* @return int
*/
function mergesort(&$nums, $start, $end) {
if ($start >= $end) return 0;
$mid = $start + (($end - $start) >> 1);
$count = $this->mergesort($nums, $start, $mid) + $this->mergesort($nums, $mid + 1, $end);
$cache = [];
$i = $t = $start;
$c = 0;
for ($j = $mid + 1; $j <= $end; $j++, $c++) {
while ($i <= $mid && $nums[$i] <= 2 * $nums[$j]) $i++;
while ($t <= $mid && $nums[$t] < $nums[$j]) $cache[$c++] = $nums[$t++];
$cache[$c] = $nums[$j];
$count += $mid - $i + 1;
}
while ($t <= $mid) $cache[$c++] = $nums[$t++];
for ($i = 0; $i < $c; $i++) {
$nums[$start + $i] = $cache[$i];
}
return $count;
}
function mergesort_and_count(&$nums, $start, $end) {
if ($start >= $end) return 0;
$mid = $start + (($end - $start) >> 1);
$count = $this->mergesort_and_count($nums, $start, $mid) + $this->mergesort_and_count($nums, $mid + 1, $end);
$j = $mid + 1;
for ($i = $start; $i <= $mid; $i++) {
while ($j <= $end && $nums[$i] > $nums[$j] * 2) $j++;
$count += $j - ($mid + 1);
}
$this->merge($nums, $start, $mid, $end);
return $count;
}
function merge(&$nums, $start, $mid, $end) {
$n1 = $mid - $start + 1;
$n2 = $end - $mid;
$l = $r = [];
for ($i = 0; $i < $n1; $i++) $l[$i] = $nums[$start + $i];
for ($i = 0; $i < $n2; $i++) $r[$i] = $nums[$mid + 1 + $i];
for ($i = 0, $j = 0, $k = $start; $k <= $end; $k++) {
if ($j >= $n2 || ($i < $n1 && $l[$i] < $r[$j])) {
$nums[$k] = $l[$i++];
} else {
$nums[$k] = $r[$j++];
}
}
}
}
本周作业
简单
191. 位1的个数
231. 2的幂
190. 颠倒二进制位
用自己熟悉的编程语言，手写各种初级排序代码，提交到第 8 周学习总结中。
1122. 数组的相对排序
242. 有效的字母异位词
中等
242. 有效的字母异位词
https://leetcode-cn.com/problems/design-a-leaderboard/