小红书 3道题 AC 100%
第一题：
数组里有0和1，可以翻转一个区间的所有数，0变1，1变0，问变完后可以使得1的个数最多是多少？
一开始没想出来，先做的后面的题，后来看到题目的提示说：可以简单变换一下，更好计算0和1的数量
行，仔细思考一下，他要求的其实就是一个区间内，0的个数-1的个数的 最大值，能找到这个区间答案就出来了。
于是遇到0，可以理解为+1，遇到1，可以理解为-1；那么就是问连续区间内 sum[i:j]的最大值是多少
这不就变成了连续最大字段和问题？
注意两个坑：
（1）n==0时，要输出-1
（2）一定要变一次，1 1 1这种，答案是2
核心代码：
a = [1,0,1,1,1] n = 5 sum = 0 max = 0 count = 0 f = 0 #判断是否有解 for i in range(n): if a[i] == 0: sum = sum + 1 else: sum = sum - 1 count = count + 1 if sum >= max: f = 1 max = sum if sum < 0: sum = 0 if f: print(max + count) else: print(count-1)
第二题：
直接用的dp做的，复杂度n*m，没想到过了
每个位置的线路次数，其实是它上边的次数+它左边的次数；
障碍点次数为0
核心代码：
#定义dp数组，默认值为0 #定义地图数组，默认值为0 #遍历k个障碍，如果有障碍，就把地图数组变成1，map[i][j] = 1 for i in range(1, m+1): for j in range(1, n+1): if map[i][j] == 1: #有障碍，那不管 continue dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[m][n]
第三题：
线段树模板题，或者RMQ
两个树，一个维护最大值，一个维护最小值，直接减就好，还找到了原题
可以帮答疑，做题，可私聊
#小红书笔试##小红书##笔经#
哔哩哔哩公司福利 351人发布
怒拒
腾讯二面872人在聊
查看20道真题和解析