头像

CodeWater




离线:15小时前


最近来访(15)
用户头像
舒化奶
用户头像
codeSakura
用户头像
芥子
用户头像
Q_83
用户头像
陈平安
用户头像
niuniuya
用户头像
羽兰明月
用户头像
OIhzc


线性表

PS:笔试中用链表方式去实现,机试中用静态链表的方式去实现,不然会TLE(new的时候太慢)。日期问题在题解中。

1.定义

将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。


2. 前驱和后继

对于线性表中的数据来说,位于当前数据之前的数据统称为“前趋元素”,前边紧挨着的数据称为“直接前趋”;
同样,后边的数据统称为“后继元素”,后边紧挨着的数据称为“直接后继”。


3. 线性表的分类

1.  数据元素在内存中集中存储,采用顺序表示结构,简称“顺序存储”;
    例如:数组
2.  数据元素在内存中分散存储,采用链式表示结构,简称“链式存储”。
    例如:单链表、双链表、循环单(双)链表

4. 不同实现方式的时间复杂度(不要硬背结论、要从实现方式入手分情况讨论,下述为特定情况下的时间复杂度)

1. 数组:随机索引O(1)、插入O(n)、删除O(n)
(插入和删除分析的是最坏的情况下时间复杂度)

2. 单链表:查找某一元素O(n)、插入O(1)、删除O(n)
   对于删除的情况(注意甄别):
    a. 如果是删除当前点,最坏情况就是O(n),因为需要查找到当前点,才能进行删除。
    b. 如果是删除当前点的下一个点,那就是0(1),因为当前点已知,那么只需要一次遍历就可知下一个点的
       位置从而进行删除。


3. 双链表:查找某一元素O(n)、插入O(1)、删除O(1)
   相比较单链表而言,可以O(1)时间删除

总结:凡是需要遍历的都是O(n)的时间复杂度,不需要遍历的就是O(1)的时间复杂度。


5.考题:

2016-1、2016-2、2012-42、2015-41、2019-41
真题部分讲解部分由于时间原因来不及,不写了。见谅
PS:综合题链表题一般需要给出结点定义。

  1. 2012-42 两个链表的第一个公共结点
  2. 2015-41 筛选链表
  3. 2019-41 重拍链表

6. 押题:

  1. AcWing 34
  2. AcWing 1451

7.代码实现:

链表的创建,插入结点、删除结点。
(建议不要死记硬背,理解记忆,以下提供参考)

7.1单链表

单链表.png

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//单链表:结构体定义
struct Node {
    int val ; //数值域
    Node* next; //存放下一个结点的地址

    //下面定义两个构造函数,便于写代码。与单链表的定义无关,可忽略
    Node(): next(NULL) {}  //空构造函数,初始化一下next即可 
    Node(int val): val(val) , next(NULL)  {}  //初始化,为结点赋值
};

//输出链表
void print(Node* head){
    /*循坏遍历,用p指针从头开始遍历,p不空的时候,不断指向下一个结点,
    每到一个结点就输出当前点的val值
    */
    for(auto p = head ; p ; p = p->next)
        cout << p->val << ' ';
    cout << endl;
}



int main(){
    //head指针指向第一个结点的地址,他不是一个结点。初始链表为空,所以head指向null
    //Node* head = NULL; 

    //创造一个长度为1的链表, 同时head指针指向开头(1)
    Node* head =  new Node(1);

    /*1
    尾插法:每次在链表的最后面插入
    新建一个2的结点,插在1的后面。定义一个新结点的时候,因为构造函数使next为null,
    所以不需要再操作。
    */
    auto a = new Node(2); 
    head->next = a;

    //1->2
    //类似的新建一个3,插在最后面
    auto b = new Node(3);
    a->next = b;

    /*1->2->3
    头插法:
    每次在head指针的后面插入。注意指针修改的顺序,不然可能会造成断链。建议写的时候
    画个图再去操作。
    */
    auto c = new Node(4);
    c->next = head->next; //这样写,和下面是不能交换的
    head->next = c;

    /*这样子写就可以交换,具体情况具体分析
    c->next = a;
    head->next = c;
    */

    /*1->4->2->3
    删除结点2
    */
    c->next = a->next;
    delete(a);

    /*1->4->3
    删除头结点:先用一个指针存下head,在改变head指向*/
    auto p = head;
    head = head->next;
    delete(p);

    //4->3
    print(head);  //输出链表

    return 0;
}

