4月22日力扣练习

第一题：力扣24题 链接https://leetcode.cn/problems/swap-nodes-in-pairs/

代码： 

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */struct ListNode* swapPairs(struct ListNode* head) { struct ListNode* current=head; struct ListNode* change; if(current!=NULL&&current->next!=NULL){ struct ListNode* change=current->next; current->next=change->next; change->next=current; head=change;  }; while(current!=NULL&&current->next!=NULL&&current->next->next!=NULL){  struct ListNode* change=current->next;current->next=change->next; change->next=current->next->next; current->next->next=change; current=current->next->next; } return head;}

解题思路：

        这题比较简单，在这里只略微提及一些需要注意的点。

        简单介绍一下逻辑：current节点用于链表遍历，交换的两个节点为current节点的后一位和后两位节点，change节点刚开始为current节点的后一位，交换后为current节点的后两位。

        为了地址交换安全和链表逻辑清晰，我们每一次while循环创建一次change节点，并将current->next赋给它。交换后current向后遍历两位，跳过已经交换完成的节点。

        由于单链表的单向性，我们在交换头节点以外的节点时，需要用到三个节点，因此在while循环遍历时，要注意判断current节点以及后两个节点均不为空。

        刚刚提到了头节点交换，由于主循环交换的是current的后两位节点，所以我们在最开始要先对头节点的交换进行特别处理，并更新要返回的头节点位置为交换后的节点。

考察点：

1. 链表的遍历，元素交换。
2. 链表地址赋值

第二题：力扣19题https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

 代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */struct ListNode* removeNthFromEnd(struct ListNode* head, int n) { struct ListNode* current=head; int count=0; while(current!=NULL){ current=current->next; count++; } if(n==count){ head=head->next; return head; } current=head; for(int i=0;inext; } if(current->next!=NULL){current->next=current->next->next;}; return head;}

解题思路： 

        我们可以用两次遍历解决，第一次遍历统计节点个数count，将删除倒数第n个转换为删除正数第count-n个。

        同时我们需要对删除节点的情况进行一些特判，如删除头节点的情况，我们可以用以下办法：

if(n==count){ head=head->next; return head; }

考察点：

1. 链表节点删除

第三题：力扣33https://leetcode.cn/problems/search-in-rotated-sorted-array/description/

 代码：

class Solution {public: int search(vector& nums, int target) { int n=(int)nums.size(); if(!n){return -1;} if(n==1){return nums[0]==target?0:-1;} int left=0,right=n-1; int mid; while(left<=right){ mid=(left+right)/2; if(nums[mid]==target){ return mid; } if(nums[0] <= nums[mid]){ if(nums[0]<=target&&target<nums[mid]){  right=mid-1; } else{  left=mid+1; } } else{ if(target<=nums[n-1]&&nums[mid] < target){  left=mid+1; }else{  right=mid-1; } }  } return -1; }};

 解题思路：

        旋转后的数组特性：数组被分成两个有序部分，任意位置的元素至少有一半区间是有序的。

        使用二分查找来优化搜索过程：

        通过比较 nums[mid] 和 nums[left] 或 nums[right]，判断哪一部分是有序的

        根据 target 是否在有序区间内，缩小搜索范围

算法步骤：

1. 初始化：left = 0，right = len(nums) - 1

2. 二分查找

      如果 nums[mid] == target，直接返回 mid

      如果 nums[left] <= nums[mid]，说明左半部分有序：

      若 target 在 [nums[left], nums[mid]] 范围内，则 right = mid - 1

      否则 left = mid + 1

      否则右半部分有序：

      若 target 在 [nums[mid], nums[right]] 范围内，则 left = mid + 1

      否则 right = mid - 1

      未找到则返回 -1

考察点:

        1.二分时间复杂度优化

        2.边界处理，防止陷入死循环。

        3.数组中没有目标值时，异常返回处理。