leetcode-数组

数组

31. 下一个排列

题目

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，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 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。

示例 1：
输入： nums = [1,2,3] 输出： [1,3,2]
示例 2：
输入： nums = [3,2,1] 输出： [1,2,3]
示例 3：
输入： nums = [1,1,5] 输出： [1,5,1]

提示：

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 100

题解

/*** @param {number[]} nums* @return {void} Do not return anything, modify nums in-place instead.*/
var nextPermutation = function (nums) {let i = nums.length - 1 - 1;// 从右向左找到第一个降序位置while ((nums[i] >= nums[i + 1]) && i >= 0) {i--;}if (i >= 0) {//有降序节点let j = nums.length - 1;//从右往左找到一个刚好比降序节点大的值进行交换while (nums[j] <= nums[i]) {j--;}[nums[i], nums[j]] = [nums[j], nums[i]]}// 把降序节点右边的值（递减列）进行从小到大排序let l = i + 1, r = nums.length - 1;while (r > l) {if (nums[l] > nums[r]) {let value = nums[r];nums[r] = nums[l];nums[l] = value;}l++;r--;}
};

57. 插入区间

题目

给你一个 无重叠的 ， 按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [start(i), end(i)] 表示第 i 个区间的开始和结束，并且 intervals 按照 start(i) 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval，使得 intervals 依然按照 start(i) 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
返回插入之后的 intervals。
注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例 1：
输入： intervals = [[1,3],[6,9]], newInterval = [2,5] 输出： [[1,5],[6,9]]
示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

提示：

• 0 <= intervals.length <= 10(4)

• intervals[i].length == 2

• 0 <= start(i) <= end(i) <= 10(5)

• intervals 根据 start(i) 按 升序 排列

• newInterval.length == 2

• 0 <= start <= end <= 10(5)

题解

/*** @param {number[][]} intervals* @param {number[]} newInterval* @return {number[][]}*/
var insert = function (intervals, newInterval) {let res = [];intervals.push(newInterval);//合并到一个数组intervals.sort((a, b) => a[0] - b[0]);//按照数组中每一项（也是数组）的第一个值，从小到大进行排序res.push(intervals[0]);//把第一个先放到res中，从第二个值开始循环（索引为1）for (var i = 1; i < intervals.length; i++) {if (res[res.length - 1][1] < intervals[i][0]) {//当res数组中最后一个的第二个值，小于 intervals[i]中的第一个值，说明没有区间不重叠res.push(intervals[i]);} else if (res[res.length - 1][1] < intervals[i][1]) {//当res数组中最后一个的第二个值，大于或等于 intervals[i]中的第一个值，小于i intervals[i]中的第二个值，说明有区间重叠，直接把 intervals[i]中的第二个值给es数组中最后一个的第二个值res[res.length - 1][1] = intervals[i][1];}}return res;
};

122. 买卖股票的最佳时机 II

题目

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

示例 1：
输入： prices = [7,1,5,3,6,4] 输出： 7 解释： 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。 最大总利润为 4 + 3 = 7 。
示例 2：
输入： prices = [1,2,3,4,5] 输出： 4 解释： 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。 最大总利润为 4 。
示例 3：
输入： prices = [7,6,4,3,1] 输出： 0 解释： 在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

提示：

• 1 <= prices.length <= 3 * 10(4)

• 0 <= prices[i] <= 10(4)

题解

