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

开一贴刷题打卡

🔗
 楼主| tall_cool_13 2018-10-14 10:56:48 | 只看该作者
全局:
对于这次的competition总体来说,第一个时间要控制住,而想把时间控制住就需要保证代码的质量,够短够清晰。第二个加强读题的能力,第四题读了几遍都没太明白题目的意思,蛋疼的很

补充内容 (2018-10-14 11:00):
不过我感觉很多人应该都是团队作战,每次都是半小时就把四道题目写完了,读题目思考思考半小时就没了,也有可能真我太菜了

补充内容 (2018-10-14 11:17):
争取下一次4题全部AC, Fighting
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-14 15:40:07 | 只看该作者
全局:
做了三题twitter的online 题目,题目完全easy,但是我居然还是写了2个小时才全部写完,马蛋蛋的
1. 第一个题判断括号,里面仅仅包含: (), [], {}
  1. # Complete the braces function below.
  2. def braces(values):
  3.     def braces_by_string(value):
  4.         # using a stack
  5.         stack = []
  6.         mapping = {"]":"[", "}":"{", ")":"("}
  7.         for v in value:
  8.             if v in mapping.values():
  9.                 stack.append(v)
  10.             else:
  11.                 if not stack:
  12.                     return False
  13.                 else:
  14.                     if stack.pop() != mapping[v]:
  15.                         return False
  16.         return True if not stack else False

  17.     return ["YES" if braces_by_string(value) else "NO" for value in values]
  18.             
复制代码


2. 第二题:给两个英文句子s和t,单词用空格隔开,t是s的子序列,输出相比较s,t漏掉的单词
  1. #
  2. # Complete the 'missingWords' function below.
  3. #
  4. # The function is expected to return a STRING_ARRAY.
  5. # The function accepts following parameters:
  6. #  1. STRING s
  7. #  2. STRING t
  8. #

  9. def missingWords(s, t):
  10.     # Write your code here
  11.     s_items, t_items = s.split(" "), t.split(" ")
  12.     s_idx, t_idx = 0, 0
  13.     res = []

  14.     while s_idx < len(s_items) and t_idx < len(t_items):
  15.         while s_idx < len(s_items) and s_items[s_idx] != t_items[t_idx]:
  16.             res.append(s_items[s_idx])
  17.             s_idx += 1

  18.         s_idx, t_idx = s_idx + 1, t_idx + 1

  19.     while s_idx < len(s_items):
  20.         res.append(s_items[s_idx])
  21.         s_idx += 1

  22.     return res
  23.    
复制代码


3. 第三题,就是Huffman树,做解码操作,而且还是最贱的那种解码
  1. def decode(codes, encoded):
  2.     # Write your code here
  3.     mapping = {code.split("\t")[0]:code.split("\t")[1] for code in codes}
  4.     res = ""
  5.     while encoded:
  6.         for k, v in mapping.items():
  7.             if encoded.find(v) == 0:
  8.                 res += "\n" if k == "[newline]" else k
  9.                 encoded = encoded[len(v):]
  10.     return res
复制代码

补充内容 (2018-10-14 15:42):
第二问,我本来是用递归做的,然后发现一直报Runtime Err,开始我以为是死循环,但是看了几遍也没看出来会死循环,然后猜可能是输入的数据长度太多,导致递归过多,所以换成非递归方式就提交成功了
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-17 04:13:38 | 只看该作者
全局:
583
  1. class Solution(object):
  2.     def __init__(self):
  3.         self.cache = {}
  4.         
  5.     def minDistance(self, word1, word2):
  6.         """
  7.         :type word1: str
  8.         :type word2: str
  9.         :rtype: int
  10.         """
  11.         if (word1, word2) in self.cache:
  12.             return self.cache[(word1, word2)]
  13.         
  14.         if len(word1) == 0 or len(word2) == 0:
  15.             res = max(len(word1), len(word2))
  16.             self.cache[(word1, word2)] = res
  17.             return res
  18.         
  19.         if word1[0] == word2[0]:
  20.             res = self.minDistance(word1[1:], word2[1:])
  21.             self.cache[(word1, word2)] = res
  22.             return res
  23.         else:
  24.             res = 1 + min(self.minDistance(word1[1:], word2[0:]), self.minDistance(word1[0:], word2[1:]))
  25.             self.cache[(word1, word2)] = res
  26.             return res
复制代码

回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-17 16:31:31 | 只看该作者
全局:
Leetcode 88, 虽然是个easy,反而觉得不太容易写,很容易写出来问题,以后review可以重点再看一下
  1. class Solution(object):
  2.     def merge(self, nums1, m, nums2, n):
  3.         """
  4.         :type nums1: List[int]
  5.         :type m: int
  6.         :type nums2: List[int]
  7.         :type n: int
  8.         :rtype: void Do not return anything, modify nums1 in-place instead.
  9.         """
  10.         # merge two arrays
  11.         for i in range(n):
  12.             nums1[m+i] = nums2[i]
  13.         
  14.         # exchange each item by operating nums1
  15.         s, e = 0, m
  16.         while e < m + n:
  17.             while nums1[s] < nums1[e]:
  18.                 s += 1
  19.             e_num = nums1[e]
  20.             for i in range(s, e)[::-1]:  # problem1
  21.                 nums1[i+1] = nums1[i]
  22.             nums1[s] = e_num
  23.             e += 1
复制代码

