[LeetCode] 每日一题 July 11~20

  • July 11 - 274. H 指数；
  • July 12 - 275. H 指数 Ⅱ；
  • July 13 - 218. 天际线问题；
  • July 14 - 1818. 绝对差值和；
  • July 15 - 1846. 减小和重新排列数组后的最大元素；
  • July 16 - 剑指 Offer 53 - I. 在排序数组中查找数字 I；
  • July 17 - 剑指 Offer 42. 连续子数组的最大和；
  • July 18 - 面试题 10.02. 变位词组；
  • July 19 - 1838. 最高频元素的频数；
  • July 20 - 1877. 数组中最大数对和的最小值

July 11 - 274. H 指数

描述

给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 N - h 篇论文每篇被引用次数 不超过 h 次。

例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。

样例

1
2
3
4
输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
1
提示：如果 h 有多种可能的值，h 指数是其中最大的那个。

思路

首先我们可以将初始的 H 指数 h 设为 0，然后将引用次数排序，并且对排序后的数组从大到小遍历。

根据 H 指数的定义，如果当前 H 指数为 h 并且在遍历过程中找到当前值 citations[i]>h，则说明我们找到了一篇被引用了至少 h+1 次的论文，所以将现有的 h 值加 1。继续遍历直到 h 无法继续增大。最后返回 h 作为最终答案。

时间复杂度：O(nlogn)，其中 n 为数组 citations 的长度。即为排序的时间复杂度。

空间复杂度：O(logn)，其中 n 为数组 citations 的长度。即为排序的空间复杂度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int h = 0;
        sort(citations.rbegin(),citations.rend());
        for(auto a:citations){
            if(a>h){
                h++;
            }
            else{
                break;
            }
        }
        return h;
    }
};

July 12 - 275. H 指数 Ⅱ

描述

这是 H 指数 的延伸题目，本题中的 citations 数组是保证有序的。

优化算法到对数时间复杂度。

思路

由于数组 citations 已经按照升序排序，因此可以使用二分查找。

设查找范围的初始左边界 left 为 0, 初始右边界 right 为 n−1，其中 n 为数组 citations 的长度。每次在查找范围内取中点 mid，则有 n−mid 篇论文被引用了至少 citations[mid] 次。如果在查找过程中满足 citations[mid]≥n−mid，则移动右边界 right，否则移动左边界 left。

时间复杂度：O(logn)，其中 n 为数组 citations 的长度。二分查找的时间复杂度为 O(logn)。

空间复杂度：O(1)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] >= n - mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return n - left;
    }
};

July 13 - 218. 天际线问题

July 14 - 1818. 绝对差值和

描述

给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。

数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。

你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。

在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 109 + 7 取余 后返回。

样例

1
2
3
4
5
6
输入：nums1 = [1,7,5], nums2 = [2,3,5]
输出：3
解释：有两种可能的最优方案：
- 将第二个元素替换为第一个元素：[1,7,5] => [1,1,5] ，或者
- 将第二个元素替换为第三个元素：[1,7,5] => [1,5,5]
两种方案的绝对差值和都是 |1-2| + (|1-3| 或者 |5-3|) + |5-5| = 3
1
2
3
输入：nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
输出：0
解释：nums1 和 nums2 相等，所以不用替换元素。绝对差值和为 0
1
2
3
4
输入：nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
输出：20
解释：将第一个元素替换为第二个元素：[1,10,4,4,2,7] => [10,10,4,4,2,7]
绝对差值和为 |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20

思路

排序 + 二分查找

时间复杂度：O(nlogn)，其中 n 是数组 nums1 和 nums2 的长度。我们需要记录 nums 1 中的元素，并进行排序，时间复杂度是 O(nlogn)。计算 maxn 需要进行 n 次二分查找，每次二分查找的时间为 O(logn)，因此时间复杂度也是 O(nlogn)。所以总的时间复杂度为 O(nlogn)。

空间复杂度：O(n)，其中 n 是数组 nums 1和 nums 2 的长度。我们需要创建大小为 n 的辅助数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    static constexpr int mod = 1'000'000'007;

    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        vector<int> rec(nums1);
        sort(rec.begin(), rec.end());
        int sum = 0, maxn = 0;
        int n = nums1.size();
        for (int i = 0; i < n; i++) {
            int diff = abs(nums1[i] - nums2[i]);
            sum = (sum + diff) % mod;
            int j = lower_bound(rec.begin(), rec.end(), nums2[i]) - rec.begin();
            if (j < n) {
                maxn = max(maxn, diff - (rec[j] - nums2[i]));
            }
            if (j > 0) {
                maxn = max(maxn, diff - (nums2[i] - rec[j - 1]));
            }
        }
        return (sum - maxn + mod) % mod;
    }
};

