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

开一贴刷题打卡

🔗
 楼主| tall_cool_13 2018-10-21 07:27:48 | 只看该作者
全局:
KMP 算法, 面试的时候坚决不写,太容易写出错了

  1. # KMP algorithm
  2. def kmp(txt, pat):
  3.     lps = [0]  # first one assigned to zero
  4.     cur, i = 0, 1
  5.     while i < len(pat):
  6.         if pat[i] == pat[cur]:
  7.             lps.append(cur + 1)
  8.             cur += 1
  9.         else:
  10.             while cur > 0:
  11.                 if pat[i] == pat[cur]:
  12.                     lps.append(cur + 1)
  13.                     cur += 1
  14.                     break
  15.                 else:
  16.                     cur = lps[cur - 1]
  17.             if cur == 0:
  18.                 if pat[i] == pat[0]:
  19.                     cur += 1
  20.                     lps.append(1)
  21.                 else:
  22.                     lps.append(0)
  23.         i = i + 1
  24.     # using lps to skip the match
  25.     i, j = 0, 0  # for the index for pat
  26.     while i < len(txt):
  27.         while j < len(pat) and i < len(txt):
  28.             if pat[j] == txt[i]:
  29.                 j += 1
  30.                 i += 1
  31.             else:
  32.                 break

  33.         if j == len(pat):  # match
  34.             return i - j

  35.         if j < len(pat):  # do not match
  36.             j = lps[j - 1] if j > 0 else 0
  37.             i += 1

  38.     return -1


  39. print kmp("MMMMAAABAAAxxxjx", "AAABAAA")
  40. print kmp("AAABAAAxxxjx", "AAABAAA")
  41. print kmp("MMMAAABAAA", "AAABAAA")
  42. print kmp("AAABAxxxjx", "AAABAAA")
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-25 07:46:36 | 只看该作者
全局:
做了一题Lt 528
  1. class Solution(object):

  2.     def __init__(self, w):
  3.         """
  4.         :type w: List[int]
  5.         """
  6.         cnt = 0
  7.         ans = []
  8.         for i in w:
  9.             ans.append(i + cnt)
  10.             cnt += i
  11.         self.ans = ans
  12.         

  13.     def pickIndex(self):
  14.         """
  15.         :rtype: int
  16.         """
  17.         import random, bisect
  18.         n = random.randint(1,  self.ans[-1])  # a <= N <= b
  19.         return bisect.bisect_left(self.ans, n)
复制代码

回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-25 08:24:50 | 只看该作者
全局:
337 重写了一把,避免重复递归
  1. class Solution(object):   
  2.     def rob(self, root):
  3.         """
  4.         :type root: TreeNode
  5.         :rtype: int
  6.         """
  7.         if not root:
  8.             return 0
  9.         
  10.         return max(self.dfs(root))
  11.    
  12.     def dfs(self, root):
  13.         if not root:
  14.             return 0, 0

  15.         ll, lr = self.dfs(root.left)
  16.         rl, rr = self.dfs(root.right)
  17.         return root.val + lr + rr, max(ll + rl, ll + rr, lr + rl, lr + rr)
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-25 11:31:28 | 只看该作者
全局:
优化了一下907, 使用单调堆栈来做


  1. class Solution(object):
  2.     def sumSubarrayMins(self, A):
  3.         """
  4.         :type A: List[int]
  5.         :rtype: int
  6.         """
  7.         left = [0] * len(A)
  8.         right = [0] * len(A)
  9.         stack = []
  10.         for idx, num in enumerate(A):
  11.             while stack and stack[-1][0] > num:
  12.                 stack.pop()
  13.             left[idx] = idx - stack[-1][1] - 1 if stack else idx
  14.             stack.append((A[idx], idx))

  15.         stack = []
  16.         B = A[::-1]
  17.         for idx, num in enumerate(B):
  18.             while stack and stack[-1][0] >= num:
  19.                 stack.pop()
  20.             right[idx] = idx - stack[-1][1] - 1 if stack else idx
  21.             stack.append((B[idx], idx))
  22.         right = right[::-1]

  23.         dp = 0
  24.         for l, r, num in zip(left, right, A):
  25.             dp += num * (l * r + l + r + 1)
  26.         return dp % (10 ** 9 + 7)
复制代码

