自学内容网 自学内容网

算法学习day20

位运算相关知识点:

1.与 & :0101&1110=0100 两个位置上都为1时,才为1

2.或 | : 0101&1110=1111  两个位置上都为0时, 才为0

3.异或 ^ :0101^1110=1111 两个位置上不相等的时,为1;相等时,为0

4.取反 ~:~0=1 ~1=0;

5.左移 << :十进制中左移就是*2;二进制中就是向左移动k位,右边补零 0001<<2=0100

6.右移 >>:十进制中右移就是/2;二进制中是向右移动k位,无符号数左边补0,有符号数左边补符号位。1000>>2=0010

位运算相关操作:

1.要将每一位上的数字取反。num^111...111(相同为0,不同为1)。num上的数字:0->1 1->0

2.取最后一位上的数字。num&1。0&1=0;1&1=1;

3.把最后一位变成1。num|1。不论num最后一位是0还是1,结果都为1

4.把最后一位变成0。(num|1)-1

5.把右数第k位变成1。num|(1<<(k-1))

6.把右数第k位取反。num^(1<<(k-1))

一、颠倒二进制位(取最后一位\有符号数的右移\|运算)

颠倒给定的 32 位无符号整数的二进制位。

输入:n = 00000010100101000001111010011100
输出:964176192 (00111001011110000010100101000000)
解释:输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596 因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000
思路:

将给定的字符串反转,使用for循环遍历,每次获取n串中的最后一个二进制数。

1.获取最后一位的操作:(n&1);2.然后把它放到最前面。(n&1)<<(31-i);

3.然后每次和结果累加。res|((n&1)<<(31-i));4.然后n右移,n>>>=1

代码:
public class Solution {
    //将每一位的最后一个数字取出来 然后左移
    public int reverseBits(int n) {
        int res=0;
        for(int i=0;i<32&&n!=0;i++){
            res=res|(n&1)<<(31-i);
            n>>>=1;
        }
        return res;
    }
}

二、汉明距离总和(求某位置上1和0的个数)

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量

暴力法:

双层for循环,对每一对数字进行判断,然后把每一对数字的汉明距离相加起来。

class Solution {
    public int totalHammingDistance(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                sum+=HammingDistance(nums[i],nums[j]);
            }
        }
        return sum;
    }
    public int HammingDistance(int num1,int num2){
        return Integer.bitCount(num1^num2);
        //1.首先先进行异或操作
        //int num3=num1^num2;
        //int count=0;
        //2.进行判断
        //while(num3!=0){
            //if((num3&1)==1)count++;
            //num3>>>=1;
        //}
        //return count;
    }
}
另一种解法:

要求汉明距离总和,暴力法是将每一个元素作为一个整体来考虑的。

该种解法是将同一个位置上所有的元素为整体考虑的。

汉明距离总和=第0列二进制位不同的数量+第1列xxx+第2列xxx+...

每一列上二进制为不同的数量=0的个数*1的个数。每一个0都可以和其他的1搭配。(for循环两两搭配)

代码:

public int totalHammingDistance(int[] nums){
    int sum=0;
    for(int i=31;i>=0;i--){
        int l0=0,l1=0;
        for(int num:nums){
            if(((num>>i)&1)==1)l1++;
            else l0++;
        }
        sum+=l0*l1;
    }
    return sum;

}

三、阶乘后的零

给定一个整数 n ,返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

0 <= n <= 104

思路:

只有出现2*5,才会出现0;所以尾随零的数量=2/5对数的数量;又因为阶乘中数字可分成2的数量一定比5的数量多,所以0的数量=min(2,5)也就是5的数量。

因此只需要在1->n这个范围里面找%5的数并且累加就可以

代码:
class Solution {
    public int trailingZeroes(int n) {
        //判断0的个数->判断1->n中 可以分解5的个数
        int count=0;
        for(int i=1;i<=n;i++){
            int temp=i;
            while(temp>0){
                if(temp%5==0){
                    count++;
                    temp/=5;
                }else break;
            }
        }
        return count;
    }
}

四、数字转换为十六进制(位运算)

首先考虑到正负数,负数的话要使用补码。

思路:

如果是正数,补码就是本身;如果是负数,补码就是反码+1;如果是0,直接返回0;

