分享我的Lintcode题解，目前进度244/248

zhuli19901106

Sliding Window Median
题意：hard难度。经过了Sliding Window Maximum之后，这题就简单多了。
解法：在那题里我就说了，用map，也就是平衡树可以有效地求可变数组的最小值、最大值、中位数。具体怎么求中位呢？把大小为K的窗口分两半即可。类似的问题还有这个：“向一个空数组中不断添加元素，每添加一个，就求一次中位数。”
这题可以用堆来做，对吧？但Sliding Window Median就不行。因为堆可以随意添加，却不能随意删除，也就是说删什么不由我们决定，而map就可以。
这道题的思路很清晰，但是动手写起来才发现也不简单，需要考虑周全。我出了一两次bug才通过。算是名副其实的hard难度。
代码：

// <map> is a powerful magic
#include <map>
using namespace std;
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: The median of the element inside the window at each moving
*/
vector<int> medianSlidingWindow(vector<int> &nums, int k) {
small.clear();
large.clear();
ns = nl = 0;
vector<int> ans;
vector<int> &a = nums;
int n = a.size();
if (n == 0 || k == 0) {
return ans;
}
ns = nl = 0;
int s, l;
int i;
for (i = 0; i < k - 1; ++i) {
add(a[i]);
}
for (i = k - 1; i < n; ++i) {
add(a[i]);
ans.push_back(small.rbegin()->first);
remove(a[i - k + 1]);
}
return ans;
}
private:
map<int, int> small, large;
int ns, nl;
void del(map<int, int> &m, int x) {
--m[x];
if (m[x] == 0) {
m.erase(x);
}
}
void adjust() {
if (small.empty() || large.empty()) {
return;
}
int n1, n2;
n1 = small.rbegin()->first;
n2 = large.begin()->first;
if (n1 <= n2) {
return;
}
del(small, n1);
++small[n2];
del(large, n2);
++large[n1];
}
void add(int x) {
if (ns == nl) {
++small[x];
++ns;
} else {
++large[x];
++nl;
}
adjust();
}
void remove(int x) {
if (small.find(x) != small.end()) {
del(small, x);
--ns;
} else {
del(large, x);
--nl;
}
if (ns < nl) {
++small[large.begin()->first];
del(large, large.begin()->first);
++ns;
--nl;
} else if (ns > nl + 1) {
++large[small.rbegin()->first];
del(small, small.rbegin()->first);
--ns;
++nl;
}
adjust();
}
};

复制代码

复杂度：时间O(N * log(K))，空间O(N)。

zhuli19901106

Trapping Rain Water II
题意：hard难度。把Trapping Rain Water扩展到三维，给定每个点(X,Y)的高度Z，求这个形状能存多少水。
解法：这题真难，我独立想了一个多小时，才发现自己把题目理解错了，然后又独立想了一个多小时，没思路。对于一维的问题，你可以只考虑左边右边的情况如何，但对于二维的问题，你不能仅仅考虑前后左右四个方向的情况。应该怎么考虑呢？这是水，可以流动，所以应该用BFS搜（要用BFS，因为这符合自然规律）。这个代码我是参考了github上其他人的做法，所以理解不深，无法讲清楚。注意其中BFS用的是堆，而不是队列，这是整个算法的核心。真心巧妙。
代码：

