157.Read N Characters Given Read4
边界
"ab" 1
"" 1
165.Compare Version Numbers
https://leetcode.com/problems/compare-version-numbers/
边界
"1.0"
"1"
311Sparse Matrix Multiplication 矩阵乘法回忆
318.Maximum Product of Word Lengths
https://leetcode.com/discuss/74580/bit-shorter-c
unordered_map<int,int> maxlen; //mask maxlen
249.Group Shifted Strings
注意循环
360.Sorted Transformed Array
双曲线，需要注意正负情况
286.Walls and Gates
https://leetcode.com/discuss/82264/benchmarks-of-dfs-and-bfs
错误解法，没有考虑返回的路径上有门的情况：
class Solution {
public:
int dfs(vector<vector<int>>& rooms, int x, int y) {
if(rooms[x][y] == -1) return INT_MAX;
if(rooms[x][y] == 0) return 0;
if(rooms[x][y] != INT_MAX) return rooms[x][y];
rooms[x][y] = -2;
int dis = INT_MAX;
if(x > 0 && rooms[x-1][y] != -2) {
dis = min(dis,dfs(rooms, x-1, y));
}
if(x < rooms.size() - 1 && rooms[x+1][y] != -2) {
dis = min(dis,dfs(rooms, x+1, y));
}
if(y > 0 && rooms[x][y-1] != -2) {
dis = min(dis,dfs(rooms, x, y-1));
}
if(y < rooms[0].size() - 1 && rooms[x][y+1] != -2) {
dis = min(dis,dfs(rooms, x, y+1));
}
rooms[x][y] = (dis == INT_MAX) ? INT_MAX : dis + 1;
return rooms[x][y];
}
void wallsAndGates(vector<vector<int>>& rooms) {
for(int i = 0; i < rooms.size(); i++)
for(int j = 0; j < rooms[0].size(); j++)
dfs(rooms, i, j);
}
};
错误：
[[0,2147483647,2147483647,0,-1,-1,0,0,0,-1,-1,0,2147483647,2147483647],
[2147483647,-1,2147483647,-1,2147483647,0,-1,2147483647,-1,2147483647,2147483647,-1,-1,2147483647],
[0,0,-1,2147483647,-1,2147483647,-1,-1,2147483647,0,0,2147483647,0,2147483647],
[-1,0,2147483647,-1,0,0,-1,2147483647,0,2147483647,0,-1,0,-1]]
0 # # 0 . . 0 0 0 . . 0 # #
# . # . # 0 . # . # # . . #
0 0 . # . # . . # 0 0 # 0 #
. 0 # . 0 0 . # 0 # 0 . 0 .
[[0,1,1,0,-1,-1,0,0,0,-1,-1,0,1,2],
[1,-1,2,-1,1,0,-1,1,-1,1,1,-1,-1,2],
[0,0,-1,2147483647,-1,1,-1,-1,1,0,0,1,0,1],
[-1,0,1,-1,0,0,-1,1,0,1,0,-1,0,-1]]
mine:
[[0,1,1,0,-1,-1,0,0,0,-1,-1,0,1,3],
[1,-1,2,-1,1,0,-1,1,-1,1,1,-1,-1,2],
[0,0,-1,2147483647,-1,1,-1,-1,1,0,0,1,0,1],
[-1,0,1,-1,0,0,-1,1,0,1,0,-1,0,-1]]
正确答案dfs，从每个门开始dfs：
class Solution {
int dirs[5] = {0,1,0,-1,0};
void dfs(vector<vector<int>>& rooms, int x, int y) {
for(int i = 0; i < 4; i++) {
int p = x + dirs[i];
int q = y + dirs[i+1];
if(0 <= p && p < rooms.size() && 0 <= q && q < rooms[0].size())
if(rooms[p][q] > rooms[x][y] + 1) {
rooms[p][q] = rooms[x][y] + 1;
dfs(rooms, p, q);
}
}
}
public:
void wallsAndGates(vector<vector<int>>& rooms) {
for(int i = 0; i < rooms.size(); i++)
for(int j = 0; j < rooms[0].size(); j++)
if(rooms[i][j] == 0)
dfs(rooms, i, j);
}
};
bfs，从门开始bfs:
class Solution {
int dirs[5] = {0,1,0,-1,0};
void bfs(vector<vector<int>>& rooms, int x, int y) {
queue<pair<int,int>> que;
que.push(make_pair(x,y));
int level = 1;
while(!que.empty()) {
int qs = que.size();
for(int i = 0; i < qs; i++) {
auto ele = que.front();
que.pop();
for(int i = 0; i < 4; i++) {
int p = ele.first + dirs[i];
int q = ele.second + dirs[i+1];
if(0 <= p && p < rooms.size() && 0 <= q && q < rooms[0].size())
if(rooms[p][q] > level) {
rooms[p][q] = level;
que.push(make_pair(p,q));
}
}
}
level++;
}
}
public:
void wallsAndGates(vector<vector<int>>& rooms) {
for(int i = 0; i < rooms.size(); i++)
for(int j = 0; j < rooms[0].size(); j++)
if(rooms[i][j] == 0)
bfs(rooms, i, j);
}
};
289 Game of Life
用两位表示当前和下次状态。
251 Flatten 2D Vector
复制数据，很easy。
不复制数据的话，用iterator，存储end和当前it。
215 Kth Largest Element in an Array
https://leetcode.com/discuss/38336/solutions-partition-priority_queue-multiset-respectively
1.O(nlogn)
2.O(nlogk)
3.O(n) O(n2)
4.O(n)
http://blog.csdn.net/acdreamers/article/details/44656295
274 H-Index
输入乱序，
1.先排序好再从i=len->0开始找h，如果citations[len-i] >= i，则h=i
2.bucket sort:
int bucketslen+1;
遍历citations，将citations[i]加入buckets[citations[i]]中，如果citations[i] >= len，将其加入buckets[len]中;
反向遍历buckets，如果nums(nums = buckets[i]从后向前累加的和) >= i，return i
275 H-Index II
输入已经排序好，用binary search即可，最后返回n-l。
134.Gas Station
两种方法：(1)A->B，则A到B
[LeetCode] Gas Station，转化为求最大序列的解法，和更简单简单的Jump解法。
六种姿势拿下连续子序列最大和问题，附伪代码（以HDU 1003 1231为例）、
http://blog.csdn.net/kenden23/article/details/14106137
http://www.cnblogs.com/zzzdevil/p/3651168.html
网友评论