文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题最少的后缀翻转次数出处1529. 最少的后缀翻转次数难度4 级题目描述要求给定一个长度为n \texttt{n}n、下标从0 \texttt{0}0开始的二进制字符串target \texttt{target}target。有另一个长度为n \texttt{n}n的二进制字符串s \texttt{s}s初始时s \texttt{s}s的每一位上都是0 \texttt{0}0。目标是让s \texttt{s}s和target \texttt{target}target相等。一步操作中可以选择下标i \texttt{i}i0 ≤ i n \texttt{0} \le \texttt{i} \texttt{n}0≤in并翻转在闭区间[i, n − 1] \texttt{[i, n} - \texttt{1]}[i, n−1]内的所有位。翻转的含义是‘0’ \texttt{0}‘0’变为‘1’ \texttt{1}‘1’‘1’ \texttt{1}‘1’变为‘0’ \texttt{0}‘0’。返回使s \texttt{s}s与target \texttt{target}target相等需要的最少翻转次数。示例示例 1输入target 10111 \texttt{target 10111}target 10111输出3 \texttt{3}3解释初始时s 00000 \texttt{s 00000}s 00000。选择下标2 \texttt{2}200000 → 00111 \texttt{00000} \rightarrow \texttt{00111}00000→00111选择下标0 \texttt{0}000111 → 11000 \texttt{00111} \rightarrow \texttt{11000}00111→11000选择下标1 \texttt{1}111000 → 10111 \texttt{11000} \rightarrow \texttt{10111}11000→10111要达成目标需要至少3 \texttt{3}3次翻转。示例 2输入target 101 \texttt{target 101}target 101输出3 \texttt{3}3解释初始时s 000 \texttt{s 000}s 000。选择下标0 \texttt{0}0000 → 111 \texttt{000} \rightarrow \texttt{111}000→111选择下标1 \texttt{1}1111 → 100 \texttt{111} \rightarrow \texttt{100}111→100选择下标2 \texttt{2}2100 → 101 \texttt{100} \rightarrow \texttt{101}100→101要达成目标需要至少3 \texttt{3}3次翻转。示例 3输入target 00000 \texttt{target 00000}target 00000输出0 \texttt{0}0解释由于s \texttt{s}s已经等于目标所以不需要任何操作。数据范围n target.length \texttt{n} \texttt{target.length}ntarget.length1 ≤ n ≤ 10 5 \texttt{1} \le \texttt{n} \le \texttt{10}^\texttt{5}1≤n≤105target[i] \texttt{target[i]}target[i]为‘0’ \texttt{0}‘0’或‘1’ \texttt{1}‘1’解法思路和算法对于长度为n nn的字符串当翻转以下标i ii开始的后缀时下标范围[ i , n − 1 ] [i, n - 1][i,n−1]中的所有字符都会翻转。下标j jj处的字符的翻转次数等于开始下标小于等于j jj的后缀的翻转次数翻转结果与翻转顺序无关因此可以从左到右遍历字符串计算最少翻转次数。对于以下标i ii开始的后缀如果将该后缀翻转两次则翻转前后的字符串相同。为了使翻转次数最少应满足对于每个下标开始的后缀至多翻转一次并且只有当必须翻转的时候才执行翻转。由于下标0 00的左侧没有其他字符因此判断以下标0 00开始的后缀的依据是target [ 0 ] \textit{target}[0]target[0]。如果target [ 0 ] ‘1’ \textit{target}[0] \text{1}target[0]‘1’则需要翻转以下标0 00开始的后缀否则不需要翻转以下标0 00开始的后缀。按照从左到右的顺序遍历字符串并翻转后缀用index \textit{index}index表示最后一次翻转的后缀的开始下标则不存在任何一个开始下标大于index \textit{index}index的后缀被翻转因此下标范围[ index , n − 1 ] [\textit{index}, n - 1][index,n−1]中的所有字符都相同。遍历过程中如果发现target \textit{target}target的两个相邻字符不同即存在i 0 i 0i0且target [ i ] ≠ target [ i − 1 ] \textit{target}[i] \ne \textit{target}[i - 1]target[i]target[i−1]则需要翻转以下标i ii开始的后缀否则字符串s ss的下标i ii和i − 1 i - 1i−1处的字符相同不可能满足s ss与target \textit{target}target相等。根据上述思路首先判断以下标0 00开始的后缀是否需要翻转然后从左到右遍历target \textit{target}target当遇到target \textit{target}target的两个相邻字符不同时需要执行一次翻转遍历结束时即可得到最少翻转次数。上述思路为贪心策略贪心策略的正确性说明如下。翻转后满足s [ 0 ] target [ 0 ] s[0] \textit{target}[0]s[0]target[0]且对于任意0 i n 0 i n0in当target [ i ] target [ i − 1 ] \textit{target}[i] \textit{target}[i - 1]target[i]target[i−1]时s [ i ] s [ i − 1 ] s[i] s[i - 1]s[i]s[i−1]当target [ i ] ≠ target [ i − 1 ] \textit{target}[i] \ne \textit{target}[i - 1]target[i]target[i−1]时s [ i ] ≠ s [ i − 1 ] s[i] \ne s[i - 1]s[i]s[i−1]因此翻转之后s ss与target \textit{target}target相等。对于每个下标开始的后缀至多翻转一次。对于i 0 i 0i0只有当s [ i ] ≠ target [ i ] s[i] \ne \textit{target}[i]s[i]target[i]时才翻转以下标i ii开始的后缀对于i 0 i 0i0只有当target [ i ] ≠ target [ i − 1 ] \textit{target}[i] \ne \textit{target}[i - 1]target[i]target[i−1]时才翻转以下标i ii开始的后缀。每次翻转都是必不可少的如果在需要翻转的下标处不翻转则一定有s [ 0 ] ≠ target [ 0 ] s[0] \ne \textit{target}[0]s[0]target[0]或者s ss的相邻下标字符的关系与target \textit{target}target的对应相邻下标字符的关系不同不可能满足s ss与target \textit{target}target相等。因此贪心策略可以确保得到最少翻转次数。代码classSolution{publicintminFlips(Stringtarget){intflips0;charprev0;intntarget.length();for(inti0;in;i){charcurrtarget.charAt(i);if(curr!prev){flips;prevcurr;}}returnflips;}}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是字符串target \textit{target}target的长度。需要遍历字符串一次计算最少反转次数。空间复杂度O ( 1 ) O(1)O(1)。