编程之美记录

将帅

将和帅各有9个位置，用一个int变量表示，int变量有8位，前4位表示将，后4位表示帅，2⁴=16>9，足够表示。

快速找出不重复

1. Hash，为2时删除key
2. 全部异或，适用于单个不同；两个不同时，例如A和B，则说明异或值在某一位上为1，说明A和B在该位上有且仅有一个为1，按照该位是否为1，进行分类，之后再进行异或判断
3. 预先计算好所有IP的和，再减去现有的所有IP和，所得即是单个。两个的情况下，构造第二个方程，例如乘或者平方和

电梯问题

找出规律，优化成 O(n)

面试问题

转化为着色问题

N条线划分出多少块区域

1 + N + | 交点数 |

连连看

1. 图像一样
2. 计算最短路径转弯数是否小于3（用bfs）

计算二进制的1的个数

int Count(BYTE v)
{
	int num = 0;
	while(v)
	{
		v &= (v-1);
		num++;
	}
	return num;
}

计算阶乘后面多少个0

转化为5的个数

int func(int N)
{
	int ret = 0;
	while(N)
	{
		ret += N/5;
		N /= 5;
	}
}

阶乘二进制中最低位1的位置

1. 转化成求质因数2的个数再加1

   int LowestOne(int N)
   {
   	int Ret = 0;
   	while(N)
   	{
   		N >>= 1;
   		Ret += N;
   	}
   }

2. N质因数2的个数能转化成N减去N的二进制表示中1的数目

找出次数超过一半的数

1. 有序：第n/2的那个
2. 无序：每次删去两个不同的ID，剩下的那个

找出前k大的数

最小堆，O(N*log₂K)

精确表达浮点数

1. 有限小数

   x = 0.a1a2......an
   x = a1a2......an/(10^n)

2. 无限循环小数

   x = 0.a1a2......an(b1b2......bn)
   10^n * x = a1a2......an.(b1b2......bn)
   10^n * x = a1a2......an + 0.(b1b2......bn)
   x = (a1a2......an + 0.(b1b2......bn))/(10^n)
   
   y = 0.(b1b2......bm)
   10^m * y = b1b2......bm.(b1b2......bm)
   y = b1b2......bm/(10^m -1)

有序数组找给定和

用双指针

数组循环移位

优化思路：

1. 右移k位相当于左移-k位
2. k’ = k % n
3. 逆序

   abcd1234 移4位
   1. 左逆序: dcba1234
   2. 右逆序: dcba4321
   3. 全逆序: 1234abcd

数组分割

2n个数，分成两个n大小的数组，要求两个子数组的和最为接近
答：动态规划

判断字符串

给定两个字符串S1和S2，判定S2是否被S1作循环移位得到的字符串包含
答：判断S2是否在S1S1里面

从无头单链表删除节点

将下一个节点赋值给当前节点，将下一个节点删除

pCurrent->Next = pNext->Next;
pCurrent->Data = pNext->Data;
delete pNext;

瓷砖覆盖地毯

1*2 覆盖 N*M

1. N=1，M为偶数，总共需要M/2块
2. N*M为奇数，无法覆盖
3. N和M至少一个为偶数，设M为偶数，简单重复N次1*M的地板的做法

点在三角形内部

面积判断

struct point
{
	double x, y;
};

double Area(point A, point B, point C)
{
	double a, b, c = 0;
	Compute(A, B, C, a, b, c)
	Double p = (a + b + c) / 2;
	return sqrt((p - a) * (p - b) * (p - c) * p);
}

bool isInTriangle(point A, point B, point C, point D)
{
	return (Area(A, B, D) + Area(B, C, D) + Area(C, A, D) <= Area(A, B, C))
}

蚂蚁爬杆

方向掉头相当于两只蚂蚁独立穿行而过，所有只要分别计算每只蚂蚁离开木杆的事件，即可求出所有蚂蚁离开木杆的时间。