一、题目描述
942、增减字符串匹配
由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:
如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I'
如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D'
给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。
示例：
输入：
s
=
"IDID"
\texttt{s = "IDID"}
s = "IDID"
输出：
[0,4,1,3,2]
\texttt{[0,4,1,3,2]}
[0,4,1,3,2]
二、题目分析
（1）题目中明确说明答案数组的元素是 [0, n] 中的元素的某种排列；
（2）贪心的思想，每次遇到 'I' ，就填充一个当前的最小值，遇到 'D' 就填充一个当前的最大值；
（3）贪心思想，局部最优以满足全局最优。
三、代码实现
class Solution {
public:
vector<int> diStringMatch(string s) {
int i, n = s.size();
vector<int> ret(n+1);
int lo = 0, hi = n;
for(i = 0; i < n; ++i){
ret[i] = (s[i] == 'I' ? lo++ : hi--);
}
ret[n] = lo;
return ret;
}
};
四、总结
1、回顾一下
vector
\texttt{vector}
vector 容器的几种初始化操作
| 序号 |
初始化方法 |
说明 |
| ① |
v
e
c
t
o
r
<
T
>
v
vector<T> v
vector<T>v |
初始化为空，容器内无元素，对应插入元素操作是 push_back() 和emplace_back() 。 |
| ② |
v
e
c
t
o
r
<
T
>
v
1
(
n
)
vector<T> v_1(n)
vector<T>v1(n),
v
e
c
t
o
r
<
T
>
v
1
(
n
,
v
a
l
)
vector<T> v_1(n, val)
vector<T>v1(n,val)
|
v
1
v_1
v1 包含了 n 个重复的元素，未指定 val 值的时候，初始化元素默认是 0 。 |
| ③ |
v
e
c
t
o
r
<
T
>
v
2
{
1
,
2
,
3
,
5
}
vector<T>v_2{\{1, 2, 3, 5\}}
vector<T>v2{1,2,3,5}，
v
e
c
t
o
r
<
T
>
v
2
=
{
1
,
2
,
3
,
5
}
vector<T>v_2 ={\{1, 2, 3, 5\}}
vector<T>v2={1,2,3,5}
|
预先赋值初始化，
v
2
v_2
v2 包含了初始值个数的元素，每个元素被赋予了对应的初始值。 |
| ④ |
v
e
c
t
o
r
<
T
>
v
3
(
v
2
)
vector<T>v_3(v_2)
vector<T>v3(v2) ,
v
e
c
t
o
r
<
T
>
v
3
(
v
2
.
b
e
g
i
n
(
)
,
v
2
.
e
n
d
(
)
)
vector<T>v_3(v_2.begin(), v_2.end())
vector<T>v3(v2.begin(),v2.end())
|
拷贝初始化,
v
3
v_3
v3 中包含有
v
2
v_2
v2 所有元素的副本。 |
