首页 > 其他分享 >随想录Day1|704. 二分查找、27. 移除元素

随想录Day1|704. 二分查找、27. 移除元素

时间:2023-09-20 21:35:05浏览次数:45  
标签:index 27 target nums int 元素 随想录 数组 移除

随想录Day1|704. 二分查找、27. 移除元素

 

704. 二分查找

LeetCode题目

文章讲解

视频讲解

给定n个元素升序的整形数组nums和一个目标值target,写一个函数搜索nums中的target,如果存在目标值则返回下标,否则返回-1。其中nums中的元素不重复,n在[1, 10000]之间,nums的每个元素都在[-9999, 9999]之间。

 

第一想法和纠正

可以用整形数组,直接10000个int(实际上并没用到这个)

二分查找,需要用到递归,核心函数输入数组的起止位置(左闭右开),比较target和中间值,如果中间值更大则再调用该函数比较左半段,否则比较右半段;如果相等则找到。必须满足l_index + 1 <= r_index(取等于的时候,数组恰好有一个值),如果这时还不相等,则没有target,应该返回-1

 

看到代码的想法

按引用传递了nums,但是我们并不应修改数组,此处应该是为了节省空间。

用于递归的函数要自己在外面另写,因为需要传入左右下标。如果把递归用的核心函数叫做search_index它应该在左下标大于右下标的时候返回。(实际上调用这个函数的时候一定可以保证l_index + 1 <= r_index,无需在此特判。)

此处需要返回什么?是单纯return还是需要返回某个值?下标如何被传递到search原函数中(作为它的返回值)?

所以需要返回下标,如果是比较左半边或右半边区间则返回调用的search_index的返回值,否则返回m_index

然后AC了!

int search(vector<int> &nums, int target)
{
    int len = nums.size();
    int index = search_index(nums, 0, len, target);
    return index;
}

