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

zhuli19901106

本帖最后由 zhuli19901106 于 2015-7-24 07:38 编辑

水逼一枚发表于 2015-7-24 06:01
我想问一下，像这个题还有类似的题目出现过的吗？就是利用HashMap左右延展来解题这类似的题目？这题想了 ...

用DP的前提是能知道“问题”与“子问题”之间的递推关系。这题并不存在和子问题的关联，所以DP无从说起。
另外，你说hashmap向两边延伸，感觉说的也太具体了吧。。不论hashmap还是map，各有各的特点，因为特点不同，所以用处就不同。并没有什么固定解法，规定一个数据结构一定要怎么用。

比如一个RMQ问题，就可以用好多数据结构来解。关键是，每种解法，写的人都清楚自己要怎么用一个数据结构。
你不妨试试building outline那题？看看什么数据结构好用。还有sliding window median。

zhuli19901106

本帖最后由 zhuli19901106 于 2015-7-24 07:57 编辑

水逼一枚发表于 2015-7-24 06:01
我想问一下，像这个题还有类似的题目出现过的吗？就是利用HashMap左右延展来解题这类似的题目？这题想了 ...

倒不是说hard题目都出现在数组上，只是因为数组和链表是最简单的数据结构，实现起来相对容易，所以面试考的尽是这些。要考其他的简直没法搞~
我们在这儿讨论的东西，专业选手们小学初中就已经会了。

zhuli19901106

Interval Sum
题意：给定一个数组，每次给你起点终点的下标，求子数组和。
解法：这题的提示居然是用线段树做，实际上这题中数组的内容不会变，所以直接求和即可，没必要用线段树或者树状数组。
代码：

typedef long long int LL;
/**
* Definition of Interval:
* classs Interval {
* int start, end;
* Interval(int start, int end) {
* this->start = start;
* this->end = end;
* }
*/
class Solution {
public:
/**
*@param A, queries: Given an integer array and an query list
*@return: The result list
*/
vector<LL> intervalSum(vector<int> &A, vector<Interval> &queries) {
vector<LL> sum;
int n = A.size();
sum.resize(n + 1, 0);
int i;
for (i = 0; i < n; ++i) {
sum[i + 1] = sum[i] + A[i];
}
vector<LL> ans;
int m = queries.size();
for (i = 0; i < m; ++i) {
ans.push_back(sum[queries[i].end + 1] - sum[queries[i].start]);
}
return ans;
}
};

复制代码

复杂度：预处理时间O(N)，每次求和时间O(1)，空间O(N)。

zhuli19901106

Interval Sum II
题意：hard难度。给定一个数组，要求实现修改单个元素，子数组求和两个功能，复杂度都是O(log(N))。
解法：树状数组，此时不用更待何时。
代码：

typedef long long int LL;
class Solution {
public:
/**
* @param A: An integer vector
*/
Solution(vector<int> A) {
n = A.size();
a.resize(n + 1, 0);
int i;
for (i = 0; i < n; ++i) {
add(i + 1, A[i]);
}
}
/**
* @param start, end: Indices
* @return: The sum from start to end
*/
LL query(int start, int end) {
++start;
++end;
return sum(end) - sum(start - 1);
}
/**
* @param index, value: modify A[index] to value.
*/
void modify(int index, int value) {
int oldValue = query(index, index);
++index;
add(index, value - oldValue);
}
private:
vector<LL> a;
int n;
int lowbit(int x) {
return x & -x;
}
void add(int index, int value) {
while (index <= n) {
a[index] += value;
index += lowbit(index);
}
}
LL sum(int index) {
LL s = 0;
while (index > 0) {
s += a[index];
index -= lowbit(index);
}
return s;
}
};

复制代码

复杂度：单次操作时间O(log(N))，全局空间O(N)。

zhuli19901106

Segment Tree Query II
题意：其实还是区间求和，不过这次线段树已经建好了，实现求和函数。
解法：因为是教学题目，所以按照提示完成即可。
代码：

/**
* Definition of SegmentTreeNode:
* class SegmentTreeNode {
* public:
* int start, end, count;
* SegmentTreeNode *left, *right;
* SegmentTreeNode(int start, int end, int count) {
* this->start = start;
* this->end = end;
* this->count = count;
* this->left = this->right = NULL;
* }
* }
*/
typedef SegmentTreeNode STN;
class Solution {
public:
/**
*@param root, start, end: The root of segment tree and
* an segment / interval
*@return: The count number in the interval [start, end]
*/
int query(STN *root, int start, int end) {
if (root == NULL) {
return 0;
}
if (start > root->end || end < root->start || start > end) {
return 0;
}
if (root->start == root->end) {
return root->count;
}
int mid = root->start + (root->end - root->start) / 2;
if (end <= mid) {
return query(root->left, start, end);
}
if (start >= mid + 1) {
return query(root->right, start, end);
}
int c1 = root->start == start ? root->left->count :
query(root->left, start, mid);
int c2 = root->end == end ? root->right->count :
query(root->right, mid + 1, end);
return c1 + c2;
}
};