July 15 - 1846. 减小和重新排列数组后的最大元素

描述

给你一个正整数数组 arr 。请你对 arr 执行一些操作（也可以不进行任何操作），使得数组满足以下条件：

  • arr 中 第一个 元素必须为 1 。
  • 任意相邻两个元素的差的绝对值 小于等于 1 ，也就是说，对于任意的 1 <= i < arr.length （数组下标从 0 开始），都满足 abs(arr[i] - arr[i - 1]) <= 1 。abs(x) 为 x 的绝对值。

你可以执行以下 2 种操作任意次：

  • 减小 arr 中任意元素的值，使其变为一个 更小的正整数 。
  • 重新排列 arr 中的元素，你可以以任意顺序重新排列。

请你返回执行以上操作后，在满足前文所述的条件下，arr 中可能的 最大值 。

样例

1
2
3
4
5
输入：arr = [2,2,1,2,1]
输出：2
解释：
我们可以重新排列 arr 得到 [1,2,2,2,1] ，该数组满足所有条件。
arr 中最大元素为 2 。
1
2
3
4
5
6
7
8
9
输入：arr = [100,1,1000]
输出：3
解释：
一个可行的方案如下：
1. 重新排列 arr 得到 [1,100,1000] 。
2. 将第二个元素减小为 2 。
3. 将第三个元素减小为 3 。
现在 arr = [1,2,3] ，满足所有条件。
arr 中最大元素为 3 。
1
2
3
输入：arr = [1,2,3,4,5]
输出：5
解释：数组已经满足所有条件，最大元素为 5 。

思路

排序 + 贪心

提示 1

如果一个数组是满足要求的，那么将它的元素按照升序排序后得到的数组也是满足要求的。

提示 1 解释

假设数组中出现了元素 x 和 y，且 x<y，由于相邻元素差值的绝对值小于等于 1，那么区间 [x,y] 内的所有整数应该都出现过。

只要我们令 x 和 y 分别为数组中元素的最小值和最大值，就说明了将数组升序排序后，得到的结果是不会出现「断层」的，也就是满足要求的。

提示 2

在提示 1 的基础上，我们得到了一个单调递增的数组。那么数组中相邻两个元素，要么后者等于前者，要么后者等于前者加上 1。

我们可以先将数组进行升序排序，随后对数组进行遍历，将 arr[i] 更新为其自身与 arr[i−1]+1 中的较小值即可。

最终的答案（最大值）即为 arr 中的最后一个元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        int n = arr.size();
        sort(arr.begin(),arr.end());
        arr[0] = 1;
        for(int i=0; i<n-1; i++){
            if(abs(arr[i+1]-arr[i])>1){
                arr[i+1] = arr[i] + 1;
            }
        }
        return arr[n-1];
    }
};

July 16 - 剑指 Offer 53 - I. 在排序数组中查找数字 I

描述

统计一个数字在排序数组中出现的次数。

样例

1
2
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
1
2
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

思路

二分查找

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 target 的下标，但这个方法的时间复杂度为 O(n)，没有利用到数组升序排列的条件。

由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

时间复杂度： O(logn) ，其中 n 为数组的长度。二分查找的时间复杂度为 O(logn)，一共会执行两次，因此总时间复杂度为 O(logn)。

空间复杂度：O(1) 。只需要常数空间存放若干变量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int first = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        int last = upper_bound(nums.begin(), nums.end(), target) - nums.begin();
        if(first >= nums.size()){
            return 0;
        }
        else{
            return last - first;
        }
    }
};

July 17 - 剑指 Offer 42. 连续子数组的最大和

描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

样例

1
2
3
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路

动态规划

时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。

空间复杂度：O(1)。我们只需要常数空间存放若干变量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0;
        int result = nums[0];
        for(const auto &x:nums){
            pre = max(x, pre+x);
            result = max(result, pre);
        }
        return result;
    }
};

July 18 - 面试题 10.02. 变位词组

描述

编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。

样例

1
2
3
4
5
6
7
8
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
说明：所有输入均为小写字母，不考虑答案输出的顺序。

思路

两个字符串互为变位词，当且仅当两个字符串包含的字母相同。同一组变位词中的字符串具备相同点，可以使用相同点作为一组变位词的标志，使用哈希表存储每一组变位词，哈希表的键为一组变位词的标志，哈希表的值为一组变位词列表。

