PTA刷题总结-Part3.1 数组与链表专题

作者: 苏wisdom | 来源:发表于2020-03-25 21:52 被阅读0次

PTA刷题总结-Part3.1 数组与链表专题
PTA刷题总结-Part 3 数据结构与算法
PTA刷题总结-Part 2 模拟与数学问题
PTA刷题总结-Part3.5 图专题
PTA刷题总结-Part3.3 排序专题
leecode刷题（22）-- 反转链表
PTA刷题总结-Part3.4 树结构专题
Python小白 Leetcode刷题历程 No.81-No.
如何刷题
数据结构与算法之美 —— 如何实现LRU缓存淘汰算法?(总结)

1 链表的基本操作

我做链表题比较习惯于给链表设置哨兵（sentinel），这样可以减少边界极端情况的判断，避免没有考虑周全导致出错。如下图中，深灰色部分就是哨兵结点。

image.png

1.1 顺序创建链表

输入样例：
1 2 3 4 5 6 7 -1
输出样例
1 2 3 4 5 6 7

读入结点，遇到-1就不读了，那么借助哨兵结点（head）创建链表的写法如下，最后返回的链表又去掉了哨兵：

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *readlist(); // 最后不返回哨兵结点

void printlist( struct ListNode *L )
{
     struct ListNode *p = L;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode *L, *Odd;
    L = readlist();
    printlist(L);

    return 0;
}


struct ListNode *readlist(){
    int curr = 0;
    scanf("%d", &curr);
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->data = NULL;
    head->next = NULL;
    struct ListNode* p = head;
    while (curr != -1){
        struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->data = curr;
        temp->next = NULL;
        p->next = temp;
        p = p->next;
        scanf("%d", &curr);
    }
    return head->next;
}

改成不使用哨兵，就需要加入对头节点是否为NULL的判断。

struct ListNode *readlist(){
    int curr = 0;
    scanf("%d", &curr);
    struct ListNode* head = NULL;
    struct ListNode* p = head;
    while (curr != -1){
        struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->data = curr;
        temp->next = NULL;
        if (head == NULL){
            head = temp;
            p = head;
        } else {
            p->next = temp;
            p = p->next;
        }
        scanf("%d", &curr);
    }
    return head;
}

1.2 逆序创建链表

逆序创建链表，其实就是把新读入的结点，插到现有链表的头部。这个时候就没有哨兵节点了。

输入样例：
1 2 3 4 5 6 7 -1
输出样例
7 6 5 4 3 2 1

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *createlist();  // 这个时候就没有哨兵节点了

int main()
{
    struct ListNode *p, *head = NULL;

    head = createlist();
    for ( p = head; p != NULL; p = p->next )
        printf("%d ", p->data);
    printf("\n");

    return 0;
}

struct ListNode *createlist(){
    int curr = 0;
    scanf("%d", &curr);

    struct ListNode *head = NULL;
    while (curr != -1){
        struct ListNode *newNode = (struct ListNode *) malloc(sizeof(struct ListNode));
        newNode->data = curr;
        newNode->next = head;
        head = newNode;
        scanf("%d", &curr);
    }
    return head;
};

1.3 插入元素

将x插入到以head为头节点的链表指针的第pos位置上
输入样例：
1 2 3 4 5 6 8 9 -1
7 7
输出样例
1 2 3 4 5 6 7 8 9

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *createlist(); // 带哨兵结点的创建链表
void insert(struct ListNode *head, int pos, int X); // 带哨兵结点的插入
void printlist( struct ListNode *head )
{
     struct ListNode *p = head->next;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode *head = NULL;
    int pos=0,X=0;
    head = createlist();
    scanf("%d %d", &pos, &X);
    insert(head, pos, X);
    printlist(head);

    return 0;
}

struct ListNode *createlist(){
    int curr = 0;
    scanf("%d", &curr);
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->data = NULL;
    head->next = NULL;
    struct ListNode* p = head;
    while (curr != -1){
        struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->data = curr;
        temp->next = NULL;
        p->next = temp;
        p = p->next;
        scanf("%d", &curr);
    }
    return head;
};

