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

开一贴刷题打卡

🔗
 楼主| tall_cool_13 2018-12-20 16:39:41 | 只看该作者
全局:
最大堆和最小堆的实现

  1. import heapq
  2. import sys


  3. # easy implementation of min-heap and max-heap
  4. class Heap(object):

  5.     def __init__(self, ttype=1):
  6.         # 0: min-heap, 1: max-heap
  7.         # support the array that contains numeric element
  8.         self.ttype = ttype
  9.         self.vals = []

  10.     def push(self, ele):
  11.         ele = sys.maxsize - ele if self.ttype == 1 else ele
  12.         heapq.heappush(self.vals, ele)

  13.     @property
  14.     def data(self):
  15.         return [sys.maxsize - i for i in self.vals] if self.ttype == 1 else self.vals

  16.     @property
  17.     def size(self):
  18.         return len(self.vals)

  19.     @property
  20.     def is_empty(self):
  21.         return len(self.vals) == 0


  22. if __name__ == "__main__":
  23.     # max-heap
  24.     obj = Heap()
  25.     arr = [1, 4, 2, 4, 0, -1, -2, -4, 11]
  26.     for i in arr:
  27.         obj.push(i)

  28.     print(obj.data)

  29.     # min-heap
  30.     obj = Heap(0)
  31.     arr = [1, 4, 2, 4, 0, -1, -2, -4, 11]
  32.     for i in arr:
  33.         obj.push(i)

  34.     print(obj.data)

复制代码

补充内容 (2018-12-20 16:39):
可以用于实现Find median

补充内容 (2018-12-23 00:29):
295
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-12-20 16:42:43 | 只看该作者
全局:
Find median的实现


补充内容 (2018-12-20 16:44):
时间复杂度, insert O(logn), find O(1)

补充内容 (2018-12-23 00:30):
Leetcode 295

补充内容 (2018-12-23 01:26):
if min.size > max.size, 分支应该是: val < min[0]
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-12-20 18:35:42 | 只看该作者
全局:
将一个数组切成两个subset,是的两个sum的difference最小,可以有两种解法,代码提供递归写法


  1. def min_difference(A):
  2.     return abs(2 * recursion(A, 0, sum(A) / 2) - sum(A))


  3. def recursion(A, idx, rest):
  4.     if idx == len(A) - 1:
  5.         return A[idx] if abs(A[idx] - rest) < abs(rest) else 0

  6.     l = A[idx] + recursion(A, idx + 1, rest - A[idx])
  7.     r = recursion(A, idx + 1, rest)
  8.     return r if abs(l - rest) > abs(r - rest) else l


  9. A = [1, 6, 11, 5, 2, 4, 2, 23, 4, 9, 32, 13]
  10. print(min_difference(A))
复制代码



补充内容 (2018-12-20 18:36):
如果让将一个数组分成两个相同的subset也是类似
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-12-20 20:26:50 | 只看该作者
全局:
看了一下树的非递归遍历
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-12-20 21:28:47 | 只看该作者
全局:
正则表达式,支持star and . , 直接使用递归即可


  1. class Solution(object):
  2.     def match(self, s, pattern):
  3.         # special case
  4.         if s == "":  # pattern: a*b*.*....
  5.             while len(pattern) >= 2 and pattern[1] == "*":
  6.                 pattern = pattern[2:]
  7.             return not pattern

  8.         if len(pattern) <= 1:
  9.             return len(s) == 1 and (pattern == s or pattern == '.')

  10.         # check if next character is star
  11.         if pattern[1] == "*":
  12.             if pattern[0] == '.' or s[0] == pattern[0]:
  13.                 if self.match(s[1:], pattern):
  14.                     return True
  15.             if self.match(s, pattern[2:]):
  16.                 return True
  17.         else:
  18.             if pattern[0] == '.' or pattern[0] == s[0]:
  19.                 if self.match(s[1:], pattern[1:]):
  20.                     return True

  21.         return False


  22. if __name__ == "__main__":
  23.     obj = Solution()
  24.     print(obj.match("aaab", "a*bb*"))
  25.     print(obj.match("aaab", "a*aaabb*"))
  26.     print(obj.match("aaab", "a*b*"))
  27.     print(obj.match("a.", ""))
  28.     print(obj.match("", ""))
  29.     print(obj.match("a.", "a."))
复制代码

补充内容 (2018-12-20 21:29):
理清楚思路就可以很快写出来

补充内容 (2018-12-20 21:30):
使用递归,不然答案可能会比较长

补充内容 (2018-12-23 00:20):
Leetcode 10
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-12-20 22:21:54 | 只看该作者
全局:
找出一个数组中过半的元素
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-12-20 22:51:24 | 只看该作者
全局:
硬币拆分问题,使用DP解决
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-12-20 23:17:54 | 只看该作者
全局:
数字从1-n出现的1的个数


补充内容 (2018-12-20 23:19):
之前做的时候没有从这个角度去思考
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-12-21 19:36:23 | 只看该作者
全局:
Pow(x, n), 使用递归,折半来做
  1. class Solution(object):
  2.     def myPow(self, x, n):
  3.         """
  4.         :type x: float
  5.         :type n: int
  6.         :rtype: float
  7.         """
  8.         if abs(n) == 1: return x if n == 1 else 1 / x
  9.         if n == 0: return 1
  10.         return self.myPow(x * x, n//2) if n % 2 == 0 else x * self.myPow(x * x, (n-1)//2)
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-12-21 19:39:25 | 只看该作者
全局:
Leetcode 535
  1. class Codec:
  2.     def __init__(self):
  3.         self.kv = {}
  4.         
  5.     def encode(self, longUrl):
  6.         """Encodes a URL to a shortened URL.
  7.         
  8.         :type longUrl: str
  9.         :rtype: str
  10.         """
  11.         import hashlib
  12.         m = hashlib.md5()
  13.         m.update(longUrl)
  14.         eUrl = m.hexdigest()
  15.         self.kv[eUrl] = longUrl
  16.         return eUrl
  17.         

  18.     def decode(self, shortUrl):
  19.         """Decodes a shortened URL to its original URL.
  20.         
  21.         :type shortUrl: str
  22.         :rtype: str
  23.         """
  24.         return self.kv[shortUrl]

  25. # md5() is asymmetric encryption
复制代码
回复

使用道具 举报

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

本版积分规则

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