📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: tall_cool_13
跳转到指定楼层
上一主题 下一主题
收起左侧

开一贴刷题打卡

🔗
 楼主| tall_cool_13 2018-10-8 13:00:40 | 只看该作者
全局:
写了一道207,除了三个问题,一个没有注意引用,第二个判断是否有死循环出现问题,第三个超时
  1. class Solution(object):
  2.     def canFinish(self, numCourses, prerequisites):
  3.         """
  4.         :type numCourses: int
  5.         :type prerequisites: List[List[int]]
  6.         :rtype: bool
  7.         """
  8.         # build a graph
  9.         pres = [[] for _ in range(numCourses)]  # p1: reference value, if pres = [[]] * numCourses
  10.         for pair in prerequisites:
  11.             pres[pair[0]].append(pair[1])
  12.         self.pres = pres
  13.         self.ddict = {}

  14.         # keep the visited node
  15.         v = [0] * numCourses
  16.         for i in range(numCourses):
  17.             if v[i] == 0:
  18.                 cur_v = []
  19.                 if not self.dfs(i, cur_v):
  20.                     return False
  21.                 else:
  22.                     for k in cur_v:
  23.                         v[k] = 1
  24.         return True

  25.     def dfs(self, i, cur_v):
  26.         if i in cur_v:
  27.             return False

  28.         cur_v.append(i)
  29.         for j in self.pres[i]:
  30.             tag = self.ddict[j] if j in self.ddict else self.dfs(j, cur_v)
  31.             self.ddict[j] = tag
  32.             if not tag:
  33.                 return False
  34.         cur_v.pop()  # p2: err to deal with the dead cycle

  35.         return True

  36.     # p3 Time Limited
复制代码

补充内容 (2018-10-8 13:24):
对代码进行了简单的分析: https://github.com/shenweihai1/a ... ster/code%20207.pdf
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-8 13:43:08 | 只看该作者
全局:
之前在判断parenthesis vaild的时候都是使用的堆栈但是其实可以直接用一个变量就可以解决,相关题目可以参考LeetCode 301
  1.     def isVaild(s):
  2.         cnt = 0
  3.         for i in s:
  4.             if i == '(': cnt += 1;
  5.             elif i == ')': cnt -= 1;
  6.             if cnt < 0: return False
  7.         return cnt == 0
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-8 14:42:33 | 只看该作者
全局:
做了一道543,easy题,使用树的高度的算法即可
  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None

  7. class Solution(object):
  8.     def diameterOfBinaryTree(self, root):
  9.         self.mmax = 0
  10.         self.cache = {}
  11.         self.loop(root)
  12.         return self.mmax
  13.         
  14.     def loop(self, root):
  15.         if not root: return
  16.         l, r = self.getHeightByNode(root.left), self.getHeightByNode(root.right)
  17.         self.mmax = self.mmax if self.mmax > l + r else l + r
  18.         self.loop(root.left)
  19.         self.loop(root.right)
  20.         
  21.     def getHeightByNode(self, root):
  22.         if not root: return 0
  23.         if root in self.cache:
  24.             return self.cache[root]
  25.         else:
  26.             l, r = self.getHeightByNode(root.left), self.getHeightByNode(root.right)
  27.             self.cache[root] = max(l, r) + 1
  28.             return self.cache[root]
  29.    
复制代码

回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-11 10:22:23 | 只看该作者
全局:
做了一题375,应该可以改写成DP,先用递归做了清晰明了
  1. import sys
  2. class Solution(object):
  3.         
  4.     def getMoneyAmount(self, n):
  5.         """
  6.         :type n: int
  7.         :rtype: int
  8.         """
  9.         return self.recursion(1, n)

  10.     def recursion(self, a, b):
  11.         # a, b the min and max number
  12.         if a >= b:
  13.             return 0
  14.         
  15.         mmin = sys.maxint
  16.         for i in range(a, b+1):
  17.             res = i + max(self.recursion(a, i-1), self.recursion(i+1, b))
  18.             mmin = mmin if mmin < res else res

  19.         return mmin
复制代码

补充内容 (2018-10-11 13:03):
用递归做的话要考虑重复调用的情况
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-12 08:12:28 | 只看该作者
全局:
一个同学的google oa的题目,题目想在限时的时间内想到最简单的方法并且提交成功并不容易, 思路其实很简单,题目如下。hhh没带电脑,在ipad上下载一个python ide编辑器,写代码一个一个字母的写真特么慢

  1. import sys
  2. import copy
  3. def func(stores, houses):
  4.     stores.sort()
  5.     ori_houses = copy.deepcopy(houses)
  6.     houses.sort()
  7.     s, h = 0, 0 # two pointers for each array
  8.     h_d={}
  9.     while h < len(houses) and s < len(stores):
  10.         c = stores[s] + 0.5 * (stores[s+1] - stores[s] if s+1 < len(stores) else sys.maxint)
  11.         while h < len(houses) and houses[h] < c:
  12.             h_d[houses[h]] = stores[s]
  13.             h += 1
  14.         s += 1
  15.     return [h_d[i] for i in ori_houses]
  16.    

  17. print func([4,18,9,23,12,5], [23,2,12,18,11,3,6,19])
复制代码

补充内容 (2018-10-12 08:14):
个人感觉现在限时的时间内把代码accepted

补充内容 (2018-10-12 08:15):
1. 代码绝对要够短,比如该题有不少方法去实现该问题但是我感觉代码量都不少,代码量只要一多就很难保证能在短时间内提交成功

