本周学习：位运算，双指针，递归和排序
双指针：
快慢指针(同向)适用于链表(常用来判断链表是否有环)，左右指针(异向)适用于数组。 下面俩例题都是类似的结构和模板
class Solution { public boolean judgeSquareSum(int c) { long left = 0; long right = (int)Math.sqrt(c); while(left<=right) { long sum = left*left+right*right; if(sum == c) return true; if(sum > c) { right--; }else{ left++; } } return false; } }
class Solution { public int[] twoSum(int[] numbers, int target) { int left = 0,right =numbers.length-1; while(left<right) { int sum = numbers[left] + numbers[right]; if(sum == target) return new int[]{left+1,right+1}; if(sum > target) { right--; }else{ left++; } } return new int []{left+1,right+1}; } }
位运算：
1.1 x&1=1 偶数 x&1=0 奇数(判断奇偶) 优先级：<< -> == -> & 所以写的时候要注意带括号
找出唯一成对的数
1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来;不用辅助存储空间，能否设计一个算法实现?
//通过异或运算，A^A = 0,0^B =B思路，1-1001中有一个重复的，通过将这些数再与1-1000相异或， 相同的都会变成0，最后剩下三个所求数，通过异或，即可得出目标数。 package exercise; import java.util.Random; class two_search { public static void main(String[]args) { int N = 1001; int a [] = new int [1001]; for(int i =0;i<a.length-1;i++) { a[i] = i+1; } print(a); a[a.length-1] = new Random().nextInt(N-1)+1; print(a); int b = new Random().nextInt(N-1); int temp = a[a.length-1]; a[a.length-1] = a[b]; a[b] = temp; print(a); int y = 0; for(int i =1;i<N;i++) { y^=i; } for(int i =0;i<N;i++) { y^=a[i]; } System.out.println(y); } public static void print(int a[]) { for(int i =0;i<a.length;i++) { System.out.print(a[i]+" "); } System.out.println(); } }
1.2 二进制获取最后一位为1/0的操作(两种) 以16举例：16二进制为10000
1.将1左移4位与16进行&运算，然后结果右移4位，最后和1进行比较，相同为1，不同为0
2.将16向右移动4位与1做与运算，结果为1最后一位就是1，结果为0最后一位就是0
例题：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。
例: 9的二进制表示为1001，有2位是1
package exercise; import java.util.Random; import java.util.Scanner; class two_search { public static void main(String[]args) { Scanner s = new Scanner(System.in); int N = s.nextInt(); System.out.println(Integer.toString(N,2)); int count = 0; //优先级：>>快于& //第一种方法：将1向左移 for(int i =0;i<32;i++) { if((N&1<<i)>>i==1) { count++; } } int num = 0; //第二种方法 将目标数向右移 for(int i =31;i>=0;i--) { if((N>>i&1) == 1) { num++; } } System.out.println(count); System.out.println(num); } }
1.3 判断一个数是否是2的次方，只需要将N 和N-1做与运算，因为N如果满足2的次方
16：10000，8：1000 ，4：100
举例：8（1000），8-1 = 7(0111) ,做与运算，结果为0，所以8为2的次方数
用一条语句判断一个整数是不是2的整数次方。
1. if(((N-1)&N) == 0) 2. { 3. System.out.println("Yes"); 4. }else { 5. System.out.println("No"); 6. }
1.4 将一个数奇偶位互换，0xaaaaaaaa = 1010 1010.... 0x55555555=0101 0101 ....
将二进制位的奇数位和偶数位互换
将目标数与0xaaaaaaaa求得偶数位，与0x55555555求得奇数位 ，然后通过位移和异或运算，将两者合到一起
package exercise; import java.util.Scanner; class two_search { public static void main(String[]args) { Scanner s = new Scanner(System.in); int N = s.nextInt(); int ou = N&0xaaaaaaaa; int ji = N&0x55555555; int num = (ou>>1)^(ji<<1); System.out.println(num); }
1.5 0-1之间浮点数的二进制表示
整数二进制表示为除二取余，0-1之间的浮点数为乘2取整。
StringBuilder 效率高，可变字符序列，线程不安全，单线程字符串操作下大量数据用StringBuilder
多线程字符串大量操作用StringBuffer。
问题描述：
给定一个介于0和1之间的实数，类型为double，打印出他的二进制表示
若该数字无法精确地用32位以内的二进制表示，则打印“ERROR”
package exercise; class two_search { public static void main(String[]args) { StringBuilder s = new StringBuilder("0."); double m = 0.625; while(m>0) { m*=2; if(m>=1) { s.append("1"); m=m-1; }else { s.append("0"); } } if(s.length()>34) { System.out.println("Error"); return; } System.out.println(s); } }
2. 递归三步走：1.找重复 2.找重复中的参数变化 3.找出口
static int f1(int n)//阶乘 { if(n==1) return 1; return n*f1(n-1); } static void f2(int i,int j)//打印i-j { if(i>j) return; System.out.print(i+" "); f2(i+1, j); } static int f3(int [] a,int n)//对数组求和 { if(n==a.length-1) return a[n]; return a[n]+f3(a, n+1); } static String f4(String s1,int end)//翻转字符串 { if(end == 0) return ""+s1.charAt(0); return s1.charAt(end)+""+f4(s1,end-1); } static int f5(int n)//斐波那契 { if(n==1||n==2) return 1; return f5(n-1)+f5(n-2); } static int f6(int m,int n)//辗转相除法求最大公因数 { if(n == 0) return m; return f6(n, m%n); } static void f7(int a[],int x)//插入排序 { if(x==0) return; f7(a, x-1); int y = a[x]; int index = x-1; while(index >-1 && y < a[index]) { a[index+1] = a[index]; index--; } a[index+1] = y; }
