+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-07(3)

2019-08(103)

2019-09(115)

2019-10(9)

2019-11(3)

2019-12(16)

2020-01(23)

2020-02(20)

第二次力扣周赛:排名149 / 2046;在完赛边缘打转(总结了5点,实力还不够)

发布于2020-02-10 17:26     阅读(324)     评论(0)     点赞(3)     收藏(2)


前言: 上午10:30 - 12:00 第二次力扣周赛,最后一题也写完了,但是没有通过。完成了 3 / 4 的题,排名 149 / 2046。

赛题:https://leetcode-cn.com/contest/weekly-contest-175

排名:https://leetcode-cn.com/contest/weekly-contest-175/ranking/


上周自己只做了一道题,排名是 890 / 1659 ,看来送分题都有一半的人不要,划水的人不少。上周打完比赛后,我大概练习了 6 道 LeetCode 来迎接今天的比赛。前两天我在忙一个仿真项目,用到基本的 python3 运算与 pygame 来操控窗体。

在这里插入图片描述

而本次排名为 149 / 2046 ,留给最后一题的时间大概为 35 分钟,在最后 10 分钟写好,但是未通过。

本次比赛大概五点心得:

  • 题目难度不大,竞争对手水平两极分化;
  • “马虎”(将在下面的复盘中讨论什么是“马虎”,以及如何避免);
  • 起码的时间复杂度;
  • 调试;
  • 关掉 QQ 与微信!

1. 竞争环境

在这里插入图片描述

2046人报名参赛,只有42人完赛。竞争对手水平普遍一般。

我90分钟正好把题做完(最后一题已经写完,但运行报错未通过),而有高手16分钟就完赛,速度是我的6倍,几乎难以想象!

2. 复盘:“别马虎!”

百度百科:马虎,指漫不经心;不介意;疏忽;轻率。如:这人太马虎。也指勉强,将就的意思。

如果没有“马虎”,即使最后一题未通过,我的排名也会提升的20名左右。

5332. 检查整数及其两倍数是否存在
def checkIfExist(self, arr) -> bool:
    def twice(a, b):
		if a == b * 2:
			return True
        if a * 2 == b:
            return True
        return False
        
    for i in range(len(arr)):
        for j in range(len(arr) - i - 1):
            if twice(arr[i], arr[j+i+1]):
            # if twice(arr[i], arr[j]):
   	            return True
    return False
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

非常简单的一道题,我没有选择遍历 n2 n^2 矩阵,而是遍历一个三角阵 n2/2 n^2 / 2 ,但是,竟然忘记了为 j 增加偏置量(将 arr[j+i+1] 错写成 arr[j] ),导致报错,非常可惜。

5333. 制造字母异位词的最小步骤数

很简答的一道题,在理解“字母异位词”时有偏差,导致做得慢了。

def minSteps(self, s: str, t: str) -> int:
    s_s = dict()
    t_s = dict()
    count = 0

    for char in s:
        s_s.setdefault(char, 0)
        s_s[char] += 1
    
    for char in t:
        s_s.setdefault(char, 0)
        s_s[char] -= 1
        if s_s[char] < 0:
            count += 1

    return count
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

上面是我的解决方案,就是对两个 str() 的每个字母查数,因此分别建两个哈希表 dict() 就行了。字母不够的话, count++ ,最后返回 count

5334. 推文计数

头一次见到“设计一个类”的问题,开始时有被吓到,实际上非常简单。

class TweetCounts:

    def __init__(self):
        # (name, [time_list])
        self.info = dict()

    def recordTweet(self, tweetName: str, time: int) -> None:
        self.info.setdefault(tweetName, list())
        self.info[tweetName].append(time)

    def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int):
        delta = 60
        if freq == "minute":
            delta = 60
        if freq == "hour":
            delta = 60 * 60
        if freq == "day":
            delta = 60 * 60 * 24
        rts = list()
        import math
        count = math.ceil((endTime - startTime + 1) / delta)
        count = max(1, count)
        time_list = self.info[tweetName]
        for i in range(count):
            start = startTime + i * delta
            end = min(start + delta, endTime + 1)
            c = 0
            for time in time_list:
                if start <= time < end:
                    c += 1
            rts.append(c)
        if len(rts) == 0:
            return 0
        return rts

# Your TweetCounts object will be instantiated and called as such:
# obj = TweetCounts()
# obj.recordTweet(tweetName,time)
# param_2 = obj.getTweetCountsPerFrequency(freq,tweetName,startTime,endTime)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

