0901小红书笔试Java
2.给定1和2的序列，有些数字需要固定在一个位置，有些可以自由移动，数据量100，动态规划做，
转移方程，
dp[i][j][0] = min(dp[i-1][j][0],dp[i-1][j][1]+1);
dp[i][j][1] = min(dp[i][j-1][0]+1,dp[i][j-1][1]);
其中i和j分别表示前（i+j）个数字中有i个1和j个2
最后注意一下特殊的地方处理就行比如固定值的地方
3.数据也太弱了吧，我把黑色节点计数输出一下就过82%，再输出个黑色节点数-1（也就是红节点删除只会影响一个黑节点丢失）过18%，这测试数据直接给试出来了，然后直接判断一下有没有红节点度为1的，有就输出黑节点总数（相当于有个叶子节点是红节点不会影响任何黑节点），没有就黑节点总数-1
言归正传
正解dfs看红节点的子节点数量维护一下就行，注意不能直接从root向下遍历求一个最小黑子节点树
随便就能举出一个反例
黑
|
红
|
黑
|
红
/\
黑 黑
这种答案肯定是3
类似资料：