当前位置:网站首页>牛客刷题系列之进阶版(搜索旋转排序数组,链表内指定区间反转)
牛客刷题系列之进阶版(搜索旋转排序数组,链表内指定区间反转)
2022-07-30 18:59:00 【雪芙花】
很多小伙伴为了刷题发愁
今天为大家推荐一款刷题神奇哦:刷题面试神器牛客
各大互联网大厂面试真题。从基础到入阶乃至原理刨析类面试题 应有尽有,赶快来装备自己吧!助你面试稳操胜券,solo全场面试官
一:搜索旋转排序数组
1.题目
2.代码实现
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0;
int right =nums.size()-1;
int mid;
while(left<=right)
{
mid = (left+right)/2;
if(nums[0]>target)//当t在右边的数组时
{
if(nums[mid]>=nums[0]) //当mid左边时,需要将left=mid+1
nums[mid] = -10001;
}
else//当t在左边的数组时
{
if(nums[mid] < nums[0]) //当mid右边时,需要将right = mid-1;
nums[mid] = 10001;
}
if(nums[mid] > target)
right = mid-1;
else if(nums[mid] <target)
left = mid+1;
else
return mid;
}
return -1;
}
};
3.思路和注意事项
- 思路是模拟二分查找来实现的
- 普通的二分查找是
if(nums[mid] > target)
right = mid-1;
else if(nums[mid] <target)
left = mid+1;
else
return mid; - nums[mid] > target时, right = mid-1; 所以我们可以用 nums[mid] = 10001;来模拟 这种情况。
- 当我们找到在特殊情况下的right 要变成mid-1时,我们就可以用 nums[mid] = 10001;来模拟 这种情况。
- 具体的情况看代码注释(主要是看mid和t在哪一边)
二:链表内指定区间反转
1.题目
2.代码实现
/** * struct ListNode { * int val; * struct ListNode *next; * }; */
class Solution {
public:
/** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */
ListNode* reverseBetween(ListNode* head, int m, int n) {
// write code here
ListNode* res =new ListNode(0);
ListNode* cur = head;
ListNode* pre = res;
res->next= head;
for(int i=1;i<m;i++)
{
pre =cur;
cur =cur->next;
}
for(int i=m;i<n;i++)
{
ListNode* tem =cur->next;
cur->next = tem->next;
tem->next = pre->next;
pre->next = tem;
}
return res->next;;
}
};
3.思路和注意事项
主要思路就是一次一次的反转
- 需要注意的是要设虚拟头节点,以防头节点的改变的情况
ps
想和博主一样刷优质面试和算法题嘛,快来刷题面试神器牛客吧,期待与你在牛客相见
边栏推荐
- Fixed asset visualization intelligent management system
- CCNA-子网划分(VLSM)
- VBA 运行时错误‘-2147217900(80040e14):自动化(Automation)错误
- Multiple instances of mysql
- 第4章 控制执行流程
- Delay queue optimization (2)
- MongoDB打破了原则引入SQL?
- The sixteenth issue of eight-part article Balabala said (MQ)
- [Prometheus] An optimization record of the Prometheus federation [continued]
- 微信小程序云开发 | 城市信息管理
猜你喜欢
随机推荐
VBA 运行时错误‘-2147217900(80040e14):自动化(Automation)错误
LeetCode 练习——关于查找数组元素之和的两道题
经济新闻:错误# 15:初始化libiomp5md。dll,但发现libiomp5md。已经初始化dll。解决方法
432.4 FPS 快STDC 2.84倍 | LPS-Net 结合内存、FLOPs、CUDA实现超快语义分割模型
3D机器视觉厂商的场景争夺战役
Does the satellite phone communicate directly with the satellite or through a ground station?
MYSQL (Basic) - An article takes you into the wonderful world of MYSQL
OSPF详解(3)
OMP: Error #15: Initializing libiomp5md.dll, but found libiomp5md.dll already initialized.解决方法
【科普】无线电波怎样传送信息?
natural language processing nltk
终端分屏工具Terminalx的使用
C# wpf borderless window add shadow effect
Two-point answer naked question (plus a little pigeonhole principle)
尊重客观事实
开心的聚餐
NC | 西湖大学陶亮组-TMPRSS2“助攻”病毒感染并介导索氏梭菌出血毒素的宿主入侵...
设计消息队列存储消息数据的 MySQL 表格
- daily a LeetCode 】 【 191. A number of 1
好未来单季营收2.24亿美元:同比降84% 张邦鑫持股26.3%