错过了腾讯的春招编程题（在牛客笔试前已经电话面所以就没参加，有自己做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、
这个题目我暂时还没有头绪，等我想到了再分享，或者有会的同学可以分享给我，十分感谢。
京公网安备 11010502036488号