补充内容 (2018-10-12 08:16):
2. 使用Python自带的库去完成一些代码,保证代码足够简短并且易读
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-14 10:45:54 | 只看该作者
全局:
刚才做了一下Leetcode 106期的比赛,还是时间掌控的不好,第一个easy 花了5分钟,第二个medium花了12分钟都还好,第三个medium居然花了47分钟才accpeted,最后一题直接没有时间做了,想了一下第那个三题还是思考的不够仔细,写的时候错了两个地方花了好一会儿才发现,而且还超时了,又回头看哪里可以优化,又花了10几分钟,等会仔细分析一下代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-14 10:46:53 | 只看该作者
全局:
922 easy题目,很简单,其实有其他优化办法,不过为了accpeted先用最简单的方法,可以不使用额外数组解决问题的

  1. class Solution(object):
  2.     def sortArrayByParityII(self, A):
  3.         """
  4.         :type A: List[int]
  5.         :rtype: List[int]
  6.         """
  7.         odd, even = [], []
  8.         for i in range(len(A)):
  9.             if A[i] % 2 == 0:
  10.                 even.append(A[i])
  11.             else:
  12.                 odd.append(A[i])
  13.         
  14.         return [even.pop() if i % 2 == 0 else odd.pop() for i in range(len(A))]
  15.         
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-14 10:48:35 | 只看该作者
全局:
921 这个medium题基本就是一个easy题,直接统计里面左右括号匹配以后最后剩余的个数即可

  1. class Solution(object):
  2.     def minAddToMakeValid(self, S):
  3.         """
  4.         :type S: str
  5.         :rtype: int
  6.         """
  7.         l = 0
  8.         r = 0
  9.         for i in S:
  10.             if i == "(":
  11.                 l += 1
  12.             elif i == ")":
  13.                 l -= 1
  14.             if l < 0:
  15.                 r += 1
  16.                 l = 0
  17.         
  18.         return l + r
  19.         
复制代码

补充内容 (2018-10-15 03:13):
https://github.com/shenweihai1/a ... master/code_921.pdf 921分析
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-14 10:53:00 | 只看该作者
全局:
923 这题其实也很简单,思考一共就花了几分钟,但我提交错了两次,整体想来:
1. 思考的时间不够,导致代码过长,代码过长就会容易出现各种问题
2. 读题不严谨,漏看了条件:return it modulo 10^9 + 7,导致错误提交了一次
3. Time Limited 了一次,这还好,一下子就看出来为啥time out了,直接改了
4. 递归exit的条件思考不够充分,也导致错误提交一次。对于递归来说尤其是exit条件尤其要注意很容易出错
该题花了40几分钟才结束战斗,还是太长了,按理半小时肯定能accepted的,警戒警戒

  1. import collections
  2. import math

  3. class Solution(object):
  4.     def __init__(self):
  5.         self.cache = {}

  6.     def threeSumMulti(self, A, target):
  7.         """
  8.         :type A: List[int]
  9.         :type target: int
  10.         :rtype: int
  11.         """
  12.         temp = collections.defaultdict(int)
  13.         for i in A:
  14.             temp[i] += 1
  15.         format_A = [(k, v) for k, v in temp.items()]
  16.         format_A = sorted(format_A, key=lambda k: k[0], reverse=True) # time limited

  17.         return self.recursion(0, 3, target, format_A)

  18.     def recursion(self, idx, times, target, format_A):
  19.         key = (idx, times, target)
  20.         if key in self.cache:
  21.             return self.cache[key]

  22.         if target < 0:
  23.             self.cache[key] = 0
  24.             return 0

  25.         if times == 0:
  26.             if target == 0:
  27.                 self.cache[key] = 1
  28.                 return 1
  29.             else:
  30.                 self.cache[key] = 0
  31.                 return 0

  32.         if idx == len(format_A):  # problem 1
  33.             self.cache[key] = 0
  34.             return 0

  35.         # 0
  36.         n0 = self.recursion(idx + 1, times, target, format_A)
  37.         # 1
  38.         n1 = format_A[idx][1] * self.recursion(idx + 1, times - 1, target - format_A[idx][0], format_A)
  39.         # 2
  40.         if format_A[idx][1] >= 2:
  41.             n2 = format_A[idx][1] * (format_A[idx][1] - 1) * 0.5 * self.recursion(idx + 1, times - 2,
  42.                                                                                   target - format_A[idx][0] * 2,
  43.                                                                                   format_A)
  44.         else:
  45.             n2 = 0
  46.         # 3
  47.         if format_A[idx][1] >= 3 and times == 3 and format_A[idx][0] * 3 == target:
  48.             n3 = format_A[idx][1] * (format_A[idx][1] - 1) * (format_A[idx][1] - 2) / 6
  49.         else:
  50.             n3 = 0
  51.         mx = int(n0 + n1 + n2 + n3)
  52.         self.cache[key] = mx
  53.         return mx % int(math.pow(10, 9) + 7)
复制代码

补充内容 (2018-10-15 03:13):
https://github.com/shenweihai1/a ... master/code_923.pdf 代码分析,可以使用Collections.Counter()
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-14 10:55:00 | 只看该作者
全局:
924 是一道hard题目,稍微读了一下题目,不算很明白题目的意思,而且只剩半小时时间了,就不做了,等会儿做一下,看起来不难
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表