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

开一贴刷题打卡

🔗
 楼主| tall_cool_13 2018-10-2 14:55:06 | 只看该作者
全局:
写了一道easy的min stack
其实时间复杂度最高的即为pop操作,当pop的数为min的时候需要遍历数组,平均为O(1)
  1. import sys
  2. class MinStack(object):

  3.     def __init__(self):
  4.         """
  5.         initialize your data structure here.
  6.         """
  7.         self.stack = []
  8.         self.mmin = sys.maxint
  9.         

  10.     def push(self, x):
  11.         """
  12.         :type x: int
  13.         :rtype: void
  14.         """
  15.         self.stack.append(x)
  16.         self.mmin = x if x < self.mmin else self.mmin
  17.         

  18.     def pop(self):
  19.         """
  20.         :rtype: void
  21.         """
  22.         if not self.stack:
  23.             pass
  24.         else:
  25.             t = self.stack.pop()
  26.             if t == self.mmin:
  27.                 self.mmin = sys.maxint
  28.                 for x in self.stack:
  29.                     self.mmin = x if x < self.mmin else self.mmin
  30.         
  31.     def top(self):
  32.         """
  33.         :rtype: int
  34.         """
  35.         if not self.stack:
  36.             return -1
  37.         else:
  38.             return self.stack[-1]
  39.         

  40.     def getMin(self):
  41.         """
  42.         :rtype: int
  43.         """
  44.         return self.mmin


  45. # Your MinStack object will be instantiated and called as such:
  46. # obj = MinStack()
  47. # obj.push(x)
  48. # obj.pop()
  49. # param_3 = obj.top()
  50. # param_4 = obj.getMin()
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-2 16:17:57 | 只看该作者
全局:
146 题,没考虑key相同的情况失误失误
  1. class LRUCache(object):
  2.     def __init__(self, capacity):
  3.         """
  4.         :type capacity: int
  5.         """
  6.         self.hhash = {}  # key => seq_no, value
  7.         self.shash = {}  # seq_no => key
  8.         self.min_seq = 0  # minimum sequence no
  9.         self.max_seq = -1  # minimum sequence no
  10.         self.capacity = capacity
  11.         self.size = 0  # elements num

  12.     def get(self, key):
  13.         """
  14.         :type key: int
  15.         :rtype: int
  16.         """
  17.         if key in self.hhash:
  18.             del_seq = self.hhash[key][0]
  19.             del self.shash[del_seq]
  20.             self.max_seq += 1
  21.             self.hhash[key] = (self.max_seq, self.hhash[key][1])
  22.             self.shash[self.max_seq] = key
  23.             # find the next min_seq
  24.             while self.min_seq not in self.shash:
  25.                 self.min_seq += 1
  26.             return self.hhash[key][1]
  27.         else:
  28.             return -1

  29.     def put(self, key, value):
  30.         """
  31.         :type key: int
  32.         :type value: int
  33.         :rtype: void
  34.         """
  35.         if self.size == self.capacity:
  36.             del_key = self.shash[self.min_seq]
  37.             del self.shash[self.min_seq], self.hhash[del_key]
  38.             self.max_seq += 1
  39.             self.hhash[key], self.shash[self.max_seq] = (self.max_seq, value), key
  40.             # find the next min_seq
  41.             while self.min_seq not in self.shash:
  42.                 self.min_seq += 1
  43.         else:
  44.             self.max_seq += 1
  45.             self.hhash[key] = (self.max_seq, value)
  46.             self.shash[self.max_seq] = key
  47.             self.size += 1
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-3 04:59:37 | 只看该作者
全局:
两个数字交互都忘记咋写了
a = a ^ b
b = a ^ b
a = a ^ b
exclusive or
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-3 07:10:19 | 只看该作者
全局:
910 我之前想了好一会儿一直不太清楚怎么做,直到看到一个博主的话,然后我就顿悟了,看其他的说的乱七八糟完全不知道说的啥:初步想法肯定把大的减小,把小的增大,最次也是同时增大或者同时减小,不存在把小的减小反而把大的增大,想到这一步就好做了,我们先将A排序,然后将若干个大的减小,剩下的小的增大,但是具体将多少个大的减小呢,这个我们不能确定,所以我们得依次遍历
  1. package Contest_103;

  2. import java.util.* ;

  3. public class smallestRange2 {
  4.     public int Solution(int[] A, int K) {
  5.         int N = A.length ;
  6.         Arrays.sort(A) ;
  7.         int ans = A[N-1] - A[0] ;
  8.         for (int i = 1; i < N -1; i ++) {
  9.             int h = Math.max(A[N-1] - K, A[i] + K) ;
  10.             int l = Math.min(A[0] + K, A[i+1] - K) ;
  11.             ans = Math.min(ans, h - l) ;
  12.         }
  13.         return ans ;
  14.     }

  15.     public static void main(String args[]) {
  16.         smallestRange2 obj = new smallestRange2() ;
  17.         //System.out.println(obj.Solution(new int[]{1}, 0));
  18.         //System.out.println(obj.Solution(new int[]{1, 2}, 0));
  19.         //System.out.println(obj.Solution(new int[]{0, 10}, 2));
  20.         System.out.println(obj.Solution(new int[]{8038,9111,5458,8483,5052,9161,8368,2094,8366,9164,53,7222,9284,5059,4375,2667,2243,5329,3111,5678,5958,815,6841,1377,2752,8569,1483,9191,4675,6230,1169,9833,5366,502,1591,5113,2706,8515,3710,7272,1596,5114,3620,2911,8378,8012,4586,9610,8361,1646,2025,1323,5176,1832,7321,1900,1926,5518,8801,679,3368,2086,7486,575,9221,2993,421,1202,1845,9767,4533,1505,820,967,2811,5603,574,6920,5493,9490,9303,4648,281,2947,4117,2848,7395,930,1023,1439,8045,5161,2315,5705,7596,5854,1835,6591,2553,8628}, 4643)); // 2
  21.         //System.out.println(obj.Solution(new int[]{1, 3, 6}, 30));
  22.     }
  23. }
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-3 13:05:43 | 只看该作者
全局:
这两天我在看别人写的Leetcode的代码,我发现我写的代码的确会比别人写的显得冗长,需要思考一下如何才能把代码写的优雅而且简短,这样对自己也有好处代码不容易出错
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-3 14:27:21 | 只看该作者
全局:
代码不仅仅accepted就算通过的,需要细细分析具体逻辑,代码分析