我的解决方案如上,时间花在了阅读理解上,很不值得,其实不应该想太多:这种题,不会太难,因此往简单了想就好。

开始时,有些偷懒,按照如下思想设置了“存储-查找”规则:

# [(name, time)]
self.info = list()
# search
for n, t in self.info:
	if n == tweetName and start_time <= t <= end_time:
		rts += 1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

这实际上是非常不科学的,我也因此复出了代价:

  • 尽管逻辑上没有错误,但是查找每个用户,都需要对所有 info 进行查找,浪费时间;
  • 因此提交代码后,报错(大量数据下,运行超时)。

我将哈希映射引入,来解决这个问题,如下。

# (name, [time_list])
self.info = dict()
# search
for t in self.info[tweetName]:
	if start_time <= t <= end_time:
		rts += 1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

看来: 起码的时间复杂度还是要考虑,不能差的离谱。

5335. 参加考试的最大学生数

最后一题给我的第一感觉很明确:广度优先搜索 BFS

但是问题是,没有起点。那索性就把所有的可用点当成起点,都来一遍。

BFS 可以用递归来写,但这着实花了我一些时间。我的解决方案如下。

def maxStudents(self, seats) -> int:
    xL = len(seats)
    yL = len(seats[0])
    useable = list()
    for i in range(xL):
        for j in range(yL):
            if seats[i][j] != '#':
                useable.append((j, i))
    
    def ok(a, b):
        if a[0] - 1 == b[0] and (a[1] == b[1] or a[1] + 1 == b[1]):
            return False
        if a[0] + 1 == b[0] and (a[1] == b[1] or a[1] + 1 == b[1]):
            return False
        if b[0] + 1 == a[0] and (b[1] == a[1] or b[1] + 1 == a[1]):
            return False
        if b[0] - 1 == a[0] and (b[1] == a[1] or b[1] + 1 == a[1]):
            return False
        return True

    rts = set()
    def bfs(seat, used_list, notused_list, count):
        
        if notused_list is None:
            rts.add(count)
            return
        used_list = used_list.copy()
        notused_list = notused_list.copy()
        for nextSeat in notused_list:
            seat_ok = True
            for s in used_list:
                if not ok(s, nextSeat):
                    seat_ok = False
            if seat_ok:
                count += 1
                used_list.append(nextSeat)
                notused_list.remove(nextSeat)
                bfs(nextSeat, used_list, notused_list, count)
            rts.add(count)
        return
    
    for s in useable:
        tmp = useable.copy()
        tmp.remove(s)
        bfs(s, [s], tmp, 1)
    return max(rts)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

因为时间紧迫+思路其实并不明晰,犯了不少“马虎”的毛病,如没有分清数组元素与横纵坐标的关系,将 useable.append((j, i)) 中的 i j 写反、忘了测试全为 '#' 的特殊例子等。

除此之外,我认为我在上面展示的方案是正确解决方案,但是提交时“报错”了,原因为“超时”。

我试了一下,确实太慢了,在本地,运行下面的例子也需要3秒左右:

[[".",".","#","#",".","#","#"],["#","#","#",".","#","#","."],
[".","#",".","#",".","#","."],[".","#",".","#",".",".","#"],
[".",".","#","#",".","#","."],["#",".","#","#",".","#","#"]]
  • 1
  • 2
  • 3

但是能运行出来,说明算法没错(没有陷入死循环)。

我准备今天休息一下,下周看看别人的正确的解决方案。我还是比较疑惑的,因为按照我的经验,经典的 bfs 陷入了这种维度爆炸的困境,那可能说明精确解法已经不好使了。但是这道题是 LeetCode 题目,则其一定有很快的精确解法。

3. 比赛经验:调试环境与屏蔽干扰!

我这次在本地建了一个 .py 文件,直接在本地调试,节省线上调试的网络传输时间。

class Solution:
    def checkIfExist(self, arr) -> bool:
    	...

solution = Solution()
arr = test_data_1
arr = test_data_2
# arr = test_data_3
print(solution.checkIfExist(arr))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

比赛时 QQ 、微信开始闪,我觉得对我没什么影响,就没有去管;但是到了后面时间紧张的时候,这很闹心,因此,我选择关掉这两个程序。实际上,以后应该从一开始就关闭。


进步还是不少的,大概总结这么多,下周想起来的话,可以再来一次。客观估计,结果不会变差,只会保持或者更好。从题目难度来看,目前没必要刻意去刷 LeetCode 。