// Think about the heap, why pick the lowest altitude?
#include <algorithm>
#include <queue>
using namespace std;
typedef struct Term {
int i, j, h;
Term(int _i = 0, int _j = 0, int _h = 0): i(_i), j(_j), h(_h) {}
bool operator < (const Term &t) const {
return h > t.h;
}
} Term;
class Solution {
public:
Solution() {
offset.resize(4, vector<int>(2));
offset[0][0] = +1;
offset[0][1] = 0;
offset[1][0] = -1;
offset[1][1] = 0;
offset[2][0] = 0;
offset[2][1] = +1;
offset[3][0] = 0;
offset[3][1] = -1;
}
/**
* @param heights: a matrix of integers
* @return: an integer
*/
int trapRainWater(vector<vector<int> > &heights) {
v.clear();
vector<vector<int> > &a = heights;
n = a.size();
m = n ? a[0].size() : 0;
if (n == 0 || m == 0) {
return 0;
}
int i, j;
v.resize(n, vector<bool>(m, false));
for (i = 0; i < n; ++i) {
pq.push(Term(i, 0, a[i][0]));
v[i][0] = true;
pq.push(Term(i, m - 1, a[i][m - 1]));
v[i][m - 1] = true;
}
for (i = 0; i < m; ++i) {
pq.push(Term(0, i, a[0][i]));
v[0][i] = true;
pq.push(Term(n - 1, i, a[n - 1][i]));
v[n - 1][i] = true;
}
Term t, t1;
int ans = 0;
while (!pq.empty()) {
t = pq.top();
pq.pop();
for (i = 0; i < 4; ++i) {
t1.i = t.i + offset[i][0];
t1.j = t.j + offset[i][1];
if (!inbound(t1.i, t1.j) || v[t1.i][t1.j]) {
continue;
}
ans += max(0, t.h - a[t1.i][t1.j]);
t1.h = max(t.h, a[t1.i][t1.j]);
pq.push(t1);
v[t1.i][t1.j] = true;
}
}
return ans;
}
private:
vector<vector<int> > offset;
int n, m;
priority_queue<Term> pq;
vector<vector<bool> > v;
bool inbound(int x, int y) {
return x >= 0 && x <= n - 1 && y >= 0 && y <= m - 1;
}
};

复制代码

复杂度：时间O(N * M * log(N * M))，空间O(N * M)。

zhuli19901106

Expression Evaluation
题意：hard难度。给定一个已经分割好的算术表达式，求值。
解法：首先，看见这题我就改python了，用C++感觉太麻烦。python里的正则和lambda函数能派上用场。这题要处理的难点有两点，一是括号，二是优先级处理。具体的处理方法可以网上搜。我在搜之前，完全不知道该怎么干。剩下的就是实现了，参见代码。符号优先级不要用硬编码的方式处理，写一堆if elif是很低效的，直接把优先级定义成一个数值，就可以一套逻辑统一处理了。所谓代码与配置分离嘛。
这题存在非法case，感觉不合理。
代码：

# There're some illegal cases, it's unfair
import re
class Solution:
# Define the precedence of operators
__pre = {}
__fun = {}
def __init__(self):
pre_count = -1
self.__pre['('] = pre_count
pre_count += 1
self.__pre['+'] = pre_count
self.__pre['-'] = pre_count
pre_count += 1
self.__pre['*'] = pre_count
self.__pre['/'] = pre_count
self.__pre['%'] = pre_count
pre_count += 1
self.__fun['+'] = lambda x, y: x + y
self.__fun['-'] = lambda x, y: x - y
self.__fun['*'] = lambda x, y: x * y
self.__fun['/'] = lambda x, y: x / y
self.__fun['%'] = lambda x, y: x % y
# @param expression: a list of strings;
# @return: an integer
def evaluateExpression(self, expression):
if (len(expression) == 0):
return 0
num = []
op = []
for token in expression:
if re.match(r'[+\-]?\d+', token):
num.append(int(token))
elif token == '(':
op.append(token)
elif token == ')':
while op[-1] != '(':
self.__calculate(num, op)
op.pop()
else:
while len(op) > 0 and self.__pre[op[-1]] >= self.__pre[token]:
self.__calculate(num, op)
op.append(token)
while len(op) > 0:
self.__calculate(num, op)
return num.pop() if len(num) > 0 else 0
def __calculate(self, num, op):
n2 = num.pop()
n1 = num.pop()
single_op = op.pop()
num.append(self.__fun[single_op](n1, n2))

