四川省建设部网站,网站后台开发做什么,h5模板在线设计,wordpress餐饮获取单值网格的最小操作数
题目描述
给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。每一次操作#xff0c;你可以对 grid 中的任一元素 加 x 或 减 x 。
单值网格 是全部元素都相等的网格。
返回使网格化为单值网格所需的 最小 操作数。如果不能#xff0c;返…获取单值网格的最小操作数
题目描述
给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。每一次操作你可以对 grid 中的任一元素 加 x 或 减 x 。
单值网格 是全部元素都相等的网格。
返回使网格化为单值网格所需的 最小 操作数。如果不能返回 -1 。
样例
样例输入 grid [[2,4],[6,8]], x 2 grid [[1,5],[2,3]], x 1 grid [[1,2],[3,4]], x 2 样例输出 4 解释可以执行下述操作使所有元素都等于 4 2 加 x 一次。 6 减 x 一次。 8 减 x 两次。 共计 4 次操作。 5 解释可以使所有元素都等于 3 。 -1 解释无法使所有元素相等。 提示
mgrid.lengthm grid.lengthmgrid.lengthngrid[i].lengthn grid[i].lengthngrid[i].length1m,n1051 m, n 10^51m,n1051m∗n1051 m * n 10^51m∗n1051x,grid[i][j]1041 x, grid[i][j] 10^41x,grid[i][j]104
思路
第一个测试用例具误导性因为第一个测试用例中所有数字变为4所需的操作次数与变为6的所需操作次数一样。 最初思路就是通过一定的操作数使所有数都变为中位数。因为中位数的性质所有数变为中位数的所需操作数肯定是最小的。
代码实现
class Solution {public int minOperations(int[][] grid, int x) {ListInteger list new ArrayList();int m grid.length, n grid[0].length;for(int i 0; i m; i){for(int j 0; j n; j){// 所有数组的差值都必须是x的倍数不然无法通过-x改变成为指定值。if(Math.abs(grid[0][0] - grid[i][j]) % x ! 0) return -1;list.add(grid[i][j]);}}int ans 0;Collections.sort(list);int k list.get(n * m / 2);for(int i 0; i list.size(); i){ans Math.abs(list.get(i) - k) / x;}return ans;}
}下一个排列
题目描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如arr [1,2,3] 以下这些都可以视作 arr 的排列[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地如果数组的所有排列根据其字典顺序从小到大排列在一个容器中那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列那么这个数组必须重排为字典序最小的排列即其元素按升序排列。 例如arr [1,2,3] 的下一个排列是 [1,3,2] 。 类似地arr [2,3,1] 的下一个排列是 [3,1,2] 。 而 arr [3,2,1] 的下一个排列是 [1,2,3] 因为 [3,2,1] 不存在一个字典序更大的排列。 给你一个整数数组 nums 找出 nums 的下一个排列。
必须 原地 修改只允许使用额外常数空间。
样例
样例输入 nums [1,2,3] nums [3,2,1] nums [1,1,5] 样例输出 [1,3,2] [1,2,3] [1,5,1] 提示
1 nums.length 1000 nums[i] 100
思路
最初思路从后枚举nums[i]并且维护已经所有已枚举过的最小值如果当前nums[i] 维护的最小值那么交换两个值。并且记录当前交换的下标i,之后在对i1 ~ n-1区间内进行排序即可。主要实现难点就是局部排序可以说很麻烦。
之后看的题解理解咯另外一种思路从后枚举一定是有单调性的在单调的基础上直接反转这个局部区间即可。反转局部区间使用双指针很方便
代码实现
class Solution {public void nextPermutation(int[] nums) {int i nums.length - 2;while(i 0 nums[i] nums[i1]) i--;if(i 0){int j nums.length - 1;while(j 0 nums[i] nums[j]) --j;swap(nums, i, j);}int l i 1, r nums.length - 1;while(l r){swap(nums, l, r);r--;l;}}private void swap(int[] nums, int a, int b){int tmp nums[a];nums[a] nums[b];nums[b] tmp;}private void reverse(int[] nums, int l, int r){while(l r){swap(nums, l, r);r--;l;}}
}
