lcode基础训练6关答案

哈哈哈 哈哈哈 哈哈哈。

器官是我们要讲的第四种重复类型的类型，他是一个十字形， 按照正常的思维啊，我们可能有的学生会想让他这样走，然后再倒回来，对吧？然后再走到路中间，然后转向，再去，这样， 对吧？用两个重复执行，而这种方法可不可以呢？当然是可以的啊，因为方法都是啊，很多的，但是呢，最佳方案永远都是只有那么一个或两个。好，我们看一下啊，如果按照刚才的思路，我们让大夫先走一二三四啊，走四步， 然后呢，大夫再退回来啊，退到直接退到这里。一，我们用减法吧啊， x 是十一，这边是 x， 十一外是十三，十三减五等于八，所以呢，我们这 你需要减八，让大夫倒退着走八步，然后呢？干嘛再让大夫啊？倒着走四步，是不是又回到了中间啊？正着走四步，又回到了中间， 这是我们再让大夫不管左转还是右转啊，都可以的。那然后继续啊，继续让他，假如说右转啊，继续让他往前走，然后倒着走八步，然后再回来，对不对？那这样我们需要重复之前两次，好，我们看一下。 好，这样的话，代码行数啊，多了一行，但是步数啊，我们少了两步，那这个应该怎么办呢？ 好，那么关于十字形的解法啊，其实他也是啊，有一定的技巧。那我们可以让大夫这样走，先走过去， 然后再走回来，然后呢，这边转向，然后再走回去，再走回来啊，同样的四个啊，重复执行四次，那我们看一下这种步法应该怎么走？ 是不是按照我们刚才思路先走，对吧？重，呃，先让他行走四步，倒回来的话就减四，然后转向，对吧？重复之前四次。好，我们看一下。 好，这样的话步数啊刚刚好，但是他的行数啊要比刚才少了一行。 那我们的目的是三星过关啊，因为在这个比赛的时候啊，这个挨扣的是有比赛的，在比赛的时候如果你用的这个步数和行数都少于他的规定啊，会额外的加分，但是前提是要求三星啊，三星的情况下才可以有这种额外加分。

好了，我们学完五种基本的重复执行类型之后呢，我们一起来实践一下啊，首先看第八关，第八关我们分析一下啊，首先我们看到一个题目之后，一定要先去找他的规律啊，找出他的主要路线，那这道题的主要路线是什么？我们可以看一下是不是这个样子， 那这是一个什么？这是不是一个阶梯形？那同时呢，两边还有支线啊，这个支线是干嘛？是不是这个样子？ 那我们就可以得到一个结论啊，他就是有这个王字型的，然后加上什么，加上阶梯型的啊？他们两个的一个组合变形，那这种题目我们应该怎样去用程序求解呢 啊？也很简单，我们只需要按照啊，一定的过程啊，按照按照顺序结构啊，一步一步的 来做啊，然后加上重复执行就可以了啊，比如说啊，第一步，好，我重新再做一遍， 因为这个大夫他直接是脸是朝这边的，那所以呢，我们就可以直接让大夫行走，这里是行走三步， 然后呢走到这里之后干嘛？是不是要想办法去收掉这两个能量块，对吧？所以这个时候呢，我们可以让大夫右转，也可以让大夫左转啊，这个根据个人的啊，这个习惯， 大夫右转之后，那么我们先把这个能量块收集一下，是不是他需要退着走一步，所以呢，这里减一， 然后呢大夫再往前走啊，正着走一二三，走三步，是不是就来到了这个能量块？这好，然后呢，大夫还需要回来，回到这个路口，然后再 转一下啊，那这里还需要减一，然后干嘛？刚才是右转对不对？那这里接梯形的啊，都是左右交替的。那所以他是左转。好，我们看一下。 注意看啊，这个时候大夫是不是在这个位置和在这个位置的时候脸都是朝这个方向的，是吧？那接下来我们是不是就可以利用重复执行了？好， 我们把这个啊加上重复执行，一共是一、二、三啊三个阶段，那我们就重复连三次 好了，这八关啊，通过了。

