LeetCode Contest 169
这次只做出了前三题。最后一题我算了一下枚举复杂度也大概是 10!=3628800 左右，但是就老是 TLE。今天早上用 C 重新写了一下就过了。有点郁闷。
第一题Find N Unique Integers Sum up to Zero
每次加入 i 和 -i 就能保证和为0。如果 n 是奇数，那么我们要添加 0。
class Solution:
def sumZero(self, n: int) -> List[int]:
ans = []
if n & 1:
ans.append(0)
for i in range(1, n//2 + 1):
ans.append(i)
ans.append(-i)
return ans
第二题All Elements in Two Binary Search Trees
二叉搜索树中序遍历能给出升序的数列，我们可以按照这个性质合并这两二叉搜索树：得到两个排好序的数列，然后合并这两个数列。但是为了快速写出这道题，我就将所有数收集到一个数组，调用函数排个序。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
ans = []
def dfs(root):
if not root:
return
ans.append(root.val)
dfs(root.left)
dfs(root.right)
dfs(root1)
dfs(root2)
ans.sort()
return ans
第三题Jump Game III
宽度优先搜索：每次跳到下一个可以跳到而且没有跳到过的点，一直到值为 0 的位置或者没有办法继续跳为止。
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
if arr[start] == 0:
return True
n = len(arr)
visited = set()
stack = [start]
visited.add(start)
while stack:
x = stack.pop()
for y in [x + arr[x], x - arr[x]]:
if 0 <= y < n and y not in visited:
if arr[y] == 0:
return True
stack.append(y)
visited.add(y)
return False
第四题Verbal Arithmetic Puzzle
首先做一个预处理，由这个单词组成等式变成字母的等式。比如
SEND + MORE = MONEY
可以变成
1000S + 100E + 10N + D + 1000M + 100O + 10R + E - 10000M - 1000O - 100N - 10E - Y = 0，
进一步化简为
1000S + 91E - 90N + D - 9000M - 900O + 10R - Y = 0.
现在我们可以枚举字母可能对应的数字即可。这里要注意一个限制，单词中第一个字母不能为 0。我们可以给出每个字母对应的数字范围。一般的字母的数字范围是从 0 到 9，而出现在单词首端的字母则从 1 到 9。我们还可以利用等式缩小某些字母的数字范围。
我用 Python 实现上述算法总是 TLE，连利用等式缩小数字范围这种优化也没有逃过 TLE。然后今天早上用 C 实现一下就过了。。。不用优化也能过的那种。
int get_multiplier(int *mult, int *nonzero, char *word, int p) {
int n = strlen(word);
char *str = word + n;
while (str != word) {
str --;
int idx = *str - 'A';
if (str == word)
nonzero[idx] = 1;
mult[idx] += p;
p *= 10;
}
return 0;
}
int dfs(int *low, int *high, int *vals, int n, int i, int cur, int used, bool *ret) {
if (*ret)
return 0;
if (i == n) {
if (cur == 0)
*ret = true;
return 0;
}
for (int d = low[i]; d <= high[i]; d ++) {
if ((used >> d) & 1)
continue;
dfs(low, high, vals, n, i+1, cur+d*vals[i], used|(1<<d), ret);
}
return 0;
}
bool isSolvable(char ** words, int wordsSize, char * result){
int mult[26] = {0};
int nonzero[26] = {0};
int n = 0;
int vals[26];
int low[26];
int high[26];
bool ret = false;
for (int i = 0; i < wordsSize; i ++)
get_multiplier(mult, nonzero, words[i], 1);
get_multiplier(mult, nonzero, result, -1);
for (int i = 0; i < 26; i ++)
if (mult[i] != 0) {
vals[n] = mult[i];
low[n] = 0;
high[n] = 9;
if (nonzero[i])
low[n] = 1;
n ++;
}
if (n > 10)
return false;
// 以下这段是优化，使用之后能使运行时间从 ～550ms 减到 ～250ms
/*
int m = 0;
for (int i = 0; i < n; i ++)
if (vals[i] > vals[m])
m = i;
if (vals[m] < 0)
return false;
int s = 0;
for (int i = 0; i < n; i ++)
if (vals[i] < 0)
s -= vals[i];
int t = 0;
for (int i = 0; i < n; i ++)
if (i != m && vals[i] > 0)
t += vals[i];
if (1 + (9 * s - t) / vals[m] < high[m])
high[m] = 1 + (9 * s - t) / vals[m];
if ((s - 9 * t) / vals[m] > low[m])
low[m] = (s - 9*t) / vals[m];
for (int i = 0; i < n; i ++)
if (vals[i] < vals[m])
m = i;
if (vals[m] > 0)
return false;
s = 0;
for (int i = 0; i < n; i ++)
if (vals[i] > 0)
s += vals[i];
t = 0;
for (int i = 0; i < n; i ++)
if (i != m && vals[i] < 0)
t -= vals[i];
if (1 + (9 * s - t) / (-vals[m]) < high[m])
high[m] = 1 + (9 * s - t) / (-vals[m]);
if ((s - 9 * t) / (-vals[m]) > low[m])
low[m] = (s - 9*t) / (-vals[m]);
*/
dfs(low, high, vals, n, 0, 0, 0, &ret);
return ret;
}