int search_index(vector<int> &nums, int l_index, int r_index, int target)
{
    int index;

    if (l_index + 1 == r_index)
    {
        if (nums[l_index] != target)
            return -1;
        return l_index;
    }

    int m_index = (l_index + r_index) / 2;
    int mvalue = nums[m_index];
    int lvalue = nums[l_index];
    int rvalue = nums[r_index];

    if (mvalue == target)
        return m_index;
    if (mvalue > target)
    {
        index = search_index(nums, l_index, m_index, target);
        return index;
    }
    else
    {
        index = search_index(nums, m_index, r_index, target);
        return index;
    }

 

看完随想录题解的想法

我想复杂啦!直接在while循环中就好,不需要额外拆出来一个函数。具体代码见文章讲解

 

27. 移除元素

LeetCode题目

文章讲解

视频讲解

给定一个数组nums和一个值val,原地移除所有数值等于val的元素,返回数组的新长度。数据满足:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

 

第一想法

只需要考虑新长度范围内的元素,说明额外辅助空间可以利用数组的尾部。如果按照最朴素的想法,从左到右遍历数组,遇到了等于val的元素就把它后面的全部元素往左移一个,时间复杂度是$O(n^2)$。

 

看完随想录题解的想法

愣住了,于是看了文章讲解,采用快慢指针法,其中:

  • 快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
  • 慢指针:指向更新新数组下标的位置

恍然大悟,也就是:

  • 当前元素等于val时,只移动快指针
  • 不等于时,把快指针指向的元素填入慢指针处,然后快慢指针均向后一位。

先填后移是为了每次快慢指针都指向将要被操作的位置,这样最后可以直接返回slow作为新数组长度。

int removeElement(vector<int> &nums, int val)
{
    int fast = 0, slow = 0;
    int len = nums.size();
    for (int i = 0; i < len; i++)
    {
        if (nums[i] == val)
            fast++;
        else
            nums[slow++] = nums[fast++];
    }
    return slow;
}

 

碎碎念

做题用时:30分钟

今天是算法训练营第一天,主要时间花给了博客园的外观搭建工作,终于把它调到较为满意了,这个可能花了五六个小时,对网页方面确实不太熟悉。但是拥有了自己的小世界真的非常幸福!

看文档也花了挺久,但是不得不说卡尔的文档写得真好啊,而且这也是第一天的固定支出,明天一定会顺利很多!今天的题目就是用的VSCode LeetCode插件,比直接在网页上敲要顺手多了,还得是IDE。

以后粉字就是题目,蓝字用于纠正,绿字表示强调。今天比较顺利,之后不顺利的时候我会更详细地记录我想错的地方和遇到的困难。

标签:index,27,target,nums,int,元素,随想录,数组,移除
From: https://www.cnblogs.com/alouette/p/17718477.html

相关文章

  • 算法学习 |Day 1 数组基础 704. 二分查找,27. 移除元素
    704.二分查找思路:二分查找的前置条件是数组有序且无重复元素,每次通过改变边界值来缩小查找范围。自己写的:可以看到对边界的判断存在问题,基本思路是左闭右闭,但是while循环的判断是按照左闭右开来写的。对于数组中仅包含一个元素且该元素是目标函数的情况会出错。重新调试后......
  • abc278题面
    A问题陈述给你一个长度为\(N\)的序列\(A=(A_1,A_2,\dots,A_N)\)。你正好执行了下面的操作\(K\)次:删除\(A\)的初始元素,并在\(A\)的尾部追加一个\(0\)。操作后打印\(A\)的所有元素。限制因素\(1\leqN\leq100\)\(1\leqK\leq100\)\(1\leqA_i\leq1......
  • dns缓存中毒43.227.199.x
    什么是DNS缓存中毒DNS缓存中毒是一种网络攻击,它使您的计算机误以为它会到达正确的地址,但事实并非如此。攻击者使用DNS缓存中毒来劫持互联网流量并窃取用户凭据或个人数据。DNS缓存中毒攻击也称为DNS欺骗,它试图诱骗用户将其私人数据输入不安全的网站。什么是DNS缓存在讨论攻击之......
  • 【POJ 3278】Catch That Cow 题解(广度优先搜索)
    农夫约翰已被告知一头逃亡奶牛的位置,并想立即抓住她。他从一条数字线上的N点(0≤N≤100000)开始,奶牛在同一条数字线上的K点(0≥K≤100000)。农夫约翰有两种交通方式:步行和坐车。*步行:FJ可以在一分钟内从任何点X移动到点X-1或X+1*坐车:FJ可以在一分钟内从任何X点移动到2×X点。如果奶......
  • Three.js——八、坐标、更改模型原点、移除、显示隐藏模型对象
    世界坐标.getWorldPosition()基础坐标也就是模型的.position属性世界坐标:就是模型资深.position和所有父对象.position累加的坐标用.getWorldPosition()属性需要用三维向量表示摸个坐标后方可读取例如:constgeometry=newTHREE.BoxGeometry(100,100,100);constmaterial......
  • [代码随想录]Day49-动态规划part17
    题目:647.回文子串思路:整体上是两种,就是s[i]与s[j]相等,s[i]与s[j]不相等这两种。当s[i]与s[j]不相等,那没啥好说的了,dp[i][j]一定是false。当s[i]与s[j]相等时,这就复杂一些了,有如下三种情况情况一:下标i与j相同,同一个字符例如a,当然是回文子串情况二:下标i与j相差为1,例如aa......
  • 27_linux 网络编程
    linux网络编程HTTP协议对应于应用层,Socket则是对ICP/IP协议的封装和应用Socket的出现只是使得程序员更方便地使用ICP/IP协议栈而已,是对ICP/IP协议的抽象,从而形成了我们知道的一些最基本的函数接口,比如create、listen、connect、accept、send、read和write等。......
  • 【POJ 3278】Catch That Cow 题解(深度优先搜索)
    农夫约翰已被告知一头逃亡奶牛的位置,并想立即抓住她。他从一条数字线上的N点(0≤N≤100000)开始,奶牛在同一条数字线上的K点(0≥K≤100000)。农夫约翰有两种交通方式:步行和坐车。*步行:FJ可以在一分钟内从任何点X移动到点X-1或X+1*坐车:FJ可以在一分钟内从任何X点移动到2×X点。如果奶......
  • 【学习笔记】(27) 整体 DP
    1.算法简介整体DP就是用线段树合并维护DP。有一些问题,通常见于二维的DP,有一维记录当前x的信息,但是这一维过大无法开下,O(nm)也无法通过。但是如果发现,对于x,在第二维的一些区间内,取值都是相同的,并且这样的区间是有限个,就可以批量处理。所以我们就可以用线段树来维护DP。......
  • 203.移除链表元素 707.设计链表 206.反转链表
    203.移除链表元素力扣题目链接(opensnewwindow)题意:删除链表中等于给定值val的所有节点。示例1:输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]示例2:输入:head=[],val=1输出:[]示例3:输入:head=[7,7,7,7],val=7输出:[]思路操作链表的两种方式:直接使用原来的......