[TOC]

## 二分

### leetcode 392. 判断子序列

s = "abc", t = "ahbgdc"

s = "axc", t = "ahbgdc"

1. 用哈希集合hase_set记录下t中每个字符出现过的位置，即最多有26个key
2. 对s中每个字母进行匹配，s[i]一定出现在s[i-1]之后，所以匹配s[i]的时候，应该找hash_set[s[i]]中大于s[i-1]的索引的索引值
3. 我们用匹配左边界的二分法（即匹配第一个大于等于目标值的数），找当前字母索引列表中第一个大于上一个字母索引的值
4. 如果某个匹配到的边界值等于当前字幕索引列表的长度，则表明无法匹配当前字母，返回False
5. 全部成功匹配返回True

## BFS

m行，对于每个询问输出相应答案。

### 字串变换

A1 ->B1

A2 -> B2

abcxuudyyyz

abcdxudxyxyz

AA BB
A1 B1
A2 B2 |-> 变换规则

… … /

### CoVH之再破难关/黑白棋

Problem

OIBH组织派出的黄金十二人+青铜五小强还没有到, 他们只能指望原先的机关能够阻拦住柯南的脚步.

### 油田问题（java）

GeoSurvComp地质调查公司负责探测地下石油储藏。 GeoSurvComp现在在一块矩形区域探测石油，并把这个大区域分成了很多小块。他们通过专业设备，来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻，那么他们被认为是同一油藏的一部分。在这块矩形区域，可能有很多油藏。你的任务是确定有多少不同的油藏。
Input

Output

Sample Input

Sample Output
0
1
2
2

### Whack-A-Mole

Problem

This time we’ll play a variation of Whack-A-Mole! We’ll play this game on a board with 16
holes, from which individual moles pop-up. Using a mallet you can then “whack a mole”
and make it go hide underground. As you might know, however, whacking a mole will
often have the effect of making other moles rise and come out from the ground. In this
version of the game, every time you hit a mole with the mallet you’ll cause the immediate
four adjacent holes to change: any moles currently there will hide, while new moles popup from previously empty holes.
Imagine, for example, that you find yourself in the following game configuration, and you
prepare yourself to hit the mole at position 10 with the mallet.

You will cause the moles in positons 9, 10, 11, and 14 to hide, but you’ll also make a mole
appear at position 6. Thus ending up in the next configuration.

If you then hit the mole at position 2, then all of the moles at positions 1, 2, and 6 will hide;
but a new one in position 3 will appear. There is no use of hitting empty holes, as nothing
in the board will change. You may assume that all puzzles have a solution.
Your task is to write a computer program which, given an initial board configuration, finds
ashortest sequence of moles that you can hit in order to empty the board.
There might be several correct solutions with the same optimal length, finding any of them
will be enough. Your answer should be given as a sequence of numbers with the correct
order of moles to “whack”, each separated by a single space.

Example
Find one of the shortest sequences of moles you have to hit in order to clear the board if
starting from the configuration with moles at positions 1, 2, 4, 8, 9, 10, 11, and 14.
Discussion: This is the same configuration of moles as given in the first illustration above.
After hitting moles at positions 10 and 2, you’ll end up in the following configuration.

At this point, a single hit to the mole at position 4 will clear the board.
Answer: 10 2 4
Attempts: 2 out of Infinity
Final marks: 9 / 9 (100.0%)

1. 其实题目就是问我们怎么样敲地鼠才能使得全部地鼠都躲起来
2. 注意有地鼠才能敲，敲完之后该位置和四周位置地鼠状态会相反（躲起来的地鼠会站起来，站起来的地鼠会躲起来）
3. 直接记录4*4矩阵状态，然后一路BFS出结果

## DFS

### 选数

已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34。

n , k （1<=n<=20，k＜n）
x1,x2，…,xn （1<=xi<=5000000）

屏幕输出，格式为：

### 单词接龙

（连成的“龙”为atoucheatactactouchoose）

### 加分二叉树

subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数。

（1）tree的最高加分

（2）tree的前序遍历

Problem

3,1,2,4

4,3,6

7,9

16

### 滑雪

Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

Problem

### 挖地雷

------ 本文结束，感谢您的阅读 ------