剑指 Offer II 位运算
001. 整数除法 位运算
学到的小知识：
两数符号判断可以用(a>0)^(b>0)
java语法 Integer.MIN_VALUE equals比较堆的内容 ==比较的栈的内容(String、基本数据)
没注意的细节： 当除数大于2^30时要break
class Solution {
public int divide(int a, int b) {//转成负数来做 因为负数有2的31次方 不会越界
if(a==Integer.MIN_VALUE&&b==-1)return Integer.MAX_VALUE;
int ans=0;
boolean flag= (a>0)^(b>0);
if(a>0)a=-a;
if(b>0)b=-b;
while(a<=b)//因为余数可能还能除以被除数，所以循环到a真正比被除数b小为止
{
int B=b;
int t=1;//初始化
while(a<=B)
{
a-=B;
ans+=t;
t+=t;
if(B002. 二进制加法
高精度加法
StringBuffer charAt append
Math.max
class Solution {
public String addBinary(String a, String b) {
StringBuffer sba =new StringBuffer(a);
StringBuffer sbb =new StringBuffer(b);
sba.reverse();
sbb.reverse();
StringBuffer ans=new StringBuffer("");
int t=0;
for(int i=0;i003. 前 n 个数字二进制中 1 的个数
int [] f=new int[n+1]
class Solution {
public int[] countBits(int n) {
int [] f=new int[n+1];
//状态表示 f[i]表示 i有1的个数
//状态计算 可以从 i右移1位这个数（除了个位）的f[i>>1]转移过来 再判断 i的个位
for(int i=0;i<=n;i++)
{
f[i]=f[i/2]+(i&1);
}
return f;
}
}
004. 只出现一次的数字
两个数相同异或每位上都是0 但有没有想过 n个相同数异或 每一位 模n 也是0
class Solution {
public int singleNumber(int[] nums) {// O(32n)
int ans=0;
for(int bit=0;bit<32;bit++)//统计这一位上1的个数 如果模三不为0 则说明那个数在这一位不为0 要加起来
{
int counter=0;
for(int i=0;i>bit)&1;
}
ans+= (counter%3) << bit;
}
return ans;
}
}
005. 单词长度的最大乘积
26字母可以用一个32位整形 状态压缩
class Solution {
public int maxProduct(String[] words) {
int n=words.length;
int [] a=new int [n];
for(int i=0;i006. 排序数组中两个数字之和 双指针
class Solution {
public int[] twoSum(int[] numbers, int target) {
int n=numbers.length;
int [] ans =new int [2];
int j=n-1;
for(int i=0;itarget)j--;
if(numbers[j]+numbers[i]==target)
{
ans[0]=i;ans[1]=j;
break;
}
}
return ans;
}
}