1. find all rotation symmetric numbers less than N digits, 16891 -> 16891,
类似LC #246 Strobogrammatic Number
对称性，11,00,88,69,96. 当n为奇数时，中间为1，8，或0
假设n为位数，k为n位数时rotation symmetric numbers的数量，则：
n = 1, k = 3
n = 2, k = 5
n = 3, k = 3 * 5
n = 4, k = 5 * 5
n = 5, k = 3 * 5 * 5
n = 6, k = 5 * 5 * 5
....
void insertToReturn(vector<string> &rt, vector<string> candidates) {
for (int i = 0; i < candidates.size(); i++) {
rt.push_back(candidates[i]);
}
}
vector<string> pad(vector<string> candidates) {
vector<string> rt;
for (int i = 0; i < candidates.size(); i++) {
rt.push_back("1" + candidates[i] + "1");
rt.push_back("8" + candidates[i] + "8");
rt.push_back("0" + candidates[i] + "0");
rt.push_back("6" + candidates[i] + "9");
rt.push_back("9" + candidates[i] + "6");
}
return rt;
}
vector<string> findAllNumber(int n) {
vector<string> odd;
vector<string> even;
odd.push_back("1");
odd.push_back("8");
odd.push_back("0");
even.push_back("11");
even.push_back("88");
even.push_back("00");
even.push_back("69");
even.push_back("96");
if (n == 1) return odd;
if (n == 2) {
insertToReturn(odd,even);
return odd;
}
vector<string> rt;
insertToReturn(rt,odd);
insertToReturn(rt,even);
for (int i = 3; i <= n; i++) {
if (i % 2 == 1) {
odd = pad(odd);
insertToReturn(rt,odd);
}else {
even = pad(even);
insertToReturn(rt,even);
}
}
return rt;
}
2. give integer, 12345, 返回 32154
先把integer转为string，然后前半部分翻转，再后半部分翻转
或直接数一下integer一共多少位
give a target string and list of strings, find the longest string that
has target as prefix, follow up, stream of target string, 用trie，每个节点保
留最长string信息。
3. integer array add one
rotation abc->bcd->cde, give a list of strings, group them if them are
rotations.
居然给我laptop，然后直接上面写，然后debug通过，给test case通过
4. given grid of colors, coordinate of a point and its color, find the
perimeter of the region that has the same color of that point.
BFS或DFS，构成perimeter的条件是只要上下左右有一个不是同颜色或者是out of bound
用一个set记录visit的信息
print all morse code given the length constraints, short “*” takes one
, long “——“takes two. (find a bug in the code) 就是排列组合的典型题
5. design: chromecast, how to know which app can be supported? There is a
cloud that can give the information to the chrome cast, appID, deviceID,
cache design.
---------------------------------------------------------------
REF: http://www.mitbbs.com/article_t/JobHunting/32882153.html
continental divider
给一个矩阵，其中0代表海洋，其他数字代表高度，秉着水往低处流的原则，求出能够
流向任意海洋的点。 比如说
0 0 0 1 2 3 0
0 1 2 2 4 3 2
2 1 1 3 3 2 0
0 3 3 3 2 3 3
那么就要给出 第二行的4 （这有这点出发，能够找到连通道四个0的区域的一条非递增
路线），当然也有可能找不到这样的点，或者找到多个点。
对每一个ocean，找出所有它能流通的山脉，然后在相应的位置上 + 1,
最后对比所有位置上的数与ocean的个数
void dfs(vector<vector<int> > &grid,vector<vector<int> > &count,vector<vector<bool>> &visit,int row,int col,int pre) {
if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || visit[row][col]) {
return;
}
visit[row][col] = true;
if (grid[row][col] != 0 && grid[row][col] < pre) {
return;
}
count[row][col]++;
//cout << row << " " << col << endl;
dfs(grid,count,visit,row + 1,col,grid[row][col]);
dfs(grid,count,visit,row - 1,col,grid[row][col]);
dfs(grid,count,visit,row,col + 1,grid[row][col]);
dfs(grid,count,visit,row,col - 1,grid[row][col]);
}
bool flow(vector<vector<int>> &grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> count(m,vector<int>(n,0));
int oceanSize = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
vector<vector<bool>> visit(m,vector<bool>(n,false));
oceanSize++;
dfs(grid,count,visit,i,j,0);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (count[i][j] == oceanSize) {
cout << i << " " << j << endl;
}
}
}
}
--------------------------------------------------------------------REF http://www.mitbbs.com/article_t1/JobHunting/33004699_0_1.html
1. 二维matrix，含0，1。 1是障碍。
00011
11100
从左上角出发到右下角， 可以往上，往下，往右移动。
把1变成0，使得你可以从左上角到右下角。
求最小的变化数字。
2个角度(dfs / bfs)
#1 找出所有路径中，含1最少的那个路径
#2 最短路径，每个路径weight为0或者1, dijkstra
Dijkstra为O(n*lgn)，可用2个queue降低复杂度为O(n)。因为edge的weight只为0或1
bool bfs(vector<vector<int> > &grid,vector<vector<bool> > &visit,queue<pair<int,int>> &q1,queue<pair<int,int>> &q2) {
while (!q1.empty()) {
int row = q1.front().first;
int col = q1.front().second;
if (row == grid.size() - 1 && col == grid[0].size() - 1) {
return true;
}
q1.pop();
if (row + 1 < grid.size() && !visit[row + 1][col]) {
visit[row + 1][col] = true;
if (grid[row + 1][col] == 0) {
q1.push(make_pair(row + 1,col));
}else {
q2.push(make_pair(row + 1,col));
}
}
if (row - 1 >= 0 && !visit[row - 1][col]) {
visit[row - 1][col] = true;
if (grid[row - 1][col] == 0) {
q1.push(make_pair(row - 1,col));
}else {
q2.push(make_pair(row - 1,col));
}
}
if (col + 1 < grid[0].size() && !visit[row][col + 1]) {
visit[row][col + 1] = true;
if (grid[row][col + 1] == 0) {
q1.push(make_pair(row,col + 1));
}else {
q2.push(make_pair(row,col + 1));
}
}
if (col - 1 >= 0 && !visit[row][col - 1]) {
visit[row][col - 1] = true;
if (grid[row][col - 1] == 0) {
q1.push(make_pair(row,col - 1));
}else {
q2.push(make_pair(row,col - 1));
}
}
}
return false;
}
int findPath(vector<vector<int> > &grid) {
int m = grid.size();
int n = grid[0].size();
queue<pair<int,int>> q1;
queue<pair<int,int>> q2;
int count = 0;
q1.push(make_pair(0,0));
vector<vector<bool> > visit(m,vector<bool>(n,false));
visit[0][0] = true;
while (!q1.empty()) {
if (bfs(grid,visit,q1,q2)) {
return count;
}
count++;
queue<pair<int,int>> empty;
q1 = q2;
swap(q2,empty);
}
return -1;
}
2。 两个区间，左闭右开。数字可以是整数或者浮点，
要你判断两个区间是否相交。
特殊例子需要你自己定义。
No comments:
Post a Comment