字符串与链表刷题集（5.30-6.6）

1.字符串的两种写法char* s hello; char* s1[] hello;前者被编译器放在文字常量区只读数据段s只是一个指针不能写s[0] a;这是在修改只读内存程序将直接出现段错误崩溃。而数组形式的写法会让s1在栈或静态区拥有一份拷贝这个副本就是可修改的。2.找出字符串中第一个只出现一次的字符int FirstUniqChar(char* str) { int count[256] { 0 }; int sz strlen(str); int i 0; for (i 0; i sz; i)//统计所有与元素出现的次数 { unsigned char ch str[i]; count[ch];//字符的本质是ASCII所以直接使用下标作为索引 } for (i 0; i sz; i) { unsigned char ch str[i];//注意索引仍需按照str的顺序来 if (count[ch] 1) { return i; } } return -1; }这是用数组模拟哈希表的写法时间复杂度n。重点在于我们需要理解字符本质是ASCII码值也就是数字所以它可以作为索引来记录自身出现的次数。比如a在某个字符串里出现了2次那么我们创建遍历字符串后count[97]这个位置就是2.3.力扣题两个链表模拟相加2. 两数相加 - 力扣LeetCodestruct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { //建立哨兵位 struct ListNode dummy; dummy.next NULL; //建立辅助指针tail便于后续定位链表尾部 struct ListNode* tail dummy; //建立进位记录数carry int carry 0; while (l1 || l2 || carry)//只要l1和l2有一个未到末尾则仍需进行相加操作同时carry若不为零说明有进位需要则仍需进行相加操作 { int sum carry;//用sum继承上一位的进位数 //对应位相加 if (l1) { sum l1-val; l1 l1-next; } if (l2) { sum l2-val; l2 l2-next; } carry sum / 10;//记录进位数 sum % 10;//记录本次相加结果 //建立新节点 struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val sum; node-next NULL; //将tail移动至尾部以此链接新节点 tail-next node; tail node; } return dummy.next;//用哨兵位访问链表首部并返回 }本题真正的难点在于如何在链表中实现整数相加过程中进位的继承以及对于单次计算结果我们如何将其和过去的结果进行连接最后就是使用哨兵位对情况的处理进行统一化。显然这需要对取模和除法运算以及链表实现的相关算法有一定理解其中对变量carry和sum的处理尤为巧妙。详情看注释。4.力扣题反转链表https://leetcode.cn/problems/reverse-linked-list题目要求我们反转一个没有前驱的单链表实际上就是在考验我们头插相关的操作。我们只需从头遍历链表把每一个元素头插到新链表即可完成反转操作。当然这里最好设立一个临时的哨兵节点以同一处理空链表的情况具体代码如下typedef struct ListNode list; struct ListNode* reverseList(struct ListNode* head) { list* pcur1 head; list dummy; dummy.next NULL; list* guard dummy; while (pcur1) { list* NewNode pcur1; pcur1 pcur1-next; NewNode-next guard-next; guard-next NewNode; } return guard-next; }这里我们先用一个结构体指针NewNode记录当前位置再让pcur向后移动这样做的好处是即使pcur移动了我们仍然可以访问它未移动时的后方节点。之后的代码很好理解让NewNode的后继指向头节点也就是哨兵节点的下一个之后再把哨兵节点重新移动到头部即让它的后继指向NewNode。5.力扣题合并两个升序链表21. 合并两个有序链表 - 力扣LeetCode解决这个问题比较容易理解的思路是依次从两个链表中选择数据较小的节点插入到新链表中直到某个链表来到尾部再将另一个剩下的所有节点按原顺序插入到新链表中即可完成合并。这里解释一下后半句。由于两个链表是升序的按照我们的取法——每次取二者较小的那个节点——只要一个链表来到末尾那么另一个链表剩下的所有节点必然大于新链表的所有节点所以直接按原顺序插入即可。具体代码如下list* mergeTwoLists(list* head1, list* head2) { assert(head1 head2); list dummy; dummy.next NULL; list* tail dummy; list* cur1 head1; list* cur2 head2; while (cur1 cur2) { if (cur1-x cur2-x) { tail-next cur1; cur1 cur1-next; } else { tail-next cur2; cur2 cur2-next; } tail tail-next; } if (cur1) { tail-next cur1; } else { tail-next cur2; } return dummy.next; }这里我们创建了一个tail来维护新链表的尾部每当完成一次插入tail就向后移动一位直到cur1或者cur2来到尾部。6.力扣题寻找交叉节点160. 相交链表 - 力扣LeetCode这里先考虑简单的思路。我们先依次遍历两个链表计算出二者长度再相减计算差值k。之后再让两个指针遍历一边但这次我们让处于长链表的指针先走k步这样当两个指针相遇时必然是到达了交叉地点。typedef struct ListNode list; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { list *cur1 headA, *cur2 headB; int lenA 0, lenB 0; while (cur1) { cur1 cur1-next; lenA; } cur1 headA; while (cur2) { cur2 cur2-next; lenB; } cur2 headB; int k lenA - lenB; if (k 0) { while (k--) cur1 cur1-next; } else { k -k; while (k--) cur2 cur2-next; } while (cur1 ! cur2) { cur1 cur1-next; cur2 cur2-next; } return cur1; }当然更优雅的解决方案是使用快慢指针。还是两个指针遍历两个链表但当某一个指针来到末尾时我们让它跳到另一个链表的头部继续走这样由于两个指针走的路程是相等的那么必然会在交叉点相遇具体的代码实现如下typedef struct ListNode list; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { list *cur1 headA, *cur2 headB; while (cur1 ! cur2) { cur1 (cur1 NULL) ? headB : cur1-next; cur2 (cur2 NULL) ? headA : cur2-next; } return cur1; }7.力扣题重排链表LCR 026. 重排链表 - 力扣LeetCode我们可以先试用快慢指针找到链表的中间节点截取链表的后半部分再使用刚刚实现过的反转方法把后半段链表反转再按题目要求的规则插入原链表具体的代码如下typedef struct ListNode list; list* FindMin(list* head) { list* fast head; list* slow head; while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; } list* revertlist(list* head) { list dummy; dummy.next NULL; list* guard dummy; list* pcur head; while (pcur) { list* next pcur-next; pcur-next guard-next; guard-next pcur; pcur next; } return guard-next; } void reorderList(struct ListNode* head){ //寻找中间节点 list* mid FindMin(head); list* newhead mid-next; mid-next NULL; //反转后半段链表 list* revert_listhead revertlist(newhead); //按规则插入 list* pcur head; list* rpcur revert_listhead; while (rpcur) { list* next pcur-next; list* rnext rpcur-next; rpcur-next next; pcur-next rpcur; pcur next; rpcur rnext; } }但是这样的方法显然不够优雅。我们知道需要插入的节点和其插入的位置在下标上是有关系的比如第n节点要插入到下标0的后方而第n - 1节点要插入到下标1的后方如果我们能按下标访问链表那这个问题就非常简单了。这里提供一种思路。我们可以先试用一个结构体类型的数组记录每一个节点指针让后用索引ij来访问数组从而访问节点进行插入操作具体代码如下typedef struct ListNode list; void reorderList(struct ListNode* head){ list* arr[50000]; list* pcur1 head; int n 0; for (n 0; pcur1 ! NULL; n, pcur1 pcur1-next) { arr[n] pcur1; } int i 0, j 0; for (j n - 1, i 0; j n / 2; j--, i) { arr[j]-next arr[i]-next; arr[i]-next arr[j]; } arr[j]-next NULL; }这里一定需要注意n在走完第一个循环后变成了节点的总个数所以j一定要从n - 1开始访问否则就会越界。再一个就是最后一定要将链表末尾next置空否则链表就会变成循环。8.力扣题无重复的最长子串3. 无重复字符的最长子串 - 力扣LeetCode在数据不大时这道题可以使用暴力解法。int lenthIfUniquel(char* s, int t)//判断传入的区间是否有重复元素 { int len t 1; for (int i 0; i len; i) { for (int j i 1; j len; j) { if (s[i] s[j]) return 1;//由于最少传入长度为1故返回1 } } return len; } int lengthOfLongestSubstring(char* s) { char* start s; int sz strlen(s); if (sz 1) return 1; int tmpsz 1;//start最多向后访问多少个字符 int len 0; while (*start) { int tmp 0, tmpsz 1; while (tmpsz sz - 1) { tmp lenthIfUniquel(start, tmpsz); if (len tmp)//更新最大长度 len tmp; tmpsz;//铆钉左边界后不断扩展右边界 } start; sz--; } return len; }从字符串头部开始依次选取区间再判断这个区间是否有重复字符若有则返回1若无则返回子串长度。每轮检查后都不断更新最大长度最终得到最大非重复子串。但显然这个暴力解法的时间复杂度来到了惊人的N^3,肯定通过不了所有测试用例。本题最高效的解法是使用哈希表但为了照顾还未学习哈希表的同学我们用更加简单易懂的方式来解决。在第二道题中我们已经知道一种思路字符本质上是数字因此可以使用数组来记录它出现的次数我们可以把这个思路应用到这里以索引 i 作为左边界j 作为右边界i作为第一层循环从字符串头部遍历j 作为内层循环从 i开始遍历。创建一个数组seen把遍历过的字符作为下标将1存入数组表示这个字符在区间i - j已经存在。如果访问到数组seen里某一个下标下的元素是1就意味着重复就跳出内层循环让i即右移左边界继续检查如果未检查到重复就利用j 和 i不断更新当前字符串长度。代码如下int lengthOfLongestSubstring(char* s) { int i 0, j 0; int sz strlen(s); int max_len 0; for (i 0; i sz; i) { int seen[5000] { 0 }; for (j i; j sz; j) { if (seen[(unsigned char)s[j]]) break; seen[(unsigned char)s[j]] 1; max_len MAX(max_len, j - i 1); } } return max_len; }