LeetCode Contest 53
这次比赛又是对Python不友好。最后一题同样的实现Python会TLE，但是C++就AC。不过也有可能我的算法不是太好。值得一提的是，我发现比赛时我第三题的算法是错误的，但是还是过了。
第一题Binary Number with Alternating Bits
比较直接，代码如下。
class Solution(object):
def hasAlternatingBits(self, n):
"""
:type n: int
:rtype: bool
"""
b = bin(n)[2:]
return all(b[i]!=b[i+1] for i in range(len(b)-1))
第二题Max Area of Island
用DFS找出每个连通分支的大小，求其中最大值。
class Solution(object):
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
n, m = len(grid), len(grid[0])
visited = set()
def dfs(i, j, s):
for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
x, y = di+i, dj+j
if x < 0 or y < 0 or x >= n or y >= m:
continue
if grid[x][y] == 0 or (x, y) in visited:
continue
s.add((x, y))
visited.add((x, y))
dfs(x, y, s)
ans = 0
for i in xrange(n):
for j in xrange(m):
if grid[i][j] == 1 and (i, j) not in visited:
visited.add((i, j))
s = set()
s.add((i, j))
dfs(i, j, s)
ans = max(len(s), ans)
return ans
第三题Number of Distinct Islands
寻找岛屿的算法跟第二题一摸一样的，关键是怎么在平移不变的条件区分两个岛屿。我比赛时候的想法是将岛屿左上角移到(0, 0)坐标，那么岛屿由每一行的列坐标以及行长度完全决定。比如岛屿
11
1
可以表示为(0, 2, 0, 1)。再比如岛屿
11
1
111
可以表示为(0, 2, 1, 1, -1, 3)。虽然比赛的时候通过了，但是这个想法是错误的，比如如下两个岛屿：
111 111
101 110
都可以表示为(0, 3, 0, 2)。正确的做法是将岛屿左上角移到(0, 0)之后，重新计算岛屿所有坐标的值，使用新的坐标排好序作为岛屿的标识。下面给出的是正确算法的代码。
class Solution(object):
def numDistinctIslands(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
def signature(s):
s = sorted(s)
a, b = s[0]
return tuple((i-a, j-b) for i, j in s)
n, m = len(grid), len(grid[0])
visited = set()
def dfs(i, j, s):
for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
x, y = di+i, dj+j
if x < 0 or y < 0 or x >= n or y >= m:
continue
if grid[x][y] == 0 or (x, y) in visited:
continue
s.add((x, y))
visited.add((x, y))
dfs(x, y, s)
ans = set()
for i in xrange(n):
for j in xrange(m):
if grid[i][j] == 1 and (i, j) not in visited:
visited.add((i, j))
s = set()
s.add((i, j))
dfs(i, j, s)
ans.add(signature(s))
return len(ans)
第四题Stickers to Spell Word
每个单词给出了一个长度为26的向量，代表每个字母出现的次数。假设给定n个单词对应的是n个向量s1, ..., sn，目标单词对应的向量为t。那么这个问题的数学表达是在满足
的情况下，求c1+...+cn的最小值。
初始状态是0向量，我们可以用bfs寻找最小值。比如使用k个单词得到的所有状态保存在cur中，那么k+1个单词的所有状态是cur中每个状态加上另一个单词得到的。这里做向量加法的时候有个很重要的技巧：对于状态c，以及一个单词s，那么定义c+s的第i个分量为
那么上述的不等式在这种新的加法下就变成了等号。这样我们就可以使用哈希表快速判断t是否在cur里。
一个简单的优化：我们不需要长度为26的向量，只需考虑t不为0的分量就行。
对于如何哈希/散列std::vector<int>，我是参考stackoverflow上的这个问答。
namespace std{
template <>
struct hash<std::vector<int>> {
size_t operator()(const std::vector<int>& v) const {
std::hash<int> hasher;
size_t seed = 0;
for (int i : v) {
seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
return seed;
}
};
}
class Solution {
public:
int minStickers(vector<string>& stickers, string target) {
if (impossible(stickers, target))
return -1;
vector<int> t(26, 0);
for (auto c: target) {
t[c-'a'] ++;
}
unordered_set<vector<int>> ss;
for (auto s: stickers) {
vector<int> tmp(26, 0);
for (auto c: s) tmp[c-'a'] ++;
vector<int> st;
for (int i=0; i<26; i++)
if (t[i] != 0)
st.push_back(min(tmp[i], t[i]));
ss.insert(st);
}
vector<int> tmp;
for (int i=0; i<26; i++)
if (t[i] != 0)
tmp.push_back(t[i]);
t = tmp;
// bfs
tmp = vector<int>(t.size(), 0);
unordered_set<vector<int>> cur, next;
cur.insert(tmp);
int ans = 0;
while (true) {
if (cur.find(t) != cur.end())
return ans;
ans ++;
next.clear();
for (auto c: cur)
for (auto s: ss)
next.insert(add(c, s, t));
cur = next;
}
}
private:
bool impossible(vector<string>& stickers, string target) {
vector<bool> t(26, false);
for (auto c: target) t[c-'a'] = true;
for (auto s: stickers)
for (auto c: s)
t[c-'a'] = false;
for (auto b: t)
if (b) return true;
return false;
}
vector<int> add(vector<int>& c, vector<int>& s, vector<int>& t) {
vector<int> ans(c.size(), 0);
for (int i=0; i<c.size(); i++)
ans[i] = min(t[i], c[i]+s[i]);
return ans;
}
};
