今日題解

推薦社區：萬人千題

二進制中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;    }};