/*** @param {number[]} prices* @return {number}*/
var maxProfit = function (prices) {let r = 0;prices.reduce((p, v) => {r += Math.max(0, v - p);//把后一项和前一项的差值为正数的相加，就是赚的最多的return v;});return r;
};//简写版
var maxProfit = function(prices, r = 0) {let r=0;return prices.reduce((p,v)=>(r+=Math.max(0,v-p),v)),r
};

327. 区间和的个数

题目

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

示例 1：
输入： nums = [-2,5,-1], lower = -2, upper = 2 输出： 3 解释： 存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
示例 2：
输入： nums = [0], lower = 0, upper = 0 输出： 1

提示：

• 1 <= nums.length <= 10(5)

• -2(31) <= nums[i] <= 2(31) - 1

• -10(5) <= lower <= upper <= 10(5)

• 题目数据保证答案是一个 32 位 的整数

题解

/*** @param {number[]} nums* @param {number} lower* @param {number} upper* @return {number}*/
var countRangeSum = function (nums, lower, upper) {let n = 0;for (var i = 0; i < nums.length; i++) {//循环nums.length次let item=0;for (var j = i; j < nums.length; j++) {//从i项开始循环item += nums[j];if(item >=lower&&item<=upper){n++}}}return n
};

349. 两个数组的交集

题目

给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：
输入： nums1 = [1,2,2,1], nums2 = [2,2] 输出： [2]
示例 2：
输入： nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出： [9,4] 解释： [4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000

• 0 <= nums1[i], nums2[i] <= 1000

题解

/*** @param {number[]} nums1* @param {number[]} nums2* @return {number[]}*/
var intersection = function (nums1, nums2) {let ary1 = new Set(nums1);//利用set去重，有has方法let ary2 = new Set(nums2);//set数据结构类数组，需要转成数组可以调数组上的方法return Array.from(ary2).filter((item) => ary1.has(item));//Array.from(ary2) 类数组转数组   
};

912. 排序数组

题目

给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：
输入： nums = [5,2,3,1] 输出： [1,2,3,5]
示例 2：
输入： nums = [5,1,1,2,0,0] 输出： [0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 10(4)

• -5 * 10(4) <= nums[i] <= 5 * 10(4)

题解

• 接收一个数组 nums，通过计数排序的方法对数组进行排序，并返回排序后的新数组 newArr

• 时间复杂度: O(n+k)

  找出最大值和最小值的循环遍历了数组 nums 一次，时间复杂度为O(n) ，其中 n是数组 nums 的长度。
  统计元素出现次数的循环也遍历了数组 nums 一次，时间复杂度为O(n) 。
  根据计数数组重建排序后的数组的循环遍历了计数数组 arr 一次，时间复杂度为O(k) ，其中k是计数数组的长度（k=max - min +1）。
  总的时间复杂度为O(n+k)。

/*** @param {number[]} nums* @return {number[]}*/
var sortArray = function (nums) {// 找最大最小值let max = 0;let min = 0;for (let i = 0; i < nums.length; i++) {max = max > nums[i] ? max : nums[i];min = min < nums[i] ? min : nums[i];}const newArr = [];// 初始化数组长度为参数长度const arr = new Array(max - min + 1).fill(0);// 统计每一个值出现的次数for (let i = 0; i < nums.length; i++) {let arrIndex = nums[i] - min;if (arr[arrIndex] !== undefined) {arr[arrIndex] += 1;} else {arr[arrIndex] = 1;}}// 把有值的数据放到新数组里for (let i = 0; i < arr.length; i++) {const list = new Array(arr[i]).fill(min + i);newArr.push(...list);}return newArr;
};

922. 按奇偶排序数组 II

题目

给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。
对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。
你可以返回 任何满足上述条件的数组作为答案 。

示例 1：
输入： nums = [4,2,5,7] 输出： [4,5,2,7] 解释： [4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
示例 2：
输入： nums = [2,3] 输出： [2,3]

提示：

• 2 <= nums.length <= 2 * 10(4)

• nums.length 是偶数

• nums 中一半是偶数

• 0 <= nums[i] <= 1000

进阶： 可以不使用额外空间解决问题吗？

题解

/*** @desc 使用额外内存* @param {number[]} nums* @return {number[]}*/
var sortArrayByParityII = function (nums) {const arr = [];let even = 0;let odd = 1;for (let i = 0; i < nums.length; i++) {if (nums[i] % 2 === 0) {arr[even] = nums[i];even += 2;}else{arr[odd] = nums[i];odd += 2;}}return arr;
};/*** @desc 不用额外空间* @param {number[]} nums* @return {number[]}*/
var sortArrayByParityII = function (nums) {let j = 1; // 奇数索引for (let i = 0; i < nums.length - 1; i += 2) {//数组中的偶数位置开始错误时if (nums[i] % 2 !== 0) {while (j < nums.length) {if (nums[j] % 2 === 1) {j += 2;} else {//奇数位置的值错误，和偶数错误值交换[nums[i], nums[j]] = [nums[j], nums[i]];j += 2;break;}}}}return nums;
};

941. 有效的山脉数组

题目

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：

• arr.length >= 3

• 在 0 < i < arr.length - 1 条件下，存在 i 使得：

  • arr[0] < arr[1] < ... arr[i-1] < arr[i]

  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]
    

示例 1：
输入： arr = [2,1] 输出： false
示例 2：
输入： arr = [3,5,5] 输出： false
示例 3：
输入： arr = [0,3,2,1] 输出： true

提示：

• 1 <= arr.length <= 10(4)

• 0 <= arr[i] <= 10(4)

题解

/*** @param {number[]} A* @return {boolean}*/
var validMountainArray = function (A) {if (A.length < 3) return false;let max = Math.max(...A);//找到最高点let index = A.indexOf(max);//拿到最高点的索引let i = 0;let isBoolean = true;let goUp = false;let goDown = false;while (i < A.length - 1) {if (i < index && A[i] < A[i + 1]) {//最高点之前是上升趋势i++;goUp = true;} else if (i >= index && A[i] > A[i + 1]) {//最高点之后是下降趋势i++;goDown = true;} else {//不满足上面就失败，break中止循环isBoolean = false;break;}}return goUp && goDown && isBoolean;
};

1014. 最佳观光组合

题目

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。

示例 1：
输入： values = [8,1,5,2,6] 输出： 11 解释： i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
示例 2：
输入： values = [1,2] 输出： 2

提示：

• 2 <= values.length <= 5 * 10(4)

• 1 <= values[i] <= 1000

题解

/*** @param {number[]} values* @return {number}*/
var maxScoreSightseeingPair = function (values) {// let max = 0;// // 双for循环 超时// for (let i = 0; i < values.length - 1; i++) {//   for (let j = i + 1; j < values.length; j++) {//     max = Math.max(max, values[i] + values[j] + i - j);//   }// }// vi + vj + i - j => (vi + i) + vj - jlet ans = 0;let max = values[0];for (let j = 1; j < values.length; j++) {ans = Math.max(ans, max + values[j] - j);max = Math.max(max, values[j] + j);}return ans;
};

1356. 根据数字二进制下 1 的数目排序

题目

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。

示例 1：
输入： arr = [0,1,2,3,4,5,6,7,8] 输出： [0,1,2,4,8,3,5,6,7] 解释： [0] 是唯一一个有 0 个 1 的数。 [1,2,4,8] 都有 1 个 1 。 [3,5,6] 有 2 个 1 。 [7] 有 3 个 1 。 按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]
示例 2：
输入： arr = [1024,512,256,128,64,32,16,8,4,2,1] 输出： [1,2,4,8,16,32,64,128,256,512,1024] 解释： 数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。
示例 3：
输入： arr = [10000,10000] 输出： [10000,10000]
示例 4：
输入： arr = [2,3,5,7,11,13,17,19] 输出： [2,3,5,17,7,11,13,19]
示例 5：
输入： arr = [10,100,1000,10000] 输出： [10,100,10000,1000]

提示：

• 1 <= arr.length <= 500

• 0 <= arr[i] <= 10^4

题解

/*** @param {number[]} arr* @return {number[]}*/
var sortByBits = function (arr) {return arr.sort((a, b) => {let aIndex = a.toString(2).match(/1/g)?.length || 0;//a.toString(2) 把数组转换成二进制的字符串，.match(/1/g)?.length || 0  匹配到1的数量没有就是0let bIndex = b.toString(2).match(/1/g)?.length || 0;if (aIndex < bIndex || (aIndex <= bIndex && a < b)) {//aIndex < bIndex  按照1的数量从小到大，aIndex <= bIndex && a < b 如果1的数量相同  从小到大排序return -1;}});
};

1599. 经营摩天轮的最大利润

题目

你正在经营一座摩天轮，该摩天轮共有 4 个座舱 ，每个座舱 最多可以容纳 4 位游客 。你可以 逆时针 轮转座舱，但每次轮转都需要支付一定的运行成本 runningCost 。
给你一个长度为 n 的数组 customers ， customers[i] 是在第 i 次轮转（下标从 0 开始）之前到达的新游客的数量。这也意味着你必须在新游客到来前轮转 i 次。如果有座舱空闲就不能让游客等待。 每位游客在登上离地面最近的座舱前都会支付登舱成本 boardingCost ，一旦该座舱再次抵达地面，他们就会离开座舱结束游玩。
你可以随时停下摩天轮，即便是 在服务所有游客之前 。如果你决定停止运营摩天轮，为了保证所有游客安全着陆，将免费进行所有后续轮转 。注意，如果有超过 4 位游客在等摩天轮，那么只有 4 位游客可以登上摩天轮，其余的需要等待 下一次轮转 。
返回最大化利润所需执行的 最小轮转次数 。 如果不存在利润为正的方案，则返回 -1 。

示例 1：

输入： customers = [8,3], boardingCost = 5, runningCost = 6 输出： 3 解释： 座舱上标注的数字是该座舱的当前游客数。 1. 8 位游客抵达，4 位登舱，4 位等待下一舱，摩天轮轮转。当前利润为 4 * $5 - 1 * $6 = $14 。 2. 3 位游客抵达，4 位在等待的游客登舱，其他 3 位等待，摩天轮轮转。当前利润为 8 * $5 - 2 * $6 = $28 。 3. 最后 3 位游客登舱，摩天轮轮转。当前利润为 11 * $5 - 3 * $6 = $37 。 轮转 3 次得到最大利润，最大利润为 $37 。
示例 2：
输入： customers = [10,9,6], boardingCost = 6, runningCost = 4 输出： 7 解释： 1. 10 位游客抵达，4 位登舱，6 位等待下一舱，摩天轮轮转。当前利润为 4 * $6 - 1 * $4 = $20 。 2. 9 位游客抵达，4 位登舱，11 位等待（2 位是先前就在等待的，9 位新加入等待的），摩天轮轮转。当前利润为 8 * $6 - 2 * $4 = $40 。 3. 最后 6 位游客抵达，4 位登舱，13 位等待，摩天轮轮转。当前利润为 12 * $6 - 3 * $4 = $60 。 4. 4 位登舱，9 位等待，摩天轮轮转。当前利润为 * $6 - 4 * $4 = $80 。 5. 4 位登舱，5 位等待，摩天轮轮转。当前利润为 20 * $6 - 5 * $4 = $100 。 6. 4 位登舱，1 位等待，摩天轮轮转。当前利润为 24 * $6 - 6 * $4 = $120 。 7. 1 位登舱，摩天轮轮转。当前利润为 25 * $6 - 7 * $4 = $122 。 轮转 7 次得到最大利润，最大利润为$122 。
示例 3：
输入： customers = [3,4,0,5,1], boardingCost = 1, runningCost = 92 输出： -1 解释： 1. 3 位游客抵达，3 位登舱，0 位等待，摩天轮轮转。当前利润为 3 * $1 - 1 * $92 = -$89 。 2. 4 位游客抵达，4 位登舱，0 位等待，摩天轮轮转。当前利润为 7 * $1 - 2 * $92 = -$177 。 3. 0 位游客抵达，0 位登舱，0 位等待，摩天轮轮转。当前利润为 7 * $1 - 3 * $92 = -$269 。 4. 5 位游客抵达，4 位登舱，1 位等待，摩天轮轮转。当前利润为 11 * $1 - 4 * $92 = -$357 。 5. 1 位游客抵达，2 位登舱，0 位等待，摩天轮轮转。当前利润为 13 * $1 - 5 * $92 = -$447 。 利润永不为正，所以返回 -1 。

提示：

• n == customers.length

• 1 <= n <= 10(5)

• 0 <= customers[i] <= 50

• 1 <= boardingCost, runningCost <= 100

题解

/*** @param {number[]} customers* @param {number} boardingCost* @param {number} runningCost* @return {number}*/
var minOperationsMaxProfit = function (customers, boardingCost, runningCost) {let remainder = 0; //等待人数let profit = 0; //盈利let orders = 0; //轮次let maxProfit = 0; //最大盈利let maxIndex = 0; //最大盈利轮次let profitOnce = 4 * boardingCost - runningCost; //一轮4个人盈利// 轮次游客for (let i = 0; i < customers.length; i++) { const customer = customers[i];// 运行一轮后剩余人数 const remainderPeople = remainder + customer - 4;if (remainderPeople > 0) {remainder = remainderPeople;const num = profit + profitOnce;maxProfit = Math.max(maxProfit, profit, num);if (maxProfit >= profit && num > profit) {maxIndex = orders + 1;}profit = num;} else {remainder = 0;const num = profit + (4 + remainderPeople) * boardingCost - runningCost;maxProfit = Math.max(maxProfit, profit, num);if (maxProfit >= profit && num > profit) {maxIndex = orders + 1;}profit = num;}orders++;}// 只需要让剩余人做完摩天轮while (remainder > 0) {if (remainder > 4) {const num = profit + profitOnce;maxProfit = Math.max(maxProfit, profit, num);profit = num;if (maxProfit >= profit) {maxIndex = orders + 1;}} else {const num = profit + remainder * boardingCost - runningCost;maxProfit = Math.max(maxProfit, profit, num);if (maxProfit > profit && profit > num) {maxIndex = orders;} else if (maxProfit > profit) {maxIndex = orders + 1;}profit = num;}remainder = remainder - 4;orders++;}return profit > 0 ? (maxIndex ? maxIndex : orders) : -1;
};

1944. 队列中可以看到的人数

题目

有 n 个人排成一个队列，从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights ，每个整数 互不相同，heights[i] 表示第 i 个人的高度。
一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的，第 i 个人能看到第 j 个人的条件是 i < j 且 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]) 。
请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人在他右侧队列中能 看到 的 人数 。

示例 1：

输入： heights = [10,6,8,5,11,9] 输出： [3,1,2,1,1,0] 解释： 第 0 个人能看到编号为 1 ，2 和 4 的人。 第 1 个人能看到编号为 2 的人。 第 2 个人能看到编号为 3 和 4 的人。 第 3 个人能看到编号为 4 的人。 第 4 个人能看到编号为 5 的人。 第 5 个人谁也看不到因为他右边没人。
示例 2：
输入： heights = [5,1,2,3,10] 输出： [4,1,1,1,0]

提示：

• n == heights.length

• 1 <= n <= 10(5)

• 1 <= heights[i] <= 10(5)

• heights 中所有数 互不相同 。

题解

/*** @param {number[]} heights* @return {number[]}*/
var canSeePersonsCount = function (heights) {const n = heights.length;const seeArr = new Array(n).fill(0);const stack = []; // 单调栈递减for (let i = n - 1; i >= 0; i--) {const currentHeight = heights[i]; //当前人高度let prevHeight = stack[stack.length - 1]; //栈里最低的while (stack.length > 0 && currentHeight > prevHeight) {// 当前人高度比栈里人高，后面的人看不到挡住了，移除矮的stack.pop();seeArr[i] += 1; //当前人可以看到prevHeight = stack[stack.length - 1];}if (stack.length) {//必定有一个人可以被当前人看到,由于不比栈里的人高，所以只能看到一个seeArr[i] += 1;}stack.push(currentHeight);}return seeArr;
};

2171. 拿出最少数目的魔法豆

题目

给定一个 正整数 数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。
请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少还有一颗 魔法豆的袋子）魔法豆的数目 相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。
请返回你需要拿出魔法豆的 最少数目。

示例 1：
输入： beans = [4,1,6,5] 输出： 4 解释： - 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。 剩下袋子中魔法豆的数目为：[4,++0++,6,5] - 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为：[4,0,++4++,5] - 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。 剩下袋子中魔法豆的数目为：[4,0,4,++4++] 总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。 没有比取出 4 个魔法豆更少的方案。
示例 2：
输入： beans = [2,10,3,2] 输出： 7 解释： - 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为：[++0++,10,3,2] - 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为：[0,10,3,++0++] - 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。 剩下袋子中魔法豆的数目为：[0,10,++0++,0] 总共拿出了 2 + 2 + 3 = 7 个魔法豆，剩下非空袋子中魔法豆的数目相等。 没有比取出 7 个魔法豆更少的方案。

提示：

• 1 <= beans.length <= 10(5)

• 1 <= beans[i] <= 10(5)

题解

/*** @param {number[]} beans* @return {number}*/
var minimumRemoval = function (beans) {// 从小到大排序beans = beans.sort((a, b) => a - b);const n = beans.length;let sum = 0, max = 0;for (let i = 0; i < n; i++) {sum += beans[i];// 保留的最多豆子max = Math.max(max, (n - i) * beans[i]);}return sum - max;
};

2397. 被列覆盖的最多行数

题目

给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ；另给你一个整数 numSelect，表示你必须从 matrix 中选择的 不同 列的数量。
如果一行中所有的 1 都被你选中的列所覆盖，则认为这一行被 覆盖 了。
形式上，假设 s = {c(1), c(2), ...., c(numSelect)} 是你选择的列的集合。对于矩阵中的某一行 row ，如果满足下述条件，则认为这一行被集合 s 覆盖：

• 对于满足 matrix[row][col] == 1 的每个单元格 matrix[row][col]（0 <= col <= n - 1），col 均存在于 s 中，或者

• row 中 不存在 值为 1 的单元格。

你需要从矩阵中选出 numSelect 个列，使集合覆盖的行数最大化。
返回一个整数，表示可以由 numSelect 列构成的集合 覆盖 的 最大行数 。

示例 1：

输入： matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2 输出： 3 解释： 图示中显示了一种覆盖 3 行的可行办法。 选择 s = {0, 2} 。 - 第 0 行被覆盖，因为其中没有出现 1 。 - 第 1 行被覆盖，因为值为 1 的两列（即 0 和 2）均存在于 s 中。 - 第 2 行未被覆盖，因为 matrix[2][1] == 1 但是 1 未存在于 s 中。 - 第 3 行被覆盖，因为 matrix[2][2] == 1 且 2 存在于 s 中。 因此，可以覆盖 3 行。 另外 s = {1, 2} 也可以覆盖 3 行，但可以证明无法覆盖更多行。
示例 2：

输入： matrix = [[1],[0]], numSelect = 1 输出： 2 解释： 选择唯一的一列，两行都被覆盖了，因为整个矩阵都被覆盖了。 所以我们返回 2 。

提示：

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 12

• matrix[i][j] 要么是 0 要么是 1

• 1 <= numSelect <= n

题解

/*** @param {number[][]} matrix* @param {number} numSelect* @return {number}*/
var maximumRows = function (matrix, numSelect) {const n = matrix[0].length; // 列const zeroCol = numSelect,  // 覆盖列数 覆盖后为0oneCol = n - numSelect; // 未覆盖列， 为1const list = []; // 覆盖列组合数量function dfs(zeroCol, oneCol, str) {if (str.length === n) {list.push(parseInt(str, 2)) // 二进制解析为十进制return;}if (zeroCol > 0) dfs(zeroCol - 1, oneCol, str + '0');if (oneCol > 0) dfs(zeroCol, oneCol, str + '1');}dfs(zeroCol, oneCol, '');let maxCover = 0;for (let i = 0; i < list.length; i++) {//每种覆盖列方案得到的覆盖数量let cover = 0; // 每种方案的覆盖数量for (let j = 0; j < matrix.length; j++) {const item = parseInt(matrix[j].join(''), 2);// 当前行转2进制if ((item & list[i]) === 0) { // 利用位运算 判断行是否被覆盖cover++;}if(j === matrix.length - 1){maxCover = Math.max(cover, maxCover);}}}return maxCover;
};

2961. 双模幂运算

题目

给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [a(i), b(i), c(i,) m(i)]，以及一个整数 target 。
如果满足以下公式，则下标 i 是 好下标：

• 0 <= i < variables.length

• ((a(i)(bi) % 10)(ci)) % m(i) == target

返回一个由 好下标 组成的数组，顺序不限 。

示例 1：
输入： variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2 输出： [0,2] 解释： 对于 variables 数组中的每个下标 i ： 1) 对于下标 0 ，variables[0] = [2,3,3,10] ，(2(3) % 10)(3) % 10 = 2 。 2) 对于下标 1 ，variables[1] = [3,3,3,1] ，(3(3) % 10)(3) % 1 = 0 。 3) 对于下标 2 ，variables[2] = [6,1,1,4] ，(6(1) % 10)(1) % 4 = 2 。 因此，返回 [0,2] 作为答案。
示例 2：
输入： variables = [[39,3,1000,1000]], target = 17 输出： [] 解释： 对于 variables 数组中的每个下标 i ： 1) 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(39(3) % 10)(1000) % 1000 = 1 。 因此，返回 [] 作为答案。

