数据结构与算法作业1——数组链表入门_struct listnode *head

第一次作业：

习题1 删除列表的倒数第n个节点

题目链接

方法一 暴力求解

（1）先遍历得到链表的节点个数

（2）删除链表的第L-N+1个节点

时间复杂度：o(n)

空间复杂度：o(1)

代码：

int getLength(struct ListNode* head) {
    int length = 0;
    while (head) {
        ++length;
        head = head->next;   //这里面的“->”左面的是取该地址的数据（也就是结构体），右面是该结构体的某个数据。
    }
    return length;
}

定义函数getLength通过遍历得到链表的node数量

？？感觉这里面没有专门的头节点吧，要不然就会比实际上的node数量多一个

答：对。头节点就是第一个位置的节点，并不一定是你自己造出来的单独空数据域的。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));   //定义一个新的结构体指针dummy，并为其分配空间。
    dummy->val = 0, dummy->next = head; //该指针指向头节点，其数据域为0。
    int length = getLength(head); 
    struct ListNode* cur = dummy; 
    for (int i = 1; i < length - n + 1; ++i) {
        cur = cur->next;
    }
    cur->next = cur->next->next;
    struct ListNode* ans = dummy->next;
    free(dummy); //注意不要忘记free
    return ans;
}

？？不了解为什么要新定义一个cur，而不是直接用dummy？

原因：dummy虽然赋值给了cur，但是只是说cur的地址和dummy的地址是一样的，在改变了cur的地址之后，dummy的地址并不变。所谓的指针传值同步是指他们的地址相同时，值是同步的，但是在改变了两个指针变量其中一个指针的地址时，他们就不同步了。

定义函数用于删去目标的node

方法二 快慢指针

快指针先走N+1步，再让慢指针前行，快慢一起行动。最后快指针到达的时候，删除慢指针下一个节点。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0, dummy->next = head; //定义指向head的指针dummy
    struct ListNode* first = head; 
    struct ListNode* second = dummy; //将head、dummy分别赋给first、second两个新定义的结构体指针
    for (int i = 0; i < n; ++i) {
        first = first->next; //快指针先行n步
    }
    while (first) {
        first = first->next;
        second = second->next; //当快指针遍历到NULL的时候，让慢指针删去它后面的node
    }
    second->next = second->next->next;
    struct ListNode* ans = dummy->next;
    free(dummy);
    return ans;
}

*本解法设置dummy的目的就是保留指向头节点的指针。

与直接返回head的区别：如果删除第一个节点（head头节点），那么直接 "second->next = second->next->next;" 这一句就是将dummy的指针域改成了原来第二个节点的地址（也可能是NULL），而返回head的时候则无论是否删除头节点，最终都会返回原头节点。

本题其他解法后续更新。

2021/9/24 不要觉得自己什么都不会很焦虑很恐惧，这正说明你在进步，当你一个个慢慢地解决难题，你应该拥有成就感——你在逐渐适应自我提升的过程。

习题2 寻找落单数

给定一个长度为n的整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。要求：写出线性时间复杂度的算法。

进阶：给出O(1)额外空间复杂度的算法，不考虑函数实参占用的空间。

例

输入：nums = [4, 2, 1, 2, 1], n = 5

返回：4

请提交如下形式的函数：

int find_alone(int nums[], int n) {

}

方法：

使用对于每个数的按位异或：

按位异或（^）的特性：

 （上图摘自  逻辑异或 - 维基百科，自由的百科全书）

 因此，对于所有的元素进行按位异或计算之后，就会得到那个落单的数。

代码：

int find_alone(int nums[], int n) {
    int i, XOR = 0;
    for(i = 0;i < n;i++){
        XOR = XOR^nums[i];
    } 
    return XOR;
}

题目3 构造优美矩阵

助教小卢喜欢一种N*N的矩阵：它由数字 1,2,3...N*N 构成，矩阵中的元素各不相同，且每行、每列及矩阵的两条对角线上的数字之和都相同。助教小卢称这种矩阵为优美矩阵，并且在N为奇数时，因为助教小卢是一个优雅的人，可以通过优雅的方式生成这一矩阵。

首先将 1 写在第一行的中间。

之后，按如下方式从小到大依次填写每个数 (K=2,3,⋯,N×N) ：

若 (K-1) 在第一行但不在最后一列，则将 K填在最后一行， (K-1)所在列的右一列；

若 (K-1) 在最后一列但不在第一行，则将 K 填在第一列， (K-1)所在行的上一行；

若 (K-1) 在第一行最后一列，则将 K 填在 (K-1) 的正下方；

若 (K-1) 既不在第一行，也不在最后一列，如果 (K-1) 的右上方还未填数，则将 K 填在 (K-1) 的右上方，否则将 K 填在 (K-1) 的正下方。

现给定 奇数N，因为助教小卢是一个优雅的人，所以他要求你，按照上述助教小卢的优雅方法，构造N×N 的优雅矩阵。

进阶：使用一维数组存储这个矩阵。

例1：

输入：N = 5

输出：

17 24 1 8 15

23 5 7 14 16

4 6 13 20 22

10 12 19 21 3

11 18 25 2 9

请提交如下形式的函数：

void make_matrix(int N) {

}

我的代码：

void make_matrix(int N) {
    int mat[N*N];
    int x, y, i, j;
    for(i = 0; i<N*N; i++){
        mat[i] = 0;
    }
    x=1, y=(N+1)/2;
    mat[N*x+y-N-1]=1;
    for(i=2; i<=N*N; i++)
    {
        if(x==1&&y!=N)
            x=N,y++;
        else if(x!=1&&y==N)
            x--,y=1;
        else if(x==1&&y==N)
            x++;
        else if(!mat[N*x-2*N+y])
            x--,y++;
        else
            x++;
        mat[N*x+y-N-1]=i;
    }
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=N;j++)
            printf("%d ",mat[N*i+j-N-1]);
        printf("\n");
    }   
}

 

第一次作业总结：

感觉只有第一题比较难，涉及到链表的知识。