大厂真题：【DP/贪心】字节跳动2023秋招-小红的 01 串

题目描述与示例

题目描述

小红拿到了一个 01 串，她准备将若干个字符'1' 染成红色，将若干个字符'0' 染成蓝色，但有个限制：如果一个'0' 和一个'1' 相邻，那么它们不能同时染色。

小红想知道，最多可以染多少个字符？

输入描述

输入仅有一行，为小红拿到的 01 串。

字符串长度不超过200000。

输出描述

一个正整数，代表能染色的最多字符。

示例一

输入

110011

输出

4

说明

染红第一个、第三个、第五个、第六个字符即可。

解题思路

每一个位置都有染和不染两种情况，故可以用状态dp来解决问题。

也可以贪心地解决问题，因为对于每一个01或10子串，只能染色一个字符，因此可以通过字符串中01或10子串的个数来进行计算。

代码

解法一：DP

Python

# 题目：【DP】字节跳动2023秋招-小红的 01 串
# 作者：闭着眼睛学数理化
# 算法：状态DP
# 代码有看不懂的地方请直接在群上提问s = input()
n = len(s)# 初始化n*2的二维dp数组
# dp[i]表示考虑第i个字符的情况
# dp[i][0]表示第i个字符染色，能得到的最多染色数目
# dp[i][1]表示第i个字符不染，能得到的最多染色数目
dp = [[0, 0] for _ in range(n)]
# 对第0个字符进行染色
dp[0][0] = 1for i in range(1, n):# 如果第i个字符和第i-1个字符不同# 两种情况：# 1. 当前字符染色，前一个字符不染# 2. 当前字符不染，前一个字符可以染色也可以不染色if s[i] != s[i-1]:# 当前字符染色，+1表示当前字符染色后，染色数目+1dp[i][0] = dp[i-1][1] + 1# 当前字符不染色，为上一个字符染色或不染取得的最大值dp[i][1] = max(dp[i-1][0], dp[i-1][1])# 如果第i个字符和第i-1个字符相同# 两种情况：# 1. 当前字符染色，前一个字符可以染色也可以不染色# 2. 当前字符不染，前一个字符可以染色也可以不染色else:dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + 1dp[i][1] = max(dp[i-1][0], dp[i-1][1])print(max(dp[-1]))

Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String s = scanner.nextLine();int n = s.length();int[][] dp = new int[n][2];dp[0][0] = 1;for (int i = 1; i < n; i++) {if (s.charAt(i) != s.charAt(i - 1)) {dp[i][0] = dp[i - 1][1] + 1;dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);} else {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]) + 1;dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);}}int maxColoring = Math.max(dp[n - 1][0], dp[n - 1][1]);System.out.println(maxColoring);}
}

C++

#include <iostream>
#include <string>
#include <vector>using namespace std;int main() {string s;cin >> s;int n = s.length();vector<vector<int>> dp(n, vector<int>(2, 0));dp[0][0] = 1;for (int i = 1; i < n; i++) {if (s[i] != s[i - 1]) {dp[i][0] = dp[i - 1][1] + 1;dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]);} else {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + 1;dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]);}}int maxColoring = max(dp[n - 1][0], dp[n - 1][1]);cout << maxColoring << endl;return 0;
}

时空复杂度

时间复杂度：O(N)。仅需一次遍历数组。

空间复杂度：O(N)。dp数组所占空间，如果使用滚动dp数组，可以将

解法二：贪心

Python

# 题目：【DP】字节跳动2023秋招-小红的 01 串
# 作者：闭着眼睛学数理化
# 算法：贪心
# 代码有看不懂的地方请直接在群上提问s = input()
n = len(s)
ans = 0
i = 0
while i < n:j = i + 1while j < n and s[j] != s[j - 1]:j += 1ans += (j - i + 1) // 2i = jprint(ans)

Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String s = scanner.next();int n = s.length();int ans = 0;for (int i = 0, j; i < n; i = j) {for (j = i + 1; j < n && s.charAt(j) != s.charAt(j - 1); ++j);ans += (j - i + 1) / 2;}System.out.println(ans);}
}

C++

#include <bits/stdc++.h>
using namespace std;const int N=200004;
char s[N];
int main(){scanf("%s",s+1);int n=strlen(s+1);int ans=0;for(int i=1,j;i<=n;i=j){for(j=i+1;j<=n&&s[j]!=s[j-1];++j);ans+=(j-i+1)/2;}printf("%d\n",ans);
}

时空复杂度

时间复杂度：O(N)。仅需一次遍历数组

空间复杂度：O(1)。仅需若干常数变量。

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多