void insert(struct ListNode *head, int pos, int X){
    struct ListNode *pre = head;
    for (int i=0;i<pos-1;i++){
        pre = pre->next;
    }
    struct ListNode *newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->data = X;
    newNode->next = pre->next;
    pre->next = newNode;
}

1.4 查找和删除元素

删除以head为头节点的链表指针上，所有数值为X的结点。其实是先查找然后删除。

输入样例：
10 11 10 12 10 -1
10
输出样例
11 12

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *createlist(); // 带哨兵结点的创建链表
void deleteItem(struct ListNode *head, int X); // 带哨兵结点的删除
void printlist( struct ListNode *head )
{
     struct ListNode *p = head->next;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode *head = NULL;
    int pos=0,X=0;
    head = createlist();
    scanf("%d",  &X);
    deleteItem(head, X);
    printlist(head);

    return 0;
}

struct ListNode *createlist(){
    int curr = 0;
    scanf("%d", &curr);
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->data = NULL;
    head->next = NULL;
    struct ListNode* p = head;
    while (curr != -1){
        struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->data = curr;
        temp->next = NULL;
        p->next = temp;
        p = p->next;
        scanf("%d", &curr);
    }
    return head;
};

void deleteItem(struct ListNode *head, int X){
    struct ListNode *pre = head;
    struct ListNode *p = pre->next;
    while (p){
        if (p->data == X){
            pre->next = pre->next->next;
            free(p);
            p = pre->next;
        } else {
            pre = pre->next;
            p = p->next;
        }
    }
}

1.5 单链表的反转

原始单链表.png

循环结束.png

1结点的next指向oldn结点.png

头结点指向newn结点.png

链表反转是个常考的操作，上图中展示了让单链表1->2->3->4->5->6->null反转前4个结点，变成4->3->2->1->5->6->null的过程。

其实就是使用三个指针newn, oldn, temp进行以下循环操作，直到反转完题目要求的结点个数

temp记录old的下一个结点位置
然后让oldn结点往回指向newn
然后依次将newn,oldn向右移动一个结点，返回第1步

循环结束后，要处理head->next->next和head->next 指向正确的位置

输入样例：
1 2 3 4 5 6 6 7 -1
输出样例
1 2 3 4 5 6 6 7
7 6 6 5 4 3 2 1

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *createlist();
struct ListNode *reverse( struct ListNode *head );

void printlist( struct ListNode *head )
{
     struct ListNode *p = head;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode *p, *head = NULL,*reHead=NULL;

    head = createlist();
    printlist(head);
    reHead = reverse(head);
    printlist(reHead);

    return 0;
}

struct ListNode *createlist(){
    int curr = 0;
    scanf("%d", &curr);
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->data = NULL;
    head->next = NULL;
    struct ListNode* p = head;
    while (curr != -1){
        struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->data = curr;
        temp->next = NULL;
        p->next = temp;
        p = p->next;
        scanf("%d", &curr);
    }
    return head->next;
};

struct ListNode *reverse( struct ListNode *head ){
    if (head==NULL){
        return NULL;
    }
    struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
    phead->data = NULL;
    phead->next = head;
    struct ListNode* newn = phead->next;
    struct ListNode* oldn = newn->next;
    while (oldn){
        struct ListNode* temp = oldn->next;
        oldn->next = newn;
        newn = oldn;
        oldn = temp;
    }
    phead->next->next = oldn;
    phead->next = newn;
    return phead->next;
}

1.6 链表的合并

链表的合并操作很容易让人想到归并排序里的merge操作，本质上都一样，只不过这里是用指针进行操作，归并排序一般用数组进行操作。

L1和L2是给定的带头结点的单链表。要注意最后L1和L2要指向NULL。

输入样例

输出样例

1 2 3 4 5 6 8 10 
NULL
NULL

List Merge(List L1, List L2){
    List L = (List)malloc(sizeof(struct Node));
    L->Next = NULL;
    List p = L,p1=L1,p2=L2;
    p1 = p1->Next;
    p2 = p2->Next;
    while (p1 && p2){
        if (p1->Data <=p2->Data){
            p->Next = p1;
            p1 = p1->Next;
            p = p->Next;
        } else {
            p->Next = p2;
            p2 = p2->Next;
            p = p->Next;
        }
    }
    if (p1){
        p->Next = p1;
    }
    if (p2){
        p->Next = p2;
    }
    L1->Next = NULL;
    L2->Next = NULL;
    return L;
}

