【初阶数据结构篇】顺序表和链表算法题

简介: 此题可以先找到中间节点,然后把后半部分逆置,最近前后两部分一一比对,如果节点的值全部相同,则即为回文。

顺序表算法题


不熟悉顺序表的可以先了解一下


顺序表实现方法


移除元素


给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。


假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作:


  • 更改 nums 数组,使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。


很容易想到的是用双指针进行遍历和赋值即可

int removeElement(int* nums, int numsSize, int val) {
    int left = 0;
    for (int right = 0; right < numsSize; right++) {
        if (nums[right] != val) {
            nums[left] = nums[right];
            left++;
        }
    }
    return left;
}
  • 注意题目中说的是元素的顺序可以发生改变,即不需要保持元素的相对顺序,可以进行优化


      如果左指针 left 指向的元素等于 val,此时将右指针 right 指向的元素复制到左指针 left 的位置,然后右指针 right 左移一位。如果赋值过来的元素恰好也等于 val,可以继续把右指针                   right 指向的元素的值赋值过来(左指针 left 指向的等于 val 的元素的位置继续被覆盖),直到左指针指向的元素的值不等于 val 为止。



注意while结束条件不要少了等于


int removeElement(int* nums, int numsSize, int val) {
    int left = 0, right = numsSize-1;
    while (left <= right) {
        if (nums[left] == val) {
            nums[left] = nums[right];
            right--;
        } else {
            left++;
        }
    }
    return left;
}

注意:返回的是元素的个数



删除有序数组中的重复项


给你一个 非严格递增排列 的数组 nums ,请你** 原地** 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。


考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:


  • 更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k


和上一道题思路大致相同,题目说了是非严格递增序列,双指针法比较前后两个元素即可

int removeDuplicates(int* nums, int numsSize) {
    int src = 0;
    int dest = 1;
    while (dest < numsSize) {
        if(nums[src]!=nums[dest])
        {
            nums[++src]=nums[dest];
        }
        dest++;
    }

    return ++src;
}


合并两个有序数组


给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。


请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。


**注意:**最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。


  • 当然可以直接把第二个数组移到第一个数组尾部,然后进行排序
  • 使用qsort函数


int cmp(int* a, int* b) {
    return *a - *b;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    for (int i = 0; i != n; ++i) {
        nums1[m + i] = nums2[i];
    }
    qsort(nums1, nums1Size, sizeof(int), cmp);
}

  • 三指针法,利用两个数组都是非递减排列


  • 因为排序好的数组仍然是非递减序列,所以我们的两个指针依次从尾部开始向前遍历,谁大把谁放到nums1的尾部若从前面开始需要新创建一个数组来存储元素最后再赋值给nums1


  • 最后出循环的时候l2和l3只可能有一个小于0
  • 若是l2,说明nums2没有遍历完,需要将剩下的元素赋值给nums1
  • 若是l3,则直接返回nums1即可
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int l1=nums1Size-1;
    int l2=m-1;
    int l3=n-1;
    while(l2>=0&&l3>=0)
    {
        if(nums1[l2]>nums2[l3])
        {
            nums1[l1]=nums1[l2];
            l2--;
        }
        else
        {
            nums1[l1]=nums2[l3];
            l3--;
        }
        l1--;

    }
    if(l2<0)
    {
        while(l1>=0)
        nums1[l1--]=nums2[l3--];
    }
}

链表算法题


不熟悉链表的可以先了解一下


单链表实现方法


移除链表元素

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点




最直观的办法就是创建一个新链表


注:不是开辟空间的深拷贝,而只是定义了指向同一结点的指针


在最后需要先判断newtail是否为空(否则链表为空链表时会报错)再将其中的next指针置为空(否则可能会出现循环

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
ListNode* removeElements(ListNode* head, int val) {
    ListNode* pcur = head;
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;
    while (pcur) {
        if (pcur->val != val) {
            if (newhead == NULL) {
                newhead = newtail = pcur;
            } else {
                newtail->next = pcur;
                newtail = newtail->next;
            }
        }
        pcur = pcur->next;
    }
    if (newtail)
        newtail->next = NULL;
    return newhead;
}
  • 在leetcode上给出了递归的方法,链表的定义具有递归的性质,因此链表题目常可以用递归的方法求解。这道题要求删除链表中所有节点值等于特定值的节点,可以用递归实现。
struct ListNode* removeElements(struct ListNode* head, int val) {
    if (head == NULL) {
        return head;
    }
    head->next = removeElements(head->next, val);
    return head->val == val ? head->next : head;
}


反转链表


给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

  • 可以和上一道题一样创建新链表,不多赘述
  • 这里介绍一种比较巧妙的方法->三指针法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)
    return head;
    ListNode* n1,*n2,*n3;
    n1=NULL,n2=head,n3=head->next;
    while(n3){
        n2->next=n1;
        n1=n2;
        n2=n3;
        n3=n3->next;
    }
    n2->next=n1;
    return n2;
    
}


链表的中间结点


给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点




  • 快慢指针法
  • 注意为偶数时返回第二个结点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* slow, *fast;
    slow=fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

