给出题目一的试题链接如下:
这一题思路就很直接,直接做一下摄氏度到开氏和华氏的温度转换即可。
给出python代码实现如下:
class Solution:
def convertTemperature(self, celsius: float) -> List[float]:
return [celsius + 273.15, celsius*1.8 + 32]
提交代码评测得到:耗时63ms,占用内存13.8MB。
给出题目二的试题链接如下:
这一题我的思路还是非常暴力的,因为从条件看到时间复杂度要求不高,因此就直接用了一个二重循环来对这一问题进行了求解。
给出python代码实现如下:
class Solution:
def subarrayLCM(self, nums: List[int], k: int) -> int:
n = len(nums)
res = 0
s = 1
for i in range(n):
s = 1
for j in range(i, n):
if k % nums[j] != 0:
break
s = math.lcm(s, nums[j])
if s == k:
res += 1
return res
提交代码评测得到:耗时468ms,占用内存14MB。
给出题目三的试题链接如下:
这一题思路上也很直接,就是分两步进行实现:
不过比较惭愧的是,其中,关于第二步的实现,我们给出了一种简单地实现:
这个方法简单,且感觉上应该是交换次数最少的排序,但是暂时想不到严格的数学说明,不过万幸而言通过了全部测试样例,只能说感觉应该是对的了……
给出python代码实现如下:
class Solution:
def minimumOperations(self, root: Optional[TreeNode]) -> int:
nodes = []
def dfs(root, depth):
nonlocal nodes
if root is None:
return
if len(nodes) <= depth:
nodes.append([root.val])
else:
nodes[depth].append(root.val)
dfs(root.left, depth+1)
dfs(root.right, depth+1)
return
dfs(root, 0)
def get_min_swap(arr):
index = {}
for i, x in enumerate(arr):
index[x] = i
s = sorted(arr)
cnt = 0
for i, x in enumerate(s):
if index[x] == i:
continue
j = index[x]
y = arr[i]
arr[i], arr[j] = x, y
index[y] = j
index[x] = i
cnt += 1
return cnt
return sum(get_min_swap(arr) for arr in nodes)
提交代码评测得到:耗时2236ms,占用内存94.7MB。
给出题目四的试题链接如下:
这一题我的思路基本就是找到每一个字符开始所能够构成的回文以及对应的终点,然后就可以使用动态规划进行求解了。
不过思路虽然是这么个思路,但是我的实现方法有点暴力了,导致超时了好几次,最后也是勉强通过了全部测试样例。
给出python代码实现如下:
class Solution:
def maxPalindromes(self, s: str, k: int) -> int:
n = len(s)
if k == 1:
return n
palindromes = defaultdict(list)
for i in range(n-k+1):
j = i
while True:
j = s.find(s[i], j+1)
if j == -1:
break
elif j+1-i < k:
continue
elif s[i:j+1] == s[i:j+1][::-1]:
palindromes[i].append(j+1)
@lru_cache(None)
def dp(idx):
if idx >= n:
return 0
res = dp(idx+1)
for j in palindromes[idx]:
res = max(res, 1+dp(j))
return res
return dp(0)
提交代码评测得到:耗时8838ms,占用内存96.4MB。
这一题看了其他大佬们的解答之后,发现大佬的思路和我的思路基本一致,也是先找到每一个字符对应的回文字符串,然后再用动态规划找到最优解。
但是,他的实现比我要优雅太多了。
首先,我是通过从头遍历的方式寻找回文,这会导致大量的冗余计算,而大佬采用的方式是从回文的中部开始检索,从而就可以从中直接剪枝,因此可以节省极大的计算量。
而另一方面,在第二步的动态规划当中,我是找寻了所有可能的情况,但是事实上,对于每一个位置的回文,只要找寻以之作为终点的最短回文即可。
从而又可以进一步优化检索效率。
这里,我们摘录大佬的解答如下:
class Solution:
def maxPalindromes(self, s: str, k: int) -> int:
n = len(s)
pals = [-1] * n
for m in range(n):
# odd
l, r = m, m
while 0 <= l and r < n and s[l] == s[r]:
if r - l + 1 >= k:
pals[r] = max(pals[r], l)
break
l -= 1
r += 1
# even
l, r = m - 1, m
while 0 <= l and r < n and s[l] == s[r]:
if r - l + 1 >= k:
pals[r] = max(pals[r], l)
break
l -= 1
r += 1
dp = [0] * (n + 1)
for r in range(n):
if pals[r] == -1:
dp[r + 1] = dp[r]
else:
dp[r + 1] = max(dp[r], dp[pals[r]] + 1)
return dp[n]