几个与概率有关的问题

看过《概率面试题精讲》这个视频之后,来总结一下视频中讲过的几个比较重要的问题。

1. random shuffle 问题

问题描述:给定一个字符串,随机返回任意一种打乱顺序之后的字符串,保证每种情况出现的概率相等。下面是一份实现代码:

char *reshuffle(char *str)
{
for (int i = strlen(str) - 1; i > 0; --i) {
int j = rand() % (i + 1);
swap(str[i], str[j]);
}
return str;
}

图解 Git(转载 & 整理)

这篇博文是我对 图解 git 的整理,按照我自己的理解加入了一些注释,在这里首先要感谢原作者和翻译者为我们带来这么精彩的图文,下面是我的整理:

1. git 常用操作

图 1:git 常用操作 1
注意:图 1 所示的四条命令在工作目录、暂存区域(又叫索引)和历史仓库之间复制文件。

git add files # 把当前文件放入暂存区域
git commit # 给暂存区域生成快照并提交到历史仓库
git reset -- files # 撤销最后一次 git add files,可用 git reset 撤销所有暂存区域文件
git checkout -- files # 把文件从暂存区域复制到工作目录,用来丢弃本地修改

使用共享内存和信号量:生产者和消费者问题

共享内存和信号量都是 Linux 下 IPC(Inter-Process Communication)的重要手段,尤其是共享内存,是最快的 IPC 方式也是最常用的方式之一。共享内存的基本思想是:同一块物理内存被映射到多个进程各自的虚拟内存空间,一个进程对共享内存数据的更新对其他进程是立即可见的,所以需要使用信号量(或者其他同步原语)来同步多个进程对共享内存的访问。图 1 显示了共享内存在进程虚拟地址空间中的位置:

图 1:共享内存

《Effective STL》中值得注意的几个条款

看完《Effective STL》之后的确有很大的收获,发现 STL 里面的坑还真是不少,这里选了几条我认为比较重要的条款来说一说。

条款9:慎重选择删除元素的方法

STL中的 remove 和 erase 有时候的确会让人比较困惑,下面分三种情况详细讨论各类容器如何使用 remove 和 erase:

1. 要删除容器中有特定值的所有对象:

(1)若容器是 vector、string 或 deque,则使用 erase-remove 习惯用法:

Container<int> c;
c.erase(remove(c.begin(), c.end(), value), c.end());

注意:remove 将值为非 value 的元素依次前移,覆盖值为 value 的元素,返回指向第一个应该废弃的元素的迭代器,不改变容器的大小。

(2)若容器是list,则使用其成员函数 list::remove(当然也可以使用如上方法),即:

c.remove(value); // 无返回值,这是 list 最高效的删除方法

(3)若容器是一个标准关联容器,则使用它的 erase 成员函数,即:

c.erase(value); // 无返回值

Leetcode 146:LRU Cache

这是 Leetcode 146 题,要求实现简单的LRU(Least Recently Used)Cache,解决这道题目的主要思想是:

  1. 使用双向链表(如 STL 中的 list)作为 cache的数据结构,保证在头尾插入和删除的时间复杂度都是 O(1)。每次访问的 Entry 若在 cache 中命中,就将它移到链表头部,若没有命中则分两种情况:若 cache 未满,将新 Entry 插入链表头部;若 cache 满了,先删除链表尾部的 Entry(即最近最少使用的 Entry),再将新 Entry 插入链表头部。
  2. 使用哈希表(如 STL 中的 unordered_map)存储 Entry 的键和 Entry 在 cachae 中位置(如list的迭代器)的映射,可以用 O(1) 时间从 cache 中找到相应的 Entry。