剑指offer（六）

发表于 | 分类于 | 阅读数 次
字数统计: 1.9k 字 | 阅读时长 ≈ 9 分钟

剑指offer刷题(九)——矩阵覆盖

题目

可以用21的矩形横着或者竖着去覆盖更大的矩形.请问n个21的矩形无重叠的覆盖一个2×n的大矩形,总共有多少种方法?

思路

这种n个的题目,我们先一一列举n小的数目的结果：
n=1:1种
n=2:2种：横着2个;竖着2个
n=3:3种:可以在n=2的基础上加1列,也可以在n=1的基础上加2列,加的2列可以参考n=2的情况;
n=4:5种：可以在n=3的基础上加1列;也可以在n=2的基础上,加2列,但是此时2×1的小矩形必须是一上一下摆放,不能一左一右,否则与n=3里的情况有重复.

由上述列举可以观察到现象,一般
有f(n)=f(n-1)+f(n-2);
仍然是斐波那契数列

C++

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
#include<iostream>
using namespace std;


class Solution{
public:
    int rectCover(int number){
        if(number<=0)
        {
            cout<<"Wrong number"<<endl;
        }
        else if(number>0&&number<=2)
        {

            return number;
        }
        else{
            int first=1,second=2,third=0;
            for(int i=3;i<=number;i++)
            {
                third=first+second;
                first=second;
                second=third;
            }

            return third;

        }
    }
};

int main()
{
    int n=8;
    Solution s;
    for (int i=1;i<=n;i++)
        cout<<s.rectCover(i)<<endl;
    return 0;
}

Python
斐波那契变体

1
2
3
4
5
6
7
8
9
10
class Solution:
    def rectCover(self, number):
        # write code here
        A=[0,1,2]
        if number<=2:
            return A[number]
        else:
            for i in range(3,number+1):
                A.append(A[i-2]+A[i-1])
            return A[number]

剑指Offer刷题(十一)：二进制中1的个数

题目

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路

一个二进制数,例如1100,它的第一个1出现在右边数起的第三个,如果将该二进制减去1,它将从刚刚那个1出现的位置开始,各个值取反.而刚刚那个1左侧的值都不变.例如1100-1=1011。此时我们若将这两个值进行与运算,则会出现1100&1011=1000.即原来的二进制上的数去掉了一个1.我们可以重复上述步骤,从而统计二进制中1的个数.

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
class Solution{
public:
    int numberof1(int n){
        int count=0;
        while(n){
            count++;
            n=(n-1)&n;
        }
        return count;
    }

};

