您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“C++怎么解決移動(dòng)所有球到每個(gè)盒子的問(wèn)題”,感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷,實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“C++怎么解決移動(dòng)所有球到每個(gè)盒子的問(wèn)題”吧!
有 n
個(gè)盒子。給你一個(gè)長(zhǎng)度為 n
的二進(jìn)制字符串 boxes
,其中 boxes[i]
的值為 '0'
表示第 i
個(gè)盒子是 空 的,而 boxes[i]
的值為 '1'
表示盒子里有 一個(gè) 小球。
在一步操作中,你可以將 一個(gè) 小球從某個(gè)盒子移動(dòng)到一個(gè)與之相鄰的盒子中。第 i
個(gè)盒子和第 j
個(gè)盒子相鄰需滿足 abs(i - j) == 1
。注意,操作執(zhí)行后,某些盒子中可能會(huì)存在不止一個(gè)小球。
返回一個(gè)長(zhǎng)度為 n
的數(shù)組 answer
,其中 answer[i]
是將所有小球移動(dòng)到第 i
個(gè)盒子所需的 最小 操作數(shù)。
每個(gè) answer[i]
都需要根據(jù)盒子的 初始狀態(tài) 進(jìn)行計(jì)算。
示例 1:
輸入:boxes = "110"
輸出:[1,1,3]
解釋:每個(gè)盒子對(duì)應(yīng)的最小操作數(shù)如下:
1) 第 1 個(gè)盒子:將一個(gè)小球從第 2 個(gè)盒子移動(dòng)到第 1 個(gè)盒子,需要 1 步操作。
2) 第 2 個(gè)盒子:將一個(gè)小球從第 1 個(gè)盒子移動(dòng)到第 2 個(gè)盒子,需要 1 步操作。
3) 第 3 個(gè)盒子:將一個(gè)小球從第 1 個(gè)盒子移動(dòng)到第 3 個(gè)盒子,需要 2 步操作。將一個(gè)小球從第 2 個(gè)盒子移動(dòng)到第 3 個(gè)盒子,需要 1 步操作。共計(jì) 3 步操作。
示例 2:
輸入:boxes = "001011"
輸出:[11,8,5,4,3,4]
提示:
n == boxes.length
1 <= n <= 2000
boxes[i]
為 '0'
或 '1'
首先遍歷一遍原始數(shù)組,求出將所有小球全部移動(dòng)到下標(biāo)0的話所需要的步驟。同時(shí),記錄下來(lái)從下標(biāo)1開(kāi)始到結(jié)束,一共有多少個(gè)小球
int right1 = 0, left1 = 0, cnt = 0; // right1記錄下標(biāo)0后面有多少個(gè)1(不包含下標(biāo)0) | cnt記錄將所有小球都移動(dòng)到下標(biāo)0需要多少步 | left1 記錄下標(biāo)0左邊有多少個(gè)1 int n = boxes.size(); for (int i = 1; i < n; i++) { if (boxes[i] == '1') { right1++, cnt += i; } } vector<int> ans(n); ans[0] = cnt;
接下來(lái)我們?cè)俅伪闅v數(shù)組,如果某個(gè)元素的上一個(gè)元素是1
,那么這個(gè)元素左邊的1的數(shù)量就會(huì)加一,因此left1++
這時(shí)候,這個(gè)盒子和上一個(gè)盒子相比,這一個(gè)盒子左邊*的所有1
需要移動(dòng)的步數(shù)都+1
,這一個(gè)盒子左邊共有left1
個(gè)1
,因此cnt += left1
。
這時(shí)候,這個(gè)盒子和上一個(gè)盒子相比,上一個(gè)盒子右邊的所有1
需要移動(dòng)的步數(shù)都-1
,上一個(gè)盒子右邊共有right1
個(gè)1,因此cnt -= right1
。
之后,如果這個(gè)盒子初始值也是1
的話,再在遍歷下一個(gè)元素之前提前更新right1
的值(right1--
)
時(shí)間復(fù)雜度O(n)
空間復(fù)雜度O(1),力扣答案不計(jì)入算法空間復(fù)雜度
class Solution { public: vector<int> minOperations(string& boxes) { int right1 = 0, left1 = 0, cnt = 0; int n = boxes.size(); for (int i = 1; i < n; i++) { if (boxes[i] == '1') { right1++, cnt += i; } } vector<int> ans(n); ans[0] = cnt; for (int i = 1; i < n; i++) { if (boxes[i - 1] == '1') left1++; cnt -= right1; cnt += left1; ans[i] = cnt; if (boxes[i] == '1') right1--; } return ans; } };
到此,相信大家對(duì)“C++怎么解決移動(dòng)所有球到每個(gè)盒子的問(wèn)題”有了更深的了解,不妨來(lái)實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。