剑指offer--编程题参考代码(2)

继续分享剑指offer的代码，大家可以去牛客网上刷一刷，我分享的都是通过的。大家可以自己写，优化一下哦。这篇主要放几个操作链表的题，加强对链表的熟悉，后面是数组的题。

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

<span style="font-size:14px;">/*
struct ListNode {
 int val;
 struct ListNode *next;
 ListNode(int x) :
   val(x), next(NULL) {
 }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead==NULL||k==0)
            return NULL;
       ListNode* p_temp = pListHead;  //一条用于从头遍历到k-1的位置
       ListNode* q = pListHead;
       int i=0;
       while( i<k-1) {
           p_temp = p_temp->next;
           i++ ;
           if(p_temp == NULL)
               return NULL;
       }
        while(p_temp->next!=NULL){
            p_temp = p_temp->next;
            q= q->next;
        }
        return q;
    }
};</span>

10.约瑟夫问题（m>n可以）
已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
通常解决这类问题时我们把编号从0~n-1，最后[1]  结果+1即为原问题的解。

这里我用一个循环链表。大家可以看有构建链表，插入结点。以及遍历之后删除结点的操作（基本的链表增删改）

class Solution {
public:
    int LastRemaining_Solution(unsigned int n, unsigned int m)
    {
        if(m==0||n==0)
            return -1;
        struct Lnode{
            int data;
            Lnode* next;
        };
        int len = sizeof(struct Lnode);
        unsigned int i=1;
        struct Lnode* head = (struct Lnode*)malloc(len);
        head->data=0;          //因为需要一个圈，这里是头结点（也就是带数据的），不是头指针。
        head->next=NULL;
        struct Lnode* cur = head;
        while(i<n){
        struct Lnode* p = (struct Lnode*)malloc(len);
        p->data=i;
        p->next=NULL;
        cur->next = p;
        cur = p ;
        i++;
        }
        cur->next = head;  //形成循环链表，首尾相连了
         
          Lnode* q=head;
          Lnode* pre;        //为下面删除结点定义一个前驱
    while(n>1){              //删除数到的结点
         i=0;
        while(i++<m-1){      //遍历到第m-1个结点
           pre=q;
           q=q->next;
        }
         pre->next=q->next;
         free(q);
          q=pre->next; 
        --n;
       }
      return (q->data);  
    }
};

11.用两个栈实现一个队列。
一般的，标准库里栈，队的操作函数：
队列：#include<queue>
申请队列：queue<type>q;
判队空：q.empty();
获取队头元素：q.front()；
入队：q.push();
出队：q.pop();
栈：#include<stack>
申请栈：stack<type>s;
入栈：s.push();
出栈：s.pop();
获取栈顶元素：s.top();
判栈空：s.empty();

class Solution
{
public:
    void push(int node) {           //入队：元素都压入栈1，直到栈2空，在node入栈（入队）
        while(!stack2.empty())
            {
              stack1.push(stack2.top());
              stack2.pop();
        }
         stack1.push(node);
    }

    int pop() {
        while(!stack1.empty())  //出队：元素都压入栈2，直到栈1空，栈顶元素出栈，即出队
            {        
             stack2.push(stack1.top());
             stack1.pop();
        }
        int m=stack2.top();
        stack2.pop();
      return   m;
    }


private:
    stack<int> stack1;
    stack<int> stack2;
};

12.设有一个带表头结点的双向循环链表L,每个结点有4个数据成员：指向先驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0.每当在链表上进行一次L.Locate（x）操纵时，令元素值x的结点的访问频度freq加1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。

 void Locate(int &x)
 {
 < 结点类型说明 >
 *p = first->next;
 while (p != first &&  p->data!=x ) p = p->next;
 if (p != first)
 {
   p->freq++ ;
 < 结点类型说明 >
 *current = p;
 current->prior->next = current->next;
 current->next->prior = current->prior;
 p = current->prior;
 while (p != first && p->freq < current->freq  ) p = p->prior;
 current->next = p->next  ;
 current->prior = p;
 p->next->prior = current;
 p->next = current;
 }
 else
 printf(“Sorry. Not find!
”);  *没找到*
 }

//这里是对双向循环链表的遍历和移动结点

13.二维数组中的查找。
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        int raw=array.size();
        int col=array[0].size();   //左下角开始，右增，上减
        int m=raw-1,n=0;
        while(m>=0&&n<col){
            if(target==array[m][n])
                return true;
            else if(target>array[m][n])
                ++n;
            else 
                --m;
        }
         return false;   
    }
};

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

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int m=array.size();
        int i=0,j=m-1,k=0;
       int a[m];
          for(int i=0;i<m;i++)  //奇数存头，偶数存尾。
            a[i]=0;
       // int* a=new int[m]();
        while(i<m){
            if(array[i]%2==0)
                a[j--]=array[i];
            if(array[i]%2==1)
                a[k++]=array[i];
            ++i;
        }
         j++;
        for(i=0;i<j;i++)      //新数组从头取完奇数
            array[i]=a[i];
        for(k=m-1;k>=j;k--)    //新数组从尾倒取完偶数
            array[i++]=a[k];
    }
};