复制代码

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

zhuli19901106

First Missing Positive
题意：给定一个整数数组，求其中不包含的最小整数。
解法：这题用哈希表肯定容易做，O(N)时间，O(N)空间。于是我们要想出O(1)空间的解法。注意，一个长度为N的数组，至多包含了1-N，那么解就是N+1。对于其他情况，解必然在1-N之间。所以我们直接用原数组当成哈希表来用。请看代码。
代码：

class Solution {
public:
/**
* @param A: a vector of integers
* @return: an integer
*/
int firstMissingPositive(vector<int> A) {
int n = A.size();
if (n == 0) {
return 1;
}
int i;
for (i = 0; i < n; ++i) {
if (A[i] <= 0 || A[i] > n) {
A[i] = n + 1;
}
}
for (i = 0; i < n; ++i) {
if (abs(A[i]) > n) {
continue;
} else if (A[abs(A[i]) - 1] > 0) {
A[abs(A[i]) - 1] *= -1;
}
}
for (i = 0; i < n; ++i) {
if (A[i] > 0) {
return i + 1;
}
}
return n + 1;
}
private:
int abs(int x) {
return x >= 0 ? x : -x;
}
};

复制代码

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

caffery24

给楼主赞一个啊。。。好羡慕楼主的意志力，楼主是研究生要毕业找工作吗？

zhuli19901106

caffery24 发表于 2015-7-24 20:44
给楼主赞一个啊。。。好羡慕楼主的意志力，楼主是研究生要毕业找工作吗？

不是，是研究生刚要开学~

zhuli19901106

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

Sliding Window Maximum
题意：hard难度。给定一个长度为N的数组，有一个宽度为K的滑动窗口，从头移到尾。每滑动一位，请给出窗口中的最大值。
解法：这题借助map的平衡树结构可以在logK时间内取得窗口最大值。不过这题自然有更优化的方法，就是单调队列。参见此题解http://blog.csdn.net/justmeh/article/details/5844650其中使用到的不是queue，而是deque，因为需要尾部入队，头尾出队的功能。
代码：

#include <deque>
using namespace std;
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: The maximum number inside the window at each moving.
*/
vector<int> maxSlidingWindow(vector<int> &nums, int k) {
d.clear();
vector<int> ans;
vector<int> &a = nums;
int n = a.size();
if (n == 0 || k == 0) {
return ans;
}
int i;
for (i = 0; i < k - 1; ++i) {
enQueue(a, i, k);
}
for (i = k - 1; i < n; ++i) {
enQueue(a, i, k);
ans.push_back(a[d.front()]);
}
return ans;
}
private:
deque<int> d;
void enQueue(vector<int> &a, int i, int k) {
while (!d.empty() && i - d.front() >= k) {
d.pop_front();
}
while (!d.empty() && a[d.back()] < a[i]) {
d.pop_back();
}
d.push_back(i);
}
};

复制代码

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

zhuli19901106

Trapping Rain Water
题意：给定类似直方图的形状，规定每条的宽度都是1。如果下雨的话，这形状能攒下多少水。
解法：这题挺好玩，第一次碰见的时候，我还想了好久如何找峰值、谷值，后来没想出好的思路。看了别人的思路后，才发现自己考虑问题的方式就错了。
关键思路在于把每一条分开想，如果左右都存在比它高的，那么这条就能存水，否则就存不了水。
代码：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param heights: a vector of integers
* @return: a integer
*/
int trapRainWater(vector<int> &heights) {
int n = heights.size();
if (n == 0) {
return 0;
}
vector<int> ll, rr;
ll.resize(n);
rr.resize(n);
int i;
int mx = 0;
for (i = 0; i <= n - 1; ++i) {
ll[i] = mx;
mx = max(mx, heights[i]);
}
mx = 0;
for (i = n - 1; i >= 0; --i) {
rr[i] = mx;
mx = max(mx, heights[i]);
}
int ans = 0;
for (i = 0; i <= n - 1; ++i) {
mx = max(0, min(ll[i], rr[i]) - heights[i]);
ans += mx;
}
return ans;
}
};

复制代码

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