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)


相关推荐

  • 线程可以通过ipc通信吗_教育理论基础知识

    线程可以通过ipc通信吗_教育理论基础知识IPC——线程基础理论

  • mysql中一条insert语句批量插入多条记录

    mysql中一条insert语句批量插入多条记录插入语句常用写法: INSERTINTOitems(name,city,price,number,picture)VALUES(‘耐克运动鞋’,’广州’,500,1000,’003.jpg’); 这种方式只能够一次插入一条数据,要想插入多条数据,就得多次调用此sql语句,意味着多次与数据库建立连接。但是这样一来,就会增加服务器的负荷,因为,执行每一次SQL服务器都要同样对SQL进行分析、优化等操作。幸好MySQL提供了另一种解决方案,就是使用一条INSERT语句来插入多条记录。这并不是标准的SQ

  • [Unity面试] 2022年Unity面试题分享「建议收藏」

    [Unity面试] 2022年Unity面试题分享「建议收藏」2022Unity面试题分享建议收藏

  • 扑克牌花色排列_扑克牌花色大小顺序图片

    扑克牌花色排列_扑克牌花色大小顺序图片前阵子去某家公司笔试,发现有一道扑克牌排序的算法题,题目的大致意思是从一个给定的扑克牌文件读取内容,里面的内容是每行一个扑克牌牌面值,如♠J,♥Q,♣A,♦10等,要求对该文本进行两种排序,一种是按S

  • 100999凑整到万位进一_速算方法 速算口诀[通俗易懂]

    100999凑整到万位进一_速算方法 速算口诀[通俗易懂]“估算法”毫无疑问是资料分析题当中的速算第一法,在所有计算进行之前必须考虑能否先行估算。所谓估算,是在精度要求并不太高的情况下,下面是出国留学网小编为大家整理的“速算方法”。本内容为大家提供参考。希望对您有所帮助。请关注出国留学网!!!速算方法一、▲“九几乘九几,左减右补数,后面空两格,写上补乘补。”9300-5005×7=880035=883500看作两个空格二、▲任意数乘25,等于此数…

  • 2、Java基础02 – 【命令行运行HelloWorld】[通俗易懂]

    2、Java基础02 – 【命令行运行HelloWorld】[通俗易懂]操作步骤:1、新建一个文件夹(可以命名为Java)2、新建一个.txt文本文件,在文件中输入如下代码:publicclassHelloWorld{publicstaticvoidmain(String[]args){System.out.println(“helloworld”);}}3、重命名将文件名改为HelloWorld.java,并创建第一个java源文件4、编译.java文件是java的源文件,但是不能直接运行,必须先被编译成为.class文件才能够

发表回复

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

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