7.2双链表

双链表.png

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//双链表:结构体定义,比单链表多一个向前指的指针
struct Node {
    int val ; //数值域
    Node* prev; //存放上一个结点的地址
    Node* next; //存放下一个结点的地址

    //下面定义两个构造函数,便于写代码。与单链表的定义无关,可忽略
    Node(): prev(NULL) , next(NULL) {}  //空构造函数,初始化prev , next即可 
    Node(int val): val(val) , prev(NULL) , next(NULL)  {}  //初始化,为结点赋值
};

//输出链表
void print(Node* head){
    /*循坏遍历,用p指针从头开始遍历,p不空的时候,不断指向下一个结点,
    每到一个结点就输出当前点的val值
    */
    for(auto p = head ; p ; p = p->next)
        cout << p->val << ' ';
    cout << endl;
}



int main(){
    //head指针指向第一个结点的地址,他不是一个结点。初始链表为空,所以head指向null
    //Node* head = NULL; 

    //创造一个双链表, 同时head指针指向开头,tail指向末尾。
    Node* head =  new Node() , *tail = new Node();
    head->next = tail , tail->prev = head;  //初始化前后指针指向

    cout<<"初始情况:" ;
    print(head); //初始情况:0->0

    /*0->1->0
    头插法:
    每次在head指针的后面插入。注意指针修改的顺序,不然可能会造成断链。建议写的时候
    画个图再去操作。
    */
    auto a = new Node(1); 
    a->next = head->next , a->prev = head;
    head->next->prev = a , head->next = a;

    //0->2->1->0
    //类似的新建一个2,插在head后面
    auto b = new Node(2);
    b->next = head->next , b->prev = head;
    head->next->prev = b , head->next = b;


    //0->2->1->3->0
    //插在1结点后面插入3也是一样
    auto c = new Node(3);
    c->next = a->next , c->prev = a;
    a->next = c , a->next->prev = c;

    cout<<"插入bac:";
    print(head);

    //删除结点b(2): 0->1->3->0   
    b->prev->next = b->next ; //修改b前面结点后指指针
    b->next->prev = b->prev ; //修改b后面结点前指指针
    delete(b);
    cout<<"最后:"; 
    print(head);  //输出链表

    return 0;
}

7.3循环双链表

循环双链表.png

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//循环双链表:结构体定义,比单链表多一个向前指的指针,同时最后一个和第一个也有指针互指
struct Node {
    int val ; //数值域
    Node* prev; //存放上一个结点的地址
    Node* next; //存放下一个结点的地址

    //下面定义两个构造函数,便于写代码。与单链表的定义无关,可忽略
    Node(): prev(NULL) , next(NULL) {}  //空构造函数,初始化prev , next即可 
    Node(int val): val(val) , prev(NULL) , next(NULL)  {}  //初始化,为结点赋值
};

//输出链表,跟之前单、双链表有点不一样
void print(Node* head){
    /*循坏遍历,用p指针从头开始遍历,p不是指向头结点的时候(因为对于循环双链表而言,没有
    空的节点),不断指向下一个结点,
    每到一个结点就输出当前点的val值
    */
    for(auto p = head->next ; p != head ; p = p->next)
        cout << p->val << ' ';
    cout << endl;
}


/*下面的代码只修改了tail指向head,其余跟双链表一样。*/
int main(){
    //head指针指向第一个结点的地址,他不是一个结点。初始链表为空,所以head指向null
    //Node* head = NULL; 

    //创造一个双链表, 同时head指针指向开头,tail指向head,头尾是同一个结点(循环)。
    Node* head =  new Node() , *tail = head;
    head->next = tail , tail->prev = head;  //初始化前后指针指向

    cout<<"初始情况(空):" ;
    print(head); //初始情况:0->0

    /*0->1->0
    头插法:
    每次在head指针的后面插入。注意指针修改的顺序,不然可能会造成断链。建议写的时候
    画个图再去操作。
    */
    auto a = new Node(1); 
    a->next = head->next , a->prev = head;
    head->next->prev = a , head->next = a;

    //0->2->1->0
    //类似的新建一个2,插在head后面
    auto b = new Node(2);
    b->next = head->next , b->prev = head;
    head->next->prev = b , head->next = b;


    //0->2->1->3->0
    //插在1结点后面插入3也是一样
    auto c = new Node(3);
    c->next = a->next , c->prev = a;
    a->next = c , a->next->prev = c;

    cout<<"插入bac:";
    print(head);

    //删除结点b(2): 0->1->3->0   
    b->prev->next = b->next ; //修改b前面结点后指指针
    b->next->prev = b->prev ; //修改b后面结点前指指针
    delete(b);
    cout<<"最后:"; 
    print(head);  //输出链表

    return 0;
}



