剑指offer：斐波那契数列相关的三道题

发表于 | 分类于

前言

　　本次是位运算、数学计算、数组操作、链表操作的四道题应用。

近期整理的四道题

题目

  1. 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
  2. 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
  3. 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
  4. 输入一个链表，输出该链表中倒数第k个结点。

分析

  1. 第一道题，我们采用精妙的位运算，关于位运算的应用，包括乘除，在第二题用过，交换值等我们分析过，在这道题里，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。
  2. 我们采用递归求指数结果，然后在考虑奇偶，正负的问题。
  3. 遍历一遍数组，求出奇偶的个数，然后在遍历一遍把奇偶值填进去。
  4. 我们先使一个head往前走k-1步，然后第二个head和第一个一起走，当第一个走到链表的结尾时，第二个所在的地方就是倒数第k个。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public int NumberOf1(int n) {
        int count=0;
        while(n!=0){
            count++;
            n=(n-1)&n;
        }
        return count;
    }
    
public double Power(double base, int exponent) {
        int n=Math.abs(exponent);
        if(n==0)
            return 1;
        if(n==1)
            return base;
        double  result=Power(base,n>>1);
        result*=result;
        if((n&1)==1)
            result*=base;
        if(exponent<0)
            result=1/result;
        return result;
  }
  
 public void reOrderArray(int [] array) {
        int [] result = new int[array.length];
        int numOfOdd = 0;
        int numOfEven = 0;
        for(int i=0;i<array.length;i++){
            if((array[i]&0x1) == 1){
                numOfOdd++;
            }else{
                numOfEven++;
            }
        }
         
        int indexOfOdd = 0;
        int indexOfEven = numOfOdd;
        for(int i=0;i<array.length;i++){
            if((array[i]&0x1) == 1){
                result[indexOfOdd++] = array[i];
            }else{
                result[indexOfEven++] = array[i];
            }
        }
        for(int i=0;i<array.length;i++){
            array[i] = result[i];
        }
    }
    
public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null||k<=0){
            return null;
        }
        ListNode n1=head;
        
        ListNode n2=head;
        for(int i=1;i<k;i++){
            if(n1.next!=null){
                n1=n1.next;
            }else{
                return null;
            }
        }
       while(n1.next!=null){
           n1=n1.next;
           n2=n2.next;
       }
        return n2;
    }