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

开一贴刷题打卡

🔗
 楼主| tall_cool_13 2018-9-28 02:24:37 | 只看该作者
全局:
Leetcode 102 比较简单,使用两个队列模拟每个层
  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 levelOrder(self, root):
  9.         """
  10.         :type root: TreeNode
  11.         :rtype: List[List[int]]
  12.         """
  13.         res = []
  14.         if root == None:
  15.             return res
  16.         
  17.         # using two queue
  18.         res = []
  19.         a, b = [root], []
  20.         
  21.         while len(a) != 0:
  22.             cur_level = []
  23.             while len(a) > 0:
  24.                 pop_node = a.pop(0)
  25.                 if pop_node.left:
  26.                     b.append(pop_node.left)
  27.                 if pop_node.right:
  28.                     b.append(pop_node.right)
  29.                 cur_level.append(pop_node.val)
  30.             res.append(cur_level)
  31.             
  32.             t = a
  33.             a = b
  34.             b = t
  35.             
  36.         return res
  37.             
  38.             
  39.             
  40.             
  41.             
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 02:31:13 | 只看该作者
全局:
Leetcode 20比较简单,直接上代码了
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 02:31:39 | 只看该作者
全局:
tall_cool_13 发表于 2018-9-28 02:31
Leetcode 20比较简单,直接上代码了
  1. class Solution(object):
  2.     def isValid(self, s):
  3.         """
  4.         :type s: str
  5.         :rtype: bool
  6.         """
  7.         # using a stack to simulate
  8.         sstack = []
  9.         for c in s:
  10.             if c in ["(", "[", "{"]:
  11.                 sstack.append(c)
  12.             elif c in [")", "]", "}"]:
  13.                 cur = "" if len(sstack) == 0 else sstack.pop()
  14.                 if (c == ")" and cur == "(") or (c == "]" and cur == "[") or (c == "}" and cur == "{"):
  15.                     pass
  16.                 else:
  17.                     return False
  18.             else:
  19.                 pass
  20.         
  21.         return len(sstack) == 0
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 03:39:54 | 只看该作者
全局:
Leetcode 49也比较简单虽然是medium题目
  1. class Solution(object):
  2.     def groupAnagrams(self, strs):
  3.         """
  4.         :type strs: List[str]
  5.         :rtype: List[List[str]]
  6.         """
  7.         if len(strs) == 0:
  8.             return []
  9.         
  10.         res = []
  11.         for sstr in strs:
  12.             res.append((sstr, "".join(sorted([c for c in sstr]))))
  13.         
  14.         res = sorted(res, key=lambda x: x[1])
  15.         
  16.         v = []
  17.         level = []
  18.         cur = ""
  19.         for sstr, sorted_str in res:
  20.             if sorted_str != cur:
  21.                 if len(level) > 0:
  22.                     v.append(level)
  23.                 level = [sstr]
  24.             else:
  25.                 level.append(sstr)
  26.             cur = sorted_str
  27.         v.append(level)
  28.         
  29.         return v
  30.             
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 03:46:42 | 只看该作者
全局:
这两天计划:
1. 基数排序
2. Leetcode  910题
3. 重新思考一下https://www.youtube.com/watch?v=YCD_iYxyXoo&feature=youtu.be
4. 三色问题
5. Leetcode 236, Leetcode 23, Leetcode 88, Leetcode 13, Leetcode 79思路简单,写一下实现
6. 统计二进制1的个数,负数情况, https://www.cnblogs.com/cotyb/archive/2016/02/11/5186461.html
7. 重新再看一下为啥Time Limited: https://leetcode.com/problems/sum-of-subarray-minimums/description/
8. Leetcode 17 使用BFS做一下
9. 做两道Design 题目, Leetcode 146
10. https://leetcode.com/problems/clone-graph/description/ 如何快速读题
11. 二分法题目


补充内容 (2018-9-30 01:12):
https://raw.githubusercontent.co ... r/radix_sorting.png Radix sorting

补充内容 (2018-9-30 02:24):
三色问题:https://github.com/shenweihai1/a ... tional-flag-problem

补充内容 (2018-9-30 04:06):
Leetcode 79比较简单,每次假设每个元素为word的第一个元素,然后依次就行dfs检测就可以。我开始感觉这个思路是不是复杂度太高了,然后网上查了查也没有其他更好的办法了

