LeetCode笔记：Weekly Contest 268
LeetCode笔记：Weekly Contest 268
codename_cys
发布于 2021-11-23 10:45:09
发布于 2021-11-23 10:45:09
文章被收录于专栏：我的充电站
1. 题目一
给出题目一的试题链接如下：
1，解题思路
这一题我的思路比较暴力，就是一个二重循环然后直接找对于任意位置上前后最远的颜色不同的位置，然后更新最大距离。
2. 代码实现
给出python代码实现如下：
class Solution:
def maxDistance(self, colors: List[int]) -> int:
n = len(colors)
res = 0
for i in range(n):
for j in range(i):
if colors[i] != colors[j]:
res = max(res, i-j)
break
for j in range(i+1, n):
if colors[i] != colors[j]:
res = max(res, j-i)
break
return res提交代码评测得到：耗时40ms，占用内存14.3MB。
2. 题目二
给出题目二的试题链接如下：
1，解题思路
这一题倒是没啥，按照题目意思直接处理就行了。
2. 代码实现
给出python代码实现如下：
class Solution:
def wateringPlants(self, plants: List[int], capacity: int) -> int:
res = 0
cap = capacity
for i, p in enumerate(plants):
if p <= cap:
res += 1
cap -= p
else:
res += 2*i+1
cap = capacity - p
return res提交代码评测得到：耗时48ms，占用内存14.5MB。
3. 题目三
给出题目三的试题链接如下：
1，解题思路
这一题我的构造思路是说记录下每一个元素的所有位置，然后对于任意一个query，只要找到对应的范围内有多少个值即可判断。而后者可以通过二分搜索减少时间复杂度。
2. 代码实现
给出python代码实现如下：
class RangeFreqQuery:
def __init__(self, arr: List[int]):
self.loc = defaultdict(list)
for i, k in enumerate(arr):
self.loc[k].append(i)
def query(self, left: int, right: int, value: int) -> int:
l = bisect.bisect_left(self.loc[value], left)
r = bisect.bisect_right(self.loc[value], right)
return r - l提交代码评测得到：耗时1528ms，占用内存53MB。
4. 题目四
给出题目四的试题链接如下：
1，解题思路
这一题我的思路是首先在n进制下获取所有的长度为i镜像数字，然后过滤掉其中在10进制下不是镜像数字的那些，直到得到的镜像数字总数多于n个，然后找到其中最小的n个进行求和处理即可。
而对于长度为i的镜像数字，我们可以通过一个迭代算法进行实现，而这个又可以通过缓存进行加速实现。
2. 代码实现
给出python代码实现如下：
class Solution:
def kMirror(self, k: int, n: int) -> int:
@lru_cache(None)
def fn(m, mid):
if m == 1:
res = [i for i in range(k)] if mid else [i for i in range(1, k)]
elif m == 2:
res = [i*k+i for i in range(k)] if mid else [i*k+i for i in range(1, k)]
else:
sub = fn(m-2, True)
res = [k*x for x in sub] if mid else []
b = k**(m-1)
for i in range(1, k):
for x in sub:
res.append(i + k*x + i*b)
return res
nums = []
i = 1
while len(nums) < n:
sub = fn(i, False)
sub = [x for x in sub if str(x) == str(x)[::-1]]
# print(i, k, sub)
nums.extend(sub)
i += 1
nums = sorted(nums)
return sum(nums[:n])提交代码评测得到：耗时1600ms，占用内存144.9MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/11/21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
