网站开发吗和APP软件一样吗,郑州网站设计制作哪家好,成都地铁建设分公司网站,html个人主页模板一、线性表
线性表#xff08;linear list#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构#xff0c;常见的线性表#xff1a;顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构#xff0c;也就说是连续的一条…一、线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构常见的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 二、顺序表的OJ题
1.原地移除数组中所有的元素val
27. 移除元素 - 力扣LeetCodehttps://leetcode.cn/problems/remove-element/description/ int removeElement(int* nums, int numsSize, int val) {int scr0,dst0;while(scrnumsSize){if(nums[scr]val){scr;}else{nums[dst]nums[scr];scr;dst;}}return dst;
}
在原数组上进行修改等于val的跳过不赋值。反之则赋值。
2.删除排序数组中的重复项
26. 删除有序数组中的重复项 - 力扣LeetCodehttps://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/ int removeDuplicates(int* nums, int numsSize) {if(numsSize0){return 0;}int fast1,slow1;while(fastnumsSize){if(nums[fast]!nums[fast-1]){nums[slow]nums[fast];slow;}fast;}return slow;
} 对于这道题先处理特殊情况如果numssize0则该数组没元素返回0。可以采用双指针法来实现定义快慢指针fast不等于fast-1对应下标的内容则让该fast对应的赋值给slow再将slow
反之则就只让fast最后返回slowslow前的数据都只出现了一次。
3.合并两个有序数组
88. 合并两个有序数组https://leetcode.cn/problems/merge-sorted-array/ void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int l1m-1,l2n-1,l3mn-1;while(l10l20){if(nums1[l1]nums2[l2]){nums1[l3]nums1[l1];l3--;l1--;}else{nums1[l3]nums2[l2];l3--;l2--;}}while(l20){nums1[l3]nums2[l2];l3--;l2--;}
}
按照题目要求本题本来就是要进行升序排序对大的数据进行尾插操作值得注意的是为什么需要对l2进行第二次循环呢
因为 前真才会判断后面的而如果前面就是假则直接判假跳过后面的了所以需要对l2进行判断。
三、链表OJ题
在之前就已经写过一些有关链表的OJ题了感兴趣的朋友可以去这个链接观看
学习c语言单链表的应用-CSDN博客文章浏览阅读899次点赞31次收藏32次。单链表OJ题https://blog.csdn.net/bskmns/article/details/136591727?spm1001.2014.3001.5501现在要对链表OJ题做些补充准备发车了哦
1.链表分割
链表分割_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId8tqId11004rp2ru/activity/ojqru/ta/cracking-the-coding-interview/question-ranking 对于这个题可以通过创建两个链表来进行分割将小于x的数据尾插到less链表中将大于x的数据尾插到great链表中。然后将less链表的未结点与great的头节点的next连接到一起使链表连在一起再将greattail置为空。返回lesshead-next.
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode*greatHead,*greattail,*lessHead,*lesstail,*cur;greatHeadgreattail(struct ListNode*)malloc(sizeof(struct ListNode));lessHeadlesstail(struct ListNode*)malloc(sizeof(struct ListNode));curpHead;while(cur){if(cur-valx){lesstail-nextcur;lesstailcur;curcur-next;}else{greattail-nextcur;greattailcur;curcur-next;}} lesstail-nextgreatHead-next;greattail-nextnullptr;return lessHead-next;}
};
2.链表的回文结构
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId49tqId29370rp1ru/activity/ojqru/ta/2016test/question-ranking 对于这个题首先要找它的中间节点使用快慢指针找中间节点然后将slow后的链表进行逆置然后将A与slow进行比较以slow不等于A作为循环如果值不相等就返回false如果A的下一个等于slow就返回true如果不是就将slow和A移到下一个。
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code herestruct ListNode* slowA;struct ListNode* fastA;while(fast fast-next){slowslow-next;fastfast-next-next;}struct ListNode* headslow;while(head){struct ListNode*nexthead-next;head-nextslow;slowhead;headnext;}headA;while(slow!A){if(A-val!slow-val){return false;}if(A-nextslow){return true;}else{slowslow-next;AA-next;}}return true;;}
};
三、相交链表
160. 相交链表 - 力扣LeetCodehttps://leetcode.cn/problems/intersection-of-two-linked-lists/两个链表找相交节点如果一个链表为空则不存在相交节点设置pa pb遍历链表while循环如果pa不等于pb就进入循环使pa和pb向后遍历如果为空就返回headB headA不为空就置为下一个。最后返回pa。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {if(headANULL||headBNULL){return NULL;}struct ListNode* paheadA,*pbheadB;while(pa!pb){papaNULL?headB:pa-next;pbpbNULL?headA:pb-next;}return pa;
} 四、环形链表
141. 环形链表 - 力扣LeetCodehttps://leetcode.cn/problems/linked-list-cycle/在这个题中要判断该链表是否有环可以通过快慢指针来进行实现while循环fastfast-next
fastfast-next-next slowslow-next,每次fast多走一步所以链表只要有环就一定可以实现判断当slowfast时 返回true否则返回false。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode* slowhead,*fasthead;while(fast fast -next){fastfast-next-next;slowslow-next;if(slowfast){return true;}}return false;
}
好了本期的内容到此结束谢谢大家观看啊
学习数据结构任重而道远加油啊各位
