A*******e
发帖数: 2419 | 1 不会是只看最优解的长度吧？
那两道Excel的题，如果想不到变形十进制，写起来很繁琐。还有那个zigzag
conversion，代码不长，但数组下标很容易算错。 | A*******e
发帖数: 2419 | 2 写了一个zigzag，通过了测试，但运行时间在C++里算慢的，相当于C#的水平。谁有更
简洁的
解法？index计算太容易错了，必须在纸上分析清楚才行。
class Solution {
public:
string convert(string s, int nRows) {
if (nRows == 1) {
return s;
}
vector char_rank;
for (int i = 0; i < s.size(); ++i) {
char_rank.push_back({s[i], GetNewIndex(i, nRows)});
}
sort(char_rank.begin(), char_rank.end(), CharRankComp());
string result;
for (const auto& it : char_rank) {
result.push_back(it.c);
}
return result;
}
private:
struct CharRank {
char c;
pair rank;
};
struct CharRankComp {
bool operator()(const CharRank& x, const CharRank& y) {
return (x.rank.first < y.rank.first) ||
(x.rank.first == y.rank.first && x.rank.second < y.rank.
second);
}
};
// Given the global index of a char, find its new index in the zig zag
form.
pair GetNewIndex(int index, int nRows) {
const int group_size = 2 * (nRows - 1);
const int group_id = index / group_size;
const int group_idx = index % group_size;
const int row = group_idx < nRows ?
group_idx : group_size - group_idx;
const int col = group_id * (nRows - 1) +
(group_idx < nRows ? 0 : group_idx - (nRows - 1));
return make_pair(row, col);
}
};
【在 A*******e 的大作中提到】
: 不会是只看最优解的长度吧？
: 那两道Excel的题，如果想不到变形十进制，写起来很繁琐。还有那个zigzag
: conversion，代码不长，但数组下标很容易算错。
|
|
