文章目錄

• • 題目分析
  • 題目鏈接

題目分析

首先需要明確一點：最優結果中1的相對位置和開始時不會改變。否則的話就是交換兩個1，會徒勞增加交換次數。 比如[1,0,0,0,0,0,1,1]，最后變成[0,0,0,0,0,1,1,1]，在變化過程中，哪個1在前哪個1在后是不會變的（不管0），即相對順序不變。

問題變為，需要經過多少次移動，可以把k個分散的1變成k個連續的1（坐標連續）。 原下標分別是$a_0,a_1,...a_{k?1}$分別移動到下標是$x,x+1,x+2,...x+k?1$（相對位置沒變）的地方，使之移動次數最少，即求一個 x 使下式
$$d=|a_0?x|+|a_1?(x+1)|+....+|a_{k?1}?(x+k?1)|$$
最小

再轉化一下，變成到點x的距離之和

$$d=|a_0?x|+|(a_1?1)?x|+|(a_2?2)?x|....+|(a_{k?1}?(k?1)?x|$$

令：
$$\begin{gathered} a_0^{\prime }=a_0 \\ {a}_1^{\prime }=a_1?1 \\ ... \\ {a}_{k?1}^{\prime }=a_{k?1}?(k?1) \end{gathered}$$

這里的映射是$a_i?i$,其中$a_i$是“1”在原序列里的下標，表示第$i+1$個"1"的下標，比如第1個“1”的下標記作$a_0$,此時$i=0$
就變成了$$d=|a_0^{\prime }?x|+|a_1^{\prime }?x|+|a_2^{\prime }?x|....+|(a_{k?1}^{\prime }?x|$$

這樣就可以用絕對值不等式（母題：貨倉選址）的模板，該式的最小值在 x 取$a_0^{\prime },a_1^{\prime },...,a_{k?1}^{\prime }$的中位數的時候取。

下面還有1個問題， 對于長度是k的區間$[a_l,a_2,a_{mid}..a_r]$，如何快速求出上面絕對值求和的最小值，最小值是x取到中位數$a_{mid}$。 求和分兩段：$a_{mid}$左邊都是小于等于$a_{mid}$的，右邊都是大于等于它的。這樣可以省去絕對值的計算。

左邊求和：left = $$\begin{gathered} (a_{mid}?a_l)+(a_{mid}?a_{l+1})+...+(a_{mid}?a_{mid?1}) \\ =a_{mid}?(mid?l)?(s[mid?1]?s[l?1]) \end{gathered}$$，s為a序列的前綴和。

右邊求和： right =$$\begin{gathered} (a_{mid+1}?a_{mid})+....+(a_r?a_{mid}) \\ =s[r]?s[mid]?a_{mid}?(r?mid) \end{gathered}$$

所以，這個窗口內移動次數 為 left + right .

以上只是一個窗口內的處理。 我們需要不斷維護滑動窗口，k個1是一個窗口。

ac代碼

class Solution { public:int minMoves(vector<int>& nums, int k) {vector<int> a;for(int i=0;i< nums.size();i++){if(nums[i]) // 找出1a.push_back(i-a.size()); // 坐標映射 第m個數的下標為i: i- m}int n=a.size();//n表示1的個數typedef long long LL;vector<LL> s(n+1);//前綴和數組for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i-1]; //下標從1開始LL res=1e18; //記錄結果：最少移動次數//枚舉所有窗口,窗口大小為k，這里枚舉的是右端點for(int i=k;i<=n;i++){//左端點int l=i-k+1;//右端點int r=i;int mid = (l+r)/2;LL x = a[mid - 1] ; // for循環下標相當于從1開始，需要-1，因為遍歷窗口的時候i=k，如果下標是從0開始的話，i應該為i= k-1.LL left = x*(mid -l )-(s[mid-1 ] - s[l-1]);LL right = s[r]-s[mid] -x*(r-mid);res = min ( res , left+ right);}return res;} };

下面是 對于滑動窗口k 枚舉左端點，只要注意好 前綴和求和時候 和下標的關系！！因為前綴和數組下標從1開始！

class Solution { public:int minMoves(vector<int>& nums, int k) {typedef long long LL;LL res =1e17;vector<int >a;for(int i=0;i<nums.size();i++)if(nums[i]) a.push_back(i-a.size());int n=a.size();//統計1的個數vector<LL> s(n+1);for(int i=1;i<=n;i++) s[i] = s[i-1] + a[i-1];//枚舉滑動窗口左端點for(int i=0;i+k-1<n;i++){int l = i ;int r = i+k -1;int mid = l+r >> 1;int x = a[mid] ;LL left = x *(mid - l) -(s[mid]-s[l]);LL right = s[r+1]- s[mid+1] - x*(r -mid);res = min ( res, left+right);}return res;} };

題目鏈接

Leetcode1703. 得到連續 K 個 1 的最少相鄰交換次數

總結

以上是生活随笔為你收集整理的Leetcode1703. 得到连续 K 个 1 的最少相邻交换次数[C++题解]:难(货仓选址加强版+滑动窗口+前缀和)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。