代码随想录
数组
1.找单身狗
【题目】：一个数组中只有两个数字是出现一次，其他所有数字都出现了两次；编写一个函数找出这两个只出现一次的数字
例如：1 2 3 4 5 1 2 3 4 6
发现5和6只出现一次
思路1：遍历统计
思路2：异或
引入：
一个数组中只有一个”单身狗“的情况：全部异或，得到的即是那个单独的数字
int main()
{
int arr[] = {5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 6, 9};
//所有数字异或
int i = 0;
int sz = sizeof(arr) / sizeof(arr[0]);
int ret = 0;
for (i = 0; i < sz; i++)
{
ret ^= arr[i];
}
// ret 就是5^6的结果，二进制中一定有1
//计算ret的第几位是1
int pos = 0;
for (i = 0; i < 32; i++)
{
if (((ret >> i) & 1) == 1)
{
pos = i;
break;
}
}
// ret的第pos位是1
//把arr数组中的每个元素的第pos位为1的数字异或在一起
int num1 = 0;
int num2 = 0;
for (i = 0; i < sz; i++)
{
if (((arr[i] >> pos) & 1) == 1)
{
num1 ^= arr[i];
}
else
{
num2 ^= arr[i];
}
}
printf("%d %d\n", num1, num2);
return 0;
}
2.轮转数组
思路1:
tmp变量保存最后一个变量，整体将数据向后移动一次，再将tmp赋值给第一个元素；将前面步骤重复k次
问题：效率超时；时间复杂度为O(N^2) 空间复杂度为O(1)
#include<stdio.h>
#include<string.h>
//该程序的空间复杂度大了
int main() {
int nums[7] = { 1, 2, 3, 4, 5, 6, 7 };
int k;
scanf("%d", &k);
int tmp = 0;
int sz = sizeof(nums) / sizeof(int);
for (int i = 0; i < k; i++)
{
tmp = nums[sz - 1];
for (int j = sz - 1; j > 0; j--)
{
nums[j] = nums[j - 1];
}
nums[0] = tmp;
}
for (int i = 0; i < sz; i++)
{
printf("%d", nums[i]);
}
}
思路2：
用空间来换取时间，开辟一个新的数组来保存移动后的元素
#include<stdio.h>
#include<string.h>
//用空间来换时间
int main() {
int nums[7] = { 1, 2, 3, 4, 5, 6, 7 };
int k;
scanf("%d", &k);
int tmp[7] = { 0 };
int sz = sizeof(nums) / sizeof(int);
for (int i = 0; i < sz; i++)
{
tmp[(i + k) % 7] = nums[i];
}
for (int i = 0; i < sz; i++)
{
nums[i] = tmp[i];
}
for (int i = 0; i < sz; i++)
{
printf("%d", nums[i]);
}
}
思路3：
三步翻转法
1，2，3，4，5，6，7
前n-k个逆置 4，3，2，1
后k个逆置 7，6，5
整体再逆置 5，6，7，1，2，3，4
#include <stdio.h>
void reverse(int *arr, int begin, int end)
{
while (begin < end)
{
int tmp = arr[begin];
arr[begin] = arr[end];
arr[end] = tmp;
begin++;
end--;
}
}
void rotate(int *nums, int numsSize, int k)
{
k %= numsSize;
reverse(nums, 0, numsSize - k - 1); //交换前numsSize-k个
reverse(nums, numsSize - k, numsSize - 1); //交换后k个
reverse(nums, 0, numsSize - 1); //再整体交换
}
3.移除元素
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YpVtFB8j-1668401878558)(E:/Typora图片/image-20221027185702799.png)]
对于数组中的元素，只能做到覆盖，并不能真正实现删除
思路1：暴力实现
两层for循环，一层用来遍历数组找到目标（待删除）的值，下一层用后续元素将这个元素覆盖
这里不够优秀的地方即是：存在多次重复挪动
void move(int *nums,int sz,int begin){
for (int i = begin; i < sz - 1;i++){
nums[i] = nums[i + 1];
}
}
int removeElement(int* nums, int numsSize, int val){
for (int i = 0; i < numsSize;i++){
if(nums[i]==val){
move(nums, numsSize, i);
numsSize--;
i--;
}
}
return numsSize;
}
思路2：双指针思路
定义两个指针，一个指针src指向原数组，另一指针des指向新数组tmp，src遍历原数组，值不等于val则将其赋值给新数组
#include <stdio.h>
int main()
{
int nums[10] = {1, 2, 3, 2, 5, 6, 2, 7, 8, 2};
int tmp[10] = {0};
int val = 2;
int des, sz = 0;
for (int i = 0; i < 10; i++)
{
if (nums[i] != val)
{
tmp[des] = nums[i];
des++;
sz++;
}
}
for (int i = 0; i < sz; i++)
{
nums[i] = tmp[i];
}
for (int i = 0; i < sz; i++)
{
printf("%d ", nums[i]);
}
return 0;
}
思路3：双指针之快慢指针
两个指针指向数组：src和des，src遍历数组来寻找与val不同的元素，若src遇到与val相同的，则指向下一个；des从下标0开始，由于src位置始终大于等于des，因此将src指向的不同于val的元素直接赋值给des指向的位置，遍历完后，des之前的元素全是与val不同的了，因此实现了删除的目的
int removeElement(int *nums, int numsSize, int val)
{
int des = 0, src = 0;
while (src < numsSize)
{
if (nums[src] == val)
{
src++;
}
else
{
nums[des] = nums[src];
src++;
des++;
}
}
return des;
}
4. 删除有序数组中的重复项
本质就是去重（一般的，去重算法要求数组是有序的，不然效率很低）
双指针法：
int removeDuplicates(int* nums, int numsSize){
int slow = 0;
int quick = 0;
while(quick<numsSize){
if(nums[quick]==nums[slow]){
quick++;
}
else{
slow++;
nums[slow] = nums[quick];
}
}
return slow+1;
}
5.合并两个有序数组
创建临时数组：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int i=0,j=0,k=0;
int* temp = (int*)malloc(sizeof(int)*(m+n)); //创建新数组
/* 每次都取两数组中较小值放入新表 */
while(i<m && j<n) {
if(nums1[i]<=nums2[j])
temp[k++] = nums1[i++];
else
temp[k++] = nums2[j++];
}
/* 若有剩余未遍历的数组元素，说明都不比原来的值小，因此整体放入数组尾部 */
while(i<m)
temp[k++] = nums1[i++];
while(j<n)
temp[k++] = nums2[j++];
/* 最后一步将新数组元素逐个放入nums1数组中，交差完事 */
for(int c=0; c<m+n; c++) {
nums1[c] = temp[c];
}
}
6.检查两个字符串数组是否相等
本题的关键即是考虑如何将两个字符串拼接成一个字符串的问题
而数组的本质即是一个指针，而数组里装的字符串，那么我们在对字符串处理的时候，又嵌套了一层指针，因此这是一个二级指针
而二级指针，一个指向每个字符串的首元素，而另一个则是对其中的字符串做处理
char * join(char ** word, int wordSize) {
char *str = (char *)malloc(sizeof(char) * wordSize * MAX_STR_LEN + 1);
int pos = 0;
for (int i = 0; i < wordSize; i++) {
pos += sprintf(str + pos, "%s", word[i]);
}
return str;
}
bool arrayStringsAreEqual(char ** word1, int word1Size, char ** word2, int word2Size) {
char *str1 = join(word1, word1Size);
char *str2 = join(word2, word2Size);
bool ret = strcmp(str1, str2) == 0;
free(str1);
free(str2);
return ret;
}
7.最大重复子字符串
思路：kmp算法
链表
1.移除单链表的元素
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
//如果这个单链表为空
if(head==NULL){
return NULL;
}
struct ListNode* cur=head; //用于指向原链表的指针
struct ListNode* newhead=NULL; //用于存头指针地址
struct ListNode* tail=NULL; //用于尾插（尾指针）（新链表）
while(cur!=NULL){
if(cur->val!=val){
//如果不等于val，就把该结点尾插入新链表中
//如果新链表为空的尾插记得单独处理
if(tail==NULL){
newhead=tail=cur;
}
else{
tail->next=cur;
tail=tail->next;
}
cur=cur->next;
}
else{
//相等的情况要删除这个结点（记得保存下一个）
struct ListNode* nextnode=cur->next;
free(cur);
cur=nextnode;
}
}
if(tail){
tail->next=NULL;
}
return newhead;
}
2.合并两个有序链表
思路：和第七题的方法相似，这里取两个链表中小的数据来尾插
开始时，开始给一个head和一个tail置空（来操作新链表），那么对于原来的链表，即用list1和list2来指向它们的头节点；当任意的一个链表全部被插入到新链表中后，那么另一个链表的剩余部分即可直接链接入新链表后；还有一个点需要考虑的是，如果有一个链表为空，那么合并之后的链表就是另一个链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode* head=NULL;
struct ListNode* tail=NULL;
//考虑链表为空的情况
if(list1==NULL){
return list2;
}
if(list2==NULL){
return list1;
}
while(list1&&list2){
if((list1->val)<(list2->val)){
if(tail==NULL){
head=tail=list1;
}
else{
tail->next=list1;
tail=tail->next;
}
list1=list1->next;
}
else{
if(tail==NULL){
head=tail=list2;
}
else{
tail->next=list2;
tail=tail->next;
}
list2=list2->next;
}
}
if(list1){
tail->next=list1;
}
if(list2){
tail->next=list2;
}
return head;
}
如果有一个带哨兵位的头节点，那么就不用再判断头节点为空的情况了，只需要作尾插即可
(带哨兵位的头结点，在尾插的时候比较方便)
3.反转链表
思路，一般的，我们同样能使用尾插的思路，从尾结点开始，一个一个的尾插入新的链表之中，这里我们采用一种，新的思路：修改每个结点间指针的指向位置，让每个结点的next，指向它的前一个结点，那么首结点的next，即指向NULL
有了这个思路，我们就可以创建指针了，首先需要n1和n2指向两个结点，修改它们间的指针指向关系；然后我们，当修改next域之后，我们就无法找到下一个待修改next的指针了，因此还需要第三个指针用于储存next域（指向下一个待修改的结点）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
//对空表单独处理
if(head==NULL){
return NULL;
}
struct ListNode* n1=NULL;
struct ListNode* n2=head;
struct ListNode* n3=head->next;
while(n2){
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
n3=n3->next;
}
return n1;
}
4.链表的中间结点
要求：只能遍历一遍
思路：快慢指针
分析：定义一个slow和fast指针指向开始位置，由于两个指针移动速度差为2倍，因此在fast指向最后一个结点时，slow指针刚好指向中间结点；注意：本题需要考虑结点数是奇数个还是偶数个（指针移动的结束条件不同）
注：偶数个结点找后一个
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* fast;
struct ListNode* slow;
fast=slow=head;
//涉及到奇数个和偶数个结点间的差异
while(fast && fast->next){
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
5.链表中倒数第k个结点
思路：快慢指针法
由于要找到倒数第k个结点，我们知道倒数第k个结点和倒数第一个结点间差k-1个结点，因此我们同样的可以定义两个指针，slow指针指向头节点，而fast指针移动k-1步，然后再让两指针同时移动，当fast指向尾结点时，slow指向的即是倒数第k个结点/或者是让指针移动k步
如果k的值大于链表的结点个数，那么倒数第k个返回NULL
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param pListHead ListNode类
* @param k int整型
* @return ListNode类
*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
struct ListNode* fast;
struct ListNode* slow;
fast=slow=pListHead;
//移动k步
for(int i=0;i<k;i++){
//链表可能没有k步长
if(fast==NULL){
return NULL;
}
fast=fast->next;
}
while(fast){
fast=fast->next;
slow=slow->next;
}
return slow;
}
6.链表分割
思路：创建两个链表，将值小于x的尾插入一个链表，将值大于x的尾插入第二个链表，最后将两个链表合并起来即可
这道题我们采用带哨兵位的头节点，方便处理：①对空表的插入 ②防止链表的值都大于或者小于值x导致的某个链表为空的情况（对空指针的问题是一个很好的解决方案）
因此对于我们创建了两个新的链表，每个链表分别需要一个指针来保存其头节点的位置，一个指针负责移动，对链表进行操作
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* lessHead;
struct ListNode* lessTail;
struct ListNode* greaterHead;
struct ListNode* greaterTail;
//创建带哨兵位的头结点
lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur=pHead;
while(cur)
{
if(cur->val<x){
lessTail->next=cur;
lessTail=lessTail->next;
}
else{
greaterTail->next=cur;
greaterTail=greaterTail->next;
}
cur=cur->next;
}
//合并
lessTail->next=greaterHead->next;
//将尾结点的next域置空
greaterTail->next=NULL;
pHead =lessHead->next;
free(lessHead);
free(greaterHead);
return pHead;
}
};
总结：使用尾插法时，本质是改变当前结点的next域，让下一结点作为这个结点的下一个结点，然而在最后，我们没有修改最后插入结点的next域，因此可能会引起一些问题，所以在使用尾插法时要记得考虑这一点，将最后插入的结点的next域置空
7.链表的回文结构
思路1：
将链表反转与原链表作比较；空间复杂度为O(n)
思路2：
反转后半段，与前半段作比较(这里就要用到之前实现过的：【找到中间结点】、【反转链表】)的函数
对于偶数个：可以直接分成两段作比较；而对于奇数个：（画图很显然）——指向空就结束
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList
{
//反转链表
struct ListNode *reverseList(struct ListNode *head)
{
//对空表单独处理
if (head == NULL)
{
return NULL;
}
struct ListNode *n1 = NULL;
struct ListNode *n2 = head;
struct ListNode *n3 = head->next;
while (n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
n3 = n3->next;
}
return n1;
}
//找到链表中间结点
struct ListNode *middleNode(struct ListNode *head)
{
struct ListNode *fast;
struct ListNode *slow;
fast = slow = head;
//涉及到奇数个和偶数个结点间的差异
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
public:
bool chkPalindrome(ListNode *A)
{
struct ListNode *mid = middleNode(A);
struct ListNode *rhead = reverseList(mid);
//中间结点前的部分与中间结点后反转后的部分作比较
while (A && rhead)
{
if (A->val != rhead->val)
{
return false;
}
A = A->next;
rhead = rhead->next;
}
return true;
}
};
8.相交链表
大思路：
结点相交——同一个结点——同一个地址
思路1：
尾结点地址相同则相交：无法找到相交位置；但是使用此方法可以直接判断出不相交的情况！
思路2：
两个链表中，每个结点地址互相比较 时间复杂度为O(n^2)
思路3：
如果两个链表一样长，那么只用比较对应位置是否相等即可，时间复杂度为O(n)
注意：本题不能用逆置的思想，因为每个结点只能有一个next域
那么怎么要它们一样长呢？——仍然采用快慢指针法
对于两个链表有长有短，那么我们通过遍历可以得到两个链表间的长度关系，让长的链表先走差距步，那么此时，两个指针指向的起始位置之后的长度即相等了
curA和curB指针分别指向这两个链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* curA=headA;
struct ListNode* curB=headB;
//代表A、B链表的长度
int lenA=0;
int lenB=0;
//比较尾结点地址可直接排除不相交情况，因此这里寻找尾结点
while(curA->next){
lenA++;
curA=curA->next;
}
while(curB->next){
lenB++;
curB=curB->next;
}
//尾结点不相等则不相交
if(curA!=curB){
return NULL;
}
//相交：找相交位置
//长度的差距
int gap=abs(lenA-lenB);
//另一种思路：先假设长短，再通过if语句修正
struct ListNode* longList=headA;
struct ListNode* shortList=headB;
if(lenA<lenB){
longList=headB;
shortList=headA;
//此时就longList一定代表长链表，shortList一定代表短链表，就不用区分AB了
}
//移动差距步gap
for(int i=0;i<gap;i++){
longList=longList->next;
}
//再逐个比较是否相等，相等的位置即是相交位置起点
while(longList!=shortList){
longList=longList->next;
shortList=shortList->next;
}
return longList;
}
9.环形链表
思路：快慢指针
假设快指针移动速度是慢指针的两倍，如果不带环，那么最终慢指针永远追不上快指针，而如果带环，那么快指针慢指针都进入环后，相当于是一个追及问题了，最后总有一时，使得快慢指针在同一位置，说明带环
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode* slow=head;
struct ListNode* fast=head;
//奇数个偶数个结点
while(fast&&fast->next){ //while的停止条件是针对不带环的情况
slow=slow->next;
fast=fast->next->next;
if(slow==fast){
return true;
}
}
return false;
}
【扩展问题】
1.为什么快指针每次走两步，慢指针走一步可以追上？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。 此时，两个指针每移动一次，之间的距离就缩小一步（fast比slow多走一步），不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇（一圈之内即可以追上）
2.为什么slow一次走一步，fast一次走两步，而fast一次走3步，走4步，…n步行吗？
假设slow每次1步，fast每次走3步。当slow进环后，假设fast和slow之间间隔距离是N，每追击一次fast和slow之间的距离缩小2；因此如果N是偶数可以直接追上，若N是奇数则会在最后不会恰好相遇，而是被反超，开启了新的一轮追击；设C代表环的周长，那么fast和slow之间的距离变成了C-1，再次追击根据时，若C-1是偶数，则可以追上，而C-1是奇数，那么追完后仍然会出现与第一相同情况的反超问题，永远追不上！
因此：相对速度差1步一定能追上，而其它情况不一定能追上
10.环形链表 II
思路1：
【结论】：一个指针head从首结点开始，另一个指针meet从相遇位置开始，一次向后移动，meet和head的相遇位置即是入口点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast&&fast->next){
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
struct ListNode* meet=slow;
//让meet和head移动，相交位置即是入口点
while(head!=meet)
{
head=head->next;
meet=meet->next;
}
return meet;
}
}
return NULL;
}
【证明结论】：
核心关系：快指针走的路程一定是慢指针的路程的二倍
思路2：
沿用【14.相交链表】的函数，由于要找两个链表的入口点，不妨将环形链表看成一个链表，而未形成环的部分看作另一个链表，将利用这个函数找到这两个链表的相交位置即是入口点
由于存在环形链表，我们可以将环形链表的meet结点的下一结点作为头节点，meet结点作为尾结点，将这个环形链表“断开”
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode *slow = head;
struct ListNode *fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
struct ListNode *meet = slow;
struct ListNode *otherhead = meet->next;
meet->next = NULL;
return getIntersectionNode(head, otherhead); //使用判断相交链表的函数
}
}
return NULL;
}