如何求负数的补码:每一位取反再加1:num^0xffffffff+1。用异或进行取反,32位,十六进制,需要八位。(二进制)

如何将二进制转换为十六进制:二进制的每四位表示一个十六进制。val[num&0xf] 然后append。num>>>4;

代码:
class Solution {
    public String toHex(int num) {
        if(num==0)return "0";
        if(num<0){
            //取反+1 32位 一个十六进制是4位
            num=num^0xffffffff+1;
        }
        char[] val={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
        StringBuilder sb=new StringBuilder();
        while(num!=0){
            sb.append(val[num&0xf]);
            num>>>=4;
        }
        return sb.reverse().toString();
    }
}

五、灯泡开关(数论题)

初始时有 n 个灯泡处于关闭状态。第一轮,你将会打开所有灯泡。接下来的第二轮,你将会每两个灯泡关闭第二个。

第三轮,你每三个灯泡就切换第三个灯泡的开关(即,打开变关闭,关闭变打开)。第 i 轮,你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮,你只需要切换最后一个灯泡的开关。

题意:

第一轮打开所有,然后接下来第n轮,每n个关闭最后一个(第n个);

思路:

第1个灯泡什么时候才会改变状态,只有第一轮的时候,剩下的几轮都涉及不到1。

第2个灯泡什么时候才会改变状态,只有第一轮和第二轮的时候。

第3个灯泡什么时候才会改变状态,只有第一轮和第三轮的时候。

第4个灯泡什么时候才会改变状态,只有第一轮和第二轮和第四轮的时候。

因此,我们发现了规律,第n个灯泡只会在它因数的时候改变状态。如果因数是奇数,就是亮的;如果因数是偶数,就是关闭的。但是一般因数都是成对出现的,只有在完全平方数的时候会出现奇数。所以这道题就是考察n以内的完全平方数有几个。

代码:
class Solution {
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    } 
}

六、Excel表列名称

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
  • 1 <= columnTitle.length <= 7
  • columnTitle 仅由大写英文组成
  • columnTitle 在范围 ["A", "FXSHRXW"] 内
思路:

类似于二十六进制。x%26,就是最后一位上的值,再将值转换成对应的字母。

(x-x%26)/26,就是将最后一位去除的值,然后继续%26,就是倒数第二位上的值,再把它转换成对应的字母。

x%26->转换为字母->x=(x-x%26)/26->x%26->转换为字母->x=(x-x%26)/26

注意:

如果x%26==0,说明该位置上为‘Z’,此时应该是(x-26)/26

代码:
/**
 * 规律:因为每隔26就晋一位 两位数字可以表示的范围在1*26->26*26 三位数字的范围是1*26*26->26*26*26
 */
class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder sb=new StringBuilder();
        while(columnNumber>0){
            int mod=columnNumber%26;
            if(mod==0){
                sb.append('Z');
                columnNumber=(columnNumber-26)/26;
            }else{
                char ch =(char)('A' + mod - 1);
                sb.append(ch);
                columnNumber=(columnNumber-mod)/26;
            }
        }
        return sb.reverse().toString();
    }
}

七、Excel表列序号

已知一个数字上每一个位置上的数字,求该数字为多少。

number=number*26+num;

class Solution {
    public int titleToNumber(String columnTitle) {
        int multi=0;
        for(int i=0;i<columnTitle.length();i++){
            int num=columnTitle.charAt(i)-'A'+1;
            multi=multi*26+num;
        }
        return multi;
    }
}

八、最大交换

给定一个非负整数,你至多可以交换一次数字中的任意两位。返回你能得到的最大值

输入: 2736
输出: 7236
解释: 交换数字2和数字7。
思路:

1.将数字转化成字符串str,然后将每一位数字都放到list集合中。然后按照降序排。

2.一个for循环找到str中和list集合中第一次不同的位置(就是要交换的位置)

3.用变量swapA记录被交换数字的位置,然后list.get(i)为要交换数字的值,使用变量b记录。

4.如果(str.charAt(i)==b),就找到了在原始字符串中要交换数字的下标。

5.然后交换即可

