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:
graphwill have length in range[1, 100].graph[i]will contain integers in range[0, graph.length - 1].graph[i]will not containior duplicate values.- The graph is undirected: if any element
jis ingraph[i], theniwill 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