一.算法效率
1.用处：判断算法的好坏，好的算法应该是高效的
2算法效率取决于时间复杂度和空间复杂度
<1>时间复杂度
1.1概念：算法中基本操作的执行次数就是算法的时间复杂度
1.2表示：大O的渐进表示法，例如O(N)
1.3计算：以最坏运行情况算出可能需要执行的最多操作数的表达式，只保留最高阶项，并舍弃 其系数
1.4例子说明
1.5常见的时间复杂度
| O(1) | 常数阶 | |
| O(N) | 线性阶 | |
| O(N^2) | 平方阶 | |
| O(logN) | 对数阶 | 例如：二分查找的空间复杂度为O(logN) |
| O(nlogn) | nlogn阶 | |
| O(2^n) | 指数阶 | 例如：使用递归法计算斐波那契数,时间复杂度为O(2^n) 当时间复杂度为指数阶时，说明该方法不适用与解题，效率太低 |
<2>空间复杂度
2.1概念：是对运行过程中额外开辟空间大小的度量
2.2表示：大O的渐进表示法，例如O(1)
2.3计算：数在实现程序的过程中共额外开辟了多少个变量，保留最高阶项，并舍弃其系数
2.4例子说明：
2.5常见的空间复杂度：
| O(1) | 开辟有限的变量 |
| O(N) | 新开辟了一个数组 |
| O(N^2) |
二.典型例题
1.旋转数组
1.1题目介绍：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
. - 力扣（LeetCode）
1.2解法
<1>逐个旋转
1.1思路讲解：将尾部的数据拿下来，再将其他元素向后挪一位，最后将拿下来的数据放在头 部，重复操作，直至完成轮转(注意：当传入的k大于数组大小时会进行一些轮 回，可以先将k%数组大小，保证k<数组大小，提高效率；在进行数组往后操 作时需要从后往前操作)
1.2时间复杂度：O(N^2) 空间复杂度:O(1)
1.3代码实现
void rotate(int* nums, int numsSize, int k) {
k%=numsSize;//避免重复操作
int tmp=0;
while(k--)
{
tmp=nums[numsSize-1];
for(int i=numsSize-1;i>0;i--)
{
nums[i]=nums[i-1];
}
nums[0]=tmp;
}
}<2>分三段逆置
2.1思路讲解：封装一个函数用于将数组逆置，在进行轮转的位置将原数组视为两部分分别逆 置，最后将整个数组逆置即可(注意当传入的k大于数组大小时会进行一些轮 回，可以先将k%数组大小，保证k<数组大小，提高效率)
2.2时间复杂度：O(N) 空间复杂度:O(1)
2.3代码实现
//数组逆置
void reverse(int* nums,int left,int right)
{
int tmp=0;
while(left<right)
{
tmp=nums[left];
nums[left]=nums[right];
nums[right]=tmp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k) {
k%=numsSize;//避免重复操作
reverse(nums,0,numsSize-k-1);
reverse(nums,numsSize-k,numsSize-1);
reverse(nums,0,numsSize-1);
}<3>创建一个新数组
3.1思路讲解：创建一个新数组，先按要轮转的位置将数据先后拷贝至新数组中，最后将新数 组的元素拷贝回原数组
3.2时间复杂度：O(N) 空间复杂度:O(N)
3.3代码实现
void rotate(int* nums, int numsSize, int k) {
k%=numsSize;//避免重复操作
int arr[]={0};
int i=0;
for(i=numsSize-k,j=0;i<numsSize;i++,j++)
{
arr[j]=nums[i];
}
for(i=0;i<numsSize-k;i++,j++)
{
arr[r]=nums[i];
}
for(i=0;i<numsSize;i++)
{
nums[i]=arr[i];
}
}2.找两个链表是否有公共节点，若有返回第一个公共节点的地址
2.1题目介绍：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始 节点。如果两个链表不存在相交节点，返回 null 。
. - 力扣（LeetCode）
2.2解法
<1>思路：1.判断是否两链表相交：看他们的尾结点的地址是否相同，若相同则相交
2.找出较长的链表与较短链表的差值，让长链表先走差值步，再让两链表同时走，当他 们指向的空间相同时，即是第一个公共节点处
<2>时间复杂度：O(N) 空间复杂度:O(1)
<3>代码实现
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
//判断是否有公共节点
ListNode* A=headA;
ListNode* B=headB;
int len1=0;
int len2=0;
while(A)
{
A=A->next;
len1++;
}
while(B)
{
B=B->next;
len2++;
}
if(A!=B)
{
return NULL;
}
else
{
int gap=abs(len1-len2);
ListNode* greatlist=headA;
ListNode* shortlist=headB;
if(len1<len2)
{
greatlist=headB;
shortlist=headA;
}
//先让长链表走直至弥补两链表的差距
while(gap--)
{
greatlist=greatlist->next;
}
while(greatlist && shortlist)
{
if(greatlist==shortlist && greatlist->val==shortlist->val)
{
return greatlist;
}
greatlist=greatlist->next;
shortlist=shortlist->next;
}
return NULL;
}
}3.判断链表是否带环
<1>题目介绍：给你一个链表的头节点 head ，判断链表中是否有环。
. - 力扣（LeetCode）
<2>思路:定义slow，fast两个指针，slow走一步，fast走两步，若在某时刻slow=fast，则说明链表 中带环
<3>方法证明
<4>代码实现
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
ListNode* fast=head;
ListNode* slow=head;
while(fast!=NULL)
{
slow=slow->next;
if(fast->next==NULL)
{
return false;
}
else
{
fast=fast->next->next;
}
if(slow==fast)
{
return true;
}
}
return false;
}<5>拓展：Q：当fast=3*slow时，可以用来判断是否带环吗？
A：可以
Q：当fast=4*slow呢？
A：可参考上述分析，这里就不在一一证明了
4.返回带环链表进入环时的第一个节点地址
<1>题目介绍：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
. - 力扣（LeetCode）
<2>思路：先判断是否为带环链表，记录slow和fast相遇时的位置，让cur指向头节点，meet位相 遇的位置，让meet和cur同时开始走，当meet和cur相等时，cur刚好位于入环的第一个 节点处
<3>方法证明：
<4>代码实现：
typedef struct ListNode ListNode;
ListNode* hasCycle(ListNode *head) {
ListNode* fast=head;
ListNode* slow=head;
while(fast!=NULL)
{
slow=slow->next;
if(fast->next==NULL)
{
return NULL;
}
else
{
fast=fast->next->next;
}
if(slow==fast)
{
return slow;
}
}
return NULL;
}
struct ListNode *detectCycle(struct ListNode *head) {
ListNode* cur=head;
ListNode* meet=hasCycle(head);
if(meet==NULL)
{
return NULL;
}
else
{
while(cur)
{
if(cur==meet)
{
return cur;
}
cur=cur->next;
meet=meet->next;
}
return NULL;
}
}5.随机链表的复制
<1>题目介绍：
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。
. - 力扣（LeetCode）
<2>思路：先开辟新节点，将其连在原链表的每个节点后面，再对新节点的random进行赋值，最后将原链表与拷贝链表分离
<3>代码实现：
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
if(head==NULL)
{
return NULL;
}
Node* cur=head;
//遍历原链表，复制其内容并插在原节点的后面
while(cur)
{
Node* copy=(Node*)malloc(sizeof(Node));
copy->val=cur->val;
copy->next=cur->next;
copy->random=NULL;
cur->next=copy;
cur=copy->next;
}
//再遍历链表，设置随机指针
cur=head;
while(cur)
{
Node* copy=cur->next;
if(cur->random)
{
copy->random=cur->random->next;
}
cur=copy->next;
}
//将复制的链表和原链表分隔开
Node* newhead=NULL,*prev,*next;
cur=head;
while(cur)
{
next=cur->next->next;
if(newhead==NULL)
{
newhead=cur->next;
prev=cur->next;
}
else
{
prev->next=cur->next;
prev=cur->next;
}
cur->next=next;
cur=next;
}
return newhead;
}
