剑指Offer——03天

调整数组的位置时奇数放在偶数前

• 模拟一下就好了

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        vector <int> a,b;
        for(int i=0;i<array.size();i++)
        {
            if(array[i]%2==1) a.push_back(array[i]);
            else b.push_back(array[i]);
        }
        array.clear();
        for(int i=0;i<a.size();i++)
        {
            array.push_back(a[i]);
        }
        for(int i=0;i<b.size();i++)
        {
            array.push_back(b[i]);
        }
    }
};

链表中倒数第k个结点

• 跑一遍链表有多少个结点，然后输出第n-k+1个结点就是倒数第k个结点

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        unsigned int num=0;
        ListNode *p = pListHead;
        while(p!=NULL)
        {
            num++;
            p=p->next;
        }
        p = pListHead;
        unsigned int i=0;
        while(p!=NULL)
        {
            if(i+k==num) return p;
            i++;
            p=p->next;
        }
        return p;
    }
};

反转链表

• 采用头插法即可

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode * p = (ListNode*) malloc(sizeof(ListNode));
        p->next = NULL;
        while(pHead!=NULL)
        {
            ListNode * k = (ListNode*) malloc(sizeof(ListNode));
            k->val = pHead->val;
            k->next = p->next;
            p->next = k;
            pHead = pHead->next;
        }
        return p->next;
    }
};

合并两个排序的链表

• 平时写代码不严谨的锅，没有考虑两个链表可能为空的情况，导致一直提示段溢出，差点怀疑人生，整整搁置数天才AC了，AC的代码写得也很不好，过几天再得重新写一下

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==NULL&&pHead2!=NULL) return pHead2;
        else if(pHead1!=NULL&&pHead2==NULL) return pHead1;
        else if(pHead1==NULL&&pHead2==NULL) return NULL;
        int num;
        if(pHead1->val<pHead2->val)
        {
            num = pHead1->val;
            pHead1 = pHead1->next;
        }
        else
        {
             num = pHead2->val;
             pHead2 = pHead2->next;
        }
        ListNode * head = new ListNode(num);
        ListNode *p = head;
        while(pHead1!=NULL&&pHead2!=NULL)
        {
            if(pHead1->val<pHead2->val)
            {
                num = pHead1->val;
                pHead1 = pHead1->next;
            }
            else
            {
                num = pHead2->val;
                pHead2 = pHead2->next;
            }
            ListNode * k = new ListNode(num);
            p->next = k;
            p = p->next;
        }
        if(pHead1!=NULL)
        {
            p->next = pHead1;
        }
        if(pHead2!=NULL)
        {
            p->next = pHead2;
        }
        return head;
    }
};

树的子结构

• 利用队列层次遍历所有树结点，再利用递归判断是否为子结构

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    bool judge(TreeNode* node1,TreeNode* node2)
    {
        if(node1==NULL&&node2!=NULL) return false;
        else if(node1!=NULL&&node2==NULL) return true;
        else if(node1==NULL&&node2==NULL) return true;
        else 
        {
            if(node1->val!=node2->val) return false;
            else 
                return judge(node1->left,node2->left)&&judge(node1->right,node2->right);
        }
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(pRoot1==NULL) return false;
        if(pRoot2==NULL) return false;
        queue <TreeNode*> q;
        q.push(pRoot1);
        while(!q.empty())
        {
            TreeNode * k = q.front();
            q.pop();
            if(judge(k,pRoot2)==true) return true;
            if(k->left!=NULL) q.push(k->left);
            if(k->right!=NULL) q.push(k->right);
        }
        return false;
    }
};

二叉树的镜像

• 利用自上而下调用递归，先将当前结点的两个子树交换，在分别对这两个子树的左右子树进行交换

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot!=NULL)
        {
            TreeNode * l = pRoot->left;
            TreeNode * r = pRoot->right;
            pRoot->left = r;
            pRoot->right = l;
            Mirror(l);
            Mirror(r);
        }
    }
};