题一.K次取反后最大化的数组和(LeetCode)
题目描述
给你一个整数数组
nums
和一个整数k
,按以下方法修改该数组:
选择某个下标
i
并将nums[i]
替换为-nums[i]
。重复这个过程恰好
k
次。可以多次选择同一个下标i
。以这种方式修改数组后,返回数组 可能的最大和 。
示例 1:
输入:nums = [4,2,3], k = 1
输出:5
解释:选择下标 1 ,nums 变为 [4,-2,3] 。示例 2:
输入:nums = [3,-1,0,2], k = 3
输出:6
解释:选择下标 (1, 2, 2) ,nums 变为 [3,1,0,2] 。示例 3:
输入:nums = [2,-3,-1,5,-4], k = 2
输出:13
解释:选择下标 (1, 4) ,nums 变为 [2,3,-1,5,4] 。
题目分析
由于我们希望数组的和尽可能大,因此除非万不得已,我们应当总是修改负数,并且优先修改值最小的负数。因为将负数 −x 修改成 x 会使得数组的和增加 2x,所以这样的贪心操作是最优的。
题解
class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int m = 0;int ret = 0;for (auto x : nums){if (x < 0) m++;}sort(nums.begin(), nums.end());if (k > m){for (int i = 0; i < m; i++){nums[i] *= -1;}sort(nums.begin(), nums.end());for (int i = 0; i < k - m; i++){nums[0] *= -1;}}else{for (int i = 0; i < k; i++){nums[i] *= -1;}}for (auto x : nums){ret += x;}return ret;}
};
题二.按身高排序(LeetCode)
题目描述
给你一个字符串数组
names
,和一个由 互不相同 的正整数组成的数组heights
。两个数组的长度均为n
。对于每个下标
i
,names[i]
和heights[i]
表示第i
个人的名字和身高。请按身高 降序 顺序返回对应的名字数组
names
。
示例 1:
输入:names = ["Mary","John","Emma"], heights = [180,165,170]
输出:["Mary","Emma","John"]
解释:Mary 最高,接着是 Emma 和 John 。
示例 2:输入:names = ["Alice","Bob","Bob"], heights = [155,185,150]
输出:["Bob","Alice","Bob"]
解释:第一个 Bob 最高,然后是 Alice 和第二个 Bob 。
题解一.哈希表
class Solution1 {
public:vector<string> sortPeople(vector<string>& names, vector<int>& heights) {map<int, string> hash;vector<string> ans;for (int i = 0; i < names.size(); ++i) hash[heights[i]] = names[i];for (auto &i : hash) ans.push_back(i.second);reverse(ans.begin(), ans.end());return ans;}
};
*题解二.对下标排序
1.创建一个下标数组。
2.仅需对下标数组排序。
3.根据下标数组排序后的结果,找到原数组的信息。
class Solution2 {
public:vector<string> sortPeople(vector<string>& names, vector<int>& heights) {int n = names.size();vector<int> index(n);for (int i = 0; i < n; i++) index[i] = i;sort(index.begin(), index.end(), [&](int i, int j){return heights[i] > heights[j];});vector<string> ret;for (int i : index){ret.push_back(names[i]);}return ret;}
};
**题三.优势洗牌(LeetCode)
题目描述
给定两个长度相等的数组
nums1
和nums2
,nums1
相对于nums2
的优势可以用满足nums1[i] > nums2[i]
的索引i
的数目来描述。返回 nums1 的任意排列,使其相对于
nums2
的优势最大化。
示例 1:
输入:nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出:[2,11,7,15]示例 2:
输入:nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出:[24,32,8,12]
题目分析
先把nums1从小到大排序,并把nums2下标排序(因为需要num2原数组的信息)
然后将nums1与nums2比较,采用left、right双指针进行比较。
- 比不过,就去拖累最大的一个。
- 能比过,则直接比
需要注意的是,nums2的调用方式 nums2[index2[i]]。
题解
class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {int n=nums1.size();sort(nums1.begin(),nums1.end());vector<int> index2(n);for(int i=0;i<n;i++) index2[i]=i;sort(index2.begin(),index2.end(),[&](int i,int j){return nums2[i]<nums2[j];});vector<int> ret(n);int left=0,right=n-1;for(auto x : nums1){if(x>nums2[index2[left]]) ret[index2[left++]]=x;else ret[index2[right--]]=x;}return ret;}
};