int main()
{
    int n=9;
    Solution s;

    cout<<s.numberof1(n)<<endl;
    return 0;
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def NumberOf1(self, n):
        # write code here
        sum=0
        if(n>=0):
            m=list(bin(n)[2:])

            for i in m:
                if(i=='1'):
                    sum+=1
        else:
            m=list((bin(((1 << 32) - 1) & n)[2:]).zfill(32))
            for i in m:
                if(i=='1'):
                    sum+=1
        return sum

关键是计算补码:
bin(1<<32)将1的2进制左移32位,相当于2的32次方
&将两个数的二进制进行与运算.
.zfill(32)填充32位

剑指Offer刷题(十二)：数值的整数次方

题目

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

思路

首先我们要知道这题要求我们不得使用库函数,同时不需要考虑大数问题。

这题目有以下几点需要注意:

  1. 0的0次方在数学上是没有意义的
  2. 0的负数次方相当于0作为除数,这也是无意义的
  3. 判断double 类型的base是否等于0不能用==号.因为计算机表述小数(包括float和double型小数)都有误差,不能直接使用 $( == )$判断两个小数是否相等。如果两个数的差的绝对值很小,那么可以认为两个double类型是的数相等

C++

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
#include<iostream>
using namespace std;

class Solution{
public:
    double Power(double base,int exponent){
        if(equal(base,0.0)){
            return 0.0;
        }
        unsigned int absExponent=0;
        if(exponent>0){
            absExponent=(unsigned int)(exponent);
        }
        else{
            absExponent=(unsigned int)(-exponent);
        }
        double result=PowerWithUnsignedExponent(base,absExponent);
        if(exponent<0){
            result=1.0/result;
        }
        return result;
    }
private:
    bool equal(double num1,double num2){
        if(num1-num2>-0.0000001&&(num1-num2)<0.0000001){
            return true;
        }
        else{
            return false;
        }


    }
    double PowerWithUnsignedExponent(double base,unsigned int exponent){

        if(exponent==0){
            if(base!=0.0)
                return 1;
        }
        if(exponent==1){
            return base;
        }
        double result=PowerWithUnsignedExponent(base,exponent>>1);
        result*=result;
        if(exponent&0x1==1){
            result*=base;
        }
        return result;
    }
};



int main(){
double base=212.3234;
int exponent=34;
Solution s;
cout<<s.Power(base,exponent)<<endl;



}

剑指Offer刷题（十三）：调整数组顺序使奇数位于偶数前面

题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路

使用一个双向队列,遍历数组，使得奇数前插入，偶数后插入。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;


class Solution{
public:
    void reOrderArray(vector<int> &array){
        deque<int> result;   %%%双端队列
        int num=array.size();
        for(int i=0;i<num;i++){%%%
            if(array[num-i-1]%2==1){
                result.push_front(array[num-i-1]);
            }
            if(array[i]%2==0){
                result.push_back(array[i]);
            }

        }
        array.assign(result.begin(),result.end());


    }

};

剑指Offer刷题（十四）：链表中倒数第k个结点

题目

输入一个链表，输出该链表中倒数第k个结点。

思路

这里采用两个指针的方法,一个指针p1指向链表的第一个元素.第二个指针p2指向链表的第k个元素.p1与p2同时往后移动,当p2达到最后一个元素时,p1指向的是倒数第k个元素.(这里要区分最后一个元素是倒数第0个还是倒数第1个,在这里我考虑的是最后一个元素是倒数第0个).

注意：链表里的元素个数很有可能还没有k大,返回的是NULL.

C++

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
#include<iostream>
using namespace std;
struct ListNode{
    int val;
    struct ListNode * next;
    ListNode(int x):val(x),next(NULL){}
};
class Solution{
public:
    ListNode * FindKthTail(ListNode * head,int k){
        if(head==NULL){
            return NULL;
        }
        ListNode * p1=head;
        ListNode *p2=head;
        for(int i=0;i<k;i++)
        {
           if(p1->next!=NULL)
           {
               p1=p1->next;
           }
           else{
                return NULL;
           }
        }
        while(p1->next!=NULL)
        {
            p1=p1->next;
            p2=p2->next;
        }
        return p2;
    }
};

int main(){
    int a[]={1,2,3,4,5,6};
    int k=2;
    ListNode * head=new ListNode(a[0]);
    ListNode * h=head;
    for(int i=1;i<6;i++){
        ListNode * p=new ListNode(a[i]);
        h->next=p;
        h=h->next;
    }
    Solution s;
    ListNode * target;
    target=s.FindKthTail(head,k);
    cout<<target->val<<endl;

return 0;
}

剑指Offer刷题（十五）：反转链表

题目

输入一个链表，反转链表后，输出链表的所有元素。

思路

方法1. 可以用一个栈来存储节点
方法2. 用三个指针,分别调换前两个指针的方向,第三个指针指示下一个节点

C++

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

#include<iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode * next;
    ListNode(int x): val(x),next(NULL){}

};


class Solution{
public:
    ListNode * Reverse(ListNode * head){
        if(head==NULL)
        {
            return NULL;
        }
        ListNode * p1;
        ListNode *p2;
        ListNode *p3;

        p1=head;
        p2=head->next;
        if(p2==NULL){
            return p1;
        }

        p3=head->next->next;
        p1->next=NULL;
        while(p3!=NULL){
            p2->next=p1;
            p1=p2;
            p2=p3;
            p3=p3->next;

        }
        p2->next=p1;
        return p2;
    }

};


int main(){
    int a[]={1,2,3,4,5};
    ListNode * head=new ListNode(a[0]);
    ListNode * q=head;
    for(int i=1;i<5;i++){
        ListNode * p=new ListNode(a[i]);
        q->next=p;
        q=q->next;
    }
    Solution s;
    head=s.Reverse(head);
    q=head;
    for(int i=0;i<5;i++){
        cout<<q->val;
        q=q->next;
    }
    return 0;


}
-------------本文结束感谢您的阅读-------------