给出题目一的试题链接如下:
这题我的解题思路多少有点暴力,就是直接一个二重循环就是了,反正题目整体的复杂度也不会很高……
给出python代码实现如下:
class Solution:
def countPairs(self, nums: List[int], k: int) -> int:
n = len(nums)
res = 0
for i in range(n):
for j in range(i+1, n):
if i*j % k == 0 and nums[i] == nums[j]:
res += 1
return res
提交代码评测得到:耗时112ms,占用内存13.8MB。
给出题目二的试题链接如下:
这一题其实感觉比上一题还要简单,三个连续的数相加之和必然等于中间这个数的3倍,因此如果给出的和无法被3整除,那么必然无解,反之就可以求得答案为
。
给出python代码实现如下:
class Solution:
def sumOfThree(self, num: int) -> List[int]:
if num % 3 == 0:
mid = num // 3
return [mid-1, mid, mid+1]
return []
提交代码评测得到:耗时62ms,占用内存13.8MB。
给出题目三的试题链接如下:
这一题其实也还好。
显然如果目标数s为奇数,则不存在可行的构造方式,直接返回空即可。
而对于s为偶数的情况,我们很容易就能给出最大数量的一种构造方式,就是从
依次开始构造,直到其求和超过s,此时我们取前
个数,然后将余下的差全部加到最后一个数上,即可完成我们的构造。
给出python代码实现如下:
class Solution:
def maximumEvenSplit(self, finalSum: int) -> List[int]:
if finalSum % 2 == 1:
return []
k = int((math.sqrt(4*finalSum+1) - 1) / 2)
res = [2*i for i in range(1, k+1)]
s = sum(res)
if s != finalSum:
res[-1] += finalSum - s
return res
提交代码评测得到:耗时763ms,占用内存26.6MB。
给出题目四的试题链接如下:
这一题没能搞定,不过看了一下别人的解答,似乎这是一道经典算法的变体,就很emo……
这里我们就直接给出别人的解题方法了,我自己也刚好学习一下,涨涨姿势……