- 382 Linked List Random Node
题意：在不知道长度的链表中随机采样
思路：蓄水池采样
- 384 Shuffle an Array
题意：洗牌
思路：注意是i + rand() % (res.size() - i)而不是rand() % res.size()。即：从拿到的牌中选牌来交换而非整副牌中选牌来交换。
- 385 Mini Parser
思路：关于stringsteam的简单使用
class Solution {
public:
NestedInteger deserialize(string s) {
istringstream in(s);
return deserialize(in);
}
private:
NestedInteger deserialize(istringstream &in){
int num;
if(in >> num)
return NestedInteger(num);
in.clear();
in.get();
NestedInteger list;
while(in.peek() != ']'){
list.add(deserialize(in));
if(in.peek() == ',')
in.get();
}
in.get();
return list;
}
};
- 386 Lexicographical Numbers
题意：字典顺序返回1-n
思路：找规律
- 388 Longest Absolute File Path
题意：最长文件路径长度
思路：stringsteam的简单使用
class Solution {
public:
int lengthLongestPath(string input) {
vector<string> lines;
string s_tmp;
stringstream ss(input);
while(getline(ss, s_tmp, '\n')) lines.push_back(s_tmp);
map<int, int> tool;
int maxlen = 0;
for(auto line : lines){
int last = line.find_first_not_of('\t');
int length = line.size() - last;
if(line.find('.') != -1){
maxlen = max(maxlen, tool[last] + length);
}else{
tool[last + 1] = tool[last] + length + 1;
}
}
return maxlen;
}
};
- 390 Elimination Game
题意：关灯实验，顺序为左右和右左交替。返回最后剩下的等的序号
思路：分治。注意右左的时候需要考虑奇偶的问题
class Solution {
public:
int lastRemaining(int n) {
return help(n, true);
}
int help(int n, bool left2right){
return n == 1 ? 1 : left2right ? 2 * help(n / 2, false)
: 2 * help(n / 2, true) - 1 + (n & 1);
}
};
