我已经拿了这个example test在我尝试用真人参加工作面试之前。挑战在于实现Equilibrium Index问题正确。
我编写了某种仅适用于简单示例和一些边缘情况的解决方案。
代码如下:
typedef vector<int> container_t;
typedef container_t::const_iterator iterator_t;
int find_equilibrium(const container_t &A);
int equi (const container_t &A)
{
const std::size_t length = A.size();
if (length == 0)
return -1;
if (length == 1 && A[0] == 0)
return -1;
if (length == 1 && A[0] != 0)
return 0;
return find_equilibrium(A);
}
int find_equilibrium(const container_t &A)
{
unsigned int i = 0;
int sum = 0;
for (iterator_t iter = A.begin(); iter != A.end(); ++iter, ++i)
{
sum += *iter; // not using std::accumulate to avoid N^2
if (sum == 0)
return i + 1;
}
return -1;
}
然而,对于像 [2, -2] 这样的情况,它存在致命缺陷。 然而,出于某种原因,它确实避免了算术溢出异常。 谷歌搜索后,我发现该算法与我自己的算法不同:
#include <numeric>
typedef vector<int> container_t;
typedef container_t::const_iterator iterator_t;
int find_equilibrium(const container_t &A);
int equi (const container_t &A)
{
const std::size_t length = A.size();
if (length == 0)
return -1;
if (length == 1)
return 0;
return find_equilibrium(A);
}
int find_equilibrium(const container_t &A)
{
unsigned int i = 0;
int left = 0, right = std::accumulate(A.begin(), A.end(), 0);
for (iterator_t iter = A.begin(); iter != A.end(); ++iter, ++i)
{
right -= *iter;
if (left == right)
return i;
left += *iter;
}
return -1;
}
此代码在数字非常大时失败,但在其他情况下可以工作。我不知道为什么。
我的问题是:
- 我处理此问题的方式有什么问题?如何在 30 分钟的时间限制内更正确地处理此类不同的问题?
- 这个问题的所有极端情况到底是什么?
- 如何才能在此示例测试中获得 100 分?
最佳答案
你的逻辑是对的。
A[0] + A[1] + A[2] = A[3] + A[4] + A[5] 等价于 A[0] + A[1] + A[2] - (A[3] + A[4] + A[5]) = 0
但是,在您的代码中,在始终添加值的循环中,您永远不会更改另一半中的值的符号。
for (iterator_t iter = A.begin(); iter != A.end(); ++iter, ++i) {
sum += *iter; // only increasing, where do you subtract the values of the second half?
if (sum == 0)
return i + 1; // from the initial value you return the next index that gives you zero sum
}
关于c++ - 均衡指数 - 我的解决方案有什么问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4861002/