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

开一贴刷题打卡

🔗
 楼主| tall_cool_13 2018-10-26 15:07:03 | 只看该作者
全局:
Lt 927 这题思路倒是简单,但是代码还是容易写错的
1. 没有考虑到最后一个pattern的结尾的0是不可以省略的
2. 如果数组中1的个数不为3的倍数可以直接排除可能性

  1. class Solution(object):
  2.     def threeEqualParts(self, A):
  3.         def find_1(A, s, N):
  4.             # find the the index of first 1 and last 1
  5.             l, r, cnt = -1, -1, 0
  6.             for idx in range(s, len(A)):
  7.                 if A[idx] == 1:
  8.                     l = idx if l == -1 else l
  9.                     cnt += 1
  10.                     if N == cnt:
  11.                         r = idx
  12.                         break
  13.             return l, r

  14.         cnt = len([1 for c in A if c == 1])
  15.         if cnt % 3 != 0:
  16.             return [-1, -1]

  17.         if cnt == 0:
  18.             return [0, len(A) - 1]

  19.         N = cnt / 3
  20.         l, r = find_1(A, 0, N)
  21.         lx, rx = find_1(A, r + 1, N)
  22.         lq, rq = find_1(A, rx + 1, N) # problem
  23.         last_0 = len(A) - 1 - rq
  24.         r = r + last_0
  25.         rx = rx + last_0
  26.         return [r, rx + 1] if r < lx and rx < lq and A[l:r + 1] == A[lx:rx + 1] == A[lq:] else [-1, -1]
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-30 11:14:56 | 只看该作者
全局:
一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。这题大家都知道用位运算不过,怎么写是一个问题
  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     # 返回[a,b] 其中ab是出现一次的两个数字
  4.     def FindNumsAppearOnce(self, array):
  5.         # write code here
  6.         m = 0
  7.         for i in array:
  8.             m ^= i
  9.         m = m - (m & (m-1))
  10.         first, last = [], []
  11.         for i in array:
  12.             (first if (i & m) == m else last).append(i)
  13.         m, n = 0, 0
  14.         for i in first:
  15.             m ^= i
  16.         for j in last:
  17.             n ^= j
  18.         return m, n
  19.          
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-30 15:00:31 | 只看该作者
全局:
定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。
思路:用空间换时间,用一个辅助栈记录当前栈中的最小值。辅助栈元素个数和数据栈保持一样的数目
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-30 16:33:04 | 只看该作者
全局:
判断一个二叉树是否是平衡二叉树
  1. # -*- coding:utf-8 -*-
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  7. class Solution:
  8.     def __init__(self):
  9.         self.diff = 0
  10.         
  11.     def IsBalanced_Solution(self, pRoot):
  12.         # write code here
  13.         # special cases
  14.         _ = self.getHeight(pRoot)
  15.         return self.diff <= 1
  16.         
  17.     def getHeight(self, root):
  18.         if not root: return 0
  19.         l = self.getHeight(root.left)
  20.         r = self.getHeight(root.right)
  21.         self.diff = max(abs(l - r), self.diff)
  22.         return max(l, r) + 1
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-31 00:30:32 | 只看该作者
全局:
查找一个环的入口
  1. # -*- coding:utf-8 -*-
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  6. class Solution:
  7.     def EntryNodeOfLoop(self, pHead):
  8.         # write code here
  9.         s, f = pHead, pHead
  10.         if not pHead or not pHead.next:
  11.             return None
  12.         
  13.         while s and f.next:
  14.             s = s.next
  15.             f = f.next.next
  16.             if s == f:
  17.                 s = pHead
  18.                 while s != f:
  19.                     s = s.next
  20.                     f = f.next
  21.                 return s
  22.         return None
复制代码

