LeetCode 6157. 二进制字符串重新安排顺序需要的时间 DP题解。

题目

6157. 二进制字符串重新安排顺序需要的时间

https://leetcode.cn/problems/time-needed-to-rearrange-a-binary-string/

给你一个二进制字符串 s 。在一秒之中，所有 子字符串 “01” 同时 被替换成 “10” 。这个过程持续进行到没有 “01” 存在。

请你返回完成这个过程所需要的秒数。

这道题是我第一次参加LC周赛的第二题。看着简单，实际上有点东西。

暴力replace

思路

n^2的思路：每一秒我们都把01子串替换为10，直到字符串中没有01。

这个做法在比赛当时是可以通过的，第二天LC官方应该是补上了这个漏洞，这个做法复杂度也高，不是题目想考的做法。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

static class BF {
    public int secondsToRemoveOccurrences(String s) {
        int ans = 0;
        while (s.contains("01")) {
            s = s.replaceAll("01", "10");
            ans++;
        }
        return ans;
    }
}

复杂度分析

时间

每一轮中都需要进行字符串遍历，整体处理O(n^2)时间。

空间

无额外空间占用，空间复杂度O(1)。

DP

思路

解法1时间效率不满足要求！

我们来分析下用例，看看能不能产生新的解法：

题干中给出了示例10110101，每秒替换之后的结果：

1
2
3
4

"1011010"
"1101100"
"1110100"
"1111000"

我们记每个1为：arr[i]。

阶段 其左侧0的个数 挪动到对应最左所需秒数 状态
第一个1，arr[1] 1 1 第一个1替换一次，到达其最终终点
第二个1，arr[2] 1 2 由于第一秒第二个1前面紧挨了第一个1，第一秒没动，第二秒才到达终点
第三个1，arr[3] 2 3 第一秒向左挪动了一位，第二秒与arr[2]紧挨，等待一秒，第三秒到达终点
第四个1，arr[4] 3 4 第一秒向左挪动了一位，第二秒向左挪动一位，第三秒与arr[3]紧挨，等待一秒，第四秒到达终点

我们结合另一个用例001011，每秒替换之后的结果：

1
2
3
4

"010101"
"101010"
"110100"
"111000"
阶段 挪动到对应最左所需秒数 其左侧0的个数 状态
第一个1，arr[1] 2 2 第一二秒均为01排列，第二秒挪动到最左
第二个1，arr[2] 3 3 第一二三秒均为01排列，第三秒挪动到最左
第三个1，arr[3] 4 3 第一秒等待，第二三四秒均01排列，第四秒到达终点

因此，我们可归纳如下要素：

要素
状态表示 dp[i]表示将 s[i] 处的1挪动到最左侧最少需要的秒数；pre0表示当前位置前序0个数；
阶段划分 每个1出现均为新的阶段，0维持与前序相同的状态值；
转移方程 s[i]=='0'时，dp[i]=dp[i-1] ;s[i]=='1' && pre0!=0时，dp[i]= max(dp[i-1]+1,pre0)，dp[i-1]+1 表示1前序为1，需要多一次移动；
边界 dp[0]=0；
目标 max(dp[i])

特别注意：

  1. dp[i-1]+1 表示，如10101/10110典型用例中，后序1挪动到位都需付出比前序1更多1的时间；
    1. 10101 第三个1比第二个1，多消耗1个时间，原因是pre0增加了1；
    2. 10110 第三个1比第二个1，多消耗1个时间，原因是第三个1紧挨着第二个1，第三个1需先等待1秒再左移；
    3. 综上，dp[i]= max(dp[i-1]+1,pre0)；
  2. pre0==0即前序还没0时，1此时状态不需要挪动，即dp[i]=0；

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public int secondsToRemoveOccurrences(String s) {
      int[] dp = new int[s.length()];
      dp[0] = 0;
      int ans = 0;
      int pre0 = s.charAt(0) == '0' ? 1 : 0;
      for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                  dp[i] = dp[i - 1];
                  pre0++;
                  continue;
            }
            // s[i]=='1'
            // 前序有0才能移动后序的1
            if (pre0 == 0) {
                  continue;
            }
            dp[i] = Math.max(dp[i - 1] + 1, pre0);
            ans = Math.max(ans, dp[i]);
      }
      return ans;
}

滚动数组压缩状态：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

/**
 * 简化版本：只维护前序值，滚动数组
 */
public int secondsToRemoveOccurrences2(String s) {
    // 状态压缩，我们只记录前序dp状态即可
    int dpPrev = 0, pre0 = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '0') {
            pre0++;
            continue;
        }
        // s[i]=='1'
        // 前序有0才能移动后序的1
        if (pre0 == 0) {
            continue;
        }
        dpPrev = Math.max(dpPrev + 1, pre0);
    }
    return dpPrev;
}

复杂度分析

时间

整个过程仅需遍历线性次数组，复杂度 O(n)。

空间

额外维护了一个dp数组，空间复杂度O(n)。

此处可以进行滚动数组压缩状态，维护一个prevDp，对应复杂度O(1)。