leetCode191/201/202/136 -Number of 1 Bits/Bitwise AND of Numbers Range/Happy Number/Single Number「建议收藏」

leetCode191/201/202/136 -Number of 1 Bits/Bitwise AND of Numbers Range/Happy Number/Single Number

大家好,又见面了,我是全栈君。

一:Number of 1 Bits

题目:

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

解法一:

此题关键是怎样推断一个数字的第i为是否为0  即: x& (1<<i)

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        for(int i = 0; i < 32; i++){
            if((n & (1<<i)) != 0)count++;
        }
        return count;
        
    }
};

解法二:此解关键在于明确n&(n-1)会n最后一位1消除,这样循环下去就能够求出n的位数中为1的个数

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

二:
Bitwise AND of Numbers Range

题目:

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

分析:此题提供两种解法:1:当m到n之前假设跨过了1,2,4,8等2^i次方的数字时(即推断m与n是否具有同样的最高位),则会为0,否则顺序将m到n相与。

解法二:利用上题中的思路。n&(n-1)会消除n中最后一个1,如1100000100当与n-1按位与时便会消除最后一个1,赋值给n(这样就减免了非常多不必要按位与的过程)

解法一:

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int bitm = 0, bitn = 0;
        for(int i =0; i < 31; i++){
            if(m & (1<<i))bitm = i;
            if(n & (1<<i))bitn = i;
        }
        if(bitm == bitn){
            int sum = m;
            for(int i = m; i < n; i++)  // 为了防止 2147483647+1 超过范围
                sum = (sum & i);
            sum = (sum & n);
            return sum;
        }
        else return 0;
    }
};

解法二:

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while(n > m){
            n &= n-1;
        }
        return n;
    }
};

三:
Happy Number

题目:

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

  • 12 + 92 = 82
  • 82 + 22 = 68
  • 62 + 82 = 100
  • 12 + 02 + 02 = 1

分析:此题关键是用一个set或者map来存储该数字是否已经出现过————hash_map+math

class Solution {
public:
    bool isHappy(int n) {
        while(n != 1){
            if(hset.count(n)) return false;    // 通过hashtable 推断是否出现过
            hset.insert(n);
            int sum = 0;
            while(n != 0){    // 求元素的各个位置平方和
                int mod = n%10;
                n = n/10;
                sum += mod * mod;
            }
            n = sum;
        }
        return true;
        
    }
private:
    set<int> hset;
};

四:Single Number

题目:

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

分析:此题关键在于用到异或

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i = 0; i < nums.size(); i++)
            ans ^= nums[i];
        return ans;
        
    }
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115212.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 经纪xx系统节点VIP案例介绍和深入分析异常

    经纪xx系统节点VIP案例介绍和深入分析异常

  • ios手游游戏辅助挂机工具_ios挂机RPG游戏大全_iPhone挂机RPG类手游排行榜_ios挂机RPG类手游精选推荐_ios挂机RP类手游下载…

    ios手游游戏辅助挂机工具_ios挂机RPG游戏大全_iPhone挂机RPG类手游排行榜_ios挂机RPG类手游精选推荐_ios挂机RP类手游下载…《康熙皇帝养成计划》是一款原创角色养成挂机手游,游戏以少年复仇为主线,融合勇闯神龙、秘境探险、帮派结盟、培养豪杰、金科演武…在《魔王村长和杂货店》中你将置身于一个日式RPG的幻想大陆之中,扮演一个看似寻常的村庄村长。宅男逆袭成大神剧情,又可与心仪校花共同谱写高校恋爱物语,还能体验玄幻修真与灵异兼备的乐趣,革新的游戏体能全面开启。《天天挂奇迹》是一款超畅快刺激的挂机RPG类游戏,游戏以经典《奇迹…

  • 用基尔霍夫定律求解电路时_基尔霍夫定律总结

    用基尔霍夫定律求解电路时_基尔霍夫定律总结1.先了解几个名词(1)支路一个二端原件视为一条支路–图中6个二端原件所以有6条支路。(2)结点两条或以上的支路连接的点。d,e可以看做一个结点。(3).回路(4).网孔1,22,

  • MySQL配置文件路径

    MySQL配置文件路径一、文件名和路径1.Linux中:/etc/my.cnf2.windows中:C:\ProgramData\MySQL\MySQLServer5.7\my.ini二、常见问题:1.windows下mysql配置文件my.ini的位置(1)找到“服务”,搜索MySQL(2)右击属性查看位置可以看到在可执行文件的路径是C:\ProgramData\MySQL\MySQLServer5.7\my.ini,即mysql的配置文件在该目录下。2.c盘没有ProgramData这个文件夹

  • thymeleaf判断对象是否为空的相关逻辑处理

    thymeleaf判断对象是否为空的相关逻辑处理thymeleaf判断对象是否为空有关逻辑处理在项目中,有时会遇到下面场景:添加页面和编辑页面共用一个页面,而通过后台传来的对象来判断提示用户是编辑页面还是添加页面,而编辑页面要使用这个对象的,添加页面用不到。在此记录下自己遇到的问题,看到了别人的博客才解决了@RequestMapping(path={“/add”,”edit”},method={RequestMethod.GET})publicStringaddOrEdit(Modelmodel,@RequestParam

  • linux 命令:whereis详解

    linux 命令:whereis详解linux命令:whereis详解

    2022年10月28日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号