又是只做出两题的一天,唉,心累成疾,不过所幸结果还算勉勉强强,不至于太过丢人吧,唉……
给出题目一的试题链接如下:
这一题没啥好说的,根据题意,每一座山的山峰高度就是前面所有元素的求和,因此,我们累加之后求一个最大值即可。
给出python代码实现如下:
class Solution:
def largestAltitude(self, gain: List[int]) -> int:
return max(0, max(accumulate(gain)))
提交代码评测得到:耗时32ms,占用内存14.1MB。
给出题目二的试题链接如下:
这一题比赛的时候就完全没有做出来,比赛完了之后看了一下别人的解法,简直惊掉了三观,因为他们的思路极其简单直接,但是我总觉得这个思路不完备,可能存在bug……
whatever,这里,我们先给出他们的解题思路说明,然后给出代码实现,读者也可以自己想一想,反正我个人总是觉得这个解法有逻辑漏洞……
他们的算法思路核心点如下:
但是,这里有一个很奇怪的逻辑,即:为什么最优解的时候一定是教所有人同一种语言呢?为什么不可能是教其中某些人语言A,而另一部分人语言B呢?
whatever,我们先按照上述思路进行代码写作,发现可以成功通过所有测试样例。
给出python代码实现如下:
class Solution:
def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
languages = [set(langs) for langs in languages]
res = len(friendships)
for lan in range(n):
teach = set()
for u, v in friendships:
u, v = u-1, v-1
if languages[u] & languages[v]:
continue
if lan not in languages[u]:
teach.add(u)
if lan not in languages[v]:
teach.add(v)
res = min(res, len(teach))
return res
提交代码评测得到:8408ms,占用内存27.8MB。
给出题目三的试题链接如下:
这一题虽然被放在了题目三,但事实上上较之第二题感觉要简单多了。
对于encoded中的每一个元素y[i] = x[i] ^ x[i+1]
,又由于基本的性质x ^ x == 0
,因此,我们对给出的数组累积求一个异或操作就能够得到一个新的数组,他们的元素分别为z[i] = x[0] ^ x[i+1]
。
剩下的问题就是我们如何求出x[0]
,由于元素总数为基数,因此,我们将偶数的元素全部求个异或操作,就能够得到除了x[0]
之外所有元素的异或结果,然后又由于元素来自于1到n,因此,我们有:
x[0] = 1^2^...^n ^ z[1]^z[3]^...
由此,我们可以反解得到全部的数字。
给出python代码实现如下:
class Solution:
def decode(self, encoded: List[int]) -> List[int]:
n = len(encoded)
x1 = 0
for i in range(1, n+2):
x1 = x1 ^ i
# print(x1)
for i in range(1, n, 2):
x1 = x1 ^ encoded[i]
# print(x1)
s = deepcopy(encoded)
for i in range(n-1):
s[i+1] = s[i] ^ s[i+1]
res = [x1] + [x1 ^ x for x in s]
return res
提交代码评测得到:耗时1492ms,占用内存35MB。
给出题目四的试题链接如下:
这一题比赛的时候我的思路是采用动态规划的解题方法,代码倒是挺容易就写出来了,但是果不其然遇到了超时问题,然后就挂了。
赛后看了一下别人的解法,他们的思路事实上比赛的时候我也想过,即:
但是,有关其中第二点的实现我当时没有想出来,后来看了别人的解答之后倒是现在能够明白了,想通了之后就感觉还是蛮简单的。
我们考察针对某一个query (n, k)
,假设p是k的一个因子,且p的阶数为m,即k % p**m == 0 and k % (p**(m+1)) != 0
。
此时,我们要将这m个p放置到n个数当中,且允许一个数中被放置多个。相当于一个切分问题,我们现在有m个全同的元素,要在其中插入n−1个格栅,使之分成n份,共有多少种不同的插入方法。
这个问题基本可以秒答了,为:
而对于不同的因子,他们的排列是相互独立的,因此,我们将所有因数的解进行求积操作即可得到我们最终的结果。
给出python代码实现如下:
class Solution:
def get_prime_number(self):
return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103]
@lru_cache(None)
def C(self, n, m):
MOD = 10**9 + 7
res = 1
if m < n // 2:
m = n - m
for i in range(m+1, n+1):
res *= i
for i in range(n-m):
res = res // (i+1)
return res % MOD
def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
MOD = 10 ** 9 + 7
primes = self.get_prime_number()
def f(n, k):
if n == 1:
return 1
elif k == 1:
return 1
factor = defaultdict(int)
res = 1
for p in primes:
while k % p == 0:
factor[p] += 1
k = k // p
res *= self.C(n-1+factor[p], n-1)
if k != 1:
res *= n
return res % MOD
return [f(n, k) for n, k in queries]
提交代码评测得到:耗时864ms,占用内存32.1MB。为当前最优的代码实现。