活动打卡代码 AcWing 3573. 日期累加

CodeWater
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int months[13] = {
    0 , 31,  28 ,31 , 30 ,31 ,30 ,31, 31 ,30 ,31 ,30 ,31
};

int is_leap(int year){
    if(year % 100 != 0 && year %4 == 0 || year % 400 == 0)
        return 1;
    return 0;
}

int get_days(int y , int m){
    if(m == 2)
        return months[m] + is_leap(y);
    return months[m];
}

//判断一整年的天数
int get_year_days(int y , int m){
    //如果是1-2月,需要判断 当年是否是闰年
    if(m <= 2)
        return 365 + is_leap(y);
    //3-12月 ,要判断明年是否是闰年
    return 365 + is_leap(y + 1);
}

int main(){
    int T;
    cin>>T;
    while(T--){
        //年份 , 月份, 日期, 累加的天数
        int y , m , d ,  s;
        cin>>y>>m>>d>>s;
        //特判2月29号,下一天是3月1号
        if(m == 2 & d == 29) s-- , m = 3 , d = 1;
        //直接加上一整年的,优化一些时间
        while(s > get_year_days(y , m)){
            s -= get_year_days(y , m);
            y++;
        }
        //不足一年的按天数
        while(s--){
            if(++d > get_days(y , m)){
                d = 1;
                if(++m > 12){
                    m = 1;
                    y++;
                }
            }
        }
        printf("%04d-%02d-%02d\n" , y , m ,d);

    }
    return 0;
}



CodeWater
1个月前

算法

模拟,跟 打印日期 一样。
但是累加的天数过大,所以优化成一年一年的往上加,不足一年的时候在按天数加。

blablabla

参考文献

y总

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int months[13] = {
    0 , 31,  28 ,31 , 30 ,31 ,30 ,31, 31 ,30 ,31 ,30 ,31
};

int is_leap(int year){
    if(year % 100 != 0 && year %4 == 0 || year % 400 == 0)
        return 1;
    return 0;
}

int get_days(int y , int m){
    if(m == 2)
        return months[m] + is_leap(y);
    return months[m];
}

//判断整一年中的天数
int get_year_days(int y , int m){
    //如果是1-2月,需要判断 当年是否是闰年
    if(m <= 2)
        return 365 + is_leap(y);
    //3-12月 ,要判断明年是否是闰年
    return 365 + is_leap(y + 1);
}

int main(){
    int T;
    cin>>T;
    while(T--){
        //年份 , 月份, 日期, 累加的天数
        int y , m , d ,  s;
        cin>>y>>m>>d>>s;
        //特判2月29号,下一天是3月1号
        if(m == 2 & d == 29) s-- , m = 3 , d = 1;
        //直接加上一整年的,优化一些时间
        while(s > get_year_days(y , m)){
            s -= get_year_days(y , m);
            y++;
        }
        //不足一年的按天数
        while(s--){
            if(++d > get_days(y , m)){
                d = 1;
                if(++m > 12){
                    m = 1;
                    y++;
                }
            }
        }
        printf("%04d-%02d-%02d\n" , y , m ,d);

    }
    return 0;
}


活动打卡代码 AcWing 3607. 打印日期

CodeWater
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//months:记录一月中有多少天
const int  months[13]={
    0 , 31 , 28 , 31 , 30 ,31 , 30 , 31 , 31 ,30 ,31 , 30 ,31
};

//判断闰年,平年返回0 , 闰年返回1
int is_leap(int year){
    if( (year % 100 != 0 && year %  4 == 0 ) || year % 400 == 0)
        return 1;
    return 0;
}

//求y年m月有多少天
int get_days(int y , int m){
    if(m == 2) return months[m] + is_leap(y);
    //其他月份直接返回
    return months[m];
}