合并两个有序链表


将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。



  • 和合并数组大致思路相同
  • 可以在创建新链表的一开始申请头结点(哨兵位),避免对于newtail和newhead为空的情况进行讨论
  • 记得最后释放空间!!!
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    ListNode* newhead,*newtail;
    newhead=newtail=(ListNode*)malloc(sizeof(ListNode));
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            newtail->next=list1;
            list1=list1->next;
        }
        else
        {
            newtail->next=list2;
            list2=list2->next;
        }
        newtail=newtail->next;
    }
    if(list1)
    {
        newtail->next=list1;
    }
    else
    {
        newtail->next=list2;
    }
    ListNode* ret=newhead->next;
    free(newhead);
    newhead=newtail=NUll;
    return ret;
}

链表分割


有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针


  • 解题思路:创建两个链表,分别存放小于x的节点和大于等于x的节点,分别进行尾插
  • 最后别忘了把大链表的尾节点置为空,否则可能会出现死循环
  • 还是别忘了释放空间


ListNode* partition(ListNode* pHead, int x) {
        if(pHead == NULL)
            return NULL;
        
        struct ListNode* lessHead, *lessTail,*greaterHead, *greaterTail;
        //创建链表表头
        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur = pHead;
        while(cur)
        {
            //小于x的尾插到lessTail
            if(cur->val < x)
            {
                lessTail->next = cur;
                lessTail = lessTail->next;
            }
            //大于等于x的尾插到greaterTail
            else
            {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
            }
            cur = cur->next;
        }
        //链接两个链表
        lessTail->next = greaterHead->next;
        greaterTail->next = NULL;
        //获取表头
        pHead = lessHead->next;
        free(lessHead);
        free(greaterHead); 
        return pHead;
    }

链表的回文结构



对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900


  • 不推荐的解法,类似数组字符串的回文解法


  • 先把链表中的元素值全部保存到数组中,然后再判断数组是否为回文。不建议使用这种解法,因为如果没有告诉链表最大长度,则不能同此解法
bool chkPalindrome(ListNode* A) {
        // write code here
        int a[900] = {0};
        ListNode* cur = A;
        int n = 0;
        //保存链表元素
        while(cur)
        {
            a[n++] = cur->val;
            cur = cur->next;
        }
        //判断数组是否为回文结构
        int begin = 0, end = n-1;
        while(begin < end)
        {
            if(a[begin] != a[end])
                return false;
            ++begin;
            --end;
        }
         
        return true;
    }
  • 解题思路:此题可以先找到中间节点,然后把后半部分逆置,最近前后两部分一一比对,如果节点的值全部相同,则即为回文。
  • 快慢指针找中间结点
  • 三指针逆置后半部分
bool chkPalindrome(ListNode* A) {
    if (A == NULL || A->next == NULL)
      return true;
    ListNode* slow, *fast, *prev, *cur, *nxt;
    slow = fast = A;
    //找到中间节点
    while (fast && fast->next)
    {
      slow = slow->next;
      fast = fast->next->next;
    }
    prev = NULL;
    //后半部分逆置
    cur = slow;
    while (cur)
    {
      nxt = cur->next;
      cur->next = prev;
      prev = cur;
      cur = nxt;
    }
    //逐点比对
    while (A && prev)
    {
      if (A->val != prev->val)
        return false;
      A = A->next;
      prev = prev->next;
    }
    return true;
  }

目录
相关文章
|
21天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
33 1
|
25天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
77 4
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
53 4
|
22天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
22天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
1月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
96 23
|
1月前
|
算法
数据结构之蜜蜂算法
蜜蜂算法是一种受蜜蜂觅食行为启发的优化算法,通过模拟蜜蜂的群体智能来解决优化问题。本文介绍了蜜蜂算法的基本原理、数据结构设计、核心代码实现及算法优缺点。算法通过迭代更新蜜蜂位置,逐步优化适应度,最终找到问题的最优解。代码实现了单链表结构,用于管理蜜蜂节点,并通过适应度计算、节点移动等操作实现算法的核心功能。蜜蜂算法具有全局寻优能力强、参数设置简单等优点,但也存在对初始化参数敏感、计算复杂度高等缺点。
59 20
|
23天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
44 5
|
21天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
50 1
|
1月前
|
机器学习/深度学习 算法 C++
数据结构之鲸鱼算法
鲸鱼算法(Whale Optimization Algorithm,WOA)是由伊朗研究员Seyedali Mirjalili于2016年提出的一种基于群体智能的全局优化算法,灵感源自鲸鱼捕食时的群体协作行为。该算法通过模拟鲸鱼的围捕猎物和喷出气泡网的行为,结合全局搜索和局部搜索策略,有效解决了复杂问题的优化需求。其应用广泛,涵盖函数优化、机器学习、图像处理等领域。鲸鱼算法以其简单直观的特点,成为初学者友好型的优化工具,但同时也存在参数敏感、可能陷入局部最优等问题。提供的C++代码示例展示了算法的基本实现和运行过程。
49 0
下一篇
DataWorks