这道题没什么特别巧妙的算法,就是纯考代码能力。对于当前数字的下一个数,我们首先考虑能否在后面加0,也就是下x10,如果可以就一直加;如果加不了,那么就在当前位置+1;如果还加不了,比如当前位置是9,或者当前数字已经等于最大值,就要退回前一位尝试+1, 如此不断尝试直到可以加到下一个数。这道题的难点在于分析出所有下一个数的可能性以及退出循环的条件。
class Solution {
public:
vector<int> lexicalOrder(int n) {
std::vector<int> result;
int curr = 1;
for (int i = 1; i <= n; ++i) {
result.push_back(curr);
if (curr * 10 <= n) {
curr *= 10;
} else if (curr % 10 != 9 && curr + 1 <= n) {
curr++;
} else {
while ((curr / 10) % 10 == 9) {
curr /= 10;
}
curr = curr / 10 + 1;
}
}
return result;
}
};
No comments:
Post a Comment