代码:
class Solution {
    public int maximumSwap(int num) {
        String str=String.valueOf(num);
        List<Character> list=new ArrayList<>();
        for(int i=0;i<str.length();i++){
            list.add(str.charAt(i));
        }
        Collections.sort(list,(a,b)->{
            return b-a;//按照降序排
        });
        int swapA=-1,swapB=-1,b=-1;
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)!=list.get(i)&&swapA==-1){
                swapA=i;//如果和降序排的数字不相等的话 被交换的数字的下标
                b=list.get(i);//交换的数字
            }
            if(str.charAt(i)==b)swapB=i;//交换的数字的下标
        }
        if(swapA!=-1){
            char ch[]=str.toCharArray();
            char temp=ch[swapA];
            ch[swapA]=ch[swapB];
            ch[swapB]=temp;
            str=String.valueOf(ch);
        }
        return Integer.parseInt(str);
    }
}

九、两数相除(二分/位运算)

给你两个整数,被除数 dividend 和除数 divisor。将两数相除,要求 不使用 乘法、除法和取余运算。返回被除数 dividend 除以除数 divisor 得到的  。

注意:假设我们的环境只能存储 32 位 有符号整数,其数值范围是 [−2 31,  231 − 1] 。本题中,如果商 严格大于 231 − 1 ,则返回 231 − 1 ;如果商 严格小于 -231 ,则返回 -231 。

1.如果被除数为-2 31次,除数为-1,那么就会出现商大于2 31次。这样就要返回Integer.MAX_VALUE;2.如果除数为0,直接返回0;

思路:

1.首先排除极端的情况。当被除数为最小值,除数为-1,返回Integer.MAX_VALUE:当除数为0的时候,直接返回0;

2.进入正题:首先取被除数和除数的绝对值,然后判断结果是正还是负。这里使用异或运算符判断。(被除数<0)^(除数<0),一正一负就为负,都正或者都负为㊣

3.while循环找商:使用二分法不断逼近。while(被除数>=(除数<<count)){count++;}

当除数*2的count次<=被除数,第一次循环找到的商为2的count次。然后第二轮循环继续找

代码:
class Solution {
    public int divide(int dividend, int divisor) {
        //如果除数为0 直接返回0;
        if(divisor==0)return 0;
        //如果商大于2的31次-1 直接返回Integer.MAX_VALUE;
        if(dividend==Integer.MIN_VALUE&&divisor==-1){
            return Integer.MAX_VALUE;
        }
        //判断最后的符号
        boolean flag=(dividend<0)^(divisor<0);
        //取绝对值
        long absDividend=Math.abs((long)dividend);
        long absDivisor=Math.abs((long)divisor);
        //开始计算
        int res=0;
        while(absDivisor<=absDividend){
            //找每一次循环商的最大值,不断逼近的过程
            //商为2的count次
            int count=0;
            while(absDividend>=(absDivisor<<count)){
                count++;
            }
            count--;//上面while循环里面多加了一个
            res+=(1<<count);//可以整除的次数 增加1<<count次
            absDividend-=(absDivisor<<count);//数减少
        }
        return flag?-1*res:res;
    }
}

十、第n位数字

给你一个整数 n ,请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。eg:第11位上的数字 12345678910 是0;

思路:

1.首先算出第n位数字在哪一个范围里面 1-9? 10-99? 100-999?

2.如何计算呢? n>length*count 就说明不在这个范围里面 length:一个数字的长度(比如两位数的长度是2,三位数的长度是3);count是这个范围里面数字的个数

3.找到范围之后,找第几个数字。long num=(n-1)/lenth 

4.找到第几个数字之后,找在这个数字中的位置。int index=(n-1)%length

5.然后求出来就ok了 String str=String.valueOf(num); return str.charAt(index)-'0';

class Solution {
    public int findNthDigit(int n) {
        long start=1;
        int length=1;//当前数字的位数
        long count=9;//当前位数的数量
        while(n>length*count){
            n-=length*count;
            length++;//变成两位数
            count*=10;//从1-9 变成 10-99 公式为:9*Math.pow(10,length-1);
            start*=10;
        }
        //计算第n位数字 具体所在的具体数字
        long num=start+(n-1)/length;
        //计算第n位数字在该数字中的位置
        int index=(n-1)%length;
        //提取第n位数字
        String str=String.valueOf(num);
        return str.charAt(index)-'0';
    }
}


原文地址:https://blog.csdn.net/2301_78191305/article/details/140679672

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!