Biweekly Contest 18

2020-01-25 22:30

1331,1332,1333,1334

3题，最后一题TLE

1331. Rank Transform of an Array

1328. Break a Palindrome

  • cpp
  • 前半区找a，直到找到不是a，替换为a，若对称的前半区全是a，则表示是aaa aaa 这种，把最后一个改成b
  • 实现中palindrome[N-1] = palindrome[N-1] == 'z' ? 'a' : palindrome[N-1]+1; 没必要

1329. Sort the Matrix Diagonally

  • cpp
  • 简单暴力迭代

1330. Reverse Subarray To Maximize Array Value

  • cpp
  • O(N^2)二维查找比较，TLE，尚未解决
  • 2020-02-06，参考discuss，AC： 参考

关键点是，在旋转子数组时，假设是[L, R]，得出新的Value公式为 S - abs(a[L-1]-a[L]) - abs(a[R] - a[R+1]) + abs(a[L-1]-a[R]) + abs(a[L] - a[R+1])

不考虑边界情况(L=0，导致L-1 = -1)，分四个情况： 1. a[L-1] < a[R] and a[L] < a[R+1] 2. a[L-1] > a[R] and a[L] < a[R+1] 3. a[L-1] < a[R] and a[L] > a[R+1] 4. a[L-1] > a[R] and a[L] > a[R+1]

然后拆分出来：

S - abs(a[L] - a[L-1]) - abs(a[R] - a[R+1]) + (a[R] - a[L-1]) + (a[R+1] - a[l])

=>

S - abs(a[L] - a[L-1]) - a[L-1] - a[L] - abs(a[R] - a[R+1]) + a[R] + a[R+1]

在第1种情况下：

X = 0 - abs(a[L] - a[L-1]) - a[L-1] - a[L]

Y = 0 - abs(a[R] - a[R+1]) + a[R] + a[R+1]

value = S + X + Y

这样，发现L和R就没啥关系，不需要绑定到一起做二维的迭代计算，使得我们可以一维个算个的，然后取最大的S+X+Y即可。4个case下X，Y的表示不同，但是也都只需要1维循环数组一次就能得到结果。

这个题，我在2020-02-06花费了小一天去梳理，主要原因是这种转化为数学公式后，分离变量，降维迭代的思维是第一次遇到，记得到校招时做过一道TopCoder上一个好像叫袜子匹配啥啥的题，解法是，转换后在所有可能结果的范围内，如[0, N]里面通过二维查找判定是不是可行解的思维，当时如果记得整理就好了！

要睡觉了做的，除了最后一题，前三题均没卡壳，已经可以了。