成都网站建设138网络顾问
2025.1.5
二分查找
1 搜索插入位置
就是简单的二分查找 注意开闭就行
这里有一句话就是nums是升序的 如果他不是严格递增 就是有相同的数字的情况下应该怎么写?
int lower_bound(vector<int>& nums, int target) {int left = 0, right = (int) nums.size() - 1; while (left <= right) { // 区间不为空int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1; // 范围缩小到 [left, mid-1]} else {left = mid + 1; // 范围缩小到 [mid+1, right]}}// 循环结束后 left = right+1// 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target// 所以 left 就是第一个 >= target 的元素下标return left;}这是代码！ 
就是在这里需要更改
2 搜索二维矩阵
第一个方法就是通过两个二分 第一个二分确定在哪一行第二个确定在那一列 这里可以用3的方法一样的
第二个方法就是通过从最后一行第一列开始，每次去除一行或者一列这个简单
3 在排序数组中查找元素的第一个和最后一个位置
我们就是写一个lower_bound （第一个大于等于当前target的元素的下表！）
4搜索旋转排序数组
分组二分查找
如果[left - mid）他是有序地我们就看target是不是在这中间不是的话left = mid+1（不在的话一定在右侧）
如果（mid,right ] 他是有序地我们就看target是不是在这中间不是的话right = mid-1(不在中间一定是在左侧 )
5
栈
1
就是一个简单的栈的应用
2
这个就是需要两个stack有一个需要注意的是
if(s2.empty()||val<=s2.top()) //这里必须<=
举例子 如果是 -1 0 -1 我们把我们最小的加入应该是 -1 -1
如果没有等于的话就是 -1 那在原来的stack中进行pop的话 我们判断如果top相同那-1会被去除
那就不对了啊！
链表问题
相交链表 （做出来了）
记住我们set中的find是迭代器的寻找 就是 set.find(..)!=headB.end();这个意思
2 反转链表
这个题
//想法就是 先弄一个 listNode * pre = null;
while(head!=null)
//标记下来我们当前的下一个 就是index = head->next;
//head->next = pre;
//在这里需要加一个判断就是if(index == null) break;
//pre = head;
//head = index;
为什么呢 如果不加判断我们的这个index ==null之后 head也会变成null所以如果return head->next就错了 所以加这个判断就没问题啦
3 会问链表
很重要这个做错了还是对链表的理解不够透彻！！！、
让 list = head 对list进行倒序
通过while 比较我们是不是相等
这个是很傻逼的！！ 因为我list是一个地址 我让list等于 head
那我不就是相当于 对head进行操作了？？？
所以严厉禁止这个想法 ！
正确想法很简答 就是把val拿出来放到vector中 通过left right 来比较就行啦 很简单的
环形链表 (一跟二都很简答)
很简单
两数相加
问题是我要知道链表如何完成串联 ！！
如果链表不存在
head = tail = new listnode（sum%10）;
如果链表存在 tail = new listnode(sum%10);
tail = tail->next;
删除链表的倒数第n个
这个题目两个点 第一必须有一个前置指针 ListNode * f3 = new ListNode(0);
让我们的
ListNode * f1 = f3;
ListNode * f2 = f3;
然后在是
f1->next = head;
f2->next = head;
f3->next = head;
因为 我们需要把指针移动 n+1 个位置！！ 如果单纯的用head 有可能移动到n+1 的那个位置不存在！
第二 我们必须返回的是 return f3->next;
不是head 因为有可能head被删除了！ 所以就是不对的！！
两两交换链表中的节点
重要的是想如何进行下一轮的交换