0922微软笔试100+100+90
三道题，一个半小时，三道题，难度相当于leetcode medium， 用cpp写的
第一题：100%
思路：这道题相当于去除“重复”后的数组大小。不过“重复”的概念是奇数位置可以交换，偶数位置可以交换，为重复的，因为可以连续交换。
所以取出奇数位置的字符组成s1,偶数位置的组成s2，然后把s1, s2分别sort， 然后把新组成的字符串s1+s2放入set中，返回set的大小，即最终不重复的数目。
第二题：100%
思路：无限制背包问题。
1，先安装要求构造出所需要的素数，这个用最简单的o(n2)算法即可,放入数组v中
2, 当 j >= v[i]时，dp[j] = min(dp[j - v[i]] + 1, dp[j]) ;
3, dp[input1] 就是最后的答案，最少的数量。
第三题 90%
思路：回文数字问题
对每个数字进行暴力判断，大概能过50%， 后面发现如果这个数本身是回文，那么一定能等于某个数和它的回文之和。所以先进行判断是否本身回文，这样优化后过了90%。
暴力判断的时候，注意不要从1开始， 比如8位数t, t = 12345678 = a + b, 那么 a和b至少是7位数，所以从10^7次方开始枚举，到t / 2 即可终止。
还有1个case超时了，暂时没其他方法。
投递腾讯等公司10个岗位 >
拼多多集团-PDD公司氛围 522人发布