“365算法每日学计划”：java语言基础题目及解答（11-15打卡）
“365算法每日学计划”：java语言基础题目及解答（11-15打卡）
自从开始做公众号开始，就一直在思考，怎么把算法的训练做好，因为思海同学在算法这方面的掌握确实还不够。因此，我现在想做一个“365算法每日学计划”。
“计划”的主要目的：
1、想通过这样的方式监督自己更努力的学习算法。
2、想和小伙伴们“组团”一起来学习交流学习算法过程中的点点滴滴。
“计划”的主要内容：
1、数据结构和算法的基础知识巩固。
2、逐步进阶的oj算法训练。
“计划”的时间安排：每周三和周六
——说在前面
365算法每日学计划
发表于2018-07-07思海同学
“算法每日学”11打卡 问题描述: 写一个算法计算出n的阶乘。 n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1 1<=n<=10. 输入： 任意一个数字n。 输出： 数字n的阶乘结果。
题目简单，请小伙伴自行思考，谢谢
365算法每日学计划
发表于2018-07-07思海同学
“算法每日学计划”12打卡： 问题描述 输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。 输入格式 输入一行，包含一个表达式。 输出格式 输出这个表达式的值。 样例输入 1-2+3*(4-5) 样例输出 -4 数据规模和约定 表达式长度不超过100，表达式运算合法且运算过程都在int内进行。
解题思路：
注意：解答群里的小伙伴提供的，感谢！ 1,初始化两个栈：运算符栈S1和储存中间结果的栈S2； 2,从左至右扫描中缀表达式； 3,遇到操作数时，将其压入S2，这里由于运算数可能大于10，所以如果数字后面一个符号是运算符，则将‘#’入S2栈充当分割线； 4, 遇到运算符时有三种情况： (4-1) 三种情况下直接入S1栈①S1为空②运算符为‘（’③运算符优先级比S1栈顶运算符的高； (4-2)如果右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃； (4-3) 若运算符优先级小于或等于S1栈顶运算符的优先级，则依次弹出S1栈顶元素，直到运算符的优先级大于S1栈顶运算符优先级； 5, 重复步骤(2)至(5)，直到表达式的最右边； 6,将S1中剩余的运算符依次弹出并压入S2； 7,依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
题解
import java.util.Scanner;
import java.util.Stack;
public class Main{
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
Stack<Integer> nums = new Stack<Integer>(); // 保存数字
Stack<Character> opes = new Stack<Character>(); // 保存操作符
String string = scanner.nextLine();
int n = 0; // 保存每一个数字
char[] cs = string.toCharArray();
for (int i = 0; i < cs.length; i++) {
char temp = cs[i];
if (Character.isDigit(cs[i])) {
n = 10 * n + Integer.parseInt(String.valueOf(cs[i])); // 大于10的数字保存
} else {
if (n != 0) {
nums.push(n);
n = 0;
}
if (temp == '(') {
opes.push(temp);
} else if (temp == ')') {
while (opes.peek() != '(') { // 括号里面运算完
int t = cal(nums.pop(), nums.pop(), opes.pop());
nums.push(t);
}
opes.pop();
} else if (isType(temp) > 0) {
if (opes.isEmpty()) { // 栈为空直接入栈
opes.push(temp);
} else {
// 若栈顶元素优先级大于或等于要入栈的元素,将栈顶元素弹出并计算,然后入栈
if (isType(opes.peek()) >= isType(temp)) {
int t = cal(nums.pop(), nums.pop(), opes.pop());
nums.push(t);
}
opes.push(temp);
}
}
}
}
// 最后一个字符若是数字,未入栈
if (n != 0) {
nums.push(n);
}
while (!opes.isEmpty()) {
int t = cal(nums.pop(), nums.pop(), opes.pop());
nums.push(t);
}
System.out.println(nums.pop());
}
// 返回的是运算符的优先级,数字和()不需要考虑
public static int isType(char c) {
if (c == '+' || c == '-') {
return 1;
} else if (c == '*' || c == '/') {
return 2;
} else {
return 0;
}
}
// 运算次序是反的,跟入栈出栈次序有关
public static int cal(int m, int n, char c) {
int sum = -987654321;
if (c == '+') {
sum = n + m;
} else if (c == '-') {
sum = n - m;
} else if (c == '*') {
sum = n * m;
} else if (c == '/') {
sum = n / m;
}
return sum;
}
}365算法每日学计划
发表于2018-07-07思海同学
“算法每日学计划”13打卡： 问题描述 给两组数，各n个。 请调整每组数的排列顺序，使得两组数据相同下标元素对应相乘，然后相加的和最小。要求程序输出这个最小值。 例如两组数分别为:1 3 -5和-2 4 1 那么对应乘积取和的最小值应为： (-5) * 4 + 3 * (-2) + 1 * 1 = -25 输入格式 第一个行一个数T表示数据组数。后面每组数据，先读入一个n，接下来两行每行n个数，每个数的绝对值小于等于1000。 n<=8,T<=1000 输出格式 一个数表示答案。 样例输入 2 3 1 3 -5 -2 4 1 5 1 2 3 4 5 1 0 1 0 1 样例输出 -25 6
注意： 这个是群里小伙伴的解答。
这里写图片描述
题目思路：最主要的逻辑是弄清楚，题目说和最小，其实就是第一行最小乘以第二行最大，第一行次小乘以第二行次大的和，弄清楚了这一点就迎刃而解了，当然为了减轻运算量，我们可以都从小到大排列，然后通过算法交叉相乘。
题解：
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int Num=in.nextInt();
int i=0,j=0,k=0,c=0;
int[] NumArr=new int[Num];
for(;c<Num;c++){
int m=in.nextInt();//每组数据中有m个元素
int[][] a=new int[2][m];
for(i=0;i<2;i++){
for(j=0;j<m;j++){
a[i][j]=in.nextInt();
}
}
int temp=0,sum=0;
for(i=0;i<2;i++){
for(j=0;j<m-1;j++){
for(k=j;k<m;k++){
if(a[i][j]>a[i][k]){
temp=a[i][j];
a[i][j]=a[i][k];
a[i][k]=temp;
}
}
}
}
for(j=0;j<m;j++){
sum+=(a[0][j]*a[1][m-j-1]);
}
NumArr[c]=sum;
}
for(c=0;c<Num;c++){System.out.println(NumArr[c]);}
}
} 365算法每日学计划
发表于2018-07-07思海同学
“算法每日学计划”14打卡： 描述 输入三个字符（可以重复）后，按各字符的ASCII码从小到大的顺序输出这三个字符。 输入 第一行输入一个数N,表示有N组测试数据。后面的N行输入多组数据，每组输入数据都是占一行，有三个字符组成，之间无空格。 输出 对于每组输入数据，输出一行，字符中间用一个空格分开。 样例输入 2 qwe asd 样例输出 e q w a d s
java：
import java.util.*;
public class Main { //程序入口
public static void main(String[] args) throws Exception { //应程序要求，OJ规范，抛出异常
Scanner cin = new Scanner(System.in); //采用Scanner读取控制台
int a = cin.nextInt(); //记录数据组数
for (int n=a; n>=1; n--) { //每组
char m, v, p; //记录三个char字符
String s1 = cin.next(); //Scanner读入的是一个String
//读取字符串中的字符
m = s1.charAt(0);
v = s1.charAt(1);
p = s1.charAt(2);
sort1(m, v, p); //方法调用
}
}
//方法：输入三个字符（可以重复）后，按各字符的ASCII码从小到大的顺序输出这三个字符。
public static void sort1(char a, char b, char c) {
char t1 = a; //分别定义三个char变量用于记录形参传来的三个值
char t2 = b;
char t3 = c;
char t; //临时变量
//三个数字，按增序输出
if (t1 > t2) { //如果第一个数大于第二个数，交换第一个数和第二个数
t = t1; //交换t1和t2
t1 = t2;
t2 = t;
}
//此时第一个数一定比第二个数小
if(t3 < t1)//若第三个数比t1小
System.out.println(t3 + " " + t1 + " " + t2 + "\n");
else if(t3 > t2) //若第三个数比t2大
System.out.println(t1 + " " + t2 + " " + t3 + "\n");
else //第三个数介于t1和t2之间
System.out.println(t1 + " " + t3 + " " + t2 + "\n");
}
}如果有小伙伴用c++的话，可以看看这个，效率更好：
#include <iostream>
using namespace std;
void sort1(char a, char b, char c) //输入三个字符，按字符的ASCII码从小到大的顺序输出这三个字符
{
char t1 = a; //分别定义三个char变量用于记录形参传来的三个值
char t2 = b;
char t3 = c;
char t; //临时变量
//三个数字，按增序输出
if (t1 > t2) //如果第一个数大于第二个数，交换第一个数和第二个数
{
t = t1; //交换t1和t2
t1 = t2;
t2 = t;
}
//此时第一个数一定比第二个数小
if(t3 < t1) //若第三个数比t1小
cout << t3 << " " << t1 << " " << t2 << endl;
else if(t3 > t2) //若第三个数比t2大
cout << t1 << " " << t2 << " " << t3 << endl;
else //第三个数介于t1和t2之间
cout << t1 << " " << t3 << " " << t2 << endl;
}
int main() //程序入口
{
int a; //记录循环次数
cin >> a;
for (int n=a; n>=1; n--)
{
char a,b,c;
cin >> a >> b >> c;
sort1(a, b, c);
}
return 0;
}365算法每日学计划
发表于2018-07-07思海同学
“算法每日学计划”15打卡： 时间限制：1.0s 内存限制：256.0MB 问题描述 已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。 输入格式 输入一个正整数N。 输出格式 输出一个整数，表示你找到的最小公倍数。 样例输入 9 样例输出 504 数据规模与约定 1 <= N <= 106。
注意：群里小伙伴解答，感谢！
解题思路： 思路分析：最大 最小公倍数，联想到两个数的求最大最小公倍数，即两个数的乘积（注：连续的两个自然数是互斥的）。
同样，我们可以拿最后三个数来做考虑。
1.当n为奇数时，n，n-1，n-2为奇偶奇，里面只有一个偶数，所以不会有2这个因子。这三个数相差不到3，所以也不会有因子3，故符合题意。
2.当n为偶数时，n，n-1，n-2为偶奇偶，此时n，n-2肯定含有因子2，所以除于2不值得。所以考虑将n-2 换成n-3，变成奇偶奇，此时也有一个问题，
n和n-3，如果n%3==0，则除于3更不值得。仍根据奇偶奇的原则，变动偶数n为n-2，此时换成n-1，n-2，n-3和1情况一样。故此时符合题意。
这里写图片描述