1 合唱团(动态规划)
分析
要求n个学生中选择k个,使这k个学生的能力值乘积最大。这是一个最优化的问题。
另外,在优化过程中,提出了相邻两个学生的位置编号差不超过d的约束。
如果不用递归或者动态规划,问题很难入手,并且,限制条件d也需要对每一个进行约束,编程十分复杂
所以,解决的方法是采用动态规划(原因:1.最优化问题2.可分解为最优子结构)
分解
1.对该问题的分解是关键。
从n个学生中,选择k个,可以看成是:先从n个学生里选择最后1个,然后在剩下的里选择k-1个,并且让这1个和前k-1个满足约束条件
2.数学描述
记第k个人的位置为one,则可以用f[one][k]表示从n个人中选择k个的方案。
然后,它的子问题,需要从one前面的left个人里面,选择k-1个,这里left表示k-1个人中最后一个(即第k-1个)人的位置,因此,子问题可以表示成f[left][k-1].
学生能力数组记为arr[n+1],第i个学生的能力值为arr[i]
one表示最后一个人,其取值范围为[1,n];
left表示第k-1个人所处的位置,需要和第k个人的位置差不超过d,因此
max{k-1,one-d}<=left<=one-1
在n和k定了之后,需要求解出n个学生选择k个能力值乘积的最大值。因为能力值有正有负,所以
当one对应的学生能力值为正时,
f[one][k] = max{f[left][k-1]arr[i]}(min{k-1,one-d}<=left<=one-1);
当one对应的学生能力值为负时
f[one][k] = max{g[left][k-1]arr[i]}(min{k-1,one-d}<=left<=one-1);
此处g[][]是存储n个选k个能力值乘积的最小值数组
编程实现
import java.util.Scanner;/** * @author shishusheng */public class NetEaseOne { public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()) { //总人数 int n = sc.nextInt(); //学生能力值,第i个人的直接对应arr[i] int[] arr = new int[n + 1]; //初始化 for (int i = 1; i <= n; i++) { arr[i] = sc.nextInt(); } //选择的学生数 int kk = sc.nextInt(); //间距 int dd = sc.nextInt(); /** * 递推的时候,以f[one][k]的形式表示 * 其中:one表示最后一个人的位置,k为包括这个人,一共有k个人 * 原问题和子问题的关系:f[one][k] = max{ f[left][k-1]*arr[one], g[left][k-1]*arr[one] } */ //动态规划数组 //人直接对应坐标,n和kk都要+1 long[][] f = new long[n + 1][kk + 1]; long[][] g = new long[n + 1][kk + 1]; //初始化k=1的情况 for(int one = 1;one<=n;one++){ f[one][1] = arr[one]; g[one][1] = arr[one]; } //自底向上递推 for(int k=2;k<=kk;k++){ for(int one = k;one<=n;one++){ //求解当one和k定的时候,最大的分割点 long tempMax = Long.MIN_VALUE; long tempMin = Long.MAX_VALUE; for(int left = Math.max(k-1,one-dd);left<=one-1;left++){ if(tempMax<Math.max(f[left][k-1]*arr[one],g[left][k-1]*arr[one])){ tempMax=Math.max(f[left][k-1]*arr[one],g[left][k-1]*arr[one]); } if(tempMin>Math.min(f[left][k-1]*arr[one],g[left][k-1]*arr[one])){ tempMin=Math.min(f[left][k-1]*arr[one],g[left][k-1]*arr[one]); } } f[one][k] = tempMax; g[one][k] = tempMin; } } //n选k最大的需要从最后一个最大的位置选 long result = Long.MIN_VALUE; for(int one = kk;one<=n;one++){ if(result<f[one][kk]){ result = f[one][kk]; } } System.out.println(result); } } }
import java.util.Scanner;/** * @author shishusheng */import java.util.*;public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); //注意while处理多个case while (in.hasNext()) { int x = in.nextInt(); int y = in.nextInt(); char[][] points = new char[x][y]; int[][] tar = new int[x][y]; for (int i = 0; i < x; i++) { String str = in.next(); points[i] = str.toCharArray(); } int startX = in.nextInt(); int startY = in.nextInt(); int k = in.nextInt(); int[] stepX = new int[k]; int[] stepY = new int[k]; for (int i = 0; i < k; i++) { stepX[i] = in.nextInt(); stepY[i] = in.nextInt(); } Queue<Integer> xQueue = new LinkedList<>(); Queue<Integer> yQueue = new LinkedList<>(); //引入队列是为了遍历到最后不能走为止 xQueue.add(startX); yQueue.add(startY); //起始点访问标记;1表示已经访问 tar[startX][startY] = 1; while (!xQueue.isEmpty() && !yQueue.isEmpty()) { //取队首 startX = xQueue.remove(); startY = yQueue.remove(); for (int i = 0; i < k; i++) { //不出界 if (startX + stepX[i] < x && startX + stepX[i] >= 0 && startY + stepY[i] < y && startY + stepY[i] >= 0) { if (tar[startX + stepX[i]][startY + stepY[i]] == 0) { if (points[startX + stepX[i]][startY + stepY[i]] == '.') { tar[startX + stepX[i]][startY + stepY[i]] = tar[startX][startY] + 1; xQueue.add(startX + stepX[I]); yQueue.add(startY + stepY[I]); } else { //访问点为X tar[startX + stepX[i]][startY + stepY[i]] = -1; } } } } } int max = 0; int getRoad = 1; for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { if (points[i][j] == '.' && tar[i][j] == 0) { //有存在没有被访问的“.”说明不能遍历完全,有些出口到不了。 getRoad = 0; } max = Math.max(max, tar[i][j]); } } if (getRoad == 0) { System.out.println(-1); } else { System.out.println(max - 1); } } } }
3Fibonacci数列
import java.util.Scanner;/** * @author shishusheng */public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int a = 0, b = 1; //程序将b与N作比较,b>N时结束循坏 //这是就能找到N最接近的两个Fibonacci数,再找出最近的那个 while (b <= N) { /** * 爬楼梯思路,自底向上计算 * 等价于 * b = a+b; * a = b-a; */ int temp = a + b; a = b; b = temp; } //最后比较与a,b的位置,得出最近 System.out.print((b - N) > (N - a) ? N - a : b - N); } }
4数字反转
import java.util.Scanner;/** * 2018/3/25 * @author shishusheng */public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int x = input.nextInt(); int y = input.nextInt(); System.out.println(rev(rev(x)+ rev(rev(y)))); } public static int rev(int num){ int temp = 0; while(num>0){ //精妙之处!!! temp = temp*10+num%10; num/=10; } return temp; } }
5下厨房
import java.util.HashSet;import java.util.Scanner;/** * @author shishusheng */public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); //去除重复元素 HashSet<String> set = new HashSet<>(); while (in.hasNext()) { String str = in.nextLine(); String[] arr = str.split(" "); for (int i = 0; i < arr.length; i++) { set.add(arr[i]); } } System.out.println(set.size()); set.clear(); } }
import java.util.Scanner;/** * 只要考虑两个条件 * 第一,总数一定能被牛的数量整除 * 第二,每头牛比平均值多出来的苹果数一定能被2整除, * 不满足这两个条件的输出-1 * 满足的情况下,将比平均值多出的苹果数除2,就是移动次数 * @author shishusheng * @date 2018/3/25 */public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int num = in.nextInt(); int[] apples = new int[num]; //苹果总数 int sum = 0; for (int i = 0; i < num; i++) { int a = in.nextInt(); sum += a; //每头牛的苹果数 apples[i] = a; } //苹果牛均数 int avg = sum / num; //分的不均匀 if (sum % num != 0) { System.out.println(-1); return; } int res = 0; //对每头牛的苹果数 for (int n : apples) { if (n > avg) { //超出平均的部分 int over = n - avg; if (over % 2 != 0) { System.out.print(-1); return; } else { res += over / 2; } } } System.out.println(res); } } }
6
import java.util.*;/** * @author shishusheng */public class Main { /** * 判断是否根据长度排序 * * @param strings * @return false:不是根据长度排的 */ public static boolean isLenOrder(String[] strings) { int length = strings[0].length(); for (int i = 1; i < strings.length; i++) { //直接比较相邻项长度 if (length <= strings[i].length()) { length = strings[i].length(); } else { return false; } } return true; } /** * 判断是否根据字典序排列 * * @param strArr * @return false:不是根据字母顺序 true:根据字母顺序 */ public static boolean isCharOrder(String[] strArr) { ArrayList<String> list = new ArrayList<>(); for (int i = 0; i < strArr.length; i++) { list.add(strArr[i]); } //JDK自带的按字典序的标准结果 Collections.sort(list); String[] strHelpArr = new String[strArr.length]; for (int i = 0; i < strHelpArr.length; i++) { //整理出标准对照数组 strHelpArr[i] = list.get(i); } for (int i = 0; i < strHelpArr.length; i++) { //与标准对照比较 if (strArr[i] != strHelpArr[i]) { return false; } } return true; } public static void main(String[] args) { Scanner s = new Scanner(System.in); while (s.hasNext()) { int n = s.nextInt(); String[] strings = new String[n]; for (int i = 0; i < n; i++) { strings[i] = s.next(); } if (isLenOrder(strings) & isCharOrder(strings)) { System.out.println("both"); } else if (isLenOrder(strings) == false & isCharOrder(strings) == true) { System.out.println("lexicographically"); } else if (isLenOrder(strings) == true & isCharOrder(strings) == false) { System.out.println("lengths"); } else { System.out.println("none"); } } } }
7喜欢的数字
import java.util.Scanner;public class Main{ public static void main(String[] args) { String str=""; Scanner input = new Scanner(System.in); while (input.hasNext()){ str =input.next(); } char[] a = str.toCharArray(); for (int i = 0; i < a.length; i++) { if(a[i]<'A' || a[i]>'Z'){ System.out.println("Dislikes"); return; } if (i<a.length-1 &&a[i]==a[i+1]){ System.out.println("Dislikes"); return; } } System.out.println("Likes"); return; } }
方法二
import java.util.Scanner;/** * @author shishusheng */public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String word = sc.next(); if (isAllInitCapital(word) && isConEql(word) && isThrEql(word)) { System.out.println("Likes"); } else { System.out.println("Dislikes"); } } } /** * 条件1:单词每个字母都是大写字母 * * @param word * @return */ public static boolean isAllInitCapital(String word) { return word.matches("[A-Z]+"); } /** * 条件2:单词没有连续相等的字母 * * @param word * @return */ public static boolean isConEql(String word) { return !word.matches(".*(.)(\\1).*"); } /** * 单词没有形如“xyxy” * 这里的x,y指的都是字母,并且可以相同)这样的子序列,子序列可能不连续。 * * @param word * @return */ public static boolean isThrEql(String word) { return !word.matches(".*(.).*(.)(.*\\1)(.*\\2).*"); } }
8买苹果
//复杂度O(1)方法import java.util.*;/** * * O(1) * 对数字特征进行分析。 * * 6,8都是偶数。因此,能凑出的个数也是偶数。 * 程序中若苹果总数是奇数,直接返回-1。 * * 再次,偶数个苹果数对8取模,其结果只可能为0,2,4,6。 * 若余数为6或者0,则可以直接用6包装情况处理,不需要回溯购买8包装的情况。 * 若余数为4,只需回溯1次即可,因为8+4=12, 12%6 = 0。 * 若余数为2,只需回溯2次即可,因为8+8+2=18, 18%6 = 0。 * * 综上,可以采用如下思路进行处理。(由于数字6和8的特征,本方法只适用于本题) * * 情况1:若num不是偶数,则直接返回-1 * 情况2:若num%8 = 0,则返回num/8 * 情况3:若num%8 != 0,则只需回溯1次或者2次8包装购买个数,就可以求解。 * 回溯1次,其结果为n/8-1+2 = n/8+1; * 回溯2次,其结果为n/8-2+3 = n/8+1。 * 因此,可以情况3下,可以返回n/8+1。 * @author shishusheng */public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNextInt()) { int n = in.nextInt(); System.out.println(count(n)); } } public static int count(int n) { if (n % 2 != 0 || n == 10 || n < 6) { //一定是偶数(6,8都是),最小是6,10以上偶数都可以; return -1; } if (n % 8 == 0) { //如果拿八个拿完最好 return n / 8; } //对于10以上的偶数,只要对8取余数不为0,就要从前面的1或者2个8中拿出2个,把余数补为6(本来余数就是6,就不用拿)。所以+1; return 1 + n / 8; } }
9
作者:芥末无疆sss
链接:https://www.jianshu.com/p/dcbbe889b86a
來源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。