Zhiming's Blog

——记录一下四道字节算法题，并解决它们！谨以为耻！

前言

字节跳动算法笔试(2020年8月9日)记录

我很惭愧，因为自己大概有两年多没有接触算法了，加上自己没有刷题，昨晚的字节跳动四道算法题，一题都没有得分，中间两道有思路，代码也写出来了。只是没有编译成功和得到预期的结果！

其实最近几天疯狂想冲一个leetcode会员，本着都已经花了这么多钱，你不物尽其用，不心疼吗？但是还是忍了一手，因为毕竟这终究是人生一道门槛必须要跨过去的那一种！

所以，就算是你不充钱，你也必须要去刷题，别！无！选！择！

那就放手一搏吧！（一棵参天大树，最好的种植时间那就是：十年前和此刻！）

很多部分思路想法参考借鉴了微信博主面鲸，感谢您，附上您的微信公众号二维码:

第一道算法题：完美字符串

第一道算法题考试的时候想了几分钟，没思路，所以没有写，但是后来看牛客网的讨论区，有人说在leetcode上面刷到过原题，再次感慨，算法题，真的是必须要去刷题，怪自己前几个月毫无根据的自信儿！不过现在也不算太晚！

题目：

长度为 n(1<=n<=500000) 的字符串，均为小写字母，允许修改m(1<=m<=n)个位置的字母，修改完毕后选取这个字符串的连续子串，满足这个子串只有一种字母，这个子串就是完美子串，求最长完美子串的长度。

样例输入：
8 1
aabaabaa

样例输出：
5 （把第3位或者第6位的任意一个b替换为a，得到aaaaa,该完美字串的长度为5）

思路：（双指针算法）

首先需要明确的是这个最完美的子串，无论长度多少，他都可能是由26个字母中的任意一个组成的。所以这里是不是需要在代码的最外面套一个for循环来一遍一遍的确定完美子串的组成字母呢？
其次，假设我们找到了完美子串的组成字母是c，看一下题目要求，求得是完美子串的长度，所以我们是不是需要再来一个for循环从母字符串中的第一位来一遍一遍的c的连续性呢？
第三点，这也是本题的最关键点！题目要求允许允许替换m个位子的字母，是不是表示字符串的最大容错为m。那么如何通过代码得出这一段最大容错为m的完美字符串呢？

考试的时候就是卡在这里，结束后，参考学习了一下大佬们的思路，茅塞顿开！
- 网上的解法是：这是典型的用two pointers来解决的问题，设置两个指针，left和right，分别考虑的是当前for循环所考虑的子串的起点和终点，每次先移动右指针，如果右指针指向的不是当前考虑的字母，那么用一个容错来改变他，直到容错大于了给定的最大容错，这个时候就需要动左指针了（右移），不停的移动，直到容错不大于最大容错时(等于的时候，就开始右指针的移动)，这个时候，left和right所指向的子串就是一个满足要求的潜在的一个可能的完美子串。
时间复杂度： O(n*26)

代码：By Python

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 读取第一行输入
n,m = input().split(' ')
n,m = int(n),int(m)

# 读取第二行输入
s = input()

# 定义完美字符串的长度变量
maxLength = 0

# 遍历26个字母，并匹配完美字符串的字母 
for i in range(26):
    # 定义左指针（完美字符串的起点）和容错（可替换的字母个数）
    left, faultTolerant = 0,0
    # 定义一个右指针（完美字符串的终点），右指针大小从0到母字符串的长度
    for right in range(n):
        # 当且仅当右指针指向的字母的ASCII码 不等于 第一个for循环指定的字母的ASCII码
        if ord(s[right]) != ord('a') + i:
            # 因为右指针不等于当前for循环的26个字母中之一，所以容错加1
            faultTolerant += 1
        #如果容错大于了输入给定的最大容错m，这个时候没办法了，就只能动左指针了（右移）
        while faultTolerant > m:
            # 存在一种情况，左指针目前匹配的刚好是for循环指定字母的ASCII码，此情况就不能减少容错
            # 如果左指针当前匹配不是for指定的字母的ASCII码，那么右移左指针不就可以减少容错了吗？
            if ord(s[left]) != ord('a') + i:
                faultTolerant -= 1
            # 注意缩进，如果在if循环中，则表示仅当左指针不匹配ACSII码，左指针才+1，显然不符合逻辑
            left += 1
        # 注意缩进
        maxLength = max(maxLength, right-left+1)
print(maxLength)

第二道算法题：交替序列和

