LeetCode 523 — DP与鸽巢原理

鸽巢原理

鸽巢原理的一种简单的表述法为： 若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少2只鸽子。 另一种为： 若有n个笼子和kn+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少k+1只鸽子。 一种推广表达是这样的： 如果要把n个物件分配到m个容器中，必有至少一个容器容纳至少\( \lceil\frac{n}{m}\rceil \)个物件。

鸽巢原理经常在计算机领域得到真正的应用。比如：哈希表的重复问题（冲突）是不可避免的，因为Keys的数目总是比Indices的数目多，不管是多么高明的算法都不可能解决这个问题。这个原理，还证明任何无损压缩算法，在把一个文件变小的同时，一定有其他文件增大来辅助，否则某些信息必然会丢失。

———维基百科

鸽巢原理的思想很简单，对应于每个具体问题就是每次选择都有n种情形供选择，若要选择kn+1次的话，那么必定存在一种选择是被选择了k+1次的。

OS X + Shadowsocks环境下的Privoxy的终端和py脚本内代理

环境：OS X + Shadowsocks
问题：虽然装有Shadowsocks，但是Twitter的pythonAPI仍无法使用

在使用Twitter的pythonAPI时，发现在Shadowsocks开启的情况下，python的爬虫无法访问使用Twitter，此处整合了几个零散方法，分别在终端内全局代理和脚本内单独代理：

Kaggle - MNIST手写体识别

0 加载所需用的库

import tensorflow as tf
import numpy as np
import pandas as pd

hihocoder 1037 — 数字三角形

1 简介

问题描述

一个被称为“数字三角形”的n(n不超过200)层迷宫，这个迷宫的第i层有i个房间，分别编号为1..i。除去最后一层的房间，每一个房间都会有一些通往下一层的房间的楼梯，用符号来表示的话，就是从第i层的编号为j的房间出发会有两条路，一条通向第i+1层的编号为j的房间，另一条会通向第i+1层的编号为j+1的房间，而最后一层的所有房间都只有一条离开迷宫的道路。这样的道路都是单向的，也就是说当沿着这些道路前往下一层的房间或者离开迷宫之后，小Ho没有办法再次回到这个房间。迷宫里同时只会有一个参与者，而在每个参与者进入这个迷宫的时候，每个房间里都会生成一定数量的奖券，这些奖券可以在通过迷宫之后兑换各种奖品。小Ho的起点在第1层的编号为1的房间，现在小Ho悄悄向其他参与者弄清楚了每个房间里的奖券数量，希望小Hi帮他计算出他最多能获得多少奖券。

编程之美 - 负数的二进制转换

1 简介

int型整数有4个字节，每个字节8个bit，所以一共32位。

1. 负十进制整数计算二进制：去掉符号，转为二进制，取反，加1
2. 负二进制整数计算十进制：取反，加1，转为十进制

观察上表可知，可将负整数去掉符号后，减去1，再计算二进制后取反。