讨论/求职面试/米哈游|春招笔试 - 客户端|图形/深度学习 - 第一批|个人题解|2021|/
米哈游|春招笔试 - 客户端|图形/深度学习 - 第一批|个人题解|2021|

个人题解,欢迎补充讨论。

  1. 1807

    输入一个字符串,求最长的包含且只包含1807这四个字符且按1→8→0→7顺序的子串的长度。

    我一开始想的是O(n2)O(n^2)的动态规划。后来发现不太对,就直接改成用一个字典来分别计算以1、8、0、7结尾的最长子串的长度,一次遍历O(n)O(n)


  1. 【C、C++、C# 限定】牛牛的游戏俱乐部

    nn个游戏,每个游戏需要1单位时间来完成。第ii个游戏必须在tit_i时间或之前完成,完成则获得wiw_i分,没完成则扣除wiw_i分。求最大获分。

    我的想法是用一个字典来储存每个时间段的所有游戏分数。然后每个时间段取最大的titi1t_i-t_{i-1}个值减去所有剩下的值得出答案。然而语言成了我最大的障碍,特别是我平常用惯Python,各种变量类型声明整得我头大。


  1. 平衡数

    [L,R][L,R]区间内奇数位数字的和等于偶数位数字的和的数的个数。

    由于上一题语言问题卡了许久,这题我就只写了个暴力解,通过13.33%。
    数据范围是10910^9,时间限制C、C++ 1秒,其它语言两秒。所以O(n)O(n)也基本会超时的。我暂时还想不出有啥更快的方法,希望大佬补充。


  1. 中序遍历

    字符串A(B(C,),D(,E))A(B(C,),D(,E))表示二叉树

    tree1.png

    求这类字符串表示的二叉树的中序遍历。

    结合用栈实现树的遍历。节点值按顺序入栈,空值也入栈。遇到逗号弹出两次,遇到右括号弹出一次。弹出顺序去掉空值即答案。


  1. 是否凸多边形

    给定nn个点坐标,按顺序连成一个多边形,求该多边形是否凸多边形。

    提示:对于一个多边形的任意边,若所有不在该边的点都在该边所在的直线的同一侧,则该多边形为凸多边形。

    对于任意边的两点(x1,y1)(x2,y2)(x_1,y_1)(x_2,y_2),用直线的两点式表示该边所在直线

    xx1x1x2=yy1y1y2\frac{x-x_1}{x_1-x_2}=\frac{y-y_1}{y_1-y_2}

    对于其余点(xi,yi)(x_i,y_i)分别代入该式的xxyy,若均为大于或小于,则都在同一侧,即该多边形为凸多边形。

16

数位dp需要有一位存的是位值,这样算至少四维,优化的话需要成差的方式需要加一个偏移量,防止是负数,这样的话可以优化成三维

展开全部 17 讨论