问题描述：【Math】423. Reconstruct Original Digits from English
解题思路：
这道题是给一个字符串，其中包含字母顺序打乱的英文单词表示的数字 0 - 9。按升序输出原始的数字。
这道题肯定是找每个英文单词的规律。首先容易想到先统计每个字符出现的次数；然后，注意到有些单词中存在独一无二的字符："zero" 中的 "z"，"two" 中的 "w"，"four" 中的 "u"，"six" 中的 "x" 以及 "eight" 中的 "e"，根据这个性质，可以先找出这些英文单词出现了几次；排除掉这些单词之后，剩下的 5 个单词其中 4 个也存在了独一无二的字符："one" 中的 "o"，"three" 中的 "t"，"five" 中的 "f"，"seven" 中的 "s"，按照上述方法继续操作；最后，剩下的 1 个单词 "nine" 中有独一无二的字符 "i"（也可以是 "e"），按照上述方法继续操作。最终，可以得到每个单词出现了几次，将结果升序排列输出即可。
这种做法类似于斯诺克运动中每次选择打哪颗红球的问题。刚开始，红球之间有干扰（单词之间存在相同字符），因此可以先选择独立的红球进行击打（选择存在独一无二的字符的单词）；这样，红球之间的干扰会随着球的入袋而慢慢减少（存在独一无二的字符的单词已经统计完次数）；那么，剩下的红球也就各自有了进球的路线（剩下的单词也存在了独一无二的单词）。
因此，在这道题中，我们需要找到一个存在第一无二字符的单词序列即可，比如 [0, 2, 4, 6, 8, 1, 3, 5, 7, 9]，当然这种序列不唯一。
刚开始写了一个没有循环的代码，很长，但相对容易理解，代码如下：
Python3 实现：
class Solution:
def originalDigits(self, s: str) -> str:
sets = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}
cnt = [0] * 10 # 保存结果
dic = collections.Counter(s)
if dic['z'] > 0:
cnt[0] = dic['z']
tmp = dic['z']
dic['z'] -= tmp; dic['e'] -= tmp; dic['r'] -= tmp; dic['o'] -= tmp
if dic['w'] > 0:
cnt[2] = dic['w']
tmp = dic['w']
dic['t'] -= tmp; dic['w'] -= tmp; dic['o'] -= tmp
if dic['u'] > 0:
cnt[4] = dic['u']
tmp = dic['u']
dic['f'] -= tmp; dic['o'] -= tmp; dic['u'] -= tmp; dic['r'] -= tmp
if dic['x'] > 0:
cnt[6] = dic['x']
tmp = dic['x']
dic['s'] -= tmp; dic['i'] -= tmp; dic['x'] -= tmp
if dic['s'] > 0:
cnt[7] = dic['s']
tmp = dic['s']
dic['s'] -= tmp; dic['e'] -= tmp; dic['v'] -= tmp; dic['e'] -= tmp; dic['n'] -= tmp
if dic['v'] > 0:
cnt[5] = dic['v']
tmp = dic['v']
dic['f'] -= tmp; dic['i'] -= tmp; dic['v'] -= tmp; dic['e'] -= tmp
if dic['g'] > 0:
cnt[8] = dic['g']
tmp = dic['g']
dic['e'] -= tmp; dic['i'] -= tmp; dic['g'] -= tmp; dic['h'] -= tmp; dic['t'] -= tmp
if dic['i'] > 0:
cnt[9] = dic['i']
tmp = dic['i']
dic['n'] -= tmp; dic['i'] -= tmp; dic['n'] -= tmp; dic['e'] -= tmp
if dic['n'] > 0:
cnt[1] = dic['n']
tmp = dic['n']
dic['o'] -= tmp; dic['n'] -= tmp; dic['e'] -= tmp
if dic['t'] > 0:
cnt[3] = dic['t']
tmp = dic['t']
dic['t'] -= tmp; dic['h'] -= tmp; dic['r'] -= tmp; dic['e'] -= tmp; dic['e'] -= tmp
# 结果输出
ans = ""
for i in range(10):
ans += str(i) * cnt[i]
return ans
更简洁的写法：
上述写法太繁琐，可以用下面更简洁的方法，思路都是一样的：
class Solution:
def originalDigits(self, s: str) -> str:
# 存储单词及其对应的独一无二的字符
en = [("zero", "z"), ("one", "o"), ("two", "w"), ("three", "t"), ("four", "u"), ("five", "f"), ("six", "x"), ("seven", "s"), ("eight", "g"), ("nine", "i")]
dic = collections.Counter(s)
ans = "" # 保存结果
for i in [0, 2, 4, 6, 8, 1, 3, 5, 7, 9]: # 按照这个序列能够保证独一无二的字符
n = dic[en[i][1]] # 独一无二的字符出现的次数
for ch in en[i][0]: # 单词的每个字符减去独一无二的字符出现的次数
dic[ch] -= n
ans += str(i) * n
return "".join(sorted(ans)) # 排序后输出结果
问题描述：【Math】593. Valid Square
解题思路：
这道题是给四个坐标，判断能否组成一个正方形。
刚开始的想法是按照 x 轴的坐标对四个点排序，然后根据点的坐标来判断。但是只考虑到了下图中的图 3 情况：
当然除了上述三种情况还有其他的情况，根据点来判断不可行。
注意到正方形有一个特点：正方形四条边相等，两条对角线相等。因此，我们可以计算两两坐标之间的距离，得到 C(4, 2) = 6 个距离；然后，对这 6 个距离从小到大排序，前四个距离相同（较短的四条边相等）且不为 0、后两个距离相同（较长的两条对角线相等），则必定为正方形，返回 True；否则，返回 False。
Python3 实现：
class Solution:
def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
def dist(x, y): # 计算两点之间的距离
return (x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2
# 计算四边形共6种组合的距离并排序
dists = sorted([dist(p1, p2), dist(p1, p3), dist(p1, p4), dist(p2, p3), dist(p2, p4), dist(p3, p4)])
# 距离不为0且有两种距离的四边形是正方形
if dists[0] != 0 and dists[0] == dists[1] == dists[2] == dists[3] and dists[4] == dists[5]:
return True
else:
return False
网友评论