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

开一贴刷题打卡

🔗
 楼主| tall_cool_13 2018-9-25 12:14:34 | 只看该作者
全局:
907 做了一下简单倒是简单但是居然超时了,明显不是最优解,让宝宝再想想

  1. class Solution(object):
  2.     def sumSubarrayMins(self, A):
  3.         """
  4.         :type A: List[int]
  5.         :rtype: int
  6.         """
  7.         if len(A) == 0:
  8.             return 0
  9.         
  10.         dp = [A[0]]
  11.         for idx in range(1, len(A)):
  12.             cur_min = A[idx]
  13.             loop_sum = A[idx]
  14.             for c_idx in range(idx - 1, -1, -1):
  15.                 if cur_min > A[c_idx]:
  16.                     cur_min = A[c_idx]
  17.                 loop_sum += cur_min
  18.             dp.append(dp[idx -1] + loop_sum)
  19.         
  20.         return dp[-1] % (pow(10,9) + 7)
  21.         
  22.         
  23.         
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-25 14:23:13 | 只看该作者
全局:
宝宝真是蛋疼了,参加了一个网络mock interview。面试者一个简单的bst题目都不会,用了40分钟最后还写得不知道啥东西,最后居然还评价我说话太多不是一个好的interviewer,不能忍。蛋疼,为了做interviewer这easy题我都来回写了多遍。面试者自己写的不对,思路不对,不想好就写,我都说过好多次你要换个思路,给hint听也不听,你如果能写的稍微好一点我会说话么,让你停一下,不要着急写代码,先解释一下思路,说等你写完,你写得完么,蛋疼。还评价面试我的题目10行就能解决,非写30行。把自己能的,你行你上啊,代码的可读性不要了。我好歹解释完思路,然后直接按思路写完,跑通了所有的例子才花了20分钟。你40分钟连思路都没理顺。真受不了傻*,气死宝宝了
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-25 14:24:36 | 只看该作者
全局:
tall_cool_13 发表于 2018-9-25 14:23
宝宝真是蛋疼了,参加了一个网络mock interview。面试者一个简单的bst题目都不会,用了40分钟最后还写得不 ...