遍历每个字符串，对于每个字符串，得到该字符串所在的一组变位词的标志，将当前字符串加入该组变位词的列表中。遍历全部字符串之后，哈希表中的每个键值对即为一组变位词。

由于互为变位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(nklogk)。

空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> map;
        for(auto str:strs){
            auto tmpstr = str;
            sort(tmpstr.begin(),tmpstr.end());
            map[tmpstr].push_back(str);
        }
        vector<vector<string>> ans;
        for(auto i=map.begin(); i!=map.end(); it++){
            ans.push_back(it->second);
        }
        return ans;
    }
};

July 19 - 1838. 最高频元素的频数

描述

元素的 频数 是该元素在一个数组中出现的次数。

给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。

执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。

样例

1
2
3
4
输入：nums = [1,2,4], k = 5
输出：3
解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。
4 是数组中最高频元素，频数是 3 。
1
2
3
4
5
6
输入：nums = [1,4,8,13], k = 5
输出：2
解释：存在多种最优解决方案：
- 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。
- 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。
- 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。
1
2
输入：nums = [3,9,6], k = 2
输出：1

思路

排序 + 滑动窗口

提示 1

操作后的最高频元素必定可以是数组中已有的某一个元素。

提示 2

优先操作距离目标值最近的（小于目标值的）元素。

提示 3

遍历数组中的每个元素作为目标值并进行尝试。此处是否存在一些可以用于优化算法的性质？

思路与算法

时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。排序数组的时间复杂度为 O(nlogn)，使用滑动窗口遍历目标值的时间复杂度为 O(n)。

空间复杂度：O(logn)，即为排序数组需要使用的栈空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//时间超限
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int max = 0;
        int n = nums.size();
        if(n == 0){
            return 0;
        }else if(n == 1){
            return 1;
        }else{
            sort(nums.begin(),nums.end());
            for(int i = 1; i<nums.size(); i++){
                int temp = 1;
                int tempk = k;
                for(int j = i-1; j>=0; j--){
                    tempk -= (nums[i] - nums[j]);
                    if(tempk>=0){  
                        temp++;
                    }
                    else{
                        break;
                    }
                }
                if(temp>max){
                    max = temp;
                }
            }
        }
        return max;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long total = 0;
        int l = 0, res = 1;
        for (int r = 1; r < n; ++r) {
            total += (long long)(nums[r] - nums[r - 1]) * (r - l);
            while (total > k) {
                total -= nums[r] - nums[l];
                ++l;
            }
            res = max(res, r - l + 1);
        }
        return res;
    }
};

July 20 - 1877. 数组中最大数对和的最小值

描述

一个数对 (a,b) 的 数对和 等于 a + b 。最大数对和 是一个数对数组中最大的 数对和 。

  • 比方说，如果我们有数对 (1,5) ，(2,3) 和 (4,4)，最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8 。

给你一个长度为 偶数 n 的数组 nums ，请你将 nums 中的元素分成 n / 2 个数对，使得：

  • nums 中每个元素 恰好 在 一个 数对中，且
  • 最大数对和 的值 最小 。

请你在最优数对划分的方案下，返回最小的 最大数对和 。

样例

1
2
3
4
输入：nums = [3,5,2,3]
输出：7
解释：数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。
1
2
3
4
输入：nums = [3,5,4,2,4,6]
输出：8
解释：数组中的元素可以分为数对 (3,5)，(4,4) 和 (6,2) 。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。

思路

排序 + 贪心

提示 1

数组内只有两个数的情况是平凡的。我们可以考虑数组中只有四个数 x1≤x2≤x3≤x4 的情况。此时 (x1,x4),(x2,x3) 的拆分方法对应的最大数对和一定是最小的。

提示 2

对于 n 个数（n 为偶数）的情况，上述的条件对应的拆分方法，即第 kk 大与第 kk 小组成的 n / 2n/2 个数对，同样可以使得最大数对和最小。

根据 提示 2，我们需要将 nums 排序。排序后，我们遍历每一个第 k 大与第 k 小组成的数对，计算它们的和，并维护这些和的最大值。同样根据 提示 2，遍历完成后求得的最大数对和就是满足要求的最小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minPairSum(vector<int>& nums) {
        int max = 0;
        int n = nums.size();
        sort(nums.begin(),nums.end());
        for(int i=0;i<n/2;i++){
            if(max < nums[i]+nums[n-i-1]){
                max = nums[i]+nums[n-i-1];
            }
        }
        return max;
    }
};