【代码随想录】2

数组篇

二分查找

int search(int* nums, int numsSize, int target) {
int left=0;
int right=numsSize-1;
while(left<=right)
{int mlddle=(left+right)/2;if(nums[mlddle]>target){right=mlddle-1;}else if(nums[mlddle]<target){left=mlddle+1;}else{return mlddle;}}
return -1;    
}

移除元素

int removeElement(int* nums, int numsSize, int val) {
int slow=0;for(int fast=0;fast<numsSize;fast++)
{if(nums[fast]!=val)
{nums[slow]=nums[fast];slow++;}}return slow;}

有序数组的平方

int* sortedSquares(int* nums, int numsSize, int* returnSize) {*returnSize=numsSize;int*arr=(int*)malloc(*returnSize*sizeof(int));if(arr==NULL){perror("malloc fail");}int k=numsSize-1;int i=0;int j=numsSize-1;while(i<=j){if(pow(nums[i],2)>pow(nums[j],2)){arr[k]=pow(nums[i],2);i++;k--;}else{arr[k]=pow(nums[j],2);j--;k--;}}return arr;free(arr);}

长度最小的数组

int minSubArrayLen(int target, int* nums, int numsSize) {
int i=0;
int min=INT_MAX;
int j=0;
int sum=0;
for(j=0;j<numsSize;j++)
{sum+=nums[j];
while(sum>=target)
{int result=j-i+1;
if(result<min)
{min=result;
}
sum-=nums[i];
i++;}}
return min==INT_MAX?0:min;
}

螺旋矩阵2

int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {*returnSize=n;*returnColumnSizes=(int*)malloc(sizeof(int)*n);int**ans=(int**)malloc(sizeof(int*)*n);int i;for( i=0;i<n;i++){ans[i]=(int*)malloc(sizeof(int)*n);(*returnColumnSizes)[i]=n;}int startx=0;int starty=0;int offset=1;int count=1;int mid=n/2;while(mid){int i=startx;int j=starty;for(j=starty;j<n-offset;j++)ans[i][j]=count++;for(i=startx;i<n-offset;i++)ans[i][j]=count++;for(;j>starty;j--)ans[i][j]=count++;for(;i>startx;i--)ans[i][j]=count++;mid--;startx++;starty++;;offset+=1;}if(n%2)ans[n/2][n/2]=count;return ans;
}

链表篇

移除链表元素
1.无哨兵位头结点

struct ListNode* removeElements(struct ListNode* head, int val) {
while(head!=NULL&&head->val==val)
{
head=head->next;}  
struct ListNode* cur=head;
while(cur!=NULL&&cur->next!=NULL)
{if(cur->next->val==val){cur->next=cur->next->next;}else{cur=cur->next;}
}
return head;}

2.有

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode*newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur=newnode;
cur->next=head;
while(cur->next!=NULL)
{if(cur->next->val==val)
cur->next=cur->next->next;
else
cur=cur->next;
}return newnode->next;}

翻转链表

struct ListNode* reverseList(struct ListNode* head) {if(head==NULL)return NULL;
struct ListNode*n1=NULL;
struct ListNode*n2=head;
struct ListNode*n3=n2->next;
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3!=NULL)
n3=n3->next;}  
return n1;  }

递归版

struct ListNode* reverse(struct ListNode*prev,struct ListNode*cur)
{
if(!cur)
return prev;
struct ListNode* tmp=cur->next;
cur->next=prev;return reverse(cur,tmp);}struct ListNode* reverseList(struct ListNode* head) {return reverse(NULL,head);
}

两两交换链表

struct ListNode* swapPairs(struct ListNode* head) {
struct ListNode* newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
if(head==NULL)
return NULL;
newnode->next=head;
struct ListNode*cur=newnode;
while(cur->next!=NULL&&cur->next->next!=NULL)
{struct ListNode*tmp1=cur->next;
struct ListNode*tmp2=cur->next->next->next;
cur->next=cur->next->next;
cur->next->next=tmp1;
tmp1->next=tmp2;
cur=cur->next->next;
}
return newnode->next;  
}

删除链表倒数第n个节点

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode*newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode*fast=newnode;
struct ListNode*slow=newnode;
newnode->next=head;
int k=n+1;
while(k)
{if(fast==NULL)
return NULL;fast=fast->next;k--;
}   
while(fast)
{fast=fast->next;
slow=slow->next;
}
slow->next=slow->next->next;return newnode->next;
}

环形链表2

struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *fast=head;
struct ListNode *slow=head;while(fast&&fast->next)
{fast=fast->next->next;
slow=slow->next;
if(slow==fast)
{struct ListNode *meet=slow;
while(meet!=head)
{meet=meet->next;
head=head->next;}
return meet;}
}
return NULL;
}