简单的算法题，聪明人来
呵呵，简单的题目还是要自己动手
我看了下；
第一个问题我目前没看到除了全排列外dp或者贪心可以解答的思路。
如果用全排列的话也没难度；如果可以用简单方法有子结构或者无后效性，答主麻烦@下我。
第二个问题没什么难度；就是输入输出，顺序程序的问题；
卧槽，本来搞完去吃早饭呢，现在可以吃午饭了，第二题不写了，擦
直接上码
public static void main(String[] args) {
//第一题
exc_1();
//第二题还是楼主自己搞吧，，蛋已碎，本以为就是个冒泡然后再想
}
/**
* 第一题
* 第一题其实可以变相成为一个排序题
* 卧槽，写了好久，本来以为就是一个冒泡而已
* 谁知道不对，最后整出来了
* 楼主看看吧
* 用的java
* 核心思想就是
* 分数小的气球总是先被打烂
* 分数大的留到最后
* 这样就能得最高分了
* 先冒泡排序，从大到小排
* 前两个数最大，接着把第三个数插入到两个数中间，顺便算下打烂这个球得到的分数
* 接着下一个，下一个，以此类推，干掉最后一个球，气球的最佳排序也给你搞出来了
*/
public static void exc_1(){
//n个气球
int n;
//n个气球的数字
int[] ab;
//最高得分
double sum = 0;
Scanner sc = new Scanner(System.in);
System.out.println("请输入气球的数量：");
n = getNum(sc);
System.out.println("请依次输入"+n+"个气球上面的数字:");
ab = new int[n];
for(int i=0;i<n;i++){
ab[i] = getNum(sc);
}
//下面是冒泡排序，把最大的排最前面
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(ab[i]<ab[j]){
int temp = ab[i];
ab[i] = ab[j];
ab[j] = temp;
}
}
}
//算法核心
switch (n) {
case 1:
sum = ab[0];
break;
case 2:
sum = ab[0]+ab[0]*ab[1];
break;
default:{
sum += ab[0]+ab[0]*ab[1];
//i表示从第三个数开始，往前面插入，找合适的位置插入
for(int i=2;i<n;i++){
int k = 1,m = 0;
double max = 0;
//找到前面数组两个数相乘最大的，就把数插在这两个数之间
//k表示左边的数下标
//m表示右边的数下标
for(int j = 1;j<i;j++){
if(max<ab[j]*ab[j-1]){
max = ab[j]*ab[j-1];
k = j;
m = j-1;
}
}
//找到后，赶紧计算分数，一会数组变顺序了就找不到了
sum += ab[i]*ab[k]*ab[m];
//交换位置，把第i个数插入那两个数之间
int temp = ab[i];
for(int p=i;p>k;p--){
ab[p] = ab[p-1];
}
ab[k] = temp;
}
}
break;
}
//遍历出气球的最终顺序
System.out.print("最佳排序为：\t");
for(int i=0;i<n;i++){
System.out.print(ab[i]+"\t");
}
System.out.println();
System.out.println("最高得分为："+sum);
}
/**
* 获取一个数字
* 防止楼主蛋疼输入字符啊之类的玩意
* @param sc
* @return
*/
public static int getNum(Scanner sc){
boolean isNum = true;
String a = "";
while(isNum){
a = sc.next();
char[] b = a.toCharArray();
int c = b.length;
int i = 0;
for(;i<c;i++){
if(b[i]<'0' || b[i] > '9'){
break;
}
}
if(i==c){
isNum = false;
}
if(isNum){
System.out.println("请不要输入英文或者符号，请输入数字：");
}
}
return Integer.parseInt(a);
}
本来lol又看到这茬了，哥就是固执，第一题，按照楼主的意思又搞一遍
直接上代码
/**
* 好吧，我又想了想
* 这是我的想法，不知道对不对，但是直觉告诉我是对的
* 当这个数组中的数大于等于3个时
* 先判断边上的两个数，看是否大于1
* 如果大于1就从固定两个数，从两个数中间开始打，从最小的打
* 如果等于1，那就直接干掉这个气球
* 之后接着判断，递归直到只剩两个数
* 两个数的时候，直接打小的，再打大的。
*/
int[] a = {4,6,8,9,2,1};
int len = a.length;
//分数
double sum = 0;
//初始化左右边界
int left = 0;
int right = len-1;
//首先判断边界
while(right >= left){
if(a[left]==1){
int temp = a[left];
//干掉这个气球记分
sum += 1.0*a[left+1];
//干掉气球后，气球位置变动
//此时只用变left的值即可
//right值则不变
left++;
continue;
}
if(a[right]==1){
int temp = a[right];
//方式同上
sum += 1.0*a[right];
//左边界向右递增，右边界向左递减
right--;
continue;
}
//此时左右边界均不为1，从中间小的开始干起
//最小的数，不包括边界
//令人蛋疼的是，最小的数可能有相等的，草！！！
int minIndex = left;
//所以整一个数，记录最小数乘以两边的数的乘积
//比较两个相等气球的得分决定打哪个，相等就打前一个
double sumTemp = 0;
/**
* 判断此时剩下的气球的数量
* right-lfet
* 0:只剩下一个气球了
* 1:还有两个气球
* 大于1则还有三个或者三个以上的气球
*
*/
switch (right-left) {
case 0:
sumTemp =1.0*a[left];
break;
case 1:
minIndex = a[left]<a[right]?left:right;
sumTemp = 1.0*a[left]*a[right];;
break;
default:
//遍历边界中的数，找到最小的，并记录他的下标
minIndex = left+1;
sumTemp = 1.0*a[minIndex-1]*a[minIndex]*a[minIndex+1];
for(int i=left+1;i<right;i++){
if(a[minIndex]>a[i]){
minIndex = i;
}else if(a[minIndex] == a[i]){
double sumTemp2 = a[i-1]*a[i]*a[i+1];
if(sumTemp2 > sumTemp){
minIndex = i;
sumTemp = sumTemp2;
}else{
//啥也不做
}
}else{
//什么也不做
}
}
break;
}
//计算得分
sum += sumTemp;
//移动数组里面的数，划分边界
//如果想保持数组里面的数与之前一致，再加一个数
int temp = a[minIndex];
for(int i=minIndex;i<right;i++){
a[i] = a[i+1];
}
//还原到原来的位置
a[right] = temp;
right --;
}
System.out.println(sum);
class Solution {
public:
int maxCoins(vector& nums) {
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.push_back(1);
vector > dp(nums.size(), vector(nums.size() , 0));
for (int len = 1; len <= n; ++len) {
for (int left = 1; left <= n - len + 1; ++left) {
int right = left + len - 1;
for (int k = left; k <= right; ++k) {
dp[left][right] = max(dp[left][right], nums[left - 1] * nums[k] * nums[right + 1] + dp[left][k - 1] + dp[k + 1][right]);
}
}
}
return dp[1][n];
}
};
能解释这段程序就行了
而且第一题只是看起来简单，其实是有陷阱的，比如说最原始的方法，因为n和m都是10的5次方，最坏情况是10亿，可以改进成每次查询看在不在左右边界里，但最坏也有2.5亿，所以题目很简单，但是怎么优化到第时间复杂度才是难点