算法

找出数组的第 K 大和 题目描述 给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。 数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复） 返回数组的 第 k 大和 。 子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。 注意：空子序列的和视作 0 。 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/find-the-k-sum-of-an-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 示例 1： 输入：nums = [2,4,-2], k = 5 输出：2 解释：所有可能获得的子序列和列出如下，按递减顺序排列： 6、4、4、2、2、0、0、-2 数组的第 5 大和是 2 。 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/find-the-k-sum-of-an-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 第k小子序列 首先考虑非负数组的情况下，然后求第k小的子序列的问题。 我们定义一个二元组(sum,i)，表示和为sum，结尾为i(第i位不算)的子序列。然后维护一个小根堆，每次取出堆顶，即sum最小的元素，然后将第i位的元素，考虑第i-1位元素选或者不选，将(sum+arr[i],i+1)和(sum+arr[i]-arr[i-1],i+1)添加到堆中，操作k次，第k次取出来的堆顶就是第k小的子序列。 考虑如下序列【1,2,4,8】，我们知道他的子序列和范围为0~15 注意观察图例中的二进制表示，可以发现对于第i位，比如8，这一列产生的数字的二进制第4位都是1，表示这个数被选择，即对应sum+arr[i]。然后可以发现数字15和11是由7产生而来，而11=7+8-4，即表示第i-1个数我们不取，即对应sum+arr[i]-arr[i-1]。可以看到对于第i位数字，他产生的那列数字，对应的第i为都是1的，这是因为在其之前的数字，第i为都是0，即已经将低位全部考虑完全了。 进一步我们知道一个长度为n的数组，其子序列个数为2^n，也即对应了二进制的表示情况 考虑负数情况 上述我们已经知道如何求一个非负数组的第k小子序列了，那么我们回到本题，考虑负数的情况。 首先这题要求的是第k大子序列和，可以转化为【最大的子序列和-第k小的子序列和】 首先最大的子序列和sum，即为数组中所有非负元素的和。当需要求比最大子序列和更小的子序列和时，相当于从sum中减去一些正数或者加上一些负数，因此将负数取绝对值，统一转化成减去一些正数的做法，然后对正数的数组求第k小的子序列和。 求第k小子序列和 同理，如果这题要求的是第k小的子序列和，那么我们同样可以转化为【最小的子序列和+第k小的子序列和】，同样，当需要求比最小子序列和更大的子序列和时，相当于给sum加上一些正数或者减去一些负数，同样将负数取绝对值，统一转化成加上一些正数的做法。 code typedef long long LL; class Solution { public: long long kSum(vector<int>& nums, int k) { priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<pair<LL,int>>> pq; LL sum=0; for(int i=0;i<nums....

重新排列后的最大子矩阵 题目描述 给你一个二进制矩阵 matrix ，它的大小为 m x n ，你可以将 matrix 中的 列 按任意顺序重新排列。 请你返回最优方案下将 matrix 重新排列后，全是 1 的子矩阵面积。 示例 1： 输入：matrix = [[0,0,1],[1,1,1],[1,0,1]] 输出：4 解释：你可以按照上图方式重新排列矩阵的每一列。 最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。 示例 2： 输入：matrix = [[1,0,1,0,1]] 输出：3 解释：你可以按照上图方式重新排列矩阵的每一列。 最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。 示例 3： 输入：matrix = [[1,1,0],[1,0,1]] 输出：2 解释：由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。 示例 4： 输入：matrix = [[0,0],[0,0]] 输出：0 解释：由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/largest-submatrix-with-rearrangements 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 对于每个单元格，从下往上统计连续1的个数 遍历数组，对于每一行，按之前统计数量降序排序 维护最小高度，遍历计算面积 code func largestSubmatrix(matrix [][]int) int { // 从下往上统计连续1的个数，作为高度 for i := 1; i < len(matrix); i++ { for j := 0; j < len(matrix[i]); j++ { if matrix[i][j] !...

最大矩形 题目描述 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 示例 1： 输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] 输出：6 解释：最大矩形如上图所示。 示例 2： 输入：matrix = [] 输出：0 示例 3： 输入：matrix = [[“0”]] 输出：0 示例 4： 输入：matrix = [[“1”]] 输出：1 示例 5： 输入：matrix = [[“0”,“0”]] 输出：0 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximal-rectangle 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 对于每个单元格，维护从上往下的连续的1的个数 遍历所有单元格，对于每个单元格，计算从左往右的连续的1的个数作为长，再从下往上遍历该列，以列的步数作为宽，维护长取最小值，求面积维护答案 code func maximalRectangle(matrix [][]byte) int { for i := 0; i < len(matrix); i++ { for j := 0; j < len(matrix[i]); j++ { matrix[i][j] = matrix[i][j] - 48 } } // 维护行上的连续1的个数 for i := 0; i < len(matrix); i++ { for j := 1; j < len(matrix[i]); j++ { if matrix[i][j] !...

分割数组的最大值 题目描述 给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法使得这 m 个子数组各自和的最大值最小。 示例 1： 输入：nums = [7,2,5,10,8], m = 2 输出：18 解释： 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。 示例 2： 输入：nums = [1,2,3,4,5], m = 2 输出：9 示例 3： 输入：nums = [1,4,4], m = 3 输出：4 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/split-array-largest-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 对数组维护前缀和 二分枚举答案，对于每个答案，二分查找区间和划分验证 code func splitArray(nums []int, m int) int { // 特殊处理 if len(nums) == 1 { return nums[0] } var l, r int var ans int = 0 // 维护前缀和数组 sum := make([]int, len(nums)+1) for i := 0; i < len(nums); i++ { l = max(l, nums[i]) r += nums[i] sum[i+1] = sum[i] + nums[i] } // 特殊处理 if m == 1 { return sum[len(sum)-1] } ans = sum[len(sum)-1] // 二分枚举答案 for l < r { mid := l + (r-l)/2 k, last := 0, 0 ok := true isans := true for k < m { // 二分查找区间和划分 p := sort....

和为K的子数组 题目描述 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1 : 输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。 说明 : 数组的长度为 [1, 20,000]。 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/subarray-sum-equals-k 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 思路一： 前缀和，枚举 做一次前缀和，对于第i个数，枚举子数组nums(j,i)，其中j<i 复杂度O(n^2) 思路二： 前缀和，hash 做一次前缀和，并且把前缀和的值保存到hash中记次数 对于目标整数k，可以表示为k=sum(j)-sum(i)，其中i<j，因此sum(i)=sum(j)-k 对于第j个数，查找sum(i)=sum(j)-k在hash中的次数，累加即为结果 例如1，2，3，4，5；目标数k=9 前缀和为1，3，6，10，15； 当j=3时（下标以0开始），sum(i)=sum(3)-k=10-9=1，因此需要找到数组中前缀和为1的次数，为1 当j=4时，sum(i)=sum(4)-k=15-9=6，因此需要找到前缀和为3的次数，为1 因此结果为2 code func subarraySum(nums []int, k int) int { sum :=make([]int,len(nums)+1) cnt :=make(map[int]int,len(nums)+1) var ans int cnt[0]++ for i:=0;i<len(nums);i++ { sum[i+1]=sum[i]+nums[i] ans += cnt[sum[i+1]-k] cnt[sum[i+1]]++ } return ans }