算法复健-第五天

今天五道题，原因题太水了

Math-Easy-错误的集合

题面

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1：

输入：nums = [1,2,2,4]
输出：[2,3]

示例 2：

输入：nums = [1,1]
输出：[1,2]

提示：

• 2 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^4

解答过程

本题第一眼印象其实是拿昨天发过的按位异或解，但是本题只能得到两个数字的异或，需要结合更多位运算知识，全忘完了，有空在复习吧

最后选择用了哈希表解，没啥好说的，时间复杂度和用位运算一样，亏点内存而已

代码

vector<int> findErrorNums(vector<int>& nums) {
        vector<int> ans;
        unordered_set<int> set;
        for (size_t i = 0; i < nums.size(); i++)
        {
            if (set.find(nums[i]) != set.end())
            {
                ans.push_back(nums[i]);
            }
            set.insert(nums[i]);
        }
        for (size_t i = 1; i <= nums.size(); i++)
        {
            if (set.find(i) == set.end())
            {
                ans.push_back(i);
            }

        }
        return ans;
    }

Math-Easy-自除数

题面

自除数 是指可以被它包含的每一位数整除的数。

• 例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。

自除数 不允许包含 0 。

给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right]（包括两个端点）内所有的 自除数 。

示例 1：

输入：left = 1, right = 22
输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

示例 2:

输入：left = 47, right = 85
输出：[48,55,66,77]

提示：

• 1 <= left <= right <= 10^4

解答过程

没想多的直接打了个暴力，击败了百分百的CPP提交，确实没什么好说的，直接遍历逐个判断就行

代码

vector<int> selfDividingNumbers(int left, int right) {
        vector<int> ans;
        for (size_t i = left; i <= right; i++)
        {
            if (isZiChu(i))
            {
                ans.push_back(i);
            }
        }
        return ans;
    }
    bool isZiChu(int n){
        if (n == 0)
        {
            return false;
        }    
        string s = to_string(n);
        for (size_t i = 0; i < s.size(); i++)
        {
            if (s.at(i) - '0' == 0)
            {
                return false;
            }

            if (n % (s.at(i) - '0') != 0)
            {

                return false;
            }

        }
        return true;
    }

Math-Easy-旋转字符串

题面

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。

s 的 旋转操作 就是将 s 最左边的字符移动到最右边。

• 例如, 若 s = 'abcde'，在旋转一次之后结果就是'bcdea' 。

示例 1:

输入: s = "abcde", goal = "cdeab"
输出: true

示例 2:

输入: s = "abcde", goal = "abced"
输出: false

提示:

• 1 <= s.length, goal.length <= 100
• s 和 goal 由小写英文字母组成

解答过程

本题思考了一下差点打暴力，发现如果在s后面再拼接一个s，这个字符串就包含所有s做移动操作的结果作为子串，所以我们只需要搜索s+s里是否包含goal就行，一句代码解决问题

代码

class Solution {
public:
    bool rotateString(string s, string goal) {
        return s.length() == goal.length() && (s+s).find(goal) != string::npos;
    }
};

Math-Easy-较大分组的位置

在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。

例如，在字符串 s = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。

分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,6] 。

我们称所有包含大于或等于三个连续字符的分组为 较大分组 。

找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。

示例 1：

输入：s = "abbxxxxzzy"
输出：[[3,6]]
解释："xxxx" 是一个起始于 3 且终止于 6 的较大分组。

示例 2：

输入：s = "abc"
输出：[]
解释："a","b" 和 "c" 均不是符合要求的较大分组。

示例 3：

输入：s = "abcdddeeeeaabbbcd"
输出：[[3,5],[6,9],[12,14]]
解释：较大分组为 "ddd", "eeee" 和 "bbb"

示例 4：

输入：s = "aba"
输出：[]

提示：

• 1 <= s.length <= 1000
• s 仅含小写英文字母

解答过程

一开始没读题以为大分组指的是最长的分组的数量，结果看到是三个或三个以上，那就没意思了，直接遍历一遍就好

代码

vector<vector<int>> largeGroupPositions(string s) {
        vector<vector<int>> ans;
        int right = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i+1] != s[i])
            {
                if (i-right+1 >= 3)
                {
                    vector<int> v = {right,i};
                    ans.push_back(v);
                }
                right = i+1;
            }
        }
        return ans;
    }

Math-Easy-公平的糖果交换

题面

爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ，aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量，bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。

两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。

返回一个整数数组 answer，其中 answer[0] 是爱丽丝必须交换的糖果盒中的糖果的数目，answer[1] 是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中 任何一个 。题目测试用例保证存在与输入对应的答案。

示例 1：

输入：aliceSizes = [1,1], bobSizes = [2,2]
输出：[1,2]

示例 2：

输入：aliceSizes = [1,2], bobSizes = [2,3]
输出：[1,2]

示例 3：

输入：aliceSizes = [2], bobSizes = [1,3]
输出：[2,3]

示例 4：

输入：aliceSizes = [1,2,5], bobSizes = [2,4]
输出：[5,4]

提示：

• 1 <= aliceSizes.length, bobSizes.length <= 10^4
• 1 <= aliceSizes[i], bobSizes[j] <= 10^5
• 爱丽丝和鲍勃的糖果总数量不同。
• 题目数据保证对于给定的输入至少存在一个有效答案。

解答过程

本题思路其实也就是直接暴搜，设需要交换的糖果为x,y,爱丽丝的糖果总数为sumA,鲍勃为sumB,则通过数学运算得到x = y + (sumA-sumB)/2,把爱丽丝的每盒糖果塞进哈希表里，遍历鲍勃的糖果数组在哈希表里搜索有没有对应的x即可

代码

vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
        int sumA = accumulate(aliceSizes.begin(), aliceSizes.end(), 0);
        int sumB = accumulate(bobSizes.begin(), bobSizes.end(), 0);
        int delta = (sumA - sumB) / 2;
        unordered_set<int> rec(aliceSizes.begin(), aliceSizes.end());
        vector<int> ans;
        for (auto& y : bobSizes) {
            int x = y + delta;
            if (rec.count(x)) {
                ans = vector<int>{x, y};
                break;
            }
        }
        return ans;
    }