好习题，六钢丝呢，特别简单啊，他要求我们输入一个整数啊，判断其是否能同时被三五七整除，如果能整除的话，输出 yes， 否则呢？输出 no 啊，那我们看到样例输入是七啊，七的这个结果呢，是不能够被三五七整除的，那么这个结果结果是 no 啊，这个代码，呃，特别容易写啊，我们直接写好了，六杠四啊，我们看到说，哎， a 等于 int input 啊， input 返回的这个结果呢，是一个字母串通过 int 函数呢，把转成整数，那这个 a 呢，就是输入的值，他同时能被三五七整出，那就是 a 对三需求求余的结果等于零，对五求余的结果等于零，对七求余的结果也等于零啊，与，呃，与的关系啊，并且的关系。如果这些条件都满足啊， print yes， 否则呢？ print no 啊，这个程序呃，特别容易，那我们看看七的结果呢？ snow 啊，我们看看一个能被三五七整除的，那显然意见一百零五 yes 啊，是对的。 呃，这道题太过容易了。 好，没问题。

我们继续来看第十关，同样是考察重复执行的一个关卡，还是老方法，我们先来寻找他的最基础的路线， 那我们可以啊，很很容易的看出来，他是一个环形的路线，在环形的同时呢，两边有这个能量块，我们就需要让大夫啊，去把这两个能量块收集掉，对吧？四个路线上都有， 那么我们就可以看出这个路线他其实是什么样的路线，那是不是一个环形的，加上什么？加上王字形的一个组合变形，对吧？那是不是看 是不是王字形？好。那么这个题目应该怎样去做呢？首先第一步啊，我们是需要 大夫啊，转一下，把这个能量块收集，然后倒着走到这，然后再回到飞船上，然后呢，飞船带着这个再夫啊 往这走，走到这个位置，那接下来呢，是不是要重复同样的动作，对吧？那这样的话啊，这个解题思路就很明显了。 好，那也有同学会问啊，老师，为什么你第一次不让大夫啊，这个飞船走到这个位置去收这个呢？两块， 好，这个啊，我们就需要强调一下，重复执行是什么？重复执行必须要做一模一样的事情才可以重复，那我们想一想啊，如果让飞船先飞到这，然后呢？下一次我们再重复执行的话，让飞船是直接让他走三步吗？能不能走？肯定不能，对不对？ 非常要这样走，这样走的情况下，是不是就和第一次不一样了？不一样的话，能不能使用重复之枪？肯定不能，对吧？所以我们一定要牢记这个啊，牢记这个概念，重复执行必须是一模一样的，这个动作才可以重复， 好了，为了实现啊，我的我们能够重复执行，那我们一起来看一下怎样做。首先大夫啊，这个左转或者右转都可以，那我就就让他右转吧， 然后走一步，收集了这个能量块，对不对？然后呢，倒着往后走，一二三走三步，那这里应该是减三， 然后呢，再往前走，走两步回到飞船。回到飞船之后，这里有一个问题啊，我先留一个悬念，那大夫要不要左转啊？重新回到 原来的位，原来在这个方向。好，先留一个悬念啊，先放这吧。好，大夫，回到飞船上之后呢，飞船要继续往前走啊，要怎么走？一二三四走四步，对不对？ 然后呢，飞船转弯右转，再往前走一步，就会来到这个位置，对吧？就会来到这个位置。好，我们一起看一下， 好，注意看啊， 此时代夫他的方向是朝这里的，对不对？那飞船呢？飞船的方向是朝这的，那一开始飞船我换一个颜色啊， 一开始飞船是不是也是啊？怎么讲啊？飞船 是顺着这个这条边的方向，对不对？那大夫是朝哪的？大夫是不是也是朝着这个方向的？然后我们就发现了啊，他们的不同之处， 如果啊，我们在这加上加上左转，那么大夫和飞船走到这的时候，那么大夫就会朝向这个方向，就和原来的方向是一样的。那么这个时候我们能不能继续用重复执行呢？我们来想一想，好，我们重复重复执行的第一个代码是什么？ 大夫，右转对不对？那么大夫右转右转之后是不是要朝这呢？朝这往前走，能不能走？不能，对吧？所以呢啊，这个左转啊，没有必要，那我们这个啊，就是一个状态的问题。 好，什么叫做状态的问题呢？就是我们每一次做完一个重复的动作之后呢，他的这个状态包括方向啊，包括这个距离，距离这个能量块有几格啊等等，这些都是要保持一致的， 虽然他不是一模一样的啊，但是他的这个状态是一样的，什么意思呢？就比如说啊，刚开始的时候啊，这个大夫和飞船他们的方向啊，都是一致的， 他们的方向啊，都是朝着这个方向的，对吧？那么我们走完一次循环之后呢，我们也应该让他们俩的方向去保持一致， 这样的情况下我们就可以继续使用重复执行了，如果方向不能保持一致的话怎么办？那你使用重复执行是不是就会出现问题， 对吧？好，那么这个是这道题的状态，那还有其他的题目有其他不同的状态，这个都需要我们自己啊，去用心去发现这些能够使用重复执行的点在哪啊？好，所以呢，这个左转啊就不需要了， 那细心的同学让我们来走慢一点，我们一起看一下，注意看此时大夫啊，他的这个方向是不是朝这呢？对吧？ 那一开始是朝这的，那走完四次之后，每次大夫的方向都会和这个正方形的边长是平行的啊，就顺着这个边长的方向好了，那么接下来呢，我们就可以使用重复执行了，一共有四次啊，那么就重复 四次。好，我们看一下效果。 ok， 第十关搞定。