Given a sorted array arr of distinct integers, write a function indexEqualsValueSearch that returns the lowest index i for which arr[i] == i. Return -1 if there is no such index. Analyze the time and space complexities of your solution and explain its correctness. 题目, 我的答案,把他能的
  1. def get_bi_divide(arr, low, high):
  2.   if high == low:
  3.     if arr[high] == high:
  4.       return high
  5.     else:
  6.       return -1
  7.    
  8.   if high - low == 1:
  9.     if arr[high] == high:
  10.       return high
  11.       
  12.     if arr[low] == low:
  13.       return low
  14.      
  15.     return -1
  16.   
  17.   mid = int((low + high)/2)  # cast int
  18.   if arr[mid] > mid:
  19.     return get_bi_divide(arr, low, mid)
  20.   elif arr[mid] == mid:
  21.     return mid
  22.   else: # arr[mid] < mid
  23.     return get_bi_divide(arr, mid, high)
  24.   
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-25 15:19:30 | 只看该作者
全局:
leetcode 128没啥好说的比较简单, 通过+1, -1 尝试数字是否在数组中
https://leetcode.com/problems/longest-consecutive-sequence/description/
  1. class Solution(object):
  2.     def longestConsecutive(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: int
  6.         """
  7.         if len(nums) == 0:
  8.             return 0
  9.         
  10.         e = []
  11.         m_length = 1
  12.         for num in nums:
  13.             if num in e:
  14.                 continue
  15.                
  16.             e.append(num)
  17.             cur_m_length = 1
  18.             
  19.             temp = num
  20.             while temp - 1 in nums:
  21.                 cur_m_length += 1
  22.                 temp = temp - 1
  23.                 e.append(temp)
  24.             
  25.             temp = num
  26.             while temp + 1 in nums:
  27.                 cur_m_length += 1
  28.                 temp = temp + 1
  29.                 e.append(temp)
  30.             
  31.             m_length = m_length if m_length > cur_m_length else cur_m_length
  32.         
  33.         return m_length
  34.                
  35.             
复制代码

补充内容 (2018-10-23 08:33):
m_length if m_length > cur_m_length else cur_m_length => max(m_length, cur_m_length)
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-25 15:20:12 | 只看该作者
全局:
tall_cool_13 发表于 2018-9-25 15:19
leetcode 128没啥好说的比较简单, 通过+1, -1 尝试数字是否在数组中
https://leetcode.com/problems/longe ...

python 的操作 element in array is O(1)时间复杂度
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-25 16:01:36 | 只看该作者
全局:
搞了一道Leetcode 7简单题
  1. class Solution(object):
  2.     def reverse(self, x):
  3.         """
  4.         :type x: int
  5.         :rtype: int
  6.         """
  7.         if x == 0:
  8.             return 0
  9.         
  10.         x = "{num}".format(num=x)
  11.         
  12.         res = ""
  13.         for idx in range(len(x) - 1, -1, -1):
  14.             res += x[idx]
  15.         
  16.         v = 0
  17.         if "-" in res:
  18.             res = res.replace("-", "")
  19.             v = -1 * int(res)
  20.         else:
  21.             v = int(res)
  22.         
  23.         return 0 if v > pow(2, 31) or v < -1 * pow(2, 31) else v
  24.             
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-25 16:17:57 | 只看该作者
全局:
3-sum 求和又是超时,明天再看
  1. class Solution(object):
  2.     def threeSum(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: List[List[int]]
  6.         """
  7.         nums = sorted(nums)
  8.         
  9.         res = []
  10.         for idx, num in enumerate(nums):
  11.             if idx + 2 < len(nums):
  12.                 cur_pos = self.get_result_by_2sum(-1 * nums[idx], idx + 1, len(nums) - 1, nums)
  13.                 for v in cur_pos:
  14.                     res.append((nums[idx], v[0], v[1]))
  15.         
  16.         return list(set(res))
  17.    
  18.     def get_result_by_2sum(self, ssum, low, high, nums):
  19.         res = []
  20.         while low < high:
  21.             if nums[low] + nums[high] == ssum:
  22.                 res.append([nums[low], nums[high]])
  23.                 low += 1
  24.                 high -= 1
  25.             elif nums[low] + nums[high] > ssum:
  26.                 high -= 1
  27.             else:
  28.                 low += 1
  29.         return res
复制代码

补充内容 (2018-9-26 12:59):
查了一下其他人的做法,time complexity 都是O(n^2),用c++同样的写法就可以过。python果然哎
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-9-26 01:32:28 | 只看该作者
全局:
leetcode 516 字符串回文问题,写了两种方法都超时不可思议的说, DP 从上到下递推,或者从下到上递推

  1. class Solution(object):

  2.     def longestPalindromeSubseq(self, s):
  3.         """
  4.         :type s: str
  5.         :rtype: int
  6.         """
  7.         # return self.get_by_recursion(s, 0, len(s) - 1)

  8.         # from down to up
  9.         dp = {}

  10.         for step in range(0, len(s)):
  11.             for n in range(0, len(s) - step):
  12.                 i = n
  13.                 j = n + step
  14.                 print i, j
  15.                 if i == j:
  16.                     dp[(i, j)] = 1
  17.                 elif j - i == 1:
  18.                     dp[(i, j)] = 2 if s[i] == s[j] else 1
  19.                 else:
  20.                     if s[i] == s[j]:
  21.                         dp[(i, j)] = dp[(i + 1, j - 1)] + 2
  22.                     else:
  23.                         dp[(i, j)] = max(dp[(i, j - 1)], dp[(i + 1, j)])
  24.         return dp[(0, len(s) - 1)]

  25.     # from up to down
  26.     def get_by_recursion(self, s, i, j):
  27.         if i == j:
  28.             return 1
  29.         elif j - i == 1:
  30.             return 2 if s[i] == s[j] else 1

  31.         if s[i] == s[j]:
  32.             return self.get_by_recursion(s, i+1, j-1) + 2
  33.         else:
  34.             return max(self.get_by_recursion(s, i, j-1), self.get_by_recursion(s, i + 1, j))


  35. if __name__ == "__main__":
  36.     obj = Solution()
  37.     print obj.longestPalindromeSubseq("bbbab")
  38.     print obj.get_by_recursion("bbbab", 0, len("bbbab") - 1)
复制代码

补充内容 (2018-10-23 08:35):
最近貌似写代码都是超时超时超时
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-3J4NB  2018-9-26 02:55:32
follow 楼主加油~

评分

参与人数 1大米 +3 收起 理由
tall_cool_13 + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
chargerhe 2018-9-26 04:12:41 | 只看该作者
全局:
我也在刷, 看这楼主给自己压力... 楼主很给力. 顺带问问 Pramp 使用体验怎么样

评分

参与人数 1大米 +3 收起 理由
tall_cool_13 + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

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

本版积分规则

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