int main(){
    int y , s; // 年份 , 天数
    while(cin>>y>>s ){

        int m = 1 , d = 1 ; //月份和日期 从1开始
        //模拟
        //1月1号也算第一天,所以先减掉一天
        s--;
        while(s--){
            //日期大于固定天数,说明到下一个月
            if(++ d > get_days(y , m)){
                //更新d日期
                d = 1;
                //m月份大于12,到下一年
                if(++m > 12){
                    m = 1;
                    y++;
                }
            }
        }
        printf("%04d-%02d-%02d\n" , y , m , d);
    }
    return 0;
}



CodeWater
1个月前

算法

模拟

打印日期.png

参考文献

y总

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//months:记录一月中有多少天
const int  months[13]={
    0 , 31 , 28 , 31 , 30 ,31 , 30 , 31 , 31 ,30 ,31 , 30 ,31
};

//判断闰年,平年返回0 , 闰年返回1
int is_leap(int year){
    if( (year % 100 != 0 && year %  4 == 0 ) || year % 400 == 0)
        return 1;
    return 0;
}

//求y年m月有多少天
int get_days(int y , int m){
    if(m == 2) return months[m] + is_leap(y);
    //其他月份直接返回
    return months[m];
}


int main(){
    int y , s; // 年份 , 天数
    while(cin>>y>>s ){

        int m = 1 , d = 1 ; //月份和日期 从1开始
        //模拟
        //1月1号也算第一天,所以先减掉一天
        s--;
        while(s--){
            //日期大于固定天数,说明到下一个月
            if(++ d > get_days(y , m)){
                //更新d日期
                d = 1;
                //m月份大于12,到下一年
                if(++m > 12){
                    m = 1;
                    y++;
                }
            }
        }
        printf("%04d-%02d-%02d\n" , y , m , d);
    }
    return 0;
}



CodeWater
1个月前

算法

分段+翻转+合并。
重排链表.png

参考文献

y总

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void rearrangedList(ListNode* head) {
        //特判只有一个结点,直接结束(不可能为空,因为数据范围大于1)
        if(!head -> next) return ;
        //n:求的链表结点数
        int n = 0 ;
        for(auto p = head ; p ; p = p -> next) n++;
        //left:前半段的结点数
        int left = (n + 1) / 2;
        //leftA:前半段的右边界,即前半段最后一个结点
        auto leftA = head;
        for(int i = 0 ; i < left - 1 ; i++) leftA = leftA -> next;

        //rightB:后半段的左边界,即后半段的第一个结点;rightC:rightB后面一个结点
        auto rightB = leftA -> next , rightC = rightB -> next;
//leftA后面指向空,rightB的下一个也指向空,因为翻转之后rightB就是后半段最后一个结点
        leftA -> next = rightB -> next = NULL;

        //翻转后半段
        while(rightC){ // 当rightC没有走到空时就继续
            auto p = rightC -> next;
            //rightC下一个结点指向rightB,翻转
            rightC -> next = rightB ;
            //两个指针rightB、rightC向后移动一个
            rightB = rightC;
            rightC = p;
        }//循环结束之后,后半段的头结点就是rightB。rightC指向了空

        //合并两个链表,p指向前半段第一个,q指向后半段第一个,后半段元素少,所以判断q不空
        for(auto p = head , q = rightB ; q ; ){
            //保存q的下一个结点,方便下面改指针指向的时候不丢失
            auto o = q -> next;
            q -> next = p -> next;
            p -> next = q;
            p = p -> next -> next;
            q = o;
        }
        //合并完成

    }
};


活动打卡代码 AcWing 3757. 重排链表

