leetcode 第 392 场算法比赛

零、背景

今天清明节休假，上午参加了比赛，题目比较简单，第一题看错题了，浪费不少时间。

A: 签到题，最大连续递增子数组长度。
B: 构造，字典序最小字符串。
C: 贪心，排序，连续区间求和。
D: 并查集。

排名：129
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/3/392

一、最长的严格递增或递减子数组

题意：给一个数组，求最长的严格递增或递减子数组。

思路：封装一个函数求递增答案，翻转数组后，再求递增就是递减的答案。

二、满足距离约束且字典序最小的字符串

题意：给一个字符串，求构造一个字符串，使得两个字符串的距离不大于 k，求满足要求的字典序最小的字符串。

字符串距离定义：各位置字符的距离之和。
字符距离定义：字母a到z组成循环字符，两个方向较短的距离为字符距离。

思路：从左到右，从小到大枚举字符，找到不超过输入字符的第一个满足要求的字符，使得累计距离和满足要求。

三、使数组中位数等于 K 的最少操作数

题意：给一个数组，可以选择任意一个元素加一或者减一，问最少多少次操作可以使得数组的中位数等于 K。

思路：显然，可以推导出一个贪心原则。

贪心1：如果对一个数字进行加一，则不需要对其进行减一。
贪心2：如果一个数字 a 小于数字 b, 操作后，数字 a的值 不可能大于数字 b的值。

由此可以推导出，对数组排序后，再进行任意次操作，各个元素小顺序是不会改变的。

数组的中位数固定不变，数组的元素顺序不会变化，中位数修改为 K 后，如果后面有小于 K 的元素，都需要调整到 K；如果前面有大于 K 的元素，则都需要调整到 K。

算法：排序，找到中位数，调整到 K，前面的元素调整到都不大于 K，后面的元素调整到都不小于 K。

四、带权图里旅途的最小代价

题意：给一个无向带权图，问两个顶点之间的最小路径代价。
路径代价：路径上所有边权的与运算，边和点循序重复走。

思路：边和点允许重复走，与运算参与的边越多，代价会越小，最优情况是把联通分支的所有边都走一遍。

故，如果两个点不连通，则没答案。
连通时，答案为联通分支上所有边的与运算。

可以通过并查集来处理联通分支与所有边的与运算。

五、最后

这次比赛比较简单，第一题我看成子序列了，浪费了 10 分钟时间，不然有可能进入千百名。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code