2019腾讯春招暑期实习提前批编程题
错过了腾讯的春招编程题（在牛客笔试前已经电话面所以就没参加，有自己做C++的笔试，对C++不熟，感觉已经凉了），但是朋友做了便截图下来然后自己练习一下，给我的感觉就是，会做的就很快写完，不会的基本没有什么思路，总之很快写完了三道题，但是有两道是不会的。下面按题目给出我的代码，有错的恳请指正。
1、
不要看到这个就以为是背包问题，这个是从大到小的，也就是说什么面值的货币都有，所以就不存在比如货币是{1，6，7}，而输入30的情况下，如果按下面的算法就出错了，按下面的算法，此时应该得到4*7+2*1=30，要6个货币，但假如是6*5=30只要5个货币。但题目给的是n种货币，所以假如先4*7+1*2=30，也是只要5个货币，所以本题很简单。。。
public static void lessCoins(){String [] lines = scanner.nextLine().split(" ");int n = Integer.parseInt(lines[0]),m = Integer.parseInt(lines[1]);int count = 0,temp = 0;while (m>0){temp = n;while (temp>m){temp--;}m-=temp;count++;}System.out.println(count);}
如果按照前面说的，那要简单动态规划了，动态规划基本就是两个步骤，定义状态，然后递推转移方程，如果想要详细了解动态规划，那么可以参考别的文章。
public static int getLessCoinsCount(int []coins,int amount){int []dp = new int[amount+1];for(int i=1;i<=amount;i++){int min = Integer.MAX_VALUE;for(int j=0;j<coins.length;j++)if(coins[j]<=i)min = Math.min(min,dp[i - coins[j]]+1);dp[i] = min == Integer.MAX_VALUE?0:min;}return dp[amount]>amount?-1:dp[amount];}
2、
这个
其实就是累加的意思，只是要对加数做个求余判断。
public static int getSum(int start,int end){int sum = 0;for (int i = start;i<=end;i++){if(i%2==0) sum += i;else sum -= i;}return sum;}int n = Integer.parseInt(scanner.nextLine());int [][]res = new int[n][2];int []r = new int[n];String [] strs = null;for (int i = 0;i<n;i++){strs = scanner.nextLine().split(" ");res[i][0] = Integer.parseInt(strs[0]);res[i][1] = Integer.parseInt(strs[1]);}for (int i = 0;i<n;i++){r[i] = getSum(res[i][0],res[i][1]);System.out.println(r[i]);}
3、
这题可能同学想到的，就是先枚举所有排列，再和原来的数组做比较，得到结果相等时计数加1，当超过1e9+7时对计数取1e9+7的余数，相信大部分人都这么想，但是，这肯定是不可取的，17的阶乘都超过了int的最大范围，何况这里有最多2000个数，那肯定是不可计算的。想一下，假设在相等的情况，有s个1，其他均为0，那么就有Cn的s种，而其他的还有2的（n-s）次方，因为0、1、2，只能有2种可能是能赢的，而这些数也是有n-s个数，于是得到公式。所以代码就很简单了：
public static int calC(int n,int s){int count = 1, e = n - s;for (int i = s + 1;i<=n;i++){count *=i;if(count>1000000007)count%=1000000007;}while (e>0){count *= 2;if(count>1000000007)count%=1000000007;e --;}return count;}
因为我没有提交过题目，也不知道对不对，但是举几个例子都是没有问题的，在s,n的范围内也是算得很快，如果不对的请指正。
4、
看到这题，是不是感觉跟计算最长子串的思想有点那么相似，如果你要这么想，就往复杂里面想了。相信学过计算机网络的同学应该都听说过滑动窗口，滑动窗口应该就是在传送报文时可以动态更新的长度，窗口长度受对方主机反馈的影响。我觉得这个意思很像啊，说下我的思路，因为要求所有颜色要命中，于是用一个list去装这个序列，这个序列肯定都包含所有颜色但也可能有重复的颜色，因为这个滑动窗口就是记录原来数组中连续最少的枪数，此外我们还要判断什么这个list满足包含所有颜色，当包含所有颜色时，就得到一个序列，这个满足条件的序列长度就被保存下来到一个res_list中，到最后对res_list排序，取最前面的数就是最小的长度。那么关键问题就是，滑动窗口怎么设计，其实很简单，因为滑动窗口要满足包含所有颜色，暂且用一个队列来保存这个滑动窗口，只有当要入队元素和队首元素一样时，我们才对队列操作，即队首元素出队，然后再入队，这就能保证当前队列不会有多余的步长，当然，你非要说中间有相同的数，那我只能说没有影响。当得到一个可用序列后，滑动窗口要更新的，就是删除队首，当队首元素后有队首元素时，删除队首元素直到没有。于是代码就出来了：
public static int lessShotCounts(int a[],int m){ArrayList<Integer> res_list = new ArrayList<>();//所有满足条件的窗口长度ArrayList<Integer> list = new ArrayList<>();//得到一条路线的标志LinkedList<Integer> t_list = new LinkedList<>();//滑动窗口的数组for(int i = 0;i<a.length;i++){if(!list.contains(a[i])){list.add(a[i]);t_list.add(a[i]);}else{if(t_list.get(0) == a[i]){t_list.remove((Object)a[i]);}t_list.add(a[i]);}boolean flag = false;if(list.contains(0) && list.size() == m + 1) flag = true;if(!list.contains(0) && list.size() == m ) flag = true;if(flag){System.out.println(Arrays.toString(t_list.toArray()));res_list.add(t_list.size());if(t_list.get(0)!=null){int temp = t_list.get(0);t_list.remove((Object)temp);list.remove((Object)temp);if(t_list.get(0)!=null){temp = t_list.get(0);while (t_list.lastIndexOf(temp) !=0 && t_list.get(0)!=null){t_list.remove((Object)temp);temp = t_list.get(0);}}}}}if(res_list.size()==0)return -1;else{Collections.sort(res_list);return res_list.get(0);}}
结果：
5、
这个题目我暂时还没有头绪，等我想到了再分享，或者有会的同学可以分享给我，十分感谢。
冷不防
我就是我
向右看齐
深藏阁楼爱情的钟
怼烎@
刺骨的言语ヽ痛彻心扉
还没有评论，来说两句吧...