当前位置:首页 » 《随便一记》 » 正文

万人千题计划-32_0泡果奶的博客

23 人参与  2022年05月24日 11:09  分类 : 《随便一记》  评论

点击全文阅读


万人千题计划

  • 今日题解
    • 推荐社区:万人千题
    • 二进制中1的个数
    • 各位相加
    • 两个数组之间的距离
    • 顺次数
    • 两个数组的交集
    • 统计特殊四元组
    • 重复至少k次且长度为m的模式

今日题解

推荐社区:万人千题

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

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/40669.html

顺次  数组  循环  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 全文当爱恨如潮生+后续+结局(裴叙白乔若梨)_(裴叙白乔若梨)全文当爱恨如潮生+后续+结局免费列表(裴叙白乔若梨)
  • 盛夏晚晴天结局+番外+后续(乔雅柠傅怀瑾)_盛夏晚晴天结局+番外+后续乔雅柠傅怀瑾
  • 「前男友婚礼当天,我不请自到」章节彩蛋限时释出‌_秦克章节试读
  • 经年离歌愁未休现已上架(顾允廷宋卿落)_经年离歌愁未休现已上架(顾允廷宋卿落)
  • 盛景太匆匆+后续+结局(宁若曦沈砚舟黎思)结局_宁若曦沈砚舟黎思+结局列表_笔趣阁(盛景太匆匆+后续+结局)
  • 全书浏览无端却被春风误完结爽文(孟南汐宋祁钰)_无端却被春风误完结爽文(孟南汐宋祁钰)全书结局
  • 爱意如风散尽时全书+后续+结局免费全书_许栀林远舟_笔趣阁(爱意如风散尽时全书+后续+结局)
  • [结婚七年,老婆一直守身如玉]完结版全文_周寒声顾州免费试读
  • 全文无端却被春风误全书+后续(孟南汐宋祁钰)_(全文无端却被春风误全书+后续)孟南汐宋祁钰列表(全文无端却被春风误全书+后续)
  • 此去经年人未还霍沉洲全书+结局沈青禾霍沉洲_此去经年人未还霍沉洲全书+结局列表_笔趣阁沈青禾霍沉洲
  • 皇帝决定选择穿越女后,皇后娘娘登基了孟承霄穆清越沈织桐完本_皇帝决定选择穿越女后,皇后娘娘登基了(孟承霄穆清越沈织桐)
  • 无端却被春风误全面完结列表_无端却被春风误全面完结(孟南汐宋祁钰)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1