常规暴力破解方法,时间复杂度O(n2):
class Solution {
public:
vector<int> minOperations(string boxes) {
int n = boxes.size();
vector<int> res;
for(int i = 0;i < n;i++)
{
int distance = 0;
for(int j = 0;j < n;j++)
{
if(i == j) continue;
if('1' == boxes[j])
distance += abs(i-j);
}
res.push_back(distance);
}
return res;
}
};
运行效率:
Runtime: 144 ms, faster than 39.87% of C++ online submissions for Minimum Number of Operations to Move All Balls to Each Box.
Memory Usage: 9.3 MB, less than 39.10% of C++ online submissions for Minimum Number of Operations to Move All Balls to Each Box.
绞尽脑汁也没有想到优化的方法,看了讨论区大神的解法:
vector<int> minOperations(string boxes) {
vector<int> res(boxes.length());
for (int i = 0, ops = 0, cnt = 0; i < boxes.length(); ++i) {
res[i] += ops;
cnt += boxes[i] == '1' ? 1 : 0;
ops += cnt;
}
for (int i = boxes.length() - 1, ops = 0, cnt = 0; i >= 0; --i) {
res[i] += ops;
cnt += boxes[i] == '1' ? 1 : 0;
ops += cnt;
}
return res;
}
运行效率:
Runtime: 4 ms, faster than 96.14% of C++ online submissions for Minimum Number of Operations to Move All Balls to Each Box.
Memory Usage: 8.7 MB, less than 91.82% of C++ online submissions for Minimum Number of Operations to Move All Balls to Each Box.
相对于暴力破解方法的144ms,速度提升明显。
这个解法主要从左向右遍历一遍,然后从右向左遍历一遍。从左向右遍历时只能记录当前结点左侧结点的1全部移动到当前结点需要的次数,当从右向左遍历时可以求解当前结点右侧结点的1全部移动到当前结点需要的次数。
另一种解法:
class Solution {
public int[] minOperations(String boxes) {
int[] answer = new int[boxes.length()];
int left = 0, right = 0, total = 0;//左边盒子的个数,右边盒子的个数,操作数
//计算第一个盒子的操作数
if (boxes.charAt(0) == '1') left ++;
for (int i = 1 ; i < boxes.length(); i++) {
if (boxes.charAt(i) == '1') {
right++;
total += i;
}
}
answer[0] = total;
//根据前一个盒子的操作数,计算下一个盒子的操作数
for (int i = 1; i < boxes.length(); i++) {
total = total + left - right;
if (boxes.charAt(i) == '1') {
left ++;
right --;
}
answer[i] = total;
}
return answer;
}
}
上面代码最难理解的部分是total = total + left - right;
左边有left个盒子有球,右边有right个盒子有球,当移动一个格子后左边的每个盒子距离增加1,右边每个盒子距离减少1,因此才有了total = total + left - right来计算下一个盒子游动次数。
运行效率:
Runtime: 4 ms, faster than 96.14% of C++ online submissions for Minimum Number of Operations to Move All Balls to Each Box.
Memory Usage: 8.7 MB, less than 91.82% of C++ online submissions for Minimum Number of Operations to Move All Balls to Each Box.