白天不懂夜的黑
来提每日一题
2024-10-18 13:13:23
蒲公英优质笔记激励计划2.0 转码 每天59秒拿下每日一题 每日一题 创作灵感 LeetCode 刷题 近期找工作现状 程序员
国区每日一题今日思路：
记忆化搜索。记memo[i][j]为perm[0,..i]恰好有j个逆数对的数目，这里不需要考虑第i个位置所填写的数字，假设第i个位置填第k大数，那么这个数与前面组成k-1个逆数对。对于每一个位置存在两种情况，当前位置存在限制arr[i]，这时只能选择dp(i, arr[i])种组合，这里隐含着两个条件，arr数组必须非递减，同时当前j与上一个位置的差值不超过i，因为i位置最多贡献i个逆数对；另一种情况是不存在限制，这时可以任意选择逆数对数目，只需要不超过i和j的较小者。递归终点i为0说明找到一种可行方案。最终答案为dp(n-1,arr[n-1])。
国际站每日一题今日思路：
贪心。将数字转换为字符串，这样便于操作每一数位，模拟所以交换可能，找到最大值。看到这点个赞吧
0
阅读：0
