今日題目:
- 二進制中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 }