def get_n_prime(count): primes = [] n = 2 while len(primes) < count: for i in range(2, n//2 + 1): if n % i == 0: break else: primes.append(n) n += 1 return primes
Monthly Archives: October 2019
Is Graph Bipartite?
Given an undirected graph
, return true
if and only if it is bipartite.
Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form: graph[i]
is a list of indexes j
for which the edge between nodes i
and j
exists. Each node is an integer between 0
and graph.length - 1
. There are no self edges or parallel edges: graph[i]
does not contain i
, and it doesn’t contain any element twice.
Example 1: Input: [[1,3], [0,2], [1,3], [0,2]] Output: true Explanation: The graph looks like this: 0----1 | | | | 3----2 We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2: Input: [[1,2,3], [0,2], [0,1,3], [0,2]] Output: false Explanation: The graph looks like this: 0----1 | \ | | \ | 3----2 We cannot find a way to divide the set of nodes into two independent subsets.
Note:
graph
will have length in range[1, 100]
.graph[i]
will contain integers in range[0, graph.length - 1]
.graph[i]
will not containi
or duplicate values.- The graph is undirected: if any element
j
is ingraph[i]
, theni
will be ingraph[j]
.
class Solution: def isBipartite(self, graph: List[List[int]]) -> bool: color = collections.defaultdict(lambda: -1) def dfs(v, cur_color): if color[v] != -1: return color[v] == cur_color color[v] = cur_color return all(dfs(e, cur_color ^ 1) for e in graph[v]) return all(dfs(v, 0) for v in range(len(graph)) if color[v] == -1)
Redis – epoll
Redis 对 epoll
的封装其实也是类似的,使用 epoll_create
创建 epoll
中使用的 epfd
:
static int aeApiCreate(aeEventLoop *eventLoop) { aeApiState *state = zmalloc(sizeof(aeApiState)); if (!state) return -1; state->events = zmalloc(sizeof(struct epoll_event)*eventLoop->setsize); if (!state->events) { zfree(state); return -1; } state->epfd = epoll_create(1024); /* 1024 is just a hint for the kernel */ if (state->epfd == -1) { zfree(state->events); zfree(state); return -1; } eventLoop->apidata = state; return 0; }
在 aeApiAddEvent
中使用 epoll_ctl
向 epfd
中添加需要监控的 FD 以及监听的事件:
static int aeApiAddEvent(aeEventLoop *eventLoop, int fd, int mask) { aeApiState *state = eventLoop->apidata; struct epoll_event ee = {0}; /* avoid valgrind warning */ /* If the fd was already monitored for some event, we need a MOD * operation. Otherwise we need an ADD operation. */ int op = eventLoop->events[fd].mask == AE_NONE ? EPOLL_CTL_ADD : EPOLL_CTL_MOD; ee.events = 0; mask |= eventLoop->events[fd].mask; /* Merge old events */ if (mask & AE_READABLE) ee.events |= EPOLLIN; if (mask & AE_WRITABLE) ee.events |= EPOLLOUT; ee.data.fd = fd; if (epoll_ctl(state->epfd,op,fd,&ee) == -1) return -1; return 0; }
由于 epoll
相比 select
机制略有不同,在 epoll_wait
函数返回时并不需要遍历所有的 FD 查看读写情况;在 epoll_wait
函数返回时会提供一个 epoll_event
数组:
typedef union epoll_data { void *ptr; int fd; /* 文件描述符 */ uint32_t u32; uint64_t u64; } epoll_data_t; struct epoll_event { uint32_t events; /* Epoll 事件 */ epoll_data_t data; };
aeApiPoll
函数只需要将 epoll_event
数组中存储的信息加 入 eventLoop
的 fired
数组中,将信息传递给上层模块:
static int aeApiPoll(aeEventLoop *eventLoop, struct timeval *tvp) { aeApiState *state = eventLoop->apidata; int retval, numevents = 0; retval = epoll_wait(state->epfd,state->events,eventLoop->setsize, tvp ? (tvp->tv_sec*1000 + tvp->tv_usec/1000) : -1); if (retval > 0) { int j; numevents = retval; for (j = 0; j < numevents; j++) { int mask = 0; struct epoll_event *e = state->events+j; if (e->events & EPOLLIN) mask |= AE_READABLE; if (e->events & EPOLLOUT) mask |= AE_WRITABLE; if (e->events & EPOLLERR) mask |= AE_WRITABLE; if (e->events & EPOLLHUP) mask |= AE_WRITABLE; eventLoop->fired[j].fd = e->data.fd; eventLoop->fired[j].mask = mask; } } return numevents; }
Select
int fd = /* file descriptor */ fd_set rfds; FD_ZERO(&rfds); FD_SET(fd, &rfds) for ( ; ; ) { select(fd+1, &rfds, NULL, NULL, NULL); if (FD_ISSET(fd, &rfds)) { /* file descriptor `fd` becomes readable */ } }
- 初始化一个可读的
fd_set
集合,保存需要监控可读性的 FD; - 使用
FD_SET
将fd
加入rfds
; - 调用
select
方法监控rfds
中的 FD 是否可读; - 当
select
返回时,检查 FD 的状态并完成对应的操作。
在 Redis 的 ae_select
文件中代码的组织顺序也是差不多的,首先在 aeApiCreate
函数中初始化 rfds
和 wfds
:
static int aeApiCreate(aeEventLoop *eventLoop) { aeApiState *state = zmalloc(sizeof(aeApiState)); if (!state) return -1; FD_ZERO(&state->rfds); FD_ZERO(&state->wfds); eventLoop->apidata = state; return 0; }
aeApiAddEvent
和 aeApiDelEvent
会通过 FD_SET
和 FD_CLR
修改 fd_set
中对应 FD 的标志位:
static int aeApiAddEvent(aeEventLoop *eventLoop, int fd, int mask) { aeApiState *state = eventLoop->apidata; if (mask & AE_READABLE) FD_SET(fd,&state->rfds); if (mask & AE_WRITABLE) FD_SET(fd,&state->wfds); return 0; }
整个 ae_select
子模块中最重要的函数就是 aeApiPoll
,它是实际调用 select
函数的部分,其作用就是在 I/O 多路复用函数返回时,将对应的 FD 加入 aeEventLoop
的 fired
数组中,并返回事件的个数:
static int aeApiPoll(aeEventLoop *eventLoop, struct timeval *tvp) { aeApiState *state = eventLoop->apidata; int retval, j, numevents = 0; memcpy(&state->_rfds,&state->rfds,sizeof(fd_set)); memcpy(&state->_wfds,&state->wfds,sizeof(fd_set)); retval = select(eventLoop->maxfd+1, &state->_rfds,&state->_wfds,NULL,tvp); if (retval > 0) { for (j = 0; j <= eventLoop->maxfd; j++) { int mask = 0; aeFileEvent *fe = &eventLoop->events[j]; if (fe->mask == AE_NONE) continue; if (fe->mask & AE_READABLE && FD_ISSET(j,&state->_rfds)) mask |= AE_READABLE; if (fe->mask & AE_WRITABLE && FD_ISSET(j,&state->_wfds)) mask |= AE_WRITABLE; eventLoop->fired[numevents].fd = j; eventLoop->fired[numevents].mask = mask; numevents++; } } return numevents; }
浓烟下的诗歌电台
We fall,
We break,
We fail,
But then,
We rise,
We heal,
We overcome.
如果有一天,你发现我在平庸面前低了头,请向我开炮。
Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because"leetcode"
can be segmented as"leet code"
.
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: Return true because"
applepenapple"
can be segmented as"
apple pen apple"
. Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: false
# TLE solution class Solution: def helper(self, s): if not s: return True return any(self.helper(s[len(word):]) for word in self.wordDict if s.startswith(word)) def wordBreak(self, s: str, wordDict: List[str]) -> bool: self.wordDict = wordDict return self.helper(s)
# Basic DP class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: dp = [False] * len(s) for i in range(len(s)): for word in wordDict: if s[:i+1].endswith(word) and (dp[i-len(word)] or i-len(word) == -1): dp[i] = True return dp[-1]
# Advanced DP class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: dp = [True] for i in range(1, len(s)+1): dp += any(dp[j] and s[j:i] in wordDict for j in range(i)), return dp[-1]
Increasing Triplet Subsequence
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.
Example 1:
Input: [1,2,3,4,5] Output: true
Example 2:
Input: [5,4,3,2,1] Output: false
History is always recurrent.
At the very first, I thought it is a typical dp question, and then I wrote a classical dp solution, and then I got a TLE…
This AC solution I actually checked it out from discuss board, that is really smart.
class Solution: def increasingTriplet(self, nums: List[int]) -> bool: N = len(nums) first = float("inf") second = float("inf") for i in range(N): if nums[i] < first: first = nums[i] elif first < nums[i] < second: second = nums[i] if nums[i] > second: return True return False
Evaluate Division
Equations are given in the format A / B = k
, where A
and B
are variables represented as strings, and k
is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0
.
Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].
The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries
, where equations.size() == values.size()
, and the values are positive. This represents the equations. Return vector<double>
.
According to the example above:
equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.
class Solution: def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]: graph = dict() # Build graph for (a, b), value in zip(equations, values): graph[a] = graph.get(a, []) + [(b, value)] graph[b] = graph.get(b, []) + [(a, 1/value)] def check(source, target): # If there is any one number of the query didn't appear in the graph, answer certainly doesn't exist. if source not in graph or target not in graph: return -1.0 visited = set() stack = collections.deque([(source, 1.0)]) while stack: front, current = stack.popleft() if front == target: return current visited.add(front) for back, value in graph[front]: if back not in visited: stack.append((back, current * value)) return -1.0 return [check(source, target) for (source, target) in queries]
TCP Header
Implement Trie (Prefix Tree)
我今天是打算去维妈买螃蟹的。
因为昨天自行车放在学校没有骑回家,所以今天是坐电车去学校的。上车的时候,算了一下边际成本,愉快的刷了卡。
到了州立图书馆之后,本来是说要去吃DonDon的,但是想到学校旁边的Don Tojo就突然想吃点别的了。于是找了一家网红店吃了一份鳗鱼饭。
吃完饭,捋了捋自己狂放不羁的头发,顺道去了一趟理发店。理完发,神清气爽的去了维妈。
发现没开门。
之后回学校坐定开始学校,打算随手水道题,于是瞄了一眼问题列表,选了Trie Tree。
以前写Trie都是要写好久的,但是这次居然五分钟不到就一次性Bug Free了,蛮开心的。
↓Code inside ↓
Continue reading