6016. Excel 表中某个范围内的单元格

Code

class Solution {
public:
    vector<string> cellsInRange(string s) {
        vector<string> res;
        for (char a = s[0]; a <= s[3]; a++) {
            for (char b = s[1]; b <= s[4]; b++) {
                string tmp = {a, b}; // 其实string可以通过“push_back”来加入字符(在一些编译器上‘+’不能直接加char字符)
                res.push_back(tmp);
            }
        }
        return res;
    }
};

6017. 向数组中追加 K 个整数(贪心)

题目描述

avatar

解题思路

自己一开始是这个思路,但是莫名其妙WA了。
于是在题解区看到一个更神仙的思路如下:
nums里面重复的元素可以剔除,这样并不会影响答案
我们先选择(1到k)一共k个数的和作为答案
但(1到k) 中的数可能在nums里面存在
那我们就这个重复的数加起来, 让后面多的一个坑即 k + 1
最后利用高斯求和公式把1 ~ k 的数用 O(1) 的时间加起来,再减去重复的

OS: 一直以为unique函数可以实现排序,但是今天才知道并没有这个功能,所以使用unique去重之前最好sort一下

Code

class Solution {
public:
    long long minimalKSum(vector<int>& nums, int k) {
        // 排序为了去重 也方面k后移
        sort(nums.begin(), nums.end());
        int n = unique(nums.begin(), nums.end()) - nums.begin();  // 所谓的去重只是把多余的数移到了最后面并没有删除
        
        long long d = 0;
        for (int i = 0; i < n; i++) 
            if (nums[i] <= k) d += nums[i], k++;
        
        return (1LL + k) * k / 2 - d ;
    }
};

6019. 替换数组中的非互质数(栈)

题目描述

avatar

解题思路

用vector模拟栈
思路参考此处

OS: (a + b) - c = a + (b - c) , (a * b) / c = a * (b / c) 这两个公式可以防止溢出

Code

class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int> &nums) {
        vector<int> s = {nums[0]};  // 只有当左边不能合并时,才加入新的数, 合并右边
        for (int i = 1; i < nums.size(); ++i) {
            s.push_back(nums[i]);
            while (s.size() > 1) {
                int x = s.back(), y = s[s.size() - 2];  // 尝试合并左边
                int g = gcd(x, y);
                if (g == 1) break;
                s.pop_back();
                s.back() *= x / g;  // 实际上是将(x * y) / g 转换为了y * (x / h) 防止溢出
            }
        }
        return s;
    }
};
上一篇 下一篇