来我们看一道高频算法面试题，最小站，什么是最小站呢？我们知道正常的站有入站操作，也有出站操作，还有拿到站顶的元素，这个操作，这三个操作的时间复杂度呢，都是常量级别的，非常的高效。那么最小站除了包含这三个操作之外呢，还有一个拿到站中最小值的操作， 这一正常的站，我们需要便利站中所有的元素才可以知道最小值，这个时间复杂度呢是线性级别的，不是特别的高效。那么最小站呢，要求拿到站中最小值，这个操作的时间复杂度呢，必须是产量级别的， 如何实现最小站呢？建议点赞收藏，指不定下一次面试的时候呢，你就遇到了，我们可以使用一个正常站来存储数据，为了能高效的拿到最小值，我们在压入数据的时候呢，将当前的最小值呢，我们先记住 继续压入二，当前最小值仍然是一不变，压入四最小值呢还是一？当我们压入一个比当前最小值还要小的元素，这个时候呢，我们是不是将最小值 设置为零呢？这个是不行的，因为当这个零弹出去的时候，我们就不知道当前的最小值是多少了。所以当压入比当前最小值还要小的元素时，除了要记住当前的最小值零之外呢，还得记住之前的最小值， 当压入五十两个最小值不变，当压入负二时，因为比零还要小，所以呢，需要记住这个最小值表示呢，当前站中的最小值呢是负二，那么当弹出这个负二的时候呢，我们也需要将最小值负二呢删除，因为当前的最小值就不是负二，而是零了。 当弹出的元素不是最小值就不要管，当弹出零的时候呢，那么最小值零也需要删除。那么右边存储这个最小值的这个数据结构呢，是不是符合先进后出的特点啊？所以呢，我们可以使用另外一个正常站来存储所有的最小值，也就是说，我们使用两个正常站来实现一个正小站。那么 data stack 用于存储数据， miss deck 用于存储所有的当前最小值。当压入元素一，在 miss deck 中也要压入当前的最小值一。当押入的元素大于 miss deck 占顶的元素的时候呢，则不管。 当压入的元素小于 minstec 占领的元素的时候呢，需要将当前的元素呢也压入到 minstec 中。如果大则不管， 如果小也压入到 minstec 中。那么每次呢，如果你想拿到这个战中的这个最小值，只需要拿到 minstec 占顶的元素就可以了，这个时间复杂度呢是 o 一特别的高效。当要弹出的这个元素等于 minstec 占顶的元素的时候呢，则说明弹出的这个元素呢，是当前的战中的最小值，需要呢从 minstec 中弹出。 如果不等的话呢，你就不管。如果相等的话，那么也需要从 mistake 中弹出当前的最小值。那么这里有一个问题哈，就是当压路的这个元素等于 mistake 占顶的这个元素 数时，需不需要将当前这个元素也压入到 minstep 中呢？如果不压入到 minstep 中的话呢，会有问题，刚弹出这个一的时候，因为和 minstec 占顶的元素相等，所以呢， minstep 占顶的一呢也需要一起弹出， 这个时候我们就不知道了当前占中的这个最小值了，所以当压入的元数小于等于 minstec 占顶的元数时，都需要将这个元数呢压入到 minstec 中。

