//思路一：
// 对每位进行按位与
public int NumberOf1(int n) {
int cnt =0;
for(int i=0;i<32;i++){
cnt += (n&1); // 对每位与 1 进行按位与运算
n >>= 1;
}
return cnt;
}//思路二：
// n&(n-1) 表示去除 n 的位级表示中最右边的 1 。
// 比如：
// n : 10110100
// n-1 : 10110011
// n&(n-1) : 10110000
public int NumberOf1(int n) {
int res=0;
while(n!=0){
res++;
n&=(n-1);
}
return res;
}//思路一：
//空间复杂度：O(1)
public int FirstNotRepeatingChar(String str) {
int[] freq = new int[256];
for (int i = 0; i < str.length(); i++)
freq[str.charAt(i)]++;
for (int i = 0; i < str.length(); i++)
if (freq[str.charAt(i)] == 1)
return i;
return -1;
}//思路二：
// 考虑到只需要找到只出现一次的字符，那么需要统计的次数信息只有 0,1,更大，
// 使用两个比特位就能存储这些信息。
public int FirstNotRepeatingChar(String str) {
BitSet bs1 = new BitSet(256); //存放出现次数的第一位
BitSet bs2 = new BitSet(256); //存放出现次数的第二位
//比如 'a'出现次数为 1(转化为二进制为 01),则 bs1['a'] = 0，bs['a']=1
//比如 'a'出现次数为 2(转化为二进制为 10 -- > 11 表示多次),则 bs1['a'] = 1，bs['a']=1
//比如 'a'出现次数为 3(转化为二进制为 11 -- > 11 表示多次),则 bs1['a'] = 1，bs['a']=1
for(int i=0;i<str.length();i++){
char c = str.charAt(i);
if(!bs1.get(c) && !bs2.get(c)){ // 00 --> 01
//c 出现次数 +1
bs2.set(c); //01
}else if(!bs1.get(c) && bs2.get(c)){ //01 --> 11 （出现次数>1 就直接变为 3）
bs1.set(c);
}
}
for(int i=0;i<str.length();i++){
char c=str.charAt(i);
if(!bs1.get(c) && bs2.get(c)){
return i;
}
}
return -1;
}//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int diff = 0;
for(int num:array){
diff^=num;
}
diff = diff & (-diff);
for(int num:array){
if((diff & num) ==0){
num1[0] ^= num;
}else{
num2[0] ^= num;
}
}
}//思路：
// 不用加减乘除
// a ^ b 表示没有考虑进位的情况下两数的和，(a & b) << 1 就是进位。
// 递归会终止的原因是 (a & b) << 1 最右边会多一个 0，
// 继续递归，进位最右边的 0 会慢慢增多，最后进位会变为 0，递归终止。
public int Add(int num1,int num2) {
if(num2==0){
return num1;
}
return Add(num1^num2,(num1 & num2)<<1);
}//思路：分治法
// a^n 次方
// 若 a 为奇数 a^n = a*（a*a)^((n-1)/2)
// 若 a 为偶数 a^n = (a*a)^(n/2)
//注意:
// n<0 时，则 a^n = 1 /(a ^(-n))
//但是当 n == Integer.MIN_VALUE 时，我们可以转化为 1 / (a^(Integer.MAX_VALUE)*a)
public double Power(double base, int exponent) {
if(exponent==0){
return 1.0;
}
if(exponent==1){
return base;
}
if(exponent==Integer.MIN_VALUE){
return 1/(Power(base,Integer.MAX_VALUE)*base);
}
if(exponent<0){
exponent = -exponent;
return 1/Power(base,exponent);
}
if(exponent%2==1){
return Power(base*base,(exponent-1)/2)*base;
}else{
return Power(base*base,exponent/2);
}
}public int mySqrt(int x) {
if(x<=1){ //x==0 或者 x==1
return x;
}
int l=1;
int r=x;
while(l<=r){
int mid=(r-l)/2+l;
int sqrt=x/mid;
if(sqrt==mid){
return mid;
}else if(sqrt<mid){
r=mid-1;
}else{
assert sqrt>mid;
l=mid+1;
}
}
return r;
}//思路一：使用 if + 递归实现
//但是不合题意
public int Sum_Solution(int n) {
int sum=n;
if(n==0){
return sum;
}
//递归形式：n+Sum_Solution(n-1)
sum+=Sum_Solution(n-1);
return sum;
}//思路二：
//本题的关键在于无法直接使用 if 语句来指定返回条件。
// 条件 && 具有短路原则，即在第一个条件语句为 false 的情况下不会去执行第二个条件语句。
// 利用这一特性，将递归的返回条件取非然后作为 && 的第一个条件语句，递归的主体转换为第二个条件语句，那么
// 当递归的返回条件为 true 的情况下就不会执行递归的主体部分，递归返回。
// 本题的递归返回条件为 n <= 0，取非后就是 n > 0；
// 递归的主体部分为 sum += Sum_Solution(n - 1)，
// 转换为条件语句后就是 (sum += Sum_Solution(n - 1)) > 0。
public int Sum_Solution(int n) {
int sum=n;
boolean b=(n>0) && (sum+=Sum_Solution(n-1))>0;
//利用 && 的短路功能结束递归,当 n <=0 时，就不会执行 sum+=Sum_Solution(n-1)
//即不会再执行递归函数了，
return sum;
}public int NumberOf1Between1AndN_Solution(int n) {
if(n<1){
return 0;
}
int res=0;
int base=1;
int round = n; // n 为原始数字
while (round>0){
int weight = round %10;
round /=10;
res += round*base;
if(weight==1){
int formatter = n%base; //formatter 就是 weight 位的后一位
res += formatter+1;
}else if(weight>1){
res += base;
}
base*=10;
}
return res;
}数字以 0123456789101112131415... 的格式序列化到一个字符串中，求这个字符串的第 index 位。
public int getDigitAtIndex(int index) {
if(index<0){
return -1;
}
int place=1;
while(true){
// place 位的数字的个数
int total = getAmountOfPlace(place);
int bits = total*place; //place 位数字的总位数
if(index<bits){
return getDigitAtIndex(index,place);
}
index -= bits;
place++;
}
}
//获取 place 位的起始数字
//比如：
//1 位数的起始数字是 0
//2 位数的起始数字是 10
//3 位数的起始数字是 100
private int getBeginNumOfPlace(int place){
if(place==1){
return 0;
}
return (int)Math.pow(10,(place-1));
}
//获取 place 位的数字的个数
//比如：
//1 位数[0-9]的数字个数是 10
//2 位数[10-99]的数字个数是 90
//3 位数[100-999]的数字个数是 900
private int getAmountOfPlace(int place) {
if(place==1){
return 10;
}
return (int)Math.pow(10,(place-1))*9;
}
//获取 place 位的所有数字中的第 index 位置的数
private int getDigitAtIndex(int index, int place) {
int beginNumber = getBeginNumOfPlace(place);
int shiftNumber = index/place; //rangeNumber 表示 index 有多少个 place 位的数
int offset = index%place; // 偏移量
String number = beginNumber+shiftNumber+"";
return number.charAt(offset)-'0';
}//思路：
// 实际上就是约瑟夫环问题:
// 将编号为 0～（N–1）这 N 个人进行圆形排列，按顺时针从 0 开始报数，报到 M–1 的人退出圆形队列，
// 剩下的人继续从 0 开始报数，不断重复。求最后出列者最初在圆形队列中的编号。
// 公式如下：f(N,M) = (f(N-1,M)+M) % N
// N 表示 N 个报数人
// M 表示 报的数
// f(N,M) N个人报数，每报到 (M-1) 时就退出环，最后出列者在圆形队列中的编号。
//写法一：递归版本
public int LastRemaining_Solution(int n, int m) {
if(n==0){
return -1;
}
if(n==1){
return 0;
}
return (LastRemaining_Solution(n-1,m)+m)%n;
}//写法二： 循环版本
public int LastRemaining_Solution(int n, int m) {
if(n==0){
return -1;
}
if(n==1){
return 0;
}
int f=0;
for(int i=2;i<=n;i++){
f=(f+m)%i;
}
return f;
}public String addStrings(String num1, String num2) {
if(num1==null || num1.length()==0){
return num2;
}
if(num2==null || num2.length()==0){
return num1;
}
int i=num1.length()-1;
int j=num2.length()-1;
int c=0;
StringBuilder res=new StringBuilder();
while(i>=0 || j>=0 || c==1){
c+=(i>=0)?num1.charAt(i)-'0':0;
c+=(j>=0)?num2.charAt(j)-'0':0;
res.append(c%10);
c/=10;
i--;
j--;
}
return res.reverse().toString();
}public int majorityElement(int[] nums) {
int cnt=0; //统计众数
int majority=-1;
int n=nums.length;
for(int num:nums){
if(cnt==0){
majority=num;
cnt++;
}else{
if(majority!=num){
cnt--;
}else{
cnt++;
}
}
}
cnt=0;
for(int num:nums){
if(num==majority){
cnt++;
}
}
return (cnt>n/2)?majority:-1;
}