1.题目描述
有一个整数n，将n分解成若干个不同自然数之和，问如何分解能使这些数的乘积最大，输出这个乘积m。
输入：一个整数
输出：
一个整数
样例输入：
15
样例输出：
144
解题思路：
要求乘积最大，就得让每一个数尽量地接近，从2,开始分，最后剩下的数依次从后面加到前面的数上面（每个数加上1）。例如10，分开后是2,3,4,剩下1，加到最后面的4上变成2,3,5。如果是18，依次是2,3,4,5，剩下4，依次加到前面的数上是3,4,5,6。
代码如下：
import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scc=new Scanner(System.in); int n = scc.nextInt(); String result = solve(n); System.out.println(result); } public static String solve(int num){ BigInteger big1=new BigInteger("1"); int a[]=new int[3000]; int n = num; int sum=2; a[0]=2; int i=1; int j=0; while(true){ a[i]=a[i-1]+1; if(sum+a[i]>n){ break; }else{ sum+=a[i]; } i++; } a[i]=n-sum; //剩余的数 j=i-1; // System.out.println(a[i]); int mm = a[i]/(j+1); int nn = a[i]%(j+1); for(int x=0;x<i;x++){ a[x]+=mm; } for(int y=0;y<nn;y++){ a[j]++; j--; } for(int k=0;k<i;k++){ // System.out.print(a[k]+" "); big1=big1.multiply(BigInteger.valueOf(a[k])); } return big1.toString(); } }
2.题目描述
拼图，是一个老少皆宜的益智游戏，在打乱的3*3的范围中，玩家只能每次将空格(0)和相邻的数字格（上、下、左、右）交换，最终调整出一个完整的拼图。
完整拼图为：
1 2 3
4 5 6
7 8 0
输入：测试数据共3行，每行3个数字 ，包括数字0、1、2、3.....8（无重复）
输出：
还原完整拼图的最少移动次数。如不需要调整，则输出0；如无解，则输出-1。
例如：
0 1 3
4 2 5
7 8 6
依次移动1,2,5,6，即可还原为正确拼图，移动次数为4
样例输入：
0 1 3
4 2 5
7 8 6
样例输出：
4
解题思路：
广度优先搜索
代码如下：
import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; import java.util.Scanner; import java.util.Set; import java.util.HashSet; import java.util.ArrayList; import java.lang.StringBuilder; public class Main{ public static String destNumbers = "123456780"; public static Set<Integer> set = new HashSet<Integer>(); public static int[]moveTable = new int[]{12,14,10,13,15,11,5,7,3}; public static ArrayList<Node> getNextMoveList(Node pNode){ int position = pNode.numbers.indexOf("0"); int moveStatus = moveTable[position]; ArrayList<Node> cNodes = new ArrayList<Node>(); for(int status=1; status <=8; status=status<<1){ if((moveStatus & status) > 0){ char[] charNumbers = pNode.numbers.toCharArray(); int switchPosition = 0; if(status == 1){ switchPosition = position - 3; } else if(status == 2){ switchPosition = position - 1; } else if(status == 4){ switchPosition = position + 1; } else if(status == 8){ switchPosition = position + 3; } charNumbers[position] = charNumbers[switchPosition]; charNumbers[switchPosition] = '0'; String s = String.valueOf(charNumbers); if(!set.contains(Integer.valueOf(s))){ set.add(Integer.valueOf(s)); Node n = new Node(pNode, s, charNumbers[position]); cNodes.add(n); } } } return cNodes; } static int getResult(Node node){ String result = ""; while(node.parentNode != null){ result += node.currentNum; node = node.parentNode; } return new StringBuffer(result).reverse().toString().length(); } static int run(String numbers){ if(numbers.equals(destNumbers)){ return 0; } ArrayList<Node> numsList = new ArrayList<Node>(); numsList.add(new Node(null, numbers, ' ')); while(numsList.size() > 0){ ArrayList<Node> tmpList = new ArrayList<Node>(); for(Node pNode : numsList){ ArrayList<Node> cNodes = getNextMoveList(pNode); for(Node cNode : cNodes){ if(cNode.numbers.equals(destNumbers)){ return getResult(cNode); } tmpList.add(cNode); } } numsList = tmpList; } return -1; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); String numbers = new String(); for(int rows=3; rows>0; rows--){ for(String n: scan.nextLine().split(" ")){ numbers += n; } } int res = run(numbers); System.out.println(String.valueOf(res)); } } class Node { public Node(Node parentNode, String numbers, char currentNum){ this.numbers = numbers; this.currentNum = currentNum; this.parentNode = parentNode; } public char currentNum; public String numbers; public Node parentNode; }
3.题目描述
一个一维数组，记录n天中每天的携程股价。
股市交易规则如下：
a）一天只能有买进或者卖出一种操作，也可以不做任何操作，卖出时价格减买入时价格即为收益
b）每次卖出操作后有冻结期，k天之后才能进行下一次买进操作（k>=1）
c）买进之后必须卖出才能再次买进
设计一个算法，找到交易收益最大化的买进卖出策略，返回最后的最大收益值
输入：
一维正整数数组，表示每天股价 （一维正整数数组，表示每天股价）
输出：
返回最大收益
样例输入：
int[] sotckPrice = {1,2,3,5,2,6,3,7};
int k = 2;
输入为
8（表示数组长度）
1（开始依次输入数组元素）
2
3
5
2
6
3
7
2（输入k）
样例输出：
8 (1买进，5卖出，3买进，7卖出，收益最大为8)
解题思路：
扫描序列，按照题意判断冷却时间，然后更新答案
代码如下：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
int n = scanner.nextInt();
int stockPrice[] = new int[n+1];
for(int i=1;i<=n;i++){
stockPrice[i] = scanner.nextInt();
}
int k = scanner.nextInt();
System.out.println(getMaxProfit(n, stockPrice, k));
}
scanner.close();
}
private static int getMaxProfit(int n,int stockPrice[],int k) {
int cur=-1000000000, ans=0;
int dp[] = new int[n+1];
for(int i=1;i<=n;i++){
dp[i] = Math.max(stockPrice[i]+cur, dp[i-1]);
if(i>=k){
cur = Math.max(cur, dp[i-k]-stockPrice[i]);
}else{
cur = Math.max(cur, -stockPrice[i]);
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
}
