挑战20天刷完leecode100

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被删除了！  所以就是不对的！！ 

两两交换链表中的节点

重要的是想如何进行下一轮的交换