复制代码

复杂度：时间O(N)，空间O(N)。

zhuli19901106

Permutation Sequence
题意：给出长度为N的全排列中，字典序第K位的那个。
解法：考虑问题和子问题的关系。
代码：

class Solution {
public:
/**
* @param n: n
* @param k: the kth permutation
* @return: return the k-th permutation
*/
string getPermutation(int n, int k) {
string ans = "";
--k;
vector<int> v;
int f = 1;
int i, j;
for (i = 1; i < n; ++i) {
f *= i;
}
v.resize(n);
for (i = 0; i < n; ++i) {
v[i] = i;
}
int p;
for (i = n - 1; i >= 1; --i) {
p = k / f;
k %= f;
ans.push_back('1' + v[p]);
for (j = p; j < i; ++j) {
v[j] = v[j + 1];
}
v.pop_back();
f /= i;
}
ans.push_back('1' + v[0]);
return ans;
}
};

复制代码

复杂度：时间O(N ^ 2)，空间O(1)。

zhuli19901106

Count of Smaller Number
题意：给定一个数组，每次query给定一个数target，求出数组中小于target的元素的个数。
解法：因为数组本身不会变，所有直接排好序二分搜索即可。（这种题用线段树不是画蛇添足么）
代码：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param A: An integer array
* @return: The number of element in the array that
* are smaller that the given integer
*/
vector<int> countOfSmallerNumber(vector<int> &A, vector<int> &queries) {
int n = queries.size();
int i, j;
vector<int> ans;
sort(A.begin(), A.end());
for (i = 0; i < n; ++i) {
j = lower_bound(A.begin(), A.end(), queries[i]) - A.begin();
ans.push_back(j);
}
return ans;
}
};

复制代码

复杂度：时间O((N + K) * log(N))，空间O(1)。

zhuli19901106

Building Outline
题意：hard难度。
解法：真难。我都懒得解释了，独立想了两个多钟头才想出来。最终确定了用map的解法。注意解法的思路在于把每个建筑的开始和结束分开想，随时关注最大高度是否发生了变化，一旦变化了，就说明轮廓有拐角了。
代码：

#include <algorithm>
#include <map>
using namespace std;
struct Term {
int x, y;
int op;
bool operator < (const Term &t) const {
if (x != t.x) {
return x < t.x;
}
if (op != t.op) {
return op < t.op;
}
if (op == 0) {
// Start of a building
return y > t.y;
} else {
// End of a building
return y < t.y;
}
}
};
class Solution {
public:
/**
* @param buildings: A list of lists of integers
* @return: Find the outline of those buildings
*/
vector<vector<int> > buildingOutline(vector<vector<int> > &buildings) {
vector<vector<int> > &a = buildings;
vector<Term> v;
Term t;
int n = a.size();
int i;
for (i = 0; i < n; ++i) {
t.x = a[i][0];
t.y = a[i][2];
t.op = 0;
v.push_back(t);
t.x = a[i][1];
t.y = a[i][2];
t.op = 1;
v.push_back(t);
}
sort(v.begin(), v.end());
map<int, int> m;
vector<int> px, py;
bool b;
m[0] = 1;
n = v.size();
for (i = 0; i < n; ++i) {
if (v[i].op == 0) {
// Start of a building
if (m.rbegin()->first < v[i].y) {
px.push_back(v[i].x);
py.push_back(v[i].y);
}
++m[v[i].y];
} else {
// End of a building
b = false;
--m[v[i].y];
if (m[v[i].y] == 0) {
b = v[i].y == m.rbegin()->first;
m.erase(v[i].y);
}
if (b) {
px.push_back(v[i].x);
py.push_back(m.rbegin()->first);
}
}
}
n = px.size();
vector<vector<int> > ans;
vector<int> seg(3);
for (i = 0; i < n - 1; ++i) {
// Ignore all zeros
if (py[i] == 0) {
continue;
}
seg[0] = px[i];
seg[1] = px[i + 1];
seg[2] = py[i];
ans.push_back(seg);
}
return ans;
}
};

