算法学习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 <= 7columnTitle仅由大写英文组成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）！