补充内容 (2018-10-31 00:30):
可以参考: https://www.cnblogs.com/zhuzhenwei918/p/7491892.html
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-31 00:49:48 | 只看该作者
全局:
递归全排序问题
  1. # -*- coding:utf-8 -*-
  2. class Solution:
  3.     def Permutation(self, ss):
  4.         # write code here
  5.         if len(ss) <= 1:
  6.             return [ss] if ss else []
  7.         
  8.         ans = []
  9.         ss = list(ss)
  10.         for idx, num in enumerate(ss):
  11.             ss[idx], ss[0] = ss[0], ss[idx]
  12.             for j in self.Permutation("".join(ss[1:])):
  13.                 ans.append(ss[0] + j)
  14.             ss[idx], ss[0] = ss[0], ss[idx]
  15.         return sorted(list(set(ans)))
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-11-2 06:36:17 | 只看该作者
全局:
剑指Offer都做了一遍,大都题目都比较简单,有11道题需要再细看一遍
1. https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tqId=11188&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking 数组中的逆序对
2. https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking 数组中数字个数超过一半 https://www.geeksforgeeks.org/majority-element/
3. https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6?tpId=13&tqId=11184&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking 1 出现的次数 https://blog.csdn.net/yi_afly/article/details/52012593
4. https://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a?tpId=13&tqId=11215&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking 二叉搜索树第k个数
5. https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=13&tqId=11216&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking 数据流中中位数 最大堆 - 最小堆
6. https://www.nowcoder.com/practice/c61c6999eecb4b8f88a98f66b273a3cc?tpId=13&tqId=11218&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking 矩阵路径 写一下
7. https://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215?tpId=13&tqId=11201&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking 不用加减乘数做加法 太tricky
8. https://www.nowcoder.com/practice/45327ae22b7b413ea21df13ee7d6429c?tpId=13&tqId=11205&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking 正则匹配 . 和 * 递归匹配*
9. https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking 二叉树下一个节点
10. https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking 复杂链复制 tricky
11. https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking 二叉搜索树以及双向链表 左子树最大右子树最小
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-11-2 06:39:17 | 只看该作者
全局:
头条北美2面,题目:给一个矩阵,里面有些点代表:物品,空地,守卫和墙。不可以移动到墙里面,请问如果指定一个物品怎么计算出最靠近的守卫的距离

  1. # coding=utf-8
  2. import sys

  3. min_dis = sys.maxint
  4. """
  5. matrix = [
  6.     # star: 0, 0: 1, wall: 2, guard: 3, visited = 4
  7.     [0, 1, 1, 0],
  8.     [2, 2, 1, 2],
  9.     [3, 1, 1, 3],
  10.     [1, 0, 1, 1]
  11. ]
  12. """


  13. def dfs(matrix, i, j, dis):
  14.     global min_dis
  15.     N = len(matrix)
  16.     # star: 0, 0: 1, wall: 2, guard: 3, visited = 4
  17.     if not (i > -1 and j > -1 and i < N and j < N):
  18.         return

  19.     if matrix[i][j] == 3:
  20.         min_dis = min(min_dis, dis)
  21.         return

  22.     d = [(1, 0), (-1, 0), (0, -1), (0, 1)]
  23.     children = []
  24.     for x, y in d:
  25.         xx = i + x
  26.         yy = j + y
  27.         if xx > -1 and yy > -1 and xx < N and yy < N and matrix[xx][yy] != 4:
  28.             if matrix[xx][yy] in [0, 1, 3]:
  29.                 children.append((xx, yy))

  30.     t = matrix[i][j]
  31.     matrix[i][j] = 4
  32.     for x, y in children:
  33.         dfs(matrix, x, y, dis + 1)
  34.     matrix[i][j] = t


  35. matrix = [
  36.     # star: 0, 0: 1, wall: 2, guard: 3, visited = 4
  37.     [0, 1, 1, 0],
  38.     [2, 2, 1, 2],
  39.     [3, 1, 1, 3],
  40.     [1, 0, 1, 1]
  41. ]
  42. dfs(matrix, 0, 0, 0)  # 5
  43. print 0 if min_dis == sys.maxint else min_dis
复制代码

补充内容 (2018-11-2 06:41):
这个题目虽然简单但是现场写代码而且还要运行accpet还是遇到了不少的小语法问题。第一个18行的代码变量N忘记定义。30,31行直接忘记写了直接用x, y作为坐标点了。

补充内容 (2018-11-2 06:42):
而且在写的时候,1. 代码写的不够简洁,边解说边写代码 2. 出现了几次简单的语法错误 3. 用了全局变量这些不太合适的写法  4. 变量名也起的不太好看

补充内容 (2018-11-2 06:43):
该代码就是面试的时候写的代码,不过感觉写的小问题的确不断
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-11-4 11:00:33 | 只看该作者
全局:
做了一下最新一期的contest,最后一个hard没做,第一个easy比较简单,第二个medium+第一题一共花了半小时,然后最后一个小时都是在搞第三题,第三题写完代码花了20分钟,可是对于超时问题花了40分钟都没有解决。在这四十分钟中,其实并没有想出一个非常有效的减少时间的方法,都在尝试一些小的方面:像是避免递归的次数,特殊情况直接退出循环啥的。
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-11-4 11:00:53 | 只看该作者
全局:
933
  1. class RecentCounter(object):

  2.     def __init__(self):
  3.         self.pings = []

  4.     def ping(self, t):
  5.         """
  6.         :type t: int
  7.         :rtype: int
  8.         """
  9.         self.pings.append(t)
  10.         b = t - 3000
  11.         for idx, num in enumerate(self.pings):
  12.             if num >= b:
  13.                 break
  14.                     
  15.         self.pings = self.pings[idx:]
  16.         return len(self.pings)
  17.         
  18.         


  19. # Your RecentCounter object will be instantiated and called as such:
  20. # obj = RecentCounter()
  21. # param_1 = obj.ping(t)
复制代码
回复

使用道具 举报

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

本版积分规则

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