网站做成app的软件,网站备案是指什么,免费购物网站系统,平台推广计划665. 非递减数列 题解#xff1a;
题目要求一个非递减数列#xff0c;我们可以考虑需要更改的情况#xff1a;
nums {4, 2, 5}
对于这个nums#xff0c;由于2的出现导致非递减#xff0c;更改的情况就是要么4调到2#xff0c;要么2调到4,5.
nums {1, 4, 2, 5} … 665. 非递减数列 题解
题目要求一个非递减数列我们可以考虑需要更改的情况
nums {4, 2, 5}
对于这个nums由于2的出现导致非递减更改的情况就是要么4调到2要么2调到4,5.
nums {1, 4, 2, 5}
对于这个nums由于2的出现导致非递减更改的情况就是要么4调到1,,2要么2调到4,5.
nums {3, 4, 2, 5}
对于这个nums由于2的出现导致非递减更改的情况就是2调到4,5.
所以算法就是
如果按照1的情况当i 1那么直接就把nums[i - 1]改成nums[i],nums[i]不动
如果按照2的情况当nums[i - 2] nums[i]那我们就优先考虑把nums[i - 1] 调小到 nums[i - 2] 并且 nums[i]
如果按照1的情况nums[i - 2] nums[i]那我们就调整nums[i],让nums[i] nums[i - 1]。
代码
class Solution {public boolean checkPossibility(int[] nums) {int count 0;//统计需要满足非递减的次数for(int i 1; i nums.length;i){if(nums[i] nums[i - 1]){if(i 1 || nums[i] nums[i - 2]){// i1就是第一个情况,后面的是第二种nums[i - 1] nums[i];}else{nums[i] nums[i - 1];}count;}}return count 1;}
} 453. 最小移动次数使数组元素相等 思路
题目要求我们每次操作将会让n-1个元素增加1来满足要求。我们可以反过来思考找到最小的数遍历其他的数累加所有元素和最小的元素的差距。
代码
class Solution {public int minMoves(int[] nums) {int minNum Arrays.stream(nums).min().getAsInt();int res 0;for(int num : nums){res num - minNum;}return res;}
} 283. 移动零 思路双指针
我们定义两个指针left, right都等于0遍历nums如果nums[right] 0那我们就让nums[left]和nums[right]进行交换再把Left增加。如果等于0那就让right。
其实Left就是第一个0的位置right就是让他找到不为0的地方。 189. 旋转数组 思路
第一步先翻转数组里的数第二步翻转前[0, k - 1]个数第三步翻转后面[k, n]的数 代码
class Solution {public void rotate(int[] nums, int k) {k % nums.length;reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);}public void reverse(int[] nums, int left, int right){while(left right){int temp nums[left];nums[left] nums[right];nums[right] temp;left;right--;}}
} 396. 旋转函数 思路
找规律 所以对应的公式 代码:
class Solution {public int maxRotateFunction(int[] nums) {int sum 0, f 0, n nums.length, ans 0;for(int i 0; i n; i){sum nums[i];f i * nums[i];//f(0);}ans f;for(int i 1; i n; i){f f sum - n * (nums[n - i]);//f[i] f[i - 1] sum -n * nums[n - i];ans Math.max(ans, f);}return ans;}
}