英雄九日集训第三天
2022/4/18(链表反转,二分)
题目描述:
剑指 Offer 06. 从尾到头打印链表 - 力扣(LeetCode) (leetcode-cn.com)
我的题解:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ /*** Note: The returned array must be malloced, assume caller calls free().*/ int* reversePrint(struct ListNode* head, int* returnSize){if(!head){*returnSize=0;return NULL;}struct ListNode* Node=head;//指向头指针int len=1;//记录链表长度while(Node=Node->next){len++;}//最后是null则输出int*temp=(int*)calloc(len,sizeof(int));//申请一个有len长度空间的int数组if(!temp){return NULL;}Node=head;for(int i=1;i<=len;i++)//从头结点到尾遍历一遍{temp[len-i]=Node->val;Node=Node->next;}*returnSize=len;return temp; }
我的思路:
/*链表的反转采用的是一样的套路: 1.用while(prone=prone->next)计算链表长度 2.用calloc(len,sizeof(typedefy))创建一个相应的长度数组 3.将链表从头到尾放入calloc申请的空间中注意的是申请的数组记得从尾部到头部放入!!
题目描述:
33. 搜索旋转排序数组 - 力扣(LeetCode) (leetcode-cn.com)
我的题解:
int binerySearch(int *nums,int low,int high,int key) { while(low<=high){int mid=low+(high-low)/2; if(nums[mid]==key){return mid;}else if(nums[mid]>key){high=mid-1;}else{low=mid+1;} }return -1; }//二分查找的方法 int search(int* nums, int numsSize, int target){// //暴力解法// int i;// for(i=0;i<numsSize;i++){// if(nums[i]==target){// return i;// } // }// return -1;//二分查找int i=1;while(i<numsSize&&nums[i]>nums[i-1])//寻找反转点{i++;//找到对应的旋转点}int rest1=binerySearch(nums,0,i-1,target);//对左边的序列进行二分查找int rest2=binerySearch(nums,i,numsSize-1,target);//对于右变得序列进行二分查找return rest1>=rest2?rest1:rest2;//若相等只可能两边等于-1依旧可以输出-1 }
我的思路:
/*第一种方法:暴力解法:遍历出所有的数组然后就是找出相应的字符输出第二种方法:二分查找法:找出找出反转之后的字符,因为反转了但是任然有两段是有序的数组所以,分开两分查找二分查找思想:while(直到左指针大于右指针跳出循环(注意相等的时候不要跳出这是因为若左指针等于右指针则两边算完的平均值等于mid仍然可以判断与target是否相等)){1.mid=left+(right-left)/2;if(nums[mid]==target){if(nums[mid]>target){}elseif{}}}return -1;//都不符合的情况 */
题目描述:
81. 搜索旋转排序数组 II - 力扣(LeetCode) (leetcode-cn.com)
我的题解:
bool search(int* nums, int numsSize, int target){ //不完全排序的二分查找if(numsSize==0){return false;}if(numsSize==1){return nums[0]==target;}//设置两个指头和指向尾巴的指针int r=numsSize-1;int l=0;while(l<=r){int mid=l+(r-l)/2;if(nums[mid]==target){return true;}//列出特殊情况就是左边的值和右边的值都和中间值相等if(nums[r]==nums[mid]&&nums[l]==nums[mid]){//这种情况下直接左指针左移右指针右移即可l++;r--;}else if(nums[l]<=nums[mid]){//如果左侧有序if(nums[l]<=target&&nums[mid]>=target){r=mid-1;}else{l=mid+1;}}else{//右边有序的情况if(nums[r]>=target&&target>=nums[mid]){l=mid+1;}else{r=mid-1;}}} return false; }
思路:
//相比于上一个含有顺序排序的二分查找就多个一个判断就是有可能左右两端的数字都和中见得数据相等从而导致了两边要同时++和--来去除多余的量
水几道题实在是hold不住了~
153. 寻找旋转排序数组中的最小值 int findMin(int* nums, int numsSize){ //我累了水题冲冲冲int i;int min=10000;for(i=0;i<numsSize;i++){if(nums[i]<min){min=nums[i];}}return min; }
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? / int climbStairs(int n){if(n==1){return 1;}if(n==2){return 2;}//return climbStairs(n-1)+climbStairs(n-2);超时int a=1,b=2,temp;for(int i=3;i<=n;i++){temp=a;a=b;//走到第二层的揭发b=temp+b;//加起来为第三层的解法后面一样} }
英雄九日集训第三天
2022/4/18(链表反转,二分)
题目描述:
剑指 Offer 06. 从尾到头打印链表 - 力扣(LeetCode) (leetcode-cn.com)
我的题解:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ /*** Note: The returned array must be malloced, assume caller calls free().*/ int* reversePrint(struct ListNode* head, int* returnSize){if(!head){*returnSize=0;return NULL;}struct ListNode* Node=head;//指向头指针int len=1;//记录链表长度while(Node=Node->next){len++;}//最后是null则输出int*temp=(int*)calloc(len,sizeof(int));//申请一个有len长度空间的int数组if(!temp){return NULL;}Node=head;for(int i=1;i<=len;i++)//从头结点到尾遍历一遍{temp[len-i]=Node->val;Node=Node->next;}*returnSize=len;return temp; }
我的思路:
/*链表的反转采用的是一样的套路: 1.用while(prone=prone->next)计算链表长度 2.用calloc(len,sizeof(typedefy))创建一个相应的长度数组 3.将链表从头到尾放入calloc申请的空间中注意的是申请的数组记得从尾部到头部放入!!
题目描述:
33. 搜索旋转排序数组 - 力扣(LeetCode) (leetcode-cn.com)
我的题解:
int binerySearch(int *nums,int low,int high,int key) { while(low<=high){int mid=low+(high-low)/2; if(nums[mid]==key){return mid;}else if(nums[mid]>key){high=mid-1;}else{low=mid+1;} }return -1; }//二分查找的方法 int search(int* nums, int numsSize, int target){// //暴力解法// int i;// for(i=0;i<numsSize;i++){// if(nums[i]==target){// return i;// } // }// return -1;//二分查找int i=1;while(i<numsSize&&nums[i]>nums[i-1])//寻找反转点{i++;//找到对应的旋转点}int rest1=binerySearch(nums,0,i-1,target);//对左边的序列进行二分查找int rest2=binerySearch(nums,i,numsSize-1,target);//对于右变得序列进行二分查找return rest1>=rest2?rest1:rest2;//若相等只可能两边等于-1依旧可以输出-1 }
我的思路:
/*第一种方法:暴力解法:遍历出所有的数组然后就是找出相应的字符输出第二种方法:二分查找法:找出找出反转之后的字符,因为反转了但是任然有两段是有序的数组所以,分开两分查找二分查找思想:while(直到左指针大于右指针跳出循环(注意相等的时候不要跳出这是因为若左指针等于右指针则两边算完的平均值等于mid仍然可以判断与target是否相等)){1.mid=left+(right-left)/2;if(nums[mid]==target){if(nums[mid]>target){}elseif{}}}return -1;//都不符合的情况 */
题目描述:
81. 搜索旋转排序数组 II - 力扣(LeetCode) (leetcode-cn.com)
我的题解:
bool search(int* nums, int numsSize, int target){ //不完全排序的二分查找if(numsSize==0){return false;}if(numsSize==1){return nums[0]==target;}//设置两个指头和指向尾巴的指针int r=numsSize-1;int l=0;while(l<=r){int mid=l+(r-l)/2;if(nums[mid]==target){return true;}//列出特殊情况就是左边的值和右边的值都和中间值相等if(nums[r]==nums[mid]&&nums[l]==nums[mid]){//这种情况下直接左指针左移右指针右移即可l++;r--;}else if(nums[l]<=nums[mid]){//如果左侧有序if(nums[l]<=target&&nums[mid]>=target){r=mid-1;}else{l=mid+1;}}else{//右边有序的情况if(nums[r]>=target&&target>=nums[mid]){l=mid+1;}else{r=mid-1;}}} return false; }
思路:
//相比于上一个含有顺序排序的二分查找就多个一个判断就是有可能左右两端的数字都和中见得数据相等从而导致了两边要同时++和--来去除多余的量
水几道题实在是hold不住了~
153. 寻找旋转排序数组中的最小值 int findMin(int* nums, int numsSize){ //我累了水题冲冲冲int i;int min=10000;for(i=0;i<numsSize;i++){if(nums[i]<min){min=nums[i];}}return min; }
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? / int climbStairs(int n){if(n==1){return 1;}if(n==2){return 2;}//return climbStairs(n-1)+climbStairs(n-2);超时int a=1,b=2,temp;for(int i=3;i<=n;i++){temp=a;a=b;//走到第二层的揭发b=temp+b;//加起来为第三层的解法后面一样} }