补充内容 (2018-10-3 14:29):
1. 使用了特殊的写法和库
2. 思考问题更深一层,考虑到了一下裁剪数据
3. 写的非常优秀!!!!!
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-5 02:21:56 | 只看该作者
全局:
做了一道49题,特意留意了代码的写法
  1. import collections

  2. class Solution(object):
  3.     def groupAnagrams(self, strs):
  4.         """
  5.         :type strs: List[str]
  6.         :rtype: List[List[str]]
  7.         """
  8.         primes = {'a': 2,
  9.                   'b': 3,
  10.                   'c': 5,
  11.                   'd': 7,
  12.                   'e': 11,
  13.                   'f': 13,
  14.                   'g': 17,
  15.                   'h': 19,
  16.                   'i': 23,
  17.                   'j': 29,
  18.                   'k': 31,
  19.                   'l': 37,
  20.                   'm': 41,
  21.                   'n': 43,
  22.                   'o': 47,
  23.                   'p': 53,
  24.                   'q': 59,
  25.                   'r': 61,
  26.                   's': 67,
  27.                   't': 71,
  28.                   'u': 73,
  29.                   'v': 79,
  30.                   'w': 83,
  31.                   'x': 89,
  32.                   'y': 97,
  33.                   'z': 101
  34.                  }
  35.         
  36.         groupList = collections.defaultdict(list)
  37.         for sstr in strs:
  38.             key = 1
  39.             for c in sstr:
  40.                 key *= primes[c]
  41.             groupList[key].append(sstr)
  42.         return groupList.values()
复制代码
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-5 16:29:47 | 只看该作者
全局:
写了一道133简单题,直接上代码
  1. # Definition for a undirected graph node
  2. # class UndirectedGraphNode:
  3. #     def __init__(self, x):
  4. #         self.label = x
  5. #         self.neighbors = []

  6. class Solution:
  7.     def __init__(self):
  8.         self.visited = []
  9.         self.hhash = {}

  10.     # @param node, a undirected graph node
  11.     # [url=home.php?mod=space&uid=160137]@return[/url] a undirected graph node
  12.     def cloneGraph(self, node):
  13.         if not node:
  14.             return None

  15.         new_node = UndirectedGraphNode(node.label)
  16.         self.hhash[node] = new_node
  17.         self.visited.append(node)
  18.         for n in node.neighbors:
  19.             new_node.neighbors.append(self.hhash[n] if n in self.visited else self.cloneGraph(n))
  20.         return new_node
复制代码


补充内容 (2018-10-5 16:34):
刚才想了一下, self.visited 变量可以直接去除掉
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-6 02:05:20 | 只看该作者
全局:
Leetcode 230
  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.cnt = 0
  10.         
  11.     def kthSmallest(self, root, k):
  12.         """
  13.         :type root: TreeNode
  14.         :type k: int
  15.         :rtype: int
  16.         """
  17.         if not root:
  18.             return None
  19.         
  20.         l = self.kthSmallest(root.left, k)
  21.         if l is not None:
  22.             return l
  23.         
  24.         self.cnt += 1
  25.         if self.cnt == k:
  26.             return root.val
  27.         
  28.         r = self.kthSmallest(root.right, k)
  29.         if r is not None:
  30.             return r
  31.         
复制代码

补充内容 (2018-10-6 02:07):
判别语句别写错,应该是if x is not None, 不能写成 if x: 不然会将0也算计去
回复

使用道具 举报

🔗
 楼主| tall_cool_13 2018-10-6 02:13:27 | 只看该作者
全局:
都忘记了我146还没写对,我要先搞一下146,蛋疼呢
回复

使用道具 举报

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

本版积分规则

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