10.15百度笔试

第一题：题目忘了跳过，总之挺简单的第二题：是一个数学规律题，在草稿纸上跟着流程做一遍就可以发现规律。第三题：因为数据量很小，我懒得优化，直接暴力dfs求解，最后用set去重

单选多选加三道算法算法做出来两道第一道n个数里面选k个数，若选的这个数的后面那个数没被选，则积分加1，求积分最大值。第二道遍历字符串，每次都将第i个字符移动到数组末尾。思路：刚开始使用linkedlist时间超限，后面用空间换时间，构造了一个大小为2n的数组，将移动过的字符变为0，最后遍历收集就好。第三道计算麻将胡的方案。给一个数n，1-n之间的牌可以用，有四个111，123这种加上一个对子就算胡了。

15道单选，5道不定项选择，3道算法题，两个小时，时间紧张，主要是算法题有些难度。选择题还是常规，数据结构（排序算法，二分查找，KMP），操作系统（Linux，磁盘调度算法，虚拟内存（最近频繁碰到）），计算机网络（HTTPS），数据库。不定项选择里，全是Java相关。算法题，难度陡然递增，2和3量大题难。第一题签到题，比较简单，确定计算最大积分公式即可。第二题，看着很容易，字符串操作类的题目，直接用暴力解析，循环n次每次将第i个字符移动到末尾，但最后超时了，过了70%多，怕时间不够先跳了，折回来分析看字符串的最大长度为10^6，如果通过StringBuilder直接删除和增加的时间复杂度是O(n)，加上一层遍历时间复杂度是O(n^2)，优化的点就是采用更高效的搜索树，降低删除和插入的时间复杂度，一般可以降低到O(logn)，想到了平衡二叉树，那么问题就转化为了实现一个平衡二叉树，定义好其节点类以及旋转，插入，删除和遍历的操作。第三题，麻将胡牌种数的题目，蛮有意思的。整体思路就是枚举和验证，核心点也是容易超时，因此需要一些技巧来优化，首先就是dp来减少重复计算，然后就是通过剪枝来提前排除不可能的情况，由于刻子和顺子在牌种确定的情况下，可以预计算出来，减少耗时，最后就是通过位运算来判断手牌状态，加速状态转移和判断。总的来说，百度这套题，选择题常规，还算比较简单，算法题属于是，想做出来简单，思路很直接，但需要一些技巧来优化避免超时的问题，区分度确实有，我觉得还算合理，算法题2和3即使不用任何优化技巧，也能拿一半的分。 #百度求职进展汇总#

两道题样例都通过，提交0%, 哭死我了。第一道找到原因，第二道有大佬可以指点一下。陷入第一二道题目的0%中。第三道没时间看。一、 第一题。 1~n 选取k个数的最大积分。初始积分为0， 对于选取的每个数i, 如果i + 1不选， 得分加1 分析， 以1 2 3 4 5和1 2 3 4 5 6为例子 （一）当n为偶数时， 例如等于6， 那么间隔取可以获得的最多得分为n/2, 当选取的个数k小于或等于n/2时候，可以获得最大 得分k 当k 大于n/2时候， 剩余k - n/2...