前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode笔记:Weekly Contest 268

LeetCode笔记:Weekly Contest 268

作者头像
codename_cys
发布2021-11-23 10:45:09
2300
发布2021-11-23 10:45:09
举报
文章被收录于专栏:我的充电站

1. 题目一

给出题目一的试题链接如下:

1,解题思路

这一题我的思路比较暴力,就是一个二重循环然后直接找对于任意位置上前后最远的颜色不同的位置,然后更新最大距离。

2. 代码实现

给出python代码实现如下:

代码语言:javascript
复制
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代码实现如下:

代码语言:javascript
复制
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代码实现如下:

代码语言:javascript
复制
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代码实现如下:

代码语言:javascript
复制
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 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目一
    • 1,解题思路
      • 2. 代码实现
      • 2. 题目二
        • 1,解题思路
          • 2. 代码实现
          • 3. 题目三
            • 1,解题思路
              • 2. 代码实现
              • 4. 题目四
                • 1,解题思路
                  • 2. 代码实现
                  领券
                  问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档