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

开一贴刷题打卡

🔗
 楼主| tall_cool_13 2018-9-28 00:06:08 | 只看该作者
全局:
做了一道非排序2-sum题目,先排序再首尾指针
  1. class Solution(object):
  2.     def twoSum(self, nums, target):
  3.         """
  4.         :type nums: List[int]
  5.         :type target: int
  6.         :rtype: List[int]
  7.         """
  8.         if len(nums) == 0:
  9.             return []
  10.         
  11.         nums = [(num, idx) for idx, num in enumerate(nums)]
  12.         nums = sorted(nums, key=lambda x: x[0])
  13.         
  14.         i = 0
  15.         j = len(nums) - 1
  16.         while i < j:
  17.             if nums[i][0] + nums[j][0] > target:
  18.                 j -= 1
  19.             elif nums[i][0] + nums[j][0] < target:
  20.                 i += 1
  21.             else:
  22.                 return [nums[i][1], nums[j][1]]
  23.         
  24.         return []
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 00:08:46 | 只看该作者
全局:
Leetcode 75. Sort Colors 荷兰三色旗问题, 已经做过不再做
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 00:35:08 | 只看该作者
全局:
一道简单的DP,题目,Leetcode 238
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 01:08:10 | 只看该作者
全局:
Leetcode 139 word break,直接递归求解即可,没有任何稍微复杂一点的逻辑


等会准备写一下 https://leetcode.com/problems/merge-sorted-array/description/,这虽然是一道easy题目,但是想一次性写对还是不容易的
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 01:19:59 | 只看该作者
全局:
做了一下78题,虽然medium不过难度就easy,代码也不复杂
  1. class Solution(object):
  2.     def subsets(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: List[List[int]]
  6.         """
  7.         if len(nums) == 0:
  8.             return []
  9.         
  10.         self.results = []
  11.         
  12.         self.recursion_subsets(nums, 0, [0] * len(nums))
  13.         return self.results
  14.    
  15.     def recursion_subsets(self, nums, idx, indices):
  16.         if idx == len(nums):
  17.             self.results.append([nums[i] for i, v in enumerate(indices) if v == 1])
  18.         else:
  19.             for i in [0, 1]:
  20.                 cur = indices[idx]
  21.                 indices[idx] = i
  22.                 self.recursion_subsets(nums, idx + 1, indices)
  23.                 indices[idx] = cur
  24.         
复制代码

补充内容 (2018-10-23 08:46):
https://leetcode.com/problems/subsets/
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 01:23:04 | 只看该作者
全局:
tall_cool_13 发表于 2018-9-28 01:19
做了一下78题,虽然medium不过难度就easy,代码也不复杂
[mw_shl_code=python,true]class Solution(object ...

其实就是一种全排序,每个位置上面可以放0或者1, 比如: [1 2], 其实就是对应的: [0, 0,], [0, 1], [1, 0], [1, 1]四种可能。还有一种写法比如: [1, 2, 3], 那么就直接遍历数字 0 -> 7, 然后计算出这个数字的二进制是啥样子, 2进制位为0就对应位置不输出, 为1则输出对应位置
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 01:40:58 | 只看该作者
全局:
Leetcode 98,比较简单,直接递归判断就行了
  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 isValidBST(self, root):
  9.         """
  10.         :type root: TreeNode
  11.         :rtype: bool
  12.         """        
  13.         if root == None:
  14.             return True
  15.         
  16.         # find the right's min, left's max
  17.         l, r = True, True
  18.         if root.right:
  19.             r = root.val < self.find_min(root.right) and self.isValidBST(root.right)
  20.             
  21.         if root.left:
  22.             l = root.val > self.find_max(root.left) and self.isValidBST(root.left)
  23.         
  24.         return l and r
  25.             
  26.     def find_min(self, root):
  27.         mmin = root.val
  28.         while root.left:
  29.             mmin = root.left.val
  30.             root = root.left
  31.         return mmin
  32.    
  33.     def find_max(self, root):
  34.         mmax = root.val
  35.         while root.right:
  36.             mmax = root.right.val
  37.             root = root.right
  38.         return mmax
  39.             
  40.             
复制代码

补充内容 (2018-9-28 01:42):
对一个节点来说,除了左右子树都是BST以外,左子树的最大值必须小于当前值,右子树的最小值必须大于当前值

补充内容 (2018-9-28 01:44):
一个优化方案,对find_min和find_max中涉及到的所有节点可以直接保存到hashmap中避免重复计算

补充内容 (2018-10-23 08:47):
https://leetcode.com/problems/validate-binary-search-tree/
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 02:01:41 | 只看该作者
全局:
206 递归比较容易做,思路很清晰,直接上代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 02:01:57 | 只看该作者
全局:
tall_cool_13 发表于 2018-9-28 02:01
206 递归比较容易做,思路很清晰,直接上代码
  1. # Definition for singly-linked list.
  2. # class ListNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None

  6. class Solution(object):
  7.     def reverseList(self, head):
  8.         """
  9.         :type head: ListNode
  10.         :rtype: ListNode
  11.         """
  12.         if head == None or head.next == None:
  13.             return head
  14.         
  15.         # recursion is a easy case
  16.         head, _ = self.reverse_recursion(head)
  17.         return head
  18.    
  19.     def reverse_recursion(self, head):
  20.         if head.next == None:
  21.             return head, head
  22.         
  23.         cur = head
  24.         head, tail = self.reverse_recursion(head.next)
  25.         tail.next = cur
  26.         cur.next = None
  27.         return head, cur
  28.    
复制代码

补充内容 (2018-10-23 08:48):
https://leetcode.com/problems/reverse-linked-list/
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-28 02:10:20 | 只看该作者
全局:
[quote]tall_cool_13 发表于 2018-9-28 02:01
  1. # Definition for singly-linked list.
  2. # class ListNode(object):
  3. #     de ...[/quote]
  4. 无递归版本,使用三个指针
  5. [code]def reverse_no(self, head):
  6.         if head == None or head.next == None:
  7.             return head
  8.         
  9.         cur = head
  10.         nnext = head.next
  11.         while nnext != None:
  12.             cur.next = nnext.next
  13.             nnext.next = head
  14.             head = nnext
  15.             nnext = cur.next
  16.             
  17.         return head
复制代码
回复

使用道具 举报

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

本版积分规则

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