提示：

• 1 <= variables.length <= 100

• variables[i] == [a(i), b(i), c(i), m(i)]

• 1 <= a(i), b(i), c(i), m(i) <= 10(3)

• 0 <= target <= 10(3)

题解

const pow = (base, exponent) => {const baseBig = BigInt(base);const exponentBig = BigInt(exponent);return baseBig ** exponentBig
}
/*** @param {number[][]} variables* @param {number} target* @return {number[]}*/
var getGoodIndices = function (variables, target) {const targetArr = [];for (let i = 0; i < variables.length; i++) {const [a, b, c, d] = variables[i];const num = pow(pow(a, b) % BigInt(10), c) % BigInt(d);if (Number(num) === target) targetArr.push(i);}return targetArr;
};

3184. 构成整天的下标对数目 I

题目

给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。
整天 定义为时间持续时间是 24 小时的 整数倍 。
例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。

示例 1：
输入： hours = [12,12,30,24,24]
输出： 2
解释：
构成整天的下标对分别是 (0, 1) 和 (3, 4)。
示例 2：
输入： hours = [72,48,24,3]
输出： 3
解释：
构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。

提示：

• 1 <= hours.length <= 100

• 1 <= hours[i] <= 10(9)

题解

/*** @param {number[]} hours* @return {number}*/
var countCompleteDayPairs = function (hours) {let count = 0;const Is24Multiple = (x, y) => {return (x + y) % 24 === 0;};for (let i = 0; i < hours.length - 1; i++) {const x = hours[i];for (let j = i + 1; j < hours.length; j++) {const y = hours[j];if (Is24Multiple(x, y)) {count++;}}}return count;
};