复制代码

复杂度：时间O(N * log(N))，空间O(N)。

zhuli19901106

本帖最后由 zhuli19901106 于 2015-7-25 01:26 编辑

Convert Expression to Polish Notation
题意：hard难度。给定一个分割过的表达式，把它转化为波兰表达式。
解法：其实这题是为了帮助理解表达式树的作用。结合之前表达式求值那题，经过适当的修改，就可以用同样的方法构造出一棵表达式树，而表达式树的前序遍历就是波兰表达式。不建树应该也可以做，但是我觉得代码已经比较复杂了，如果还耗脑子写个非递归版的前序遍历，怕是要出bug，所以就不找麻烦了。
代码：

import re
'''
Definition of ExpressionTreeNode:
class ExpressionTreeNode:
def __init__(self, symbol):
self.symbol = symbol
self.left, self.right = None, None
'''
ETN = ExpressionTreeNode
class Solution:
# Define the precedence of operators
__pre = {}
__fun = {}
def __init__(self):
pre_count = -1
self.__pre['('] = pre_count
pre_count += 1
self.__pre['+'] = pre_count
self.__pre['-'] = pre_count
pre_count += 1
self.__pre['*'] = pre_count
self.__pre['/'] = pre_count
self.__pre['%'] = pre_count
pre_count += 1
# @param expression: A string list
# @return: The Polish notation of this expression
def convertToPN(self, expression):
if (len(expression) == 0):
return None
num = []
op = []
for token in expression:
if re.match(r'[+\-]?\d+', token):
num.append(ETN(token))
elif token == '(':
op.append(token)
elif token == ')':
while op[-1] != '(':
self.__calculate(num, op)
op.pop()
else:
while len(op) > 0 and self.__pre[op[-1]] >= self.__pre[token]:
self.__calculate(num, op)
op.append(token)
while len(op) > 0:
self.__calculate(num, op)
ans = []
root = num.pop() if len(num) > 0 else None
self.__preorder(root, ans)
return ans
def __calculate(self, num, op):
n2 = num.pop()
n1 = num.pop()
single_op = ETN(op.pop())
single_op.left = n1
single_op.right = n2
num.append(single_op)
def __preorder(self, root, ans):
if root == None:
return
ans.append(root.symbol)
self.__preorder(root.left, ans)
self.__preorder(root.right, ans)

复制代码

复杂度：时间O(N)，空间O(N)。

zhuli19901106

本帖最后由 zhuli19901106 于 2015-7-25 01:25 编辑

Convert Expression to Reverse Polish Notation
题意：hard难度。给定一个分割过的表达式，把它转化为逆波兰表达式。
解法：和上次波兰表达式一样，构造表达式树，然后进行后序遍历即可。
代码：

import re
'''
Definition of ExpressionTreeNode:
class ExpressionTreeNode:
def __init__(self, symbol):
self.symbol = symbol
self.left, self.right = None, None
'''
ETN = ExpressionTreeNode
class Solution:
# Define the precedence of operators
__pre = {}
__fun = {}
def __init__(self):
pre_count = -1
self.__pre['('] = pre_count
pre_count += 1
self.__pre['+'] = pre_count
self.__pre['-'] = pre_count
pre_count += 1
self.__pre['*'] = pre_count
self.__pre['/'] = pre_count
self.__pre['%'] = pre_count
pre_count += 1
# @param expression: A string list
# @return: The Reverse Polish notation of this expression
def convertToRPN(self, expression):
if (len(expression) == 0):
return None
num = []
op = []
for token in expression:
if re.match(r'[+\-]?\d+', token):
num.append(ETN(token))
elif token == '(':
op.append(token)
elif token == ')':
while op[-1] != '(':
self.__calculate(num, op)
op.pop()
else:
while len(op) > 0 and self.__pre[op[-1]] >= self.__pre[token]:
self.__calculate(num, op)
op.append(token)
while len(op) > 0:
self.__calculate(num, op)
ans = []
root = num.pop() if len(num) > 0 else None
self.__postorder(root, ans)
return ans
def __calculate(self, num, op):
n2 = num.pop()
n1 = num.pop()
single_op = ETN(op.pop())
single_op.left = n1
single_op.right = n2
num.append(single_op)
def __postorder(self, root, ans):
if root == None:
return
self.__postorder(root.left, ans)
self.__postorder(root.right, ans)
ans.append(root.symbol)

