本文主要是介绍【每日刷题】Day27，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【每日刷题】Day27
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 61. 旋转链表 - 力扣（LeetCode）
2. 字符串变形_牛客题霸_牛客网 (nowcoder.com)
3. 138. 随机链表的复制 - 力扣（LeetCode）
1. 61. 旋转链表 - 力扣（LeetCode）
//思路：这题实际上和189. 轮转数组 - 力扣（LeetCode）一样，将链表中的值存入数组后，将数组三段逆置得到旋转后的结果，再将数组中的值放回原链表。
typedef struct ListNode LN;
void Reverse(int* arr,int left,int right)//逆置函数
{
while(left<right)
{
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left++;
right--;
}
}
struct ListNode* rotateRight(struct ListNode* head, int k)
{
if(head==NULL)
{
return NULL;
}
if(head->next==NULL)
{
return head;
}
int arr[501] = {0};
LN* pmove = head;
LN* pmove1 = head;
int i = 0;
int j = 0;
int count = 0;
while(pmove)//将链表的值存入数组中
{
arr[i++] = pmove->val;
pmove = pmove->next;
count++;
}
k%=count;
Reverse(arr,i-k,i-1);//三段逆置得到旋转后的结果
Reverse(arr,0,i-1-k);
Reverse(arr,0,i-1);
while(pmove1)//再将数组中的值放回原链表
{
pmove1->val = arr[j++];
pmove1 = pmove1->next;
}
return head;
}
2. 字符串变形_牛客题霸_牛客网 (nowcoder.com)
//思路：先将整个字符串都逆置，然后遍历字符串，将大小写改变，每遍历完一个单词，将这个单词再逆置一次，然后进行下一次遍历。
void Reverse(char* s,int left,int right)
{
while(left<right)//逆置函数
{
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
char* trans(char* s, int n )
{
Reverse(s,0,n-1);//将整个字符串逆置
int i = 0;
int j = 0;
while(i<n)//遍历字符串
{
j = i;
while(j<n&&s[j]!=' ')//遍历每个单词，改变大小写，遇到' '说明当前单词遍历完毕
{
if(s[j]>='A'&&s[j]<='Z')
{
s[j]+=32;
}
else if(s[j]>='a'&&s[j]<='z')
{
s[j]-=32;
}
j++;
}
Reverse(s,i,j-1);//逆置该单词
i = j+1;// i走到j下一个位置处进行下一次遍历
}
return s;
}
3. 138. 随机链表的复制 - 力扣（LeetCode）
//这是之前 每日刷题Day23 中这题的优化解法，时间复杂度为O(N)。
//思路：在原链表后面插入节点，将节点与原链表相连接，先不处理random，画图理解
//将节点按照上图所示方法插入节点后，再来处理random，先看原链表的random
//再来看看节点的random应该如何处理
//仔细观察不难发现，节点的random其实就可以通过原链表前一个节点random的next找到（蓝色线），下面开始写代码
typedef struct Node SN;
struct Node* copyRandomList(struct Node* head)
{
if(!head)
{
return NULL;
}
SN* pmove = head;
SN* Sentry = (SN*)malloc(sizeof(SN));
while(pmove)//插入节点
{
SN* newnode = (SN*)malloc(sizeof(SN));
newnode->next = pmove->next;
newnode->val = pmove->val;
pmove->next = newnode;
pmove = newnode->next;
}
pmove = head;
while(pmove)//设置节点中random的指向与原链表保持一致
{
SN* newnode = pmove->next;
if(pmove->random==NULL)//这里需要考虑原链表random为NULL的情况，防止对空指针解引用
{
newnode->random = pmove->random;
}
else
{
newnode->random = pmove->random->next;
}
pmove = newnode->next;
}
pmove = head;
Sentry->next = head->next;
while(pmove)//将插入的节点提取出来，并恢复原链表
{
SN* cur = pmove->next;
SN* pmove1 = cur->next;
pmove->next = pmove1;
pmove = pmove->next;
if(pmove1)
{
cur->next = pmove1->next;
}
}
return Sentry->next;
}
这篇关于【每日刷题】Day27的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
