1、来自网易：
为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
思路：按照工作难度进行排序，这里用到了Arrays.sort(),重写了compare方法。再按照dp的方法，每次比较和前一项工作获利最大的填入map。最后直接取map.floorKey()(方法调用返回的最大键小于等于key，或者null，如果不存在这样的键)
import java.util.*;
public class Main{
ublic static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
TreeMap<Integer, Integer> map=new TreeMap<>();
int m=sc.nextInt();//工作的数量
int n=sc.nextInt();//小伙伴的数量
int[][] work=new int[m][2];
for(int i=0;i<m;i++){
work[i][0]=sc.nextInt();//工作难度
work[i][1]=sc.nextInt();//工作获利
}
//按工作难度排序
Arrays.sort(work,new Comparator<int[]>() {
public int compare(int[] num1,int[] num2){
return num1[0]-num2[0];
}
});
//dp使相应的工作难度获利最大，并把结果存入map中
for(int i=1;i<m;i++){
work[i][1]=Math.max(work[i-1][1], work[i][1]);
map.put(work[i-1][0], work[i-1][1]);
}
//最后一项加入map
map.put(work[m-1][0], work[m-1][1]);
for(int i=0;i<n;i++){
//根据工作难度找工作
int d=sc.nextInt();
Integer index=map.floorKey(d);
if(index!=null){
System.out.println(map.get(index));
}else{
System.out.println(0);
}
}
}
}
2、题目：整数成绩最大化
给出一个整数n，将n分解为至少两个整数之和，使得这些整数的乘积最大化，输出能够获得的最大的乘积。
例如：
2=1+1，输出1；
10=3+3+4，输出36。
输入为1个整数，输出为1个整数
示例1：输入：10，输出：36
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
//2和3单独处理
if(n==2){
System.out.println(1);
return;
}
if(n==3){
System.out.println(2);
return;
}
System.out.println(getResult(n));
}
//最优化问题，尽量都分成3，不足部分就分成2
static long getResult(int n){
long result=1;
while(n>4){
result=result*3;
n-=3;
}
result = result*n;
return result;
}
}
3、题目：寻找合法字符串
给出一个正整数n，请给出所有的包含n个'('和n个')'的字符串，使得'('和')'可以完全匹配。
例如：
'(())()'，'()()()' 都是合法的；
'())()('是不合法的。
请按照字典序给出所有合法的字符串。
示例1：输入：2 输出：(()),()()
由于字符串只有左括号和右括号两种字符，而且最终结果必定是左括号3个，右括号3个，所以我们定义两个变量left和right分别表示剩余左右括号的个数，如果在某次递归时，左括号的个数大于右括号的个数，说明此时生成的字符串中右括号的个数大于左括号的个数，即会出现')('这样的非法串，所以这种情况直接返回，不继续处理。如果left和right都为0，则说明此时生成的字符串已有3个左括号和3个右括号，且字符串合法，则存入结果中后返回。如果以上两种情况都不满足，若此时left大于0，则调用递归函数，注意参数的更新，若right大于0，则调用递归函数，同样要更新参数。代码如下：
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
List<String> list=new ArrayList<>();
DFS(n,n,"",list);
Collections.sort(list);
for(int i=0;i<list.size();i++){
if(i<list.size()-1){
System.out.print(list.get(i)+",");
}else{
System.out.print(list.get(i));
}
}
}
static void DFS(int left,int right,String result,List<String> list){
if(left<0||right<0||left>right){
return;
}
if(left==0&&right==0){
list.add(result);
return;
}
DFS(left-1,right,result+"(",list);
DFS(left,right-1,result+")",list);
}
}
引申：全排列的递归算法
算法思路：
(1)n个元素的全排列=（n-1个元素的全排列）+（另一个元素作为前缀）；
(2)出口：如果只有一个元素的全排列，则说明已经排完，则输出数组；
(3)不断将每个元素放作第一个元素，然后将这个元素作为前缀，并将其余元素继续全排列，等到出口，出口出去后还需要还原数组；
4、Map：
Map<String,Integer> map=new Hashmap<>();
(1)int t=map.get(str);
(2) for(String key:map.keySet()){
if(str.equals(key)){
int i=map.get(key);
map.put(str,i+1);
}else{
map.put(str,1);
}
}
6、题目：
给定一个整型数组a (int[])，包含N个元素。判断是否这N个整数可以构造出一个 "按位与等式"，即是否存在这样一个等式：将数组中的任意N-1个整数进行按位求与操作(即Java中的"&"操作)，得到的结果等于剩下的那个整数，注意这N个整数在等式中均必须出现且只出现一次。举例一：给定一个数组[5，20，4]，结果为：true，因为 "20 & 5 = 4"。举例二：[5，3，7，19]，结果为：false，因为数组中任何三个整数按位取与，均无法等于剩下的那个整数。请按如下函数定义，写出你的程序。（注：不能使用本地IDE）
boolean isAndEqationExist(int[] a);
分析：一个重要的点是，等号右边的数字的特征：因为是求与的结果，所以必然是最小的数字。如果能分析到这个点，则只需要一次求与的尝试，即可得出结论。
即每次都遍历找最小值，同时求它们相与的结果，（一个数与自己是不变的），结果等于最小值，则返回true；
boolean isAndEqationExist(int[] a) {
if (a == null || a.length == 0)
return false;
int s = a[0];
int min = s;
for (int i = 1; i < a.length; i++) {
s &= a[i];
if (min > a[i])
min = a[i];
}
if (min == s)
return true;
return false;
}
7、
动态规划！！！
当求解的问题满足以下两个条件时， 就应该使用动态规划：
（1）主问题的答案 包含了 可分解的子问题答案 （也就是说，问题可以被递归的思想求解）
（2）递归求解时， 很多子问题的答案会被多次重复利用
动态规划的本质思想就是递归， 但如果直接应用递归方法， 子问题的答案会被重复计算产生浪费， 同时递归更加耗费栈内存（具体为什么更加消耗栈内存， 需要额外了解函数调用过程中， 进程栈内存的管理方式），所以通常用一个二维矩阵（表格）来保存不同子问题的答案， 避免重复计算
例题：合唱团（2016网易）
有 n 个学生站成一排，每个学生有一个能力值，从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，返回最大的乘积。 每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。
思路：
因为有正有负，负负得正，所以要维护两个dp数组，一个存储最大，一个存储最小。
定义fmax[k][i]表示当选中了k个学生，并且以第i个学生为结尾，所产生的最大乘积；fmin[k][i]表示 当选中了k个学生，并且以第i个学生为结尾，所产生的最小乘积；
当前的最大fmax[k+1][i+1]应该是前面产生的最大乘积当前学生的能力值。那么fmax[k+1][i+1]=max(fmax[k][i]stu[i+1],fmin[k][i]stu[i+1])，即当选中了k个学生后，再选择第i+1编号学生，所产生的最大乘积；
同理fmin[k+1][i+1]=min(fmin[k][i]stu[i+1],fmax[k][i]*stu[i+1])。
最后，遍历一遍fmax[K][i]求得最大值（i从1～N）。
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNextInt()){
int n=sc.nextInt();
int arr[]=new int[n+1];
for(int i=1;i<=n;i++){
arr[i]=sc.nextInt();
}
int k=sc.nextInt();
int d=sc.nextInt();
long[][] fmax=new long[k+1][n+1];//记录最大乘积
long[][] fmin=new long[k+1][n+1];//记录最小乘积
// fmax[k][i]表示 : 当选中了k个学生，并且以第i个学生为结尾，所产生的最大乘积；
// fmin[k][i]表示 : 当选中了k个学生，并且以第i个学生为结尾，所产生的最小乘积；
long result=Integer.MIN_VALUE;
for(int i=1;i<=n;i++){
fmax[1][i]=arr[i];
fmin[1][i]=arr[i];
for(int m=2;m<=k;m++){//m是选中的学生数，要构造选中序列，最多选中k个学生
for(int j=i-1;j>0&&i-j<=d;j--){//j是从第i位往前，控制序列的位置范围不超过d
fmax[m][i]=Math.max(fmax[m][i],Math.max(fmax[m-1][j]*arr[i],fmin[m-1][j]*arr[i]));
//fmax[m][i]记录下每个i对应的最大乘积，每次要先和上次的最大乘积还有这次往前增加了一位之后的位置fmax[m-1][j](m-1是因为如果m=2，就是0或者1)或者fmin[m-1][j]与当前值arr[i]的乘积的最大值，再做比较求最大
fmin[m][i]=Math.min(fmin[m][i],Math.min(fmax[m-1][j]*arr[i],fmin[m-1][j]*arr[i]));
//最小值和最大值道理一样
}
}
result=Math.max(result,fmax[k][i]);//相当于递归找出最大的乘积
}
System.out.println(result);
}
}
}