PiperLiu
2020-2-9 15:28:14

发布了136 篇原创文章 · 获赞 42 · 访问量 1万+


所属网站分类: 技术文章 > python文章

作者:我下面给你吃

链接: http://www.pythonheidong.com/blog/article/231012/

来源:python黑洞网 www.pythonheidong.com

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

3 0

赞一赞 or 踩一踩

收藏该文
已收藏

评论内容:(最多支持255个字符)

相似文章

  5171. 最接近的因数

  Python实现生成西瓜数据集的Excel文件

  Leetcode - 删除排序数组中的重复项

  python第五天-字符串

  数据结构|LeetCode(力扣)经典题:队列

  python学习笔记(3)

  TYD_初识python数据可视化库-Matplotlib

  Scrapy安装与应用教程

  python实现修改文件中的内容

  mac环境下python3.6安装pyhanlp工具包

优质资源排行榜

 python经典电子书大合集下载 下载次数 8138

 零基础java开发工程师视频教程全套,基础+进阶+项目实战(152G) 下载次数 7550

 零基础前端开发工程师视频教程全套,基础+进阶+项目实战(共120G) 下载次数 7442

 零基础大数据全套视频400G 下载次数 7006

 零基础php开发工程师视频教程全套,基础+进阶+项目实战(80G) 下载次数 6893

 零基础软件测试全套系统教程 下载次数 6506

 全套人工智能视频+pdf 下载次数 6443

 IOS全套视频教程 基础班+就业班 下载次数 4680

 编程小白的第一本python入门书(高清版)PDF下载 下载次数 3647

10  effective python编写高质量Python代码的59个有效方法 pdf下载 下载次数 3361

11  Python深度学习 pdf下载 下载次数 3156

12  笨办法学python pdf下载 下载次数 3087

13  Python Cookbook第三版中文PDF下载高清完整扫描原版 下载次数 3024

14  树莓派Python编程指南 pdf下载 下载次数 3011

15  python从入门到精通视频(全60集)python视频教程下载 下载次数 3009

16  python项目开发视频 下载次数 3002

17  使用python+pygame开发的小游戏《嗷大喵快跑》源码下载 下载次数 3000

18  黑马2017年java就业班全套视频教程 下载次数 2992

19  Python基础教程 pdf下载 下载次数 2988

20  python实战项目 平铺图像板系统源码下载,适用于想要保存,标记和共享图像,视频和网页的用户 下载次数 2987

21  利用python实现程序内存监控脚本 下载次数 2987

22  老男孩python自动化视频 下载次数 2983

23  老王python基础+进阶+项目视频教程 下载次数 2974

24  尚硅谷Go学科全套视频 下载次数 2972

25  某硅谷Python项目+AI课程+核心基础视频教程 下载次数 2968

26  Web前端实战精品课程 下载次数 2967

27  Python算法教程_中文版 pdf下载 下载次数 2966

28  tron python小游戏 下载次数 2963

29  [小甲鱼]零基础入门学习Python 下载次数 2962

30  老男孩python全栈开发15期 下载次数 2958

31  2017最新web前端开发完整视频教程附源码 下载次数 2948

32  最新全套完整JAVAWEB2018开发视频 下载次数 2926

33  流畅的Python PDF下载高清完整扫描原版 下载次数 2919

34  Spring boot实战视频6套下载 下载次数 2910

35  python全套视频十五期(116G) 下载次数 2908

36  Python高性能编程 pdf下载 下载次数 2906

37  Python项目实战 下载次数 2887

38  30个小时搞定Python网络爬虫 含源码 下载次数 2884

39  简明python教程 (A Byte of Python)pdf下载 下载次数 2884

40  利用Python进行数据分析 pdf下载 下载次数 2884

41  python全自动抢火车票教程-python视频教程下载 下载次数 2883

42  尚硅谷大数据之Hadoop视频 下载次数 2876

43  Python A~B~C~ python视频教程下载 下载次数 2866

44  数据结构与算法视频(小甲鱼讲解-全) 下载次数 2864

45  web小程序表白天数倒计时源码下载 下载次数 2863

46  python基础视频教程 下载次数 2862

47  go语言全套视频 下载次数 2855

48  清华学霸尹成Python爬虫视频-ok 下载次数 2846

49  黑马前端36期最全视频和代码 下载次数 2843

50  2018最新全套web前端视频教程+源码下载 下载次数 2841