这一道题相对而言，比较简单，因为可以套for循环，暴力求解出来，只是可惜我没有跑出正确答案，应该是自己中间代码出了一些逻辑上面的问题吧！

题目：

给定一个长度为n的整数序列 $A_1$ , $A_2$ , ... , $A_N$ ,找出其中的一段连续子序列，使得该段连续子序列的交替和最大。序列 $A_p$ , $A_{p+1}$ , ..., $A_q$ 的交替和为： $A_p$ - $A_{p+1}$ + $A_{p+2}$ - $A_{p+3}$ + ... + $(-1)^{q-p}$ * $A_q$ 。

输入描述：

输入的第一行为一个正整数n(n<=1e5)，表示序列的长度

输入的第二行为n个整数，依次给出了 $A_1$ , $A_2$ , ... , $A_N$ 。( $-10^5$ $\leq$ $A_i$ $\leq$ $10^5$ )

输出描述：
输出一个整数，表示最大的序列交替和

样例输入：
5
1 2 3 4 5

样例输出：
5 （就只有最后一个数字5，如果有序列的话，第二位永远比第一位数字大）

样例输入：
5
1 -2 3 -4 5

样例输出：
15 （ 1-(-2)+3-(-4)+5 = 15 ）

思路：（动态规划算法）

以下思路参考面鲸公众号的题目分析

做这个题之前我们先看看另外一个问题。给定一个长度为n的整数序列，找出其中一段连续子序列，使得该段连续子序列的和最大。这是一道经典的动态规划-「最大子段和问题」
对于最大子段和问题，假设 $C_i$ $C_{i}$ 是 $A_1$ $A_{1}$ , $A_2$ $A_{2}$ , ... , $A_i$ $A_{i}$ 包含 $A_i$ $A_{i}$ 的向前连续延伸的最大子段之和。那么以结尾的，有两种情况：
- 第一种，这个最大子序列中只有 $A_i$ 时，那么 $C_i$ = $A_i$
- 第二种，这个子序列包含了 $A_{i-1}$ 时，那么这个时候是不是可以想象成 $C_i$ = $C_{i-1}$ + $A_i$ ，有一种递归的思路
所以我们可以得到「状态转移方程」， $C_i$ =max ( $C_{i-1}$ + $A_i$ , $A_i$ )
考虑到这种递归的想法的时候，就需要考虑到 「边界情况」，当 i=1时，我们同样需要考虑用 $A_1$ $A_{1}$ 和不用 $A_1$ $A_{1}$ 这两种情况
- 第一种，用 $A_1$ ，那么 $C_1$ = $A_1$
- 第一种，不用 $A_1$ ，那么 $C_1$ =0
- 因此， $C_1$ =max ( 0, $A_1$ )
到这里思路就特别的清晰了吧，对于对于本地，这个子段是连续的交替加减，那么我们是不是可以将这个给定的数组变成两个数组，对于某一个元素 $A_i$ ，一个数组中 $A_i$ 为正整数,另一个数组 $A_i$ 为负整数。
这里还有一点需要注意，我发现面鲸大大没有在文章中说出来！就是如果 $A_i$ 是数组中的第一位时，我们不能改变其正负性。所以变动只能从第二位开始，且如果第二位整数没有改变正负性，那么就设置第一位元素为0，以适配整体的算法逻辑。举例如下：
- 假设输入的数组为：[a, b, c, d]
- 将其变为两个数组，其中一个是：[a, -b, c, -d]
- 另一个是：[0, b, -c, d]，这样子就可以适配一个算法逻辑了

附上LeetCode上动态规划算法的逻辑指导图：太绝妙了这个算法！

代码：By Python

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 读取第一行输入，输入数组长度
n = int(input())

# 读取第二行输入，输入的数组
m0 = list(map(int,input().split(' ')))
m1 = m0.copy()

# 为了节约空间和时间成本这里用两个for循环来展现两个正负性不同的数组
# m0列表的偶数位元素变为负，m1列表的奇数位元素变为负
for i in range(1,n,2):
    m0[i],m1[i-1] = -m0[i],-m1[i-1]

# 考虑到如果数组长度为奇数，则奇数位变负数组的最后一项在上述for循环中未变负
if len(m1)%2 == 1:
    m1[-1] = -m1[-1]

# 因为题目规定了最大子序列的首项不改变正负性，所以设定m1数组的首项为0，以适应相同的规划算法
m1[0] = 0

# 动态规划算法！太绝妙了！
for i in range(1,n):
    m0[i] += max(m0[i-1],0)
    m1[i] += max(m1[i-1],0)

print(max(max(m0),max(m1)))