插： 前些天发现了一个巨牛的人工智能学习网站，普通易懂，风趣幽默，不由得分享一下给各人。点击跳转到网站。
对峙不懈，越努力越荣幸，各人一起学习鸭~~~
标题：
给你三个正整数 n、index 和 maxSum 。你必要构造一个同时满意下述全部条件的数组 nums（下标 从 0 开始 计数）：
nums.length == n
nums 是 正整数 ，此中 0 <= i < n
abs(nums - nums[i+1]) <= 1 ，此中 0 <= i < n-1
nums 中全部元素之和不高出 maxSum
nums[index] 的值被 最大化
返回你所构造的数组中的 nums[index] 。
留意：abs(x) 等于 x 的条件是 x >= 0 ；否则，abs(x) 等于 -x 。
示例 1：
输入：n = 4, index = 2, maxSum = 6
输出：2
表明：数组 [1,1,2,1] 和 [1,2,2,1] 满意全部条件。不存在其他在指定下标处具有更大值的有效数组。
示例 2：
输入：n = 6, index = 1, maxSum = 10
输出：3
提示：
1 <= n <= maxSum <= 10^9
0 <= index < n
java代码：
class Solution { public int maxValue(int n, int index, int maxSum) { int left = 1, right = maxSum; while (left < right) { int mid = (left + right + 1) / 2; if (valid(mid, n, index, maxSum)) { left = mid; } else { right = mid - 1; } } return left; } public boolean valid(int mid, int n, int index, int maxSum) { int left = index; int right = n - index - 1; return mid + cal(mid, left) + cal(mid, right) <= maxSum; } public long cal(int big, int length) { if (length + 1 < big) { int small = big - length; return (long) (big - 1 + small) * length / 2; } else { int ones = length - (big - 1); return (long) big * (big - 1) / 2 + ones; } }} |
