704、二分查找
题目链接:https://leetcode.cn/problems/binary-search/
文章讲解:https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
视频讲解:https://www.bilibili.com/video/BV1fA4y1o715
想法:
之前有学过二分查找,但是写不出来,看了题解之后思路清晰了,两个解法都实现了。
问题:
1、vector的使用,https://blog.csdn.net/weixin_45935610/article/details/123121742;
2、自动类型转换丢失精度https://en.cppreference.com/w/cpp/language/implicit_conversion;
3、算术左移运算符,https://blog.csdn.net/weixin_45935610/article/details/123121742;
4、no matching function for call error,https://mrcodehunter.com/no-matching-function-for-call-to-cpp/
今日收获:
1、当查找的数组中的元素有序且无重复元素的时候,可以考虑二分查找‘
2、每次循环处理边界条件的时候。注意循环不变量原则,区间的定义就是不变量。
27、移除元素
题目链接:https://leetcode.cn/problems/remove-element/
文章讲解:https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解:https://www.bilibili.com/video/BV12A4y1Z7LP
想法:
一开始想到的就是暴力解法,遍历数组,然后移动元素,时间复杂度确实高,后面实现了双指针法,这种方法不改变原来元素的相对顺序。
问题:
手动模拟了,当删除的元素在第一个位置,或者删除的元素连续出现的情况,更加深入理解了双指针法。
收获:
快慢指针就是快指针走的快,用来查找新数组中的元素,慢指针更新新数组的位置,如果当前位置不是要删除的元素,慢指针向后移一位,表明一个新元素被添加到数组中,而每循环一次,快指针都会向前走一位,直到循环结束,慢指针在每一次循环体内不一定前进,这就是双指针法又叫快慢指针的原因吧。改变顺序的想向双指针法二刷的时候再来看。