# LeetCode174-Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2(K) -3 3
-5 -10 1
10 30 -5(P)

Notes:

• The knight’s health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

# 思路

• 由于碱基无非ACGT四种类型，可以使用00 01 10 11四个状态代替ACGT四种碱基，比如AAGCT就是00 00 10 01 11，对任意一个长度为10的子串都可以转化使用20个位的int值hint。这样就可将unordered_set<string> repeated转变为unordered_set<int> repeated, 一定程度上减少了所需的存储空间。
• 值得一提的是，每次从s[i]->s[i+9]变为s[i+1]->s[i+10]，使用了这样一个方法： 其中eraser是一个宏定义, 值为0x3ffff, 二进制是00111111111111111111, 用于擦除hint中的最高2位s[i]碱基对应的值, 再左移2, 最后加上s[i+10]的碱基对应的值。

12 1100 110 11
13 1101 110 11
14 1110 111 11
15 1111 111 11

# 分析

stp1：最小值为2，取出2并删除2，4，6，8，10，12，集合变为{3, 5, 7, 9, 11}；
stp2：最小值为3，取出3并删除3，6，9，集合变为{5, 7, 11}

# 注意

1. 一开始我用unordered_set来标记一个数是否被删除，后来内存使用超出要求。后来改用bool数组来记录就AC了。
2. 注意是小于n，而非小于等于n。

# LeetCode 208-Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.

### 注意

• startsWith(prefix)方法不需要待检查的prefix是字典树中单词的结尾；
• search(key)方法要求待检查key是字典树中单词的结尾；
• 对指针数组的声明应该是TrieNode *child[26]

# LeetCode 209-Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

## 分析

### 步骤

• 我们设置bottom和top控制子数组的头部和尾部。
• 初始化bottom=0，top为-1，表示一个空的子数组
• 子数组和sum=0，最小长度len=0。
• 当sum < s时，在当前子数组的尾部增加一个元素bottom[++top]。
• 当sum ≥ s时，去掉当前子数组的头部元素，并++bottom。
• 退出循环的条件：top == nums.size() 或 bottom>top（此时已经存在最小len为1，不可能更小，可以退出）。

O(n)及O(nlogn)算法

# LeetCode 210-Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

## 注意

• 值得注意的是，特殊情况输入numCourses ＝ 1，prereqisities为空数组时，答案为[0]，只有1个节点，并没有边的存在。

• 第二种方法中onStack在每次结束本次递归时，需要变为false，表示这条路径上后面的节点在后面的判断环中，不会被认为是同一路径上的节点。（感觉好绕）