补充内容 (2018-10-17 16:37):
range反序: range(3, 6)[::-1] 或者 reversed(range(3, 6) 或者 sorted(range(3, 6), reverse=True))
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-18 00:08:21 | 只看该作者
全局:
Leetcode 924, 这题其实很简单,但是花的时间也不少
1. 题目理解错误,一直以为remove a node,就是将和这个node有关的所有节点链接全部断开,其实仅仅只是从initial 里面去掉该节点,其他啥都没做。需要多读题
2. 提交的时候错了两次,第一次是没有考虑到相同node的特殊情况,这个其实不应该忽略的,其实在做这个题目之前就知道这种特殊情况了,写代码忘记处理了
3. 第二次错误提交感觉还是题目描述不清,倒不是我的问题,看到条件graph[i][j] == graph[j][i],我一直以为这个是无向图,但是其实看错误的case明显这是一个有向图
  1. class Solution(object):
  2.     def minMalwareSpread(self, graph, initial):
  3.         """
  4.         :type graph: List[List[int]]
  5.         :type initial: List[int]
  6.         :rtype: int
  7.         """
  8.         # group the graph
  9.         groups = []
  10.         visited = []
  11.         self.N = len(graph[0])
  12.         self.graph = graph

  13.         for i in range(self.N):
  14.             group = []
  15.             self.spread(i, group, visited)
  16.             groups.append(group)
  17.         # find the distribution of initial node
  18.         mmin, mmax_len = -1, -1
  19.         for group in groups:
  20.             n = [n for n in initial if n in group]
  21.             if len(n) == 1 and len(group) >= mmax_len:
  22.                 if len(group) == mmax_len: # no consider the same condition
  23.                     mmin, mmax_len = min(n[0], mmin), len(group)
  24.                 else:
  25.                     mmin, mmax_len = n[0], len(group)
  26.         return min(initial) if mmin == -1 else mmin

  27.     def spread(self, i, group, visited):
  28.         if i not in visited:
  29.             visited.append(i)
  30.             group.append(i)
  31.             rows = [idx for idx, n in enumerate(self.graph[i]) if n == 1]
  32.             columns = [idx for idx in range(self.N) if self.graph[idx][i] == 1]  # problem, 0 <= graph[i][j] == graph[j][i] <= 1
  33.             rows.extend(columns)
  34.             children = list(set(rows))
  35.             for j in children:
  36.                 self.spread(j, group, visited)
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-18 13:44:33 | 只看该作者
全局:
Leetcode 907, 又是超时,肯定有O(N)时间复杂度的算法,现在的复杂度是O(N)

  1. class Solution(object):
  2.     def sumSubarrayMins(self, A):
  3.         """
  4.         :type A: List[int]
  5.         :rtype: int
  6.         """        
  7.         dp = 0
  8.         for idx in range(0, len(A)):
  9.             cur_min = A[idx]
  10.             for i in range(0, idx + 1)[::-1]:
  11.                 cur_min = min(cur_min, A[i])
  12.                 dp += cur_min
  13.         
  14.         return dp % (10 ** 9 + 7)
  15.         
  16.         
  17.         
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-18 14:09:30 | 只看该作者
全局:
671
  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 __init__(self):
  9.         self.ans = []
  10.         
  11.     def findSecondMinimumValue(self, root):
  12.         """
  13.         :type root: TreeNode
  14.         :rtype: int
  15.         """
  16.         def recursion(root):
  17.             if root:
  18.                 self.ans.append(root.val)
  19.                 recursion(root.left)
  20.                 recursion(root.right)
  21.         
  22.         recursion(root)
  23.         self.ans = sorted(list(set(self.ans)))
  24.         return -1 if len(self.ans) <= 1 else self.ans[1]
  25.         
复制代码

补充内容 (2018-10-19 15:28):
看似简单其实还是需要好好思考一下的
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-19 04:28:31 | 只看该作者
全局:
看了一下最长子序列,递归和非递归的方法
  1. def find_LIS(A):
  2.     N = len(A)
  3.     dp = [1] * N
  4.     for i in range(0, N):
  5.         for j in range(0, i):
  6.             dp[i] = dp[j] + 1 if A[i] >= A[j] and dp[j] + 1 > dp[i] else dp[i]

  7.     return max(dp)

  8. def find_LIS_r(A):
  9.     N = len(A)
  10.     dp = [1] * N
  11.     for i in range(0, N):
  12.         dp[i] = recursion(A, i)
  13.     return max(dp)

  14. def recursion(A, i):
  15.     if i == 0:
  16.         return 1

  17.     mmax = 1
  18.     for j in range(0, i):
  19.         if A[j] <= A[i]:
  20.             mmax = max(recursion(A, j) + 1, mmax)
  21.     return mmax


  22. if __name__ == "__main__":
  23.     print find_LIS_r([1, -1, 2, -3, 4, -5, 6, -7])
复制代码

补充内容 (2018-10-19 04:31):
今天和人聊天他说dp不是递归,我突然一愣,回去想了想,这完全就是两个不一样的东西。dp是一个策略,偏策略,而递归是一个实现方法,偏实现。

补充内容 (2018-10-19 04:32):
所有的dp都可以用递归来实现,因为本质上来说dp就是通过缩小数据集来获取最优解答的。但是反之就不对
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-19 06:03:31 | 只看该作者
全局:
看了几题动态规划的题目
https://github.com/shenweihai1/courses_work/blob/master/dp.pdf
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-19 15:29:04 | 只看该作者
全局:
回复

使用道具 举报

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

本版积分规则

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