CodeWater
1个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void rearrangedList(ListNode* head) {
        //特判只有一个结点,直接结束(不可能为空,因为数据范围大于1)
        if(!head -> next) return ;
        //n:求的链表结点数
        int n = 0 ;
        for(auto p = head ; p ; p = p -> next) n++;
        //left:前半段的结点数
        int left = (n + 1) / 2;
        //leftA:前半段的右边界,即前半段最后一个结点
        auto leftA = head;
        for(int i = 0 ; i < left - 1 ; i++) leftA = leftA -> next;

        //rightB:后半段的左边界,即后半段的第一个结点;rightC:rightB后面一个结点
        auto rightB = leftA -> next , rightC = rightB -> next;
//leftA后面指向空,rightB的下一个也指向空,因为翻转之后rightB就是后半段最后一个结点
        leftA -> next = rightB -> next = NULL;

        //翻转后半段
        while(rightC){ // 当rightC没有走到空时就继续
            auto p = rightC -> next;
            //rightC下一个结点指向rightB,翻转
            rightC -> next = rightB ;
            //两个指针rightB、rightC向后移动一个
            rightB = rightC;
            rightC = p;
        }//循环结束之后,后半段的头结点就是rightB。rightC指向了空

        //合并两个链表,p指向前半段第一个,q指向后半段第一个,后半段元素少,所以判断q不空
        for(auto p = head , q = rightB ; q ; ){
            //保存q的下一个结点,方便下面改指针指向的时候不丢失
            auto o = q -> next;
            q -> next = p -> next;
            p -> next = q;
            p = p -> next -> next;
            q = o;
        }
        //合并完成

    }
};


活动打卡代码 AcWing 3756. 筛选链表

CodeWater
2个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* filterList(ListNode* head) {
        /*因为题目中链表结点大于等于1,所以不需要判空*/
        //标志数组,标志一个元素是否已经出现过
        bool st[10001] = {};
        //第一个头结点一定会留下,设置true
        st[abs(head->val)] = true;
        //开始从头结点进行遍历,每次判断是否有下一个结点
        for(auto p = head ; p -> next;){
            //下一个结点的值(取绝对值,因为在判断的时候也是从绝对值判断是否删除)
            int x = abs(p->next->val);
            //下一个结点值在数组中已经出现过,删除
            if(st[x]){
                //先保存下一个结点
                auto q = p->next;
                //指向下下个结点
                p->next = q->next;
                //这个时候就可以删除下一个结点了
                delete q;

            }else{//没有出现在数组中,这个点保留
                //p继续遍历下一个位置
                p = p->next;
                //最后标记一下存在该数
                st[x] = true;
            }
        }
        //最后返回头结点
        return head;

    }
};



CodeWater
2个月前

题目描述

一个单链表中有 m 个结点,每个结点上的元素的绝对值不超过 n。

现在,对于链表中元素的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。

请输出筛选后的新链表。

例如,单链表 21 -> -15 -> -15 -> -7 -> 15,在进行筛选和删除后,变为 21 -> -15 -> -7。

输入样例:
输入:21->-15->-15->-7->15

输出:21->-15->-7
数据范围
1≤m≤1000,
1≤n≤10000


算法

遍历链表的时候,用一个数组标记是否已经出现过该元素。出现就在对应的位置true,否则false;
筛选链表.png

时间复杂度

O(m)


参考文献

y总


C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* filterList(ListNode* head) {
        /*因为题目中链表结点大于等于1,所以不需要判空*/
        //标志数组,标志一个元素是否已经出现过
        bool st[10001] = {};
        //第一个头结点一定会留下,设置true
        st[abs(head->val)] = true;
        //开始从头结点进行遍历,每次判断是否有下一个结点
        for(auto p = head ; p -> next;){
            //下一个结点的值(取绝对值,因为在判断的时候也是从绝对值判断是否删除)
            int x = abs(p->next->val);
            //下一个结点值在数组中已经出现过,删除
            if(st[x]){
                //先保存下一个结点
                auto q = p->next;
                //指向下下个结点
                p->next = q->next;
                //这个时候就可以删除下一个结点了
                delete q;

            }else{//没有出现在数组中,这个点保留
                //p继续遍历下一个位置
                p = p->next;
                //最后标记一下存在该数
                st[x] = true;
            }
        }
        //最后返回头结点
        return head;

    }
};



CodeWater
2个月前
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        //p指针指向a头结点,q指针指向b头结点
        auto p = headA , q = headB;

        /*测试输出两条链表的代码(可忽略):
        while(p) cout<<p->val<<' ' , p = p-> next;
        cout<<endl;
        while(q) cout<<q->val<<' ' , q = q-> next;
        */

        //当p,q一直不相等的时候,一直循环,直到找到答案
        while(p != q){
            //p不空,移到当前链表当前位置的下一个结点
            if(p) p = p -> next;
            //否则遍历完A链表之后,就指向B链表的头结点
            else p = headB;
            //q跟p的操作一样,不空一直遍历当前链表,遍历完再从另外一条链表继续遍历
            if(q) q = q -> next;
            else q = headA;

        }
        //最后返回答案
        return p;
    }
};