LeetCode(微博搜索)-20240316-1

本条微博地址 sunny晴天先生
今日LeetCode最佳评论 客观的，真实的，一阵见血的 本条微博地址 gitpush-force
关注我，每天59秒拿下每日一题
国区每日一题今日思路：
动态规划。因为每一个格子只能从前一列中三个位置转移，记dp[i][j]表示(i,j)位置处最大移动次数。初始时所有dp值为0，dp计算时外层循环为列，保证前一列的状态优先被计算。若当前位置不可以从前一列转移得到，需要将当前位置置为一个异常值，防止后续dp过程中得到起点不是在第一列的路径。每次更新为dp值后，维护全局最优值。
国际站每日一题今日思路：
前缀和问题。这道题看似是最长连续子序列，其实本质还是前缀和问题。若一段连续子序列中0和1的个数相等，其前缀和0个数与前缀和1个数差值相等，这样才能根据前缀和计算出区间中0个数和1个数相等。记录每个位置的0和1个数的差值，每个差值只需要维护第一个出现的位置，若差值已出现，说明当前位置可以作为右端点，尝试更新全局最优。
#每日一题# #LeetCode# #每天59秒拿下每日一题#