1.7 快慢指针

1.7.1 快慢指针解决单链表回文问题

leetcode-234:回文链表
请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *createlist(); // 不带头结点的创建链表
bool isPalindrome(struct ListNode* head); // 判断是否是回文单链表
void printlist( struct ListNode *head )
{
     struct ListNode *p = head;
     while (p) {
           printf("%d ", p->val);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode *head = NULL;
    head = createlist();

    bool ans = isPalindrome(head);
    if (ans){
        printf("true");
    } else {
        printf("false");
    }
    return 0;
}

struct ListNode *createlist(){
    int curr = 0;
    scanf("%d", &curr);
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = NULL;
    head->next = NULL;
    struct ListNode* p = head;
    while (curr != -1){
        struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->val = curr;
        temp->next = NULL;
        p->next = temp;
        p = p->next;
        scanf("%d", &curr);
    }
    return head->next;
};


bool isPalindrome(struct ListNode* head){
    struct ListNode* fast = head, *slow = head;
    // fast ==NULL 偶数,slow指向链表1->2->2->1->NULL的第二个2
    // fast != NULL 奇数,slow指向链表1->2->3->2->1->NULL的3
    while (fast !=NULL && fast->next!=NULL){
        fast = fast->next->next;
        slow = slow->next;
    }
    if(fast!=NULL){ // 奇数时slow再向右一步
        slow = slow->next;
    }

    // 反转slow后面的链表
    struct ListNode* newn = NULL;
    struct ListNode* oldn = slow;
    while (oldn){
        struct ListNode* temp = oldn->next;
        oldn->next = newn;
        newn = oldn;
        oldn = temp;
    }

    // 比较
    struct ListNode* left = head;
    struct ListNode* right = newn;
    while (right){
        if (left->val != right->val){
            return false;
        }
        left = left->next;
        right = right->next;
    }
    return true;
}

1.7.2 快慢指针解决环形链表问题

判断是否有环
leetcode-141:环形链表
给定一个链表，判断链表中是否有环。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode *fast = head, *slow = head;
    while (fast && fast->next){
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow){
            return true;
        }
    }
    return false;
}

