java - 算法 - 腾讯2018春招
1.小Q定义了一种数列称为翻转数列:
给定整数n和m, 满足n能被2m整除。对于一串连续递增整数数列1, 2, 3, 4..., 每隔m个符号翻转一次, 最初符号为‘-‘;。
例如n = 8, m = 2, 数列就是: -1, -2, +3, +4, -5, -6, +7, +8.
而n = 4, m = 1, 数列就是: -1, +2, -3, + 4.
小Q现在希望你能帮他算算前n项和为多少。
输入描述:
输入包括两个整数n和m(2 <= n <= 109, 1 <= m), 并且满足n能被2m整除。
输出描述:
输出一个整数, 表示前n项和。
输入例子1:
8 2
输出例子1:
8
package tx; import java.math.BigInteger; import java.util.*; public class q1{ public static void main(String[] args){ Scanner s = new Scanner(System.in); String str = s.nextLine(); String[] strArr = str.split(" "); BigInteger n = new BigInteger(strArr[0]); BigInteger m = new BigInteger(strArr[1]); BigInteger sum = m.multiply(n).divide(new BigInteger("2")); System.out.println(sum); } }
题本身不难- - 用初中数学只是就能得出结果是 m*n/2
主要是用到了bigInteger处理大数字。
2.
牛牛和羊羊正在玩一个纸牌游戏。这个游戏一共有n张纸牌, 第i张纸牌上写着数字ai。
牛牛和羊羊轮流抽牌, 牛牛先抽, 每次抽牌他们可以从纸牌堆中任意选择一张抽出, 直到纸牌被抽完。
他们的得分等于他们抽到的纸牌数字总和。
现在假设牛牛和羊羊都采用最优策略, 请你计算出游戏结束后牛牛得分减去羊羊得分等于多少。
输入描述:
输入包括两行。第一行包括一个正整数n(1 <= n <= 105),表示纸牌的数量。第二行包括n个正整数ai(1 <= ai <= 109),表示每张纸牌上的数字。
输出描述:
输出一个整数, 表示游戏结束后牛牛得分减去羊羊得分等于多少。
输入例子1:
3 2 7 4
输出例子1:
5
package tx; import java.util.*; public class q2{ public static void main(String[] args){ Scanner s = new Scanner(System.in); String str1 = s.nextLine(); int num = Integer.parseInt(str1); String str2 = s.nextLine(); String[] strArr = str2.split(" "); int[] iArr = new int[num]; for(int i = 0; i < num; i++) { iArr[i] = Integer.parseInt(strArr[i]); } sort(iArr, 0, num - 1); int sum = 0; for(int i = 0; i < num; i++){ if(i % 2 == 0){ sum = sum + iArr[i]; } else{ sum = sum - iArr[i]; } //System.out.println(iArr[i]); } System.out.println(sum); } public static void sort( int[] iArr, int start, int end){ //冒泡排序会超时,采用快速排序 if(start > end){ return; } int base = start; int low = start; int high = end; while(low < high){ while(low < end && iArr[low] >= iArr[base]){ low++; } while(high > start && iArr[high] <= iArr[base]){ high--; } if(low > high){ break; } else{ int temp = iArr[high]; iArr[high] = iArr[low]; iArr[low] = temp; } } int temp = iArr[high]; iArr[high] = iArr[base]; iArr[base] = temp; sort(iArr, start, high - 1); sort(iArr, high + 1, end); } }
考察了排序,先排序后遍历做加减法就行。
而且由于有运行时间限制,所以用快速排序,冒泡排序等时间复杂度是O²的会超时。
3.小Q的父母要出差N天,走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半,但是他又不想在父母回来之前的某一天没有巧克力吃,请问他第一天最多能吃多少块巧克力
输入描述:
每个输入包含一个测试用例。每个测试用例的第一行包含两个正整数,表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)。
输出描述:
输出一个数表示小Q第一天最多能吃多少块巧克力。
输入例子1:
3 7
输出例子1:
4
package tx; import java.util.*; public class q3{ public static void main(String[] args){ Scanner s = new Scanner(System.in); int n = s.nextInt(); //天数 int m = s.nextInt(); //巧克力数量 //二分法查找第一天的最大巧克力数量 int start = 0; int end = m; while(start < end){ int sweetNum = (end + start) / 2; if(isEnough(n, m, sweetNum)){ //System.out.println(sweetNum + "够了"); start = sweetNum + 1; } else{ end = sweetNum; } } if(n == 1) { //n = 1时二分查找会有问题,所以单独拿出来。 System.out.println(m); } else { System.out.println(end - 1); } } public static boolean isEnough(int n , int m, int sweetNum){ //判断 sweet在n天内能否够吃 for(int i = 0; i < n ; i++) { m = m - sweetNum; sweetNum = (int)Math.ceil(sweetNum * 1.0 / 2); } if(m >= 0){ return true; } else{ return false; } } }
本质:从m个顺序排列的数字中(1 - m)寻找符合要求的最大值。
用遍历会超时,用二分查找,寻找符合要求的最大值。
4.小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌,现在小Q想用这些歌组成一个总长度正好为K的歌单,每首歌最多只能在歌单中出现一次,在不考虑歌单内歌曲的先后顺序的情况下,请问有多少种组成歌单的方法。
输入描述:
每个输入包含一个测试用例。每个测试用例的第一行包含一个整数,表示歌单的总长度K(1<=K<=1000)。接下来的一行包含四个正整数,分别表示歌的第一种长度A(A<=10)和数量X(X<=100)以及歌的第二种长度B(B<=10)和数量Y(Y<=100)。保证A不等于B。
输出描述:
输出一个整数,表示组成歌单的方法取模。因为答案可能会很大,输出对1000000007取模的结果。
输入例子1:
5 2 3 3 3
输出例子1:
9
package tx; import java.math.BigInteger; import java.util.*; public class q4{ public static void main(String[] args){ Scanner s = new Scanner(System.in); int k = Integer.parseInt(s.nextLine()); //天数 String str = s.nextLine(); //巧克力数量 String[] steArr = str.split(" "); int a = Integer.parseInt(steArr[0]); //长度 int x = Integer.parseInt(steArr[1]); //数量 int b = Integer.parseInt(steArr[2]); int y = Integer.parseInt(steArr[3]); //求出两种歌的个数有多少种组合。 ArrayList<Integer> aa = new ArrayList(); ArrayList<Integer> bb = new ArrayList(); for(int i = 0; i <= x; i++){ int r = k - a * i; if(r % b == 0 && r/b <= y){ aa.add(i); bb.add(r/b); } } BigInteger bi = new BigInteger("0"); for(int i = 0; i < aa.size(); i++){ BigInteger temp = getC(aa.get(i), x); temp = temp.multiply(getC(bb.get(i), y)); bi = bi.add(temp); } bi = bi.mod(new BigInteger("1000000007")); System.out.println(bi); } public static BigInteger getC(int x, int y){ if (x == 0) { return new BigInteger("1"); } BigInteger bi = new BigInteger("1"); for(int i = 1; i <= y; i++){ bi = bi.multiply(new BigInteger("" + i)); } for(int i = 1; i <= x; i++){ bi = bi.divide(new BigInteger("" + i)); } for(int i = 1; i <= ( y - x); i++){ bi = bi.divide(new BigInteger("" + i)); } bi = bi.mod(new BigInteger("1000000007")); return bi; } }
我是先求出x 和 y的数量上的组合种类,然后对每种情况分别求x和y的 C(n,m)的乘积, 然后结果相加
比如例题中只有一种情况:x取1个,y取1个
c(1,3) * c(1,3) = 9
x从3个中取1个,y也是从3个中取1个,总共有9中不同取法。
c(n,m) : 不考虑顺序的情况下,从m个物品中抽出n个有多少种排列组合
数学公式:C(n,m)=n! / ( m! * (n-m)! )
还有2个- -明天再做。。。