今日题解

推荐社区：万人千题

二进制中1的个数

思路：不断地让n和n-1做与运算（n&=(n-1)），直到n变为0
因为每次运算会使n的最低位被翻转

class Solution {public:    int hammingWeight(uint32_t n) {        int res = 0;        while(n) {            n&=(n-1);            res++;        }        return res;    }};

各位相加

思路：主要是确保 res 一定是个位数，其他的不难想出来

class Solution {public:    int addDigits(int num) {        int res = 0;        while(num)        {            res += num %10;            num /= 10;            if(res >= 10)//确保res是1位数            {                res %= 10;                res++;            }        }        return res;    }};

两个数组之间的距离

思路：很直接的想法，两层for循环，遍历两个数组，判断对应的值相减是否小于d，若小于，则–res;

class Solution {public:    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {        int res = arr1.size();        for(int &i : arr1) {            for(int &j : arr2) {                if(abs(i-j) <= d) {                    --res;                    break;                }            }        }        return res;    }};

顺次数

思路：两层循环完美解决，外循环决定第一个数，内循环产生所有顺次数，只有当数字范围在[low, high]中时，存入结果。
比如：
i为1时，内层循环产生 1、12、123、…、123456789
i为2时，内层循环产生2、23、234、…、23456789
由于顺次数的长度最长为9，所以只用遍历1-8开头的所有顺次数

class Solution {public:    vector<int> sequentialDigits(int low, int high) {        vector<int> res;        for(int i=1; i<=9; ++i) {            int num = i;            for(int j = i+1; j<=9; ++j) {                num = num*10 + j;                if(num >= low && num <= high) {                    res.push_back(num);//每次循环都在res后面加一位数                }            }        }        sort(res.begin(), res.end());        return res;    }};

两个数组的交集

思路：快乐哈希表，舒服你我他

class Solution {public:    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {        unordered_set<int> res;        unordered_set<int> nums1_set(nums1.begin(), nums1.end());        for(auto &n2 : nums2) {            // nums2 的元素在 nums1_set 中出现过            if(nums1_set.find(n2) != nums1_set.end()) {                res.insert(n2);            }        }        return vector<int> (res.begin(), res.end());    }};

统计特殊四元组

思路：四层循环暴力破解

class Solution {public:    int countQuadruplets(vector<int>& nums) {        int n=nums.size();        int count=0;        for(int i=0;i<n;i++)        {            for(int j=i+1;j<n;j++)            {                for(int k=j+1;k<n;k++)                {                    for(int l=k+1;l<n;l++)                    {                        if(nums[i]+nums[j]+nums[k]==nums[l])                        {                            count++;                        }                    }                }            }        }        return count;    }};

方法二：统计左侧的两数之和，同时统计右侧的两数之差，比较左侧是否与右侧相等

class Solution {public:    int countQuadruplets(vector<int>& nums) {        int res = 0;        unordered_map<int, int> map;        int size = nums.size();        for(int i=1; i<size-2; ++i) {            for(int j=0; j<i; ++j) {                map[nums[i] + nums[j]]++;            }            for(int j=i+2; j<size; ++j) {                if(map.count(nums[j] - nums[i+1])) {                    res += map[nums[j] - nums[i+1]];                }            }        }        return res;    }};

重复至少k次且长度为m的模式

思路：
由于模式的长度为m，且需要重复k次，所以模式起始位置在[0, n - m * k]之间。
假设模式起始位置为i，判断后续序列[ i + m, i + m * k )是否满足条件，其实只需要判断arr[ j ]与arr[ j - m ]是否相同。

class Solution {public:    bool containsPattern(vector<int>& arr, int m, int k) {        int size = arr.size();        //如果数组中不存在至少重复 k 次且长度为 m 的模式，返回false        if(size < m*k) return false;                int i, j;        for(i=0; i<size-m*k + 1; ++i) {//注意这里需要加一，否则会错            for(j=i+m; j<i+m*k; ++j) {                if(arr[j] != arr[j-m]) break;            }            if(j == i + m*k) return true;        }        return false;    }};