今日题目：
- 二进制中1的个数
- 数值的整数次方
- 调整数组顺序使奇数位于偶数前面
- 链表中倒数第K个节点
- 链表中环的入口节点
今天的题目都比较简单，但是前三道题都有不同的解法，4,5两题就不在这边讨论了，其中第五道题大家可以了解一下floyd判圈算法。
1. 二进制中1的个数
题目描述：
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解法一：
1 public int NumberOf1(int n) { 2 3 int res = 0, count = 32; 4 while(count-- > 0){ 5 if((n&1) == 1) 6 res++; 7 n = n >> 1; 8 } 9 return res; 10 }
解法二，这个解法要由于解法一，循环的次数为1出现的次数：
1 public int NumberOf1(int n) { 2 3 int res = 0; 4 while(n != 0){ 5 res++; 6 n = (n-1)&n; 7 } 8 return res; 9 }
2. 数值的整数次方
题目描述：
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
这题需要考虑到的是exponent为负数时的情况，其他的并不复杂，下面给出递归和迭代的解法。
解法一，递归：
1 public double Power(double base, int exponent) { 2 if(exponent < 0){ 3 exponent *= -1; 4 base = 1/base; 5 } 6 return power(base,exponent); 7 } 8 9 public double power(double m, int n){ 10 if(n == 0) 11 return 1; 12 if(n == 1) 13 return m; 14 double res = power(m,n>>1); 15 res *= res; 16 if((n&1) == 1) 17 res *= m; 18 return res; 19 }
解法二，迭代：
1 public double Power(double base, int exponent) { 2 if(exponent < 0){ 3 exponent *= -1; 4 base = 1/base; 5 } 6 double res = 1.0; 7 while(exponent != 0){ 8 if((exponent&1) == 1) 9 res *= base; 10 base *= base; 11 exponent >>= 1; 12 } 13 return res; 14 }
3.调整数组顺序使奇数位于偶数前面
题目描述：
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
这道题本身不难，通过数组常见的操作就能实现，但是牛客网相对于书上而言多了一个条件，就是要保证相对位置不变，因此考虑使用插入排序和冒泡排序的思想来实现，因为它们都是稳定排序，可以确保相对位置的不变。
解法一，利用排序实现，时间复杂度为O(n2)
1 //冒泡排序 2 public void reOrderArray(int [] array) { 3 if(array.length < 2) 4 return; 5 for(int i = 0; i < array.length; i++){ 6 for(int j = array.length-1; j > i; j--){ 7 if((array[j-1]&1) == 0 && (array[j]&1)==1){ 8 int tmp = array[j]; 9 array[j] = array[j-1]; 10 array[j-1] = tmp; 11 } 12 } 13 } 14 15 } 16 17 //插入排序 18 public void reOrderArray(int [] array) { 19 if(array.length < 2) 20 return; 21 for(int i = 1; i < array.length; i++){ 22 if((array[i]&1) == 1){ 23 int tmp = array[i]; 24 int j = i-1; 25 for(;j >= 0 && (array[j]&1)==0; j--) 26 array[j+1] = array[j]; 27 array[j+1] = tmp; 28 29 } 30 } 31 32 }
解法二，以空间换时间，复杂度均为O(n)：
1 public void reOrderArray(int [] array) { 2 if(array.length==0||array.length==1) return; 3 int oddCount=0,oddBegin=0; 4 int[] newArray=new int[array.length]; 5 for(int i=0;i<array.length;i++){ 6 if((array[i]&1)==1) oddCount++; 7 } 8 for(int i=0;i<array.length;i++){ 9 if((array[i]&1)==1) newArray[oddBegin++]=array[i]; 10 else newArray[oddCount++]=array[i]; 11 } 12 for(int i=0;i<array.length;i++){ 13 array[i]=newArray[i]; 14 } 15 }