Press "Enter" to skip to content

Posts published in “Desgin”

花花酱 LeetCode 1206. Design Skiplist

Design a Skiplist without using any built-in libraries.

A Skiplist is a data structure that takes O(log(n)) time to adderase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists are just simple linked lists.

For example: we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way:


Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add , erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n).

To be specific, your design should include these functions:

  • bool search(int target) : Return whether the target exists in the Skiplist or not.
  • void add(int num): Insert a value into the SkipList. 
  • bool erase(int num): Remove a value in the Skiplist. If num does not exist in the Skiplist, do nothing and return false. If there exists multiple num values, removing any one of them is fine.

See more about Skiplist : https://en.wikipedia.org/wiki/Skip_list

Note that duplicates may exist in the Skiplist, your code needs to handle this situation.

Example:

Constraints:

  • 0 <= num, target <= 20000
  • At most 50000 calls will be made to searchadd, and erase.

Solution:

C++

Python3

花花酱 LeetCode 1472. Design Browser History

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Implement the BrowserHistory class:

  • BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
  • void visit(string url) visits url from the current page. It clears up all the forward history.
  • string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
  • string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

Example:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation: BrowserHistory browserHistory = new BrowserHistory("leetcode.com"); browserHistory.visit("google.com"); // You are in "leetcode.com". Visit "google.com" browserHistory.visit("facebook.com"); // You are in "google.com". Visit "facebook.com" browserHistory.visit("youtube.com"); // You are in "facebook.com". Visit "youtube.com" browserHistory.back(1); // You are in "youtube.com", move back to "facebook.com" return "facebook.com" browserHistory.back(1); // You are in "facebook.com", move back to "google.com" return "google.com" browserHistory.forward(1); // You are in "google.com", move forward to "facebook.com" return "facebook.com" browserHistory.visit("linkedin.com"); // You are in "facebook.com". Visit "linkedin.com" browserHistory.forward(2); // You are in "linkedin.com", you cannot move forward any steps. browserHistory.back(2); // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com" browserHistory.back(7); // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"

Constraints:

  • 1 <= homepage.length <= 20
  • 1 <= url.length <= 20
  • 1 <= steps <= 100
  • homepage and url consist of  ‘.’ or lower case English letters.
  • At most 5000 calls will be made to visitback, and forward.

Solution: Vector

Time complexity:
visit: Amortized O(1)
back: O(1)
forward: O(1)

C++

Python中的整型占多少个字节?

说到计算机中的整型,相信很多人都会联想到32位整型(或者int),是程序员日常生活中用的最多的一种类型。32位整型顾名思义,占用32个位也就是4个字节,取值范围−2,147,483,648~ 2,147,483,647 。C/C++中是4个字节,Java中也是4个字节,但是Python中呢?

我们知道Python中也有int类,而且非常好用,原生支持高精度计算。但是Python中的一个整型到底占用多少字节呢?我相信绝大多数的Python程序员从未想过这一点,越是习以为常的东西越是不会在意它的存在

在Python中,如果想要知道一个对象所占用的内存大小,只需要使用sys.getsizeof这个API就可以了。那就让我们来试一下不同的整数

从上面的小实验可以看出,一个整型最少要占24字节(0),1开始就要占用28个字节,到了2的30次方开始要占用32个字节,而2的128次方则要占用44个字节。我们可以得到两点规律,1. 字节数随着数字增大而增大。2. 每次的增量是4个字节。 好像至此已经回答了我们的题目中的问题:Python中的整型占多少个字节?答案是:变长的(相对于int32的定长),而且最少24个字节。

你以为本文到这里就结束了吗?那你就图样图森破了。一个整型数2,居然要占用28个字节!这完全了颠覆了我的认知,我一定搞清楚为什么。 在哥们的帮助下,我找到了Python的源码。 https://github.com/python/cpython

Python的官方实现是C语言,所以叫cpython。这也就意味着只要Python还在,C就会不消失。其他实现还有jython(Java), IronPython (.Net), PyPy (Python)。

第一件事情要搞清楚的是Python中int类型在cpython的名字是什么?看了半天,在 longobject.h 中发现了一个叫 PyLongObject 的结构体。然而它只是一个马甲,是 _longobject的别名。在longintrepr.h中找到了 _longobject 的定义如下:

在文件的开头就看到了typedef uint32_t digit;digit就是unit32_t, 每个元素占4个字节。但PyObject_VAR_HEAD又是什么鬼?在object.h中发现了它是个宏,上面的注释倒是挺有意思的。

等一下,PyVarObject又是什么?还好定义就在下面。

又一层嵌套,是不是已经晕了,继续查看PyObject的定义,这次反而在上面了。

有完没完啊?_PyObject_HEAD_EXTRA又是什么?看了一下发现它只在debug build中有定义,这里就不展开了。Py_ssize_t等于ssize_t如果有定义的话, ssize_t在64位的机器上就是long_typeobject又是什么?感觉应该非常大,不然就不会用指针了。不过话说回来,既然用了指针,我又何必去关心它是什么呢?反正就是8个字节而已,指向一个内存地址。至此真相大了一个白,如果我们把structs flatten, PyLongObject 定义如下:

ob_refcnt引用计数 8个字节,ob_type类型信息 8个字节(指针),ob_size变长部分元素的个数,8个字节。ob_digit变长的数据部分,字节数为4*abs(ob_size),ob_size可以为0,所以最少8+8+8=24字节,每次增量都是4 (unsigned int) 的倍数。这和我们之前观察到的实验结果吻合。

以上都是基于64位的Python,对于32位的版本,定义如下:

32位就要比64位小很多了,最少12个字节,增量为2个字节。

好了,今天就写到这里。相信你对整型数或者Python有了一个新的认识。下面一篇我们会将会介绍整型数在Python中的表示和计算。

花花酱 LeetCode 895. Maximum Frequency Stack

Problem

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

  • push(int x), which pushes an integer x onto the stack.
  • pop(), which removes and returns the most frequent element in the stack.
    • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:

Input: 
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

Note:

  • Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
  • It is guaranteed that FreqStack.pop() won’t be called if the stack has zero elements.
  • The total number of FreqStack.push calls will not exceed 10000 in a single test case.
  • The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
  • The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

 

Solution 1: Buckets

We have n  stacks. The i-th stack has the of elements with freq i when pushed.

We keep tracking the freq of each element.

push(x): stacks[++freq(x)].push(x)  # inc x’s freq and push it onto freq-th stack

pop(): x = stacks[max_freq].pop(), –freq(x); # pop element x from the max_freq stack and dec it’s freq.

Time complexity: O(1) push / pop

Space complexity: O(n)

C++

Solution2: Priority Queue

Use a max heap with key: (freq, seq), the max freq and closest to the top of stack element will be extracted first.

Time complexity: O(logn)

Space complexity: O(n)

C++

Related Problems

花花酱 LeetCode 872. Implement Rand10() Using Rand7()

Problem

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

Input: 3
Output: [8,1,10]

Note:

  1. rand7 is predefined.
  2. Each testcase has one argument: n, the number of times that rand10 is called.

Solution: Math

Time complexity: O(49/40) = O(1)

Time complexity: O(7/6 + 7 / 5) = O(1)