剑指offer（七）

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

剑指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
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;

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

};
class Solution{
public:
    ListNode * MergeList(ListNode * head1,ListNode * head2){
        if(head1==NULL){
            return head2;
        }
        if(head2==NULL){
            return head1;
        }
        ListNode *MergeNode;
        if(head1->val>=head2->val){
            MergeNode=head2;
            MergeNode->next=MergeList(head1,head2->next);
        }
        else{
            MergeNode=head1;
            MergeNode->next=MergeList(head1->next,head2);
        }

        return MergeNode;


    }


};

int main(){
    int a[]={1,2,3,4,5};
    int b[]={2,4,5,6,7};
    ListNode * L1=new ListNode(a[0]);
    ListNode * L2=new ListNode(b[0]);
    ListNode * p1= L1;
    ListNode * p2= L2;

    for(int i=1;i<5;i++)
    {
        ListNode * n1= new ListNode(a[i]);
        ListNode * n2= new ListNode(b[i]);
        p1->next=n1;
        p2->next=n2;
        p1=p1->next;
        p2=p2->next;
    }
    Solution s;
    ListNode * m;
    m=s.MergeList(L1,L2);

    while(m!=NULL){
        cout<<m->val<<endl;
        m=m->next;
    }
}

剑指Offer刷题（十七）：树的子结构

题目

输入两颗二叉树A，B，判断B是不是A的子结构。（PS：我们约定空树不是任意一个树的子结构）。

思路

判断B是不是A的子树,很显然,我们首先需要找到A中与B的根节点相同的节点.然后再看他的子树是不是和B一样.由于树的特点就是递归,所以整个判断过程也是递归的。
代码分为两部分

  1. 在A中找与B的根节点匹配的节点
  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
#include<iostream>
using namespace std;
struct TreeNode{
    int val;
    TreeNode * left;
    TreeNode * right;
    TreeNoede(int x):val(x),left(NULL),right(NULL){}
};

class Solution{
public:
    bool Issubtree(TreeNode * head1,TreeNode * head2){
        bool result=false;
        if(head1!=NULL && head2!=NULL){


            if(head1->val==head->val){
                result=DoesTree1HasTree2(head1,head2);
            }
            if(!result){
                result=HasSubtree(head1->left,head2);

            }
            if(!result){
                result=HasSubtree(head->right,head2);
            }
        }
        return result;
    }
private:
    bool DoseTree1HasTree2(TreeNode *p1,TreeNode *p2){
        if(p2==NULL){%%这是为了递归出口
            return true;
        }
        if(P1==NULL){%%递归出口
            return false;
        }
        if(p1->val!=p2->val){
            return false;
        }

        return DoseTree1HasTree2(p1->left,p2->left)&&DoseTree1HasTree2(p1->right,p2->right);


    }

};

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

struct TreeNode{
int val;
TreeNode * left;
TreeNode * right;
TreeNode(int x):val(x),left(NULL),right(NULL){}

};

class Solution{
public:
    TreeNode * reverseTree(TreeNode * root){
        if(root==NULL)
        {
            return NULL;
        }
        TreeNode * p;
        p=root->left;
        root->left=reverseTree(root->right);
        root->right=reverseTree(p);
        return root;

    }


};
int main()
{
    TreeNode * root1=new TreeNode(1);
    TreeNode * left1=new TreeNode(2);
    TreeNode * right1=new TreeNode(3);

    root1->left=left1;
    root1->right=right1;
    Solution s;


    TreeNode * reverseT=s.reverseTree(root1);
    if(reverseT==NULL)
    {
        cout<<"root is NULL"<<endl;
    }
    else{
        cout<<"root is"<<reverseT->val<<endl;
    }
    if(reverseT->left==NULL){
        cout<<"left is NULL"<<endl;
    }
    else{
        cout<<"left is "<<reverseT->left->val<<endl;
    }
    if(reverseT->right==NULL)
    {
        cout<<"right is NULL"<<endl;
    }
    else{
        cout<<"right is "<<reverseT->right->val<<endl;
    }

    return 0;
}

剑指Offer刷题（十九）：顺时针打印矩阵

题目

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵：
pic1
则依次打印出数组：1，2，3，4，8，12，16，15，14，13，9，5，6，7，11，10。

思路

按正常逻辑操作

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

class Solution{
public:
    vector<int> searchfor(vector<vector<int>> A){
        int N=A.size();
        int M=A[0].size();
        int left=0;
        int right=M-1;
        int top=0;
        int bottom=N-1;

        vector<int> v;
        while(left<=right && top<=bottom){
            for(int i=left;i<=right;i++){
                v.push_back(A[top][i]);

            }
            for(int j=top+1;j<=bottom;j++){
                v.push_back(A[j][right]);
            }

            if(top!=bottom){%%相等会时不要再返回一遍
                for(int k=right-1;k>=left;k--){
                    v.push_back(A[bottom][k]);
                }
            }
            if(left!=right){
                for(int z=bottom-1;z>top;z--){
                    v.push_back(A[z][left]);
                }
            }
            left=left+1;
            right=right-1;
            top=top+1;
            bottom=bottom-1;
        }
        return v;
    }


};


int main(){
    vector<vector<int>> A;
    for(int i=0;i<8;i++){
        vector<int>a;
        A.push_back(a);
        for(int j=0;j<5;j++){
            A[i].push_back(i*j);
        }
    }
    Solution s;
    cout<<A.size();
    vector<int> target;
    target=s.searchfor(A);
    int size1=target.size();
    cout<<"size:"<<size1<<endl;
    for(int i=0;i<size1;i++){
        cout<<target[i]<<endl;
    }
return 0;
}

剑指Offer刷题（二十）：包含min函数的栈

题目

定义栈的数据结构，请在类型中实现一个能够得到栈最小元素的min函数。

思路

一开始的想法是设置一个tag来标记最小值,但之后会发现这样能统计进到栈里的元素里的最小值,但是一旦这个最小值离开了栈，我们怎么知道下一个小的是什么呢.而网上较好的方法是同样设置一个min的最小栈来起作用

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

class Solution{
public:

    void push(int val)
    {
        Data.push(val);
        if(Min.empty())
            Min.push(val);
        if(Min.top()>val){
            Min.push(val);
        }

    }
    void pop(){
        if(Data.top()==Min.top){
            Min.pop();
        }
        Data.pop()
    }
    int top(){
        return Data.top();
    }
    int min(){
        return Min.top();
    }

private:
    stack<int> Min;
    stack<int> Data


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