复制代码

复杂度：时间O(N)，空间O(N)。

zhuli19901106

Expression Tree Build
题意：hard难度。给定一个分割过的算术表达式，构造表达式树。
解法：教学题。还是根据表达式求值那题的处理思路修改得来。总之，这些题的规则都是相同的。最好理解+记忆，这样面试遇到了才不会抓瞎。
代码：

import re
"""
Definition of ExpressionTreeNode:
class ExpressionTreeNode:
def __init__(self, symbol):
self.symbol = symbol
self.left, self.right = None, None
"""
ETN = ExpressionTreeNode
class Solution:
# Define the precedence of operators
__pre = {}
__fun = {}
def __init__(self):
pre_count = -1
self.__pre['('] = pre_count
pre_count += 1
self.__pre['+'] = pre_count
self.__pre['-'] = pre_count
pre_count += 1
self.__pre['*'] = pre_count
self.__pre['/'] = pre_count
self.__pre['%'] = pre_count
pre_count += 1
# @param expression: A string list
# @return: The root of expression tree
def build(self, expression):
if (len(expression) == 0):
return None
num = []
op = []
for token in expression:
if re.match(r'[+\-]?\d+', token):
num.append(ETN(token))
elif token == '(':
op.append(token)
elif token == ')':
while op[-1] != '(':
self.__calculate(num, op)
op.pop()
else:
while len(op) > 0 and self.__pre[op[-1]] >= self.__pre[token]:
self.__calculate(num, op)
op.append(token)
while len(op) > 0:
self.__calculate(num, op)
return num.pop() if len(num) > 0 else None
def __calculate(self, num, op):
n2 = num.pop()
n1 = num.pop()
single_op = ETN(op.pop())
single_op.left = n1
single_op.right = n2
num.append(single_op)

复制代码

复杂度：时间O(N)，空间O(N)。

zhuli19901106

Valid Sudoku
题意：给定一个数独，检查是否有效。只要不存在冲突，就算有效。数独规则就不说了。
解法：按规则检查即可。
代码：

#include <cmath>
using namespace std;
class Solution {
public:
/**
* @param board: the board
* @return: wether the Sudoku is valid
*/
bool isValidSudoku(const vector<vector<char> >& board) {
int n2 = board.size();
int n = (int)sqrt(n2);
vector<vector<bool> > row;
vector<vector<bool> > col;
vector<vector<bool> > block;
row.resize(n2, vector<bool>(n2, false));
col.resize(n2, vector<bool>(n2, false));
block.resize(n2, vector<bool>(n2, false));
int i, j;
int idx;
for (i = 0; i < n2; ++i) {
for (j = 0; j < n2; ++j) {
if (board[i][j] == '.') {
continue;
}
idx = board[i][j] - '1';
if (row[i][idx]) {
return false;
}
row[i][idx] = true;
if (col[j][idx]) {
return false;
}
col[j][idx] = true;
if (block[i / n * n + j / n][idx]) {
return false;
}
block[i / n * n + j / n][idx] = true;
}
}
return true;
}
};

复制代码

复杂度：时间O(N ^ 2)，空间O(N ^ 2)。

分享我的Lintcode题解，目前进度244/248

浏览过的版块