题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
题解
最先浮现在脑中的是一个图的结构。
其实是看起点最远能到达的点吧？动态规划：$dp[i]=max( \sum_{k=1}^{nums[i]}dp[i+k] ,i)$
更进一步，或许连dp数组都不需要呢？还没想出来，先要着吧。
在细节上做了一点修改。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| bool canJump(vector<int>& nums) {
int vsize = nums.size();
bool* dp;
dp = new bool[vsize];
for (int i = 0; i < vsize - 1; i++)
dp[i] = false;
dp[vsize - 1] = true;
int k = vsize - 2;
while (k >= 0)
{
int step = nums[k];
if (k + step >= vsize-1)
dp[k] = true;
else
{
while (!dp[k]&&step)
{
dp[k] = dp[k + step];
step--;
}
}
k--;
}
return dp[0];
}
|
倒是没出什么大问题，只不过时空效率低得没脸看……
题目描述
给出一个区间的集合，请合并所有重叠的区间。
题解
这个时候排序就很重要了。如果是一个二维数组，也可以是用sort，我们可以选择根据某一列来进行排序，如果我们不重写cmp函数，那么默认的是根据第一列来排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| vector<vector<int>> merge(vector<vector<int>>& intervals) {
int vsize = intervals.size();
if (vsize <= 1)return intervals;
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
res.push_back(intervals[0]);
for (int i = 1; i < vsize; i++)
{
if (res.back()[1] >= intervals[i][0])
res.back()[1] = max(res.back()[1], intervals[i][1]);
else
res.push_back(intervals[i]);
}
return res;
}
|