上个视频我们聊了低洁斯特拉提出的使用两个赞来实现四则表达式的计算，对于这种每一个运算符都有括号的表达式呢，是完全没问题，但是如果表达式中没有括号或者呢括号中有三个及以上的操作数的话呢，就会有问题，我们需要基于这两个赞呢来继续改进。 如果表达式中没有括号的话，需要考虑 u 型级问题，便利表达式遇到数值压入操作数占下一个运算符压入运算符占下一个数值压入操作数占 下一个运算服加，这个时候需要和运算服占占顶的运算服呢比较优先级，这里当前的加号他的优先级是低于占顶的乘法， 所以呢，需要先做乘法操作，也就是呢，先将操作处在站顶的两个数值呢弹出，再将运算符在站顶的运算符呢弹出进行计算， 得到的结果再次压入到操作数站，然后将加号压入运算符站，下一个数值压入操作数站。 当表达式便利完后呢，如果运算符占不为空的话呢，就需要继续进行计算，将操作数占占顶的两个数的数值弹出，再将运算符占顶的运算符呢弹出进行计算，将结果呢压入到操作数占， 如果运算符站这个时候空了，那么操作数站站顶的这个数值呢，就是最终的结果。再来看一个比较复杂的表达，是 数值压入操作数账下一个运算符，这个时候因为运算符账呢是空的，那么直接压入到运算符账 下一个数值压入操作速战下一个运算符减号，这个时候运算符赞呢，他不是空的，那么就需要比较优先级，这里减号和占顶的加号，他的优先级是一样的，所以呢，可以先 做前面的加法操作，也就是呢，一加二等于三，将结果呢压入操作数账，然后将减法压入运算符账， 下一个数值压入操作数站，下一个运算符乘法，他的优先级比运算符站站顶的运算符呢优先级要高。所以呢，直接将乘法压入运算符站，下一个左括号，直接压入运算符站， 下一个数值压入操作数站，下一个运算符减号，这个时候运算符占占顶，它是一个左括号。所以呢，直接将减号压入运算符站，下一个数值 压入操作速战，下一个运算符加号，它的 u 星级呢，比占顶的减法跟 u 星级是一样的，对吧？所以可以呢，先把之前的减法操作呢先做掉，也就是呢，四减五等于负一，将结果 压入操作速战，然后将加法压入到运算符战，下一个数值压入操作速战，下一个又括号，这个时候执行占顶的加法操作，也就是负一加六等于五，将结果压入到操作速战， 证实运算符占占顶是一个左括号，表明呢括号内的表达式呢，已经计算完了，可以将左括号呢弹出。下一个是运算符减法，他的优先级呢，是低于占顶的乘法，所以呢，先执行之前的乘法操作，也就是三乘以五等于十五，将结果压入到操作速站， 继续比较当前的运算符和占顶运算符的优先级。当前运算符减号和占顶的运算符减号呢，优先级是一样的，所以呢，先执执行之前的减法操作，也就是呢，三，减掉十五等于负十二， 将结果压入到操作数站，然后将减法压入到运算符站，下一个数值压入操作数站。 当表达式便利完后，因为运算服占呢不为空，所以呢，执行占顶的减法操作，也就是呢，负十二减掉七等于负十九，将结果压入到操作数占。如果运算服占空了，那么操作数占占顶的数值呢，就是整个表达式最终的结果。 这个是代码，同志们可以看一下。这里和上一个视频呢，有四点不同的地方，第一个，遇到左括号，压入到运算符站。第二个，如果当前运算符的优先级是小于等于占顶的优先级的话呢，则对占顶的运算符呢，先计算 第三个，如果遇到右括号，则一直计算占顶的运算符，直到遇到左括号为止。第四个，如果运算符占不 为空，需要呢，继续计算。同时，这里有一个 evo 的辅助函数作用，就是呢，使用预算符占占顶的符号来计算超拓数占占顶的两个数值。