补充内容 (2018-10-25 11:35):
对于A[i],求出从i-1开始连续大于A[i]的个数记做l, 从i+1开始连续大于等于A[i]的个数记做r, 则所有子数组中A[i]作为最小值得个数为 (l * r + l + r + 1)
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-25 13:26:50 | 只看该作者
全局:
写了一下3sum,优化的地方: 对输入数组进行了一次trim,因为对于输入数组来说同一个数字出现三次以上和只出现3次效果是一抹一样的
  1. import collections
  2. class Solution(object):
  3.     def threeSum(self, nums):
  4.         dnums = collections.defaultdict(int)
  5.         for num in nums:
  6.             dnums[num] += 1

  7.         nnums = []
  8.         for k, v in dnums.items():
  9.             for _ in range(3 if v >= 3 else v):
  10.                 nnums.append(k)

  11.         nnums = sorted(nnums)

  12.         # find all solutions
  13.         ans = []
  14.         for i in range(len(nnums) - 1):
  15.             s, e = i + 1, len(nnums) - 1
  16.             while s < e:
  17.                 if nnums[s] + nnums[e] == -nnums[i]:
  18.                     ans.append((nnums[i], nnums[s], nnums[e]))
  19.                     s += 1
  20.                     e -= 1
  21.                 elif nnums[s] + nnums[e] > -nnums[i]:
  22.                     e -= 1
  23.                 else:
  24.                     s += 1
  25.         return list(set(ans))
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-26 01:14:09 | 只看该作者
全局:
重写了一下923,没有使用递归,利用了2sum的性质是效率提高
  1. import collections


  2. class Solution(object):
  3.     def get_cnt(self, m, n):
  4.         return m if n == 1 else (m * (m - 1) / 2 if n == 2 else m * (m - 1) * (m - 2) / 6)

  5.     def threeSumMulti(self, A, target):
  6.         dnums = collections.Counter(A)
  7.         nnums = []
  8.         for k, v in dnums.items():
  9.             for _ in range(3 if v >= 3 else v):
  10.                 nnums.append(k)

  11.         nnums = sorted(nnums)
  12.         # find all solutions
  13.         ans = []
  14.         for i in range(len(nnums) - 1):
  15.             s, e = i + 1, len(nnums) - 1
  16.             while s < e:
  17.                 if nnums[s] + nnums[e] == target - nnums[i]:
  18.                     ans.append((nnums[i], nnums[s], nnums[e]))
  19.                     s, e = s + 1, e - 1
  20.                 elif nnums[s] + nnums[e] > target - nnums[i]:
  21.                     e -= 1
  22.                 else:
  23.                     s += 1

  24.         # calculate nsetlist
  25.         r = 0
  26.         for l in list(set(ans)):
  27.             c = 1
  28.             for k, v in collections.Counter(l).items():
  29.                 c *= self.get_cnt(dnums[k], v)
  30.             r += c
  31.         return r % (10 ** 9 + 7)
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-26 09:18:42 | 只看该作者
全局:
Leetcode 926

  1. import sys
  2. class Solution(object):
  3.     def minFlipsMonoIncr(self, A):
  4.         """
  5.         :type S: str
  6.         :rtype: int
  7.         """
  8.         if not A:
  9.             return 0
  10.         left, right, cnt = [], [], 0
  11.         for c in A:
  12.             left.append(cnt)
  13.             if c == '1': cnt += 1

  14.         cnt = 0
  15.         for c in A[::-1]:
  16.             right.append(cnt)
  17.             if c == '0': cnt += 1
  18.         right = right[::-1]

  19.         ans = sys.maxint
  20.         for l, r, c in zip(left, right, A):
  21.             mmin = l + r + (1 if c == '0' else 0)
  22.             ans = min(mmin, ans)

  23.         return min(len([c for c in A if c == '1']), ans)
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-26 09:44:04 | 只看该作者
全局:
写了一下快排,用python写很容易
  1. def QuickSort(A):
  2.     if len(A) <= 1:
  3.         return A

  4.     base = A[0]
  5.     left, right = [], []
  6.     for i in range(1, len(A)):
  7.         (left if A[i] <= base else right).append(A[i])
  8.     return QuickSort(left) + [base] + QuickSort(right)
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-26 10:12:04 | 只看该作者
全局:
总结了一下最近在写Leetcode的时候,python的一些使用小技巧
  1. # sort two columns by flashbacks
  2. ans = [(1, 2), (1, 1), (-1, 2)]
  3. ans = sorted(ans, key=lambda x: (-x[1], -x[0]))
  4. print ans
  5. # [(1, 2), (-1, 2), (1, 1)]

  6. # total sorting
  7. from itertools import permutations
  8. mc = [1, 2, 3]
  9. print list(permutations(mc))
  10. # [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

  11. from itertools import combatations
  12. mc = [1, 2, 3]
  13. print sum([(list(combinations(input, i))) for i in range(len(input) + 1)], [])
  14. # [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

  15. print sum([[1, 2, 3], [2, 3, 4]], [])
  16. # [1, 2, 3, 2, 3, 4]

  17. import random
  18. print random.randint(1, 3) # a <= N <= b
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-26 10:12:31 | 只看该作者
全局:
继上面
  1. import bisect
  2. ac = [1, 1, 2, 3]
  3. # 遇到相同选最左边
  4. # 遇到相同数字插在该数字的左边
  5. print bisect.bisect_left(ac, 2.9)  # 3
  6. print bisect.bisect_left(ac, 3) # 3
  7. print bisect.bisect_left(ac, 3.1) # 4
  8. print bisect.bisect_left(ac, 0.9)  # 0
  9. print bisect.bisect_left(ac, 1) # 0
  10. print bisect.bisect_left(ac, 1.1) # 2

  11. from collections import Counter
  12. a = [1, 2, 3, 1, 1, 2]
  13. print Counter(a) # Counter({1: 3, 2: 2, 3: 1})

  14. # exchage two numbers
  15. a, b = b, a

  16. # using xrange to replace range

  17. # 推导式
  18. a = [1, 2, 3]
  19. b = [2, 3, 4]
  20. print [(i, j) for i in a for j in b if i > 1 and j > 2]  # [(2, 3), (2, 4), (3, 3), (3, 4)]

  21. # find the most frequent element
  22. A = [1,2,3,4,2,2,3,1,4,4,4]
  23. print max(set(test), key=A.count) # count if the function

  24. # map
  25. ac = [(1, 2), [2, 3]]
  26. print map(list, ac)  # [[1, 2], [2, 3]]
  27. print map(lambda x: x[1], ac) # [2, 3]

  28. # filter
  29. ac = xrange(-5, 5)
  30. print filter(lambda x: x >= 0, ac)  # [0, 1, 2, 3, 4]

  31. ac = [1, 2, 3]
  32. bc = [2, 3, 4]
  33. print dict(zip(ac, bc))  # {1: 2, 2: 3, 3: 4}

  34. # 列表展开
  35. A = [[1, 2], [3, 4], [5, 6]]
  36. print sum(A, [])
  37. print [c for l in A for c in l if c > 1]

  38. # using lambda
  39. pow = lambda x: x ** 2
  40. print pow(8) # 64

  41. # 操作集合
  42. A = {1, 2, 3}
  43. B = {3, 4, 5}
  44. print A | B  # set([1, 2, 3, 4, 5])
  45. print A & B  # set([3])
  46. print A - B  # set([1, 2])
  47. print B - A  # set([4, 5])

  48. # 操作计数
  49. A = collections.Counter([1, 2, 2])
  50. B = collections.Counter([1, 2, 2, 4, 5, 2, 4])
  51. # cnt <= 0 直接会去除
  52. print A + B  # Counter({2: 5, 1: 2, 4: 2, 5: 1})
  53. print B - A  # Counter({4: 2, 2: 1, 5: 1})

  54. # 比较重要的一个, 排序字典
  55. A = dict(("%s" % x, x) for x in range(5))
  56. print A # {'1': 'v', '0': 'v', '3': 'v', '2': 'v', '4': 'v'}
  57. A = collections.OrderedDict(("%s" % x, "v") for x in range(10))
  58. print A # OrderedDict([('0', 'v'), ('1', 'v'), ('2', 'v'), ('3', 'v'), ('4', 'v')])
复制代码

补充内容 (2018-10-26 10:13):
https://github.com/shenweihai1/algorithms/wiki/notes-for-python
回复

使用道具 举报

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

本版积分规则

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