复制带随机指针的链表最长连续递增序列数组的度写字符串需要的行数最短补全词

复制带随机指针的链表

来源：杭哥

138. 复制带随机指针的链表 - 力扣（LeetCode）

typedef struct Node Node;
Node* BuyNode(int x)
{Node* newnode = (Node*)malloc(sizeof(Node));newnode->val=x;newnode->next=NULL;newnode->random=NULL;return newnode;
}
struct Node* copyRandomList(struct Node* head) 
{if (head==NULL){return NULL;}Node* newnode=NULL;Node* cur=head;Node* newhead=BuyNode(cur->val);Node* cur2=newhead;cur=cur->next;while(cur!=NULL){newnode=BuyNode(cur->val);cur2->next=newnode;cur2=newnode;cur=cur->next;}Node* now1=head;Node* now2=newhead;cur=head;cur2=newhead;while(now1!=NULL){if (now1->random==NULL){now2->random=NULL;}else{cur=head;cur2=newhead;while(cur!=NULL){if (now1->random==cur){now2->random=cur2;}cur=cur->next;cur2=cur2->next;}}now1=now1->next;now2=now2->next;}   return newhead;
}

typedef struct Node Node;
Node* BuyNode(int x)
{Node* newnode = (Node*)malloc(sizeof(Node));newnode->val=x;newnode->random=NULL;newnode->next=NULL;return newnode;
}
struct Node* copyRandomList(struct Node* head) 
{if (head==NULL){return NULL;}Node* newnode=NULL;Node* prev=head;Node* cur=head->next;while(1){newnode = BuyNode(prev->val);prev->next=newnode;newnode->next=cur;if (cur==NULL){break;}prev=cur; cur=cur->next;}cur=head->next;prev=head;while(1){if (prev->random==NULL){cur->random=NULL;}else{cur->random=prev->random->next;}prev=prev->next->next;if (prev==NULL){break;}cur=cur->next->next;}Node* newhead=head->next;prev=head;cur=head->next;Node* fur=NULL;while(1){fur=cur->next;prev->next=fur;if (fur==NULL){break;}cur->next=fur->next;prev=fur;cur=cur->next;}return newhead;    
}

我想说：

1. 一种方法的话是时间复杂度为o(N^2)的方法，第二种方法的话是时间复杂度为O(N)的方法。

2. 第二种方法主要就是说，相当于在原先链表的基础之上，先给他插入一些新的拷贝节点，最主要关心的问题就是拷贝节点的random指针指向的位置，可以发现一个规律：拷贝节点的random指针指向的拷贝节点应该是其原先节点的random指针指向的节点的next指向的节点。

---

最长连续递增序列

来源：自己LeetCode刷题

674. 最长连续递增序列 - 力扣（LeetCode）

int findLengthOfLCIS(int* nums, int numsSize)
{int left=0;int right=1;int ans=1;while(right<numsSize){while (right<numsSize && nums[right-1]<nums[right]){right++;}ans=ans>(right-left)?ans:(right-left);left=right;right++;}return ans;
}

我想说：

1. 蛮简单的，双指针。

---

数组的度

来源：自己LeetCode刷题

697. 数组的度 - 力扣（LeetCode）

#include <stdlib.h>
int cmp(const void* e1, const void* e2)
{return *((int*)e1)-*((int*)e2);
}
int findgap(int x,int *nums, int numsSize)
{int max=0;int min=numsSize;int l=-1;int r=-1;for (int i=0;i<numsSize;i++){if (nums[i]==x){min=min<i?min:i;max=max>i?max:i;}}return max-min+1;
}
int findShortestSubArray(int* nums, int numsSize)
{if (numsSize==1){return 1;}int obj=0;int ans=0;int arr[numsSize];for (int i=0;i<numsSize;i++){arr[i]=nums[i];}qsort(arr,numsSize,4,cmp);int left=0;int right=1;while(right<numsSize){while (right < numsSize  &&  arr[right]==arr[right-1]){right++;}if (right-left>ans){ans=right-left;obj=arr[left];}else if (ans==right-left){int obj1=arr[left];int gap1=findgap(obj1,nums,numsSize);int gap=findgap(obj,nums,numsSize);if (gap1<gap){obj=obj1;}}left=right;right++;}return findgap(obj,nums,numsSize);
}

我想说：

1. 很遗憾，现在只会暴力解法。

---

写字符串需要的行数

来源：自己LeetCode刷题

806. 写字符串需要的行数 - 力扣（LeetCode）

#include <string.h>
int* numberOfLines(int* widths, int widthsSize, char * s, int* returnSize)
{int* p = (int*)malloc(sizeof(int)*2);int sz=strlen(s);int row=0;int sum=0;for (int i=0;i<sz;i++){int num=s[i]-97;if (sum+widths[num]>100){row++;sum=0;i--;}else{sum+=widths[num];}}p[0]=row+1;p[1]=sum;*returnSize=2;return p;
}

我想说：

1. 字符的话在计算机眼里本质上也是一个整型。

---

最短补全词

来源：自己LeetCode刷题

748. 最短补全词 - 力扣（LeetCode）

int cmp(const void* e1, const void* e2)
{return tolower(*((char*)e1))-tolower(*((char*)e2));
}
char * shortestCompletingWord(char * licensePlate, char ** words, int wordsSize)
{int i=0;char lp[10]={0};int sz=0;int len=1010;char* ans=NULL;while(licensePlate[i]!='\0'){if (isalpha(licensePlate[i])){lp[sz++]=licensePlate[i];}i++;}qsort(lp,sz,1,cmp);for (i=0;i<wordsSize;i++){int sz1=strlen(words[i]);char str[sz1+1];strcpy(str,words[i]);qsort(str,sz1,1,cmp);int k=0;int j=0;while(k<sz && j<sz1){while (j<sz1 && tolower(lp[k])!=tolower(str[j])){j++;}if (j==sz1){break;}k++;j++;}if (k==sz){if (sz1<len){len=sz1;ans=words[i];}}}return ans;
}

我想说：

1. 依托于排序解题，也算是暴力解法吧。

---