补充内容 (2018-9-30 04:43):
统计1的个数还是用第三方库比较好,负数的情况使用的补码, https://github.com/shenweihai1/algorithms/wiki/the-number-of-1's

补充内容 (2018-9-30 06:02):
奇怪再写一次就不超时, Leetcode 907

补充内容 (2018-9-30 06:16):
Leetcode 17的确应该用dfs,并不是所有情况都通用的

补充内容 (2018-9-30 06:21):
之前最讨厌读长题目,花时间读清楚题目再动笔是最重要的

补充内容 (2018-9-30 06:43):
在做二分的时候我之前一直默认low 不可以大于high,但是他是可以的!!!
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-30 01:43:26 | 只看该作者
全局:
Leetcode 621:
  1. class Solution(object):
  2.     def leastInterval(self, tasks, n):
  3.         """
  4.         :type tasks: List[str]
  5.         :type n: int
  6.         :rtype: int
  7.         """
  8.         nums = [0] * 26
  9.         for l in tasks:
  10.             nums[ord(l) - ord("A")] += 1
  11.         
  12.         mmax_size = 0
  13.         for j in nums:
  14.             mmax_size = mmax_size if mmax_size > j else j
  15.         
  16.         p = 0
  17.         for j in nums:
  18.             p += (1 if j == mmax_size else 0)
  19.             
  20.         return max(len(tasks), (n+1) * (mmax_size-1) + p)
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-30 02:18:09 | 只看该作者
全局:
三色问题
  1. class Solution(object):
  2.     def sortColors(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: void Do not return anything, modify nums in-place instead.
  6.         """
  7.         if len(nums) <= 1:
  8.             #return nums
  9.             return None
  10.         
  11.         low, mid, high = 0, 0, len(nums) - 1
  12.         while mid <= high:
  13.             if nums[mid] == 0:
  14.                 self.swap(nums, low, mid)
  15.                 mid += 1
  16.                 low += 1
  17.             elif nums[mid] == 1:
  18.                 mid += 1
  19.             else: # nums[mid] == 2
  20.                 self.swap(nums, mid, high)
  21.                 high -= 1
  22.             
  23.         # return nums
  24.    
  25.     def swap(self, nums, s, e):
  26.         v = nums[s]
  27.         nums[s] = nums[e]
  28.         nums[e] = v
  29.             
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-30 06:43:35 | 只看该作者
全局:
tall_cool_13 发表于 2018-9-28 03:46
这两天计划:
1. 基数排序
2. Leetcode  910题
  1. def index_equals_value_search(arr):
  2.   return get_bi_divide(arr, 0, len(arr) - 1)


  3. def get_bi_divide(arr, low, high):
  4.   if low > high: # it is possbile!
  5.     return -1

  6.   if high == low:
  7.     if arr[high] == high:
  8.       return high
  9.     else:
  10.       return -1

  11.   mid = int((low + high)/2)  # cast int
  12.   if arr[mid] > mid:
  13.     return get_bi_divide(arr, low, mid-1)
  14.   elif arr[mid] == mid:
  15.     return mid
  16.   else: # arr[mid] < mid
  17.     return get_bi_divide(arr, mid+1, high)

  18. if __name__ == "__main__":
  19.   print index_equals_value_search([-8,1,2,5])
  20.   print index_equals_value_search([-1,0,3,6])
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-2 14:37:16 | 只看该作者
全局:
做了一个236递归简洁
  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 lowestCommonAncestor(self, root, p, q):
  9.         """
  10.         :type root: TreeNode
  11.         :type p: TreeNode
  12.         :type q: TreeNode
  13.         :rtype: TreeNode
  14.         """
  15.         if root == None:
  16.             return None
  17.         
  18.         if root == p or root == q:
  19.             return root
  20.         
  21.         l = self.lowestCommonAncestor(root.left, p, q)
  22.         r = self.lowestCommonAncestor(root.right, p, q)

  23.         if l and r:
  24.             return root
  25.         
  26.         if l:
  27.             return l
  28.         elif r:
  29.             return r
  30.         else:
  31.             return None
  32.         
  33.         
  34.         
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-2 14:41:07 | 只看该作者
全局:
236思路
回复

使用道具 举报

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

本版积分规则

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