找到链表开始入环的第一个节点
leetcode-142: 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast = head, *slow = head;
    while (fast && fast->next){
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow){
            break;
        }
    }
    if (fast == NULL || fast->next == NULL){
        return NULL;
    }
    slow = head;
    while (slow != fast){
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

找到链表倒数第k个元素
leetcode:返回倒数第 k 个节点
 leetcode:面试题22. 链表中倒数第k个节点
 leetcode-19:删除链表的倒数第N个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


int kthToLast(struct ListNode* head, int k){
    struct ListNode* fast = head, *slow = head;
    while (k>0){
        fast = fast->next;
        k--;
    }
    while (fast){
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}

2 静态链表

动态链表使用指针来建立结点之间的关联关系，而当题目告诉你结点地址在5位数及以内时，可以使用静态链表。
静态链表其实就是使用结构体数组，数组中每个元素是一个包含数据、下一个地址的结构体。使用数组的方便之处在于，可以直接使用下标表示结点的地址，查询也快速。

02-线性结构3 Reversing Linked List (25分)

给定整数 K 和单链表 L, 你需要每K个元素把链表反转一次。

例如给定链表 1→2→3→4→5→6, K=3,那么反转后的结果是3→2→1→6→5→4;
如果 K=4, 输出结果是 4→3→2→1→5→6.
要注意这道题会有多余结点不在链表上

样例输入

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

样例输出

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

这道题我用了两种方法。第一种方法偷懒，直接使用了c++的reverse() 方法，但是当时写完仍然不知道对单链表到底怎么反转。于是尝试用c写了第二种方法。

#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <vector> 
using namespace std;
#define MaxLen 100001 
struct node{
    int Addr;
    int num;
    int NextAddr;
};
typedef struct node Node;
Node nodes[MaxLen];
vector<Node> nodeList;
int main(){
    int firstAdd, N, K;
    scanf("%d %d %d", &firstAdd, &N,&K);
    while (N--){
        Node n;
        scanf("%d %d %d", &n.Addr, &n.num,&n.NextAddr);
        nodes[n.Addr] = n;
    }
    int address = firstAdd;
    while(address!=-1){
        nodeList.push_back(nodes[address]);
        address = nodes[address].NextAddr;
    }
    int len = nodeList.size();
    int period = len/K;
    for (int i=1;i<=period;i++){
        int head = (i-1)*K;
        int end = i*K;
        reverse(nodeList.begin()+head,nodeList.begin()+end);
    }

    for (int i=0;i<len-1;i++){
        nodeList[i].NextAddr = nodeList[i+1].Addr;
        printf("%05d %d %05d\n", nodeList[i].Addr,nodeList[i].num,nodeList[i].NextAddr);
    }
    nodeList[len-1].NextAddr =-1;
    printf("%05d %d %d", nodeList[len-1].Addr,nodeList[len-1].num,nodeList[len-1].NextAddr);
}

c语言，手写反转链表

#include <stdlib.h>
#include <stdio.h>

struct node{
    int Addr;
    int num;
    int NextAddr;
};
typedef struct node Node;
Node nodes[100001];

int main(){
    // 读入
    int firstAdd, N, K;
    scanf("%d %d %d", &firstAdd, &N,&K);
    for (int i=0;i<N;i++){
        Node currNode;
        scanf("%d %d %d", &currNode.Addr, &currNode.num,&currNode.NextAddr);
        nodes[currNode.Addr] = currNode;
    }

    Node head;
    head.Addr = NULL;
    head.num = NULL;
    head.NextAddr = firstAdd;
    Node *currHead = &head; // 指向头节点，作为每次翻转的头指针

    // 获取真实结点个数,因为会有多余结点不在链表上
    Node *q = &head;
    int realN = 0;
    while (q && q->NextAddr!=-1){
        q = &nodes[q->NextAddr];
        realN++;
    }
    // 逆序
    int period = realN/K;
    while (period > 0 && K>1){ // 如果K=1就不需要做逆序
        Node *newn = &nodes[currHead->NextAddr];
        Node *oldn = &nodes[newn->NextAddr];
        int len = K;
        while (len>1){ // 4个结点翻转时，会有3个结点指向前一个结点
            Node *temp; // 依次3个相邻指针 newn,oldn,temp
            if (oldn->NextAddr!=-1){
                temp = &nodes[oldn->NextAddr];
            } else {
                temp = NULL;
            }

            oldn->NextAddr = newn->Addr;
            newn = oldn;
            oldn = temp;
            len--;
        }
        Node *temp2 = &nodes[currHead->NextAddr]; // 指向下一批要翻转结点的头节点
        if (oldn){
            nodes[currHead->NextAddr].NextAddr = oldn->Addr;
        } else {
            nodes[currHead->NextAddr].NextAddr = -1;
        }

        currHead->NextAddr = newn->Addr;
        if(period == realN/K){
            head.NextAddr = newn->Addr;
        }
        currHead = temp2;
        period--;
    }

     // 输出
    Node p = nodes[head.NextAddr];
    while(p.NextAddr != -1){
        printf("%05d %d %05d\n", p.Addr, p.num,p.NextAddr);
        p = nodes[p.NextAddr];
    }
    printf("%05d %d %d\n", p.Addr, p.num,p.NextAddr);
}

3 线性结构练习题

02-线性结构2 一元多项式的乘法与加法运算 (20分)
设计函数分别求两个一元多项式的乘积与和。

输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

输出样例:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

最开始我是用链表做的。链表的注意点有

head节点是没有数据的，真正的第一个数据在head->Next节点里，这样写的目的是利用哨兵简化实现难度
指针指向一个不存在的地址时就会出现段错误
理解题意，题目说的是head->Next为NULL时，只需要输出0 0
当相加时俩系数相互抵消，那么这个节点也就不存在了

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode *List;
struct LNode{
    int co;
    int exp;
    List Next;
};

List PtrL;
List read(int n1){
    List pL1 = (List) malloc(sizeof(struct LNode));
    pL1->Next = NULL;
    List t = pL1;
    for (int i=0;i<n1;i++){
        List a = (List) malloc(sizeof(struct LNode));
        a->Next = NULL;
        scanf("%d", &(a->co));
        scanf("%d", &(a->exp));
        t->Next = a;
        t = t->Next;
    }
    t->Next = NULL;
    return pL1;
}

void attach(int c, int e, List rear){
    List t = (List) malloc(sizeof(struct LNode));
    t->co = c;
    t->exp = e;
    t->Next = NULL;
    rear->Next = t;
    rear = t;
}

List Addp2(List L1,List L2){
    List r = (List) malloc(sizeof(struct LNode));
    r->Next = NULL;
    List curr = r;
    List p1 = L1->Next, p2=L2->Next;
    if (!p1 && !p2){
        return NULL;
    }
    while (p1 && p2){
        if (p1->exp > p2->exp){
            attach(p1->co, p1->exp, curr);
            p1 = p1->Next;
            curr = curr->Next;
        }
        else if (p1->exp < p2->exp){
            attach(p2->co, p2->exp, curr);
            p2 = p2->Next;
            curr = curr->Next;
        }
        else {
            int sum = 0;
            sum = p1->co+p2->co;
            if (sum){
                attach(sum, p2->exp, curr);
                curr = curr->Next;
            }
            p1 = p1->Next;
            p2 = p2->Next;  
        }
    }
    while (p1){
        attach(p1->co, p1->exp, curr);
        p1 = p1->Next;
        curr = curr->Next;
    }
    while (p2){
        attach(p2->co, p2->exp, curr);
        p2 = p2->Next;
        curr = curr->Next;
    }
    return r;
}
List Multiply(List pL1,List pL2){
    List p1 = pL1->Next, p2=pL2->Next;
    List sumHead = (List) malloc(sizeof(struct LNode));
    if (!p1 && !p2){
        return NULL;
    }
    List t = sumHead;
    while (p1){
        attach(p2->co * p1->co, p2->exp + p1->exp, t);
        p1 = p1->Next;
        t= t->Next;
    }
    p2 = p2->Next;
    while (p2){ // 当p2为NULL时退出循环
        p1 = pL1->Next;// p1重新回到起点 
        t = sumHead;
        while (p1){
            int c = p2->co * p1->co;
            int e = p2->exp + p1->exp;
            while (t->Next && t->Next->exp > e){
                t = t->Next;
            }
            if ((t->Next) && (t->Next->exp==e)){
                if (t->Next->co + c !=0){
                    t->Next->co+=c;
                } else {
                    List dis = t->Next;
                    t->Next = dis->Next;
                    free(dis);
                }
            }
            else {
                List insert = (List) malloc(sizeof(struct LNode));
                insert->co = c;
                insert->exp = e;
                insert->Next = t->Next;
                t->Next = insert;
                t = t->Next;
            }

            p1 = p1->Next;
        }
        p2 = p2->Next;
        
    }
    return sumHead;
}

void Display(List L){
    List p = L;

    p = p->Next;
    if (p==NULL){
        printf("0 0");
    }
    int flag = 0;
    while (p){
        if (flag==0){
            printf("%d %d", p->co, p->exp);
            flag = 1;
        } else {
            printf(" %d %d", p->co, p->exp);
        }
        p = p->Next;
    }
}

int main(){
    int n1=0,n2=0;
    scanf("%d", &n1);
    List pL1 = read(n1);
    scanf("%d", &n2);
    List pL2 = read(n2);
    
    List M = Multiply(pL1,pL2);
    Display(M);
    printf("\n");
    List A = Addp2(pL1,pL2);
    Display(A);
    return 0;
}

然后参考网上的方法使用结构数组和连续数组，其中连续数组的下标是指数exp，值是系数co

#include <stdio.h>
struct Poly{
    int ex;
    int co;
}Poly[1001];
int main(){
    int n1,n2,M[2005]={0},A[1001]={0};
    scanf("%d", &n1);
    for (int i=0;i<n1;i++){
        scanf("%d %d", &Poly[i].co,&Poly[i].ex);
        A[Poly[i].ex] += Poly[i].co;
    }
    
    int temp1,temp2;
    scanf("%d", &n2);
    for (int i=0;i<n2;i++){
        scanf("%d %d", &temp1,&temp2);
        A[temp2]+=temp1;
        for (int j=0;j<n1;j++){
            M[temp2+Poly[j].ex] += (temp1*Poly[j].co);
        }
    }
    int isFirst =1;// 1-是第一个输出
    int haveOutput = 0; // 0 不是零多项式
    for (int i=2001;i>=0;i--){
        if (M[i]!=0){
            if (!isFirst){
                printf(" %d %d", M[i],i);
            } else {
                isFirst = 0;
                printf("%d %d", M[i],i);
            }
            haveOutput = 1;
        }
    }
    if (!haveOutput){
        printf("0 0");
    }
    isFirst =1;
    haveOutput = 0;
    printf("\n");
    for (int i=1001;i>=0;i--){
        if (A[i]!=0){
            if (!isFirst){
                printf(" %d %d", A[i],i);
            } else {
                isFirst = 0;
                printf("%d %d", A[i],i);
            }
            haveOutput = 1;
        }
    }
    if (!haveOutput){
        printf("0 0");
    }
}

PTA刷题总结-Part3.1 数组与链表专题
1 链表的基本操作我做链表题比较习惯于给链表设置哨兵（sentinel），这样可以减少边界极端情况的判断，避免没...
PTA刷题总结-Part 3 数据结构与算法
PTA刷题总结-Part 1 基础部分PTA刷题总结-Part 2 模拟与数学问题PTA刷题总结-Part 3 数...
PTA刷题总结-Part 2 模拟与数学问题
PTA刷题总结-Part 1 基础部分PTA刷题总结-Part 2 模拟与数学问题PTA刷题总结-Part 3 数...
PTA刷题总结-Part3.5 图专题
1 图的基本概念图是由两个集合构成 G=(V,E) 非空但有限的定点集合V 可以为空的边的集合E 相关术语无向...
PTA刷题总结-Part3.3 排序专题
本章节涵盖了冒泡排序O(n^2) 、选择排序O(n^2) 、插入排序O(n^2)、快速排序O(nlogn)和归并排...
leecode刷题（22）-- 反转链表
leecode刷题（22）-- 反转链表反转数组反转一个单链表。示例: 进阶:你可以迭代或递归地反转链表。你...
PTA刷题总结-Part3.4 树结构专题
1 关于树的重要定义节点的高度=从下往上，节点到叶子结点的最长路径（边数）。所以叶子结点高度为1 节点的深度=从...
Python小白 Leetcode刷题历程 No.81-No.
Python小白 Leetcode刷题历程 No.81-No.85 搜索旋转排序数组Ⅱ、删除排序链表中...
如何刷题
来自YouTube小姐姐的视频介绍小白刷题入门 ?传送门要点根据分出专题来刷题。可按照数据类型（树，图，链表），动...
数据结构与算法之美 —— 如何实现LRU缓存淘汰算法?(总结)
链表与数组链表定义: 百度百科数组定义:百度百科总结:链表和数组最大差别是在内存空间结构上，连续(数组)和...

PTA刷题总结-Part3.1 数组与链表专题

1 链表的基本操作

1.1 顺序创建链表

1.2 逆序创建链表

1.3 插入元素

1.4 查找和删除元素

1.5 单链表的反转

1.6 链表的合并

1.7 快慢指针

1.7.1 快慢指针解决单链表回文问题

1.7.2 快慢指针解决环形链表问题

2 静态链表

3 线性结构练习题

相关文章

PTA刷题总结-Part3.1 数组与链表专题

PTA刷题总结-Part 3 数据结构与算法

PTA刷题总结-Part 2 模拟与数学问题

PTA刷题总结-Part3.5 图专题

PTA刷题总结-Part3.3 排序专题

leecode刷题（22）-- 反转链表

PTA刷题总结-Part3.4 树结构专题

Python小白 Leetcode刷题历程 No.81-No.

如何刷题

数据结构与算法之美 —— 如何实现LRU缓存淘汰算法?(总结)

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读