剑指offer LeetCode 刷题笔记

剑指offer LeetCode 刷题笔记

文章目录

• 001 [整数除法](/?favorite=e8X3pBZi)
• 002 [二进制加法](/?favorite=e8X3pBZi)
• 003 [前 n 个数字二进制中 1 的个数](/?favorite=e8X3pBZi)
• 004 [只出现一次的数字](/)

001 整数除法

提示：关键知识点：1.Integer.MIN_VALUE,Intefer.MAX_VALUE;
2.利用位运算的快速相减
位运算快速相减伪代码：

INPUT:a,b
OUTPUT:a-b
ans=0
while a>=b:base=1temp_b=bwhile a-temp_b>=temp_b:temp_b<<=1base<<=1a-=temp_bans+=basereturn ans

class Solution {public int divide(int a, int b) {if (b==-1)if (a==Integer.MIN_VALUE)return Integer.MAX_VALUE;else return -a;if (b==1)return a;int ans=0;int k=1;if (a>0) {a=-a;k=-k;}if (b>0) {b=-b;k=-k;}// 快速相减while (a<=b){int base=1;int temp=b;while (a-temp<=temp){temp=temp<<1;base=base<<1;}a=a-temp;ans=ans+base;}return ans*k;}
}

提示：实际使用时考虑到int的限制使用了负数进行运算

002 二进制加法

提示：关键知识点：
1.可变字符串：StringBuffer
2.字符串取数 charAt()
3.char to int int=char-'0'
int to char char=int+'0'

class Solution {public String addBinary(String a, String b) {int len=a.length();StringBuffer strb=new StringBuffer();if (len<b.length())len=b.length();int base=0;for (int i=0;i<len;i++){int res=base;res+=(a.length()-i>0?a.charAt(a.length()-i-1):'0')-'0';res+=(b.length()-i>0?b.charAt(b.length()-i-1):'0')-'0';if (res>=2){res=res%2;base=1;}else {base=0;}strb.String(res));}if (base==1){strb.String(1));}verse();String();}
}

003 前 n 个数字二进制中 1 的个数

提示：关键知识点：比较简单但不容易想到的dp
dp思路：
二进制数字分为两种情况：
如果是奇数会比上一个偶数多一个1，如：00 和01
如果是偶数会和他的二分之一1的个数一样多，如：10和100
所以dp状态转换方程显而易见

if (i%2==0){dp[i]=dp[i/2];
}else{dp[i]=dp[i-1]+1;
}

class Solution {public int[] countBits(int n) {int [] dp=new int[n+1];for (int i=0; i<=n ; i++){if (i==0){dp[i]=0;}else if(i==1){dp[i]=1;}else{if (i%2==0){dp[i]=dp[i/2];}else{dp[i]=dp[i-1]+1;}}}return dp;
}
}

004 只出现一次的数字

列表list语法参考
int string 互相转换的参考

class Solution {public int singleNumber(int[] nums) {List<String> num_list=new ArrayList<>();List<String> res_list=new ArrayList<>();for(int i=0;i<nums.length;i++){if (ains(nums[i]+ "")){// for(int j=0;j<num_list.size();j++){//     if((j)==nums[i]) //         ve(j--);// }String(nums[i]));}else{res_list.String(nums[i]));num_list.String(nums[i]));}}return Integer.parseInt((0));}
}