A.带分数
题目：
100可以表示为带分数的形式：100 = 3 + 69258/714。
还可以表示为：100 = 82 + 3546/197。
注意特征：带分数中，数字 1 ~ 9 分别出现且只出现一次（不包含 0）。
类似这样的带分数，100 有 11 种表示法。
给出一个数，得到它能够用带分数表示的个数。
思路：
枚举出所有可能性。数字1到9只出现一次的话可以先创建一个1~9之间所有数字都只出现一次的数组，然后将这个数组全排列，每次排列都进行一次验证。
代码：
点击查看代码
import java.util.Scanner;
public class Main {
static int ans;
private static int N;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
N = scanner.nextInt();
int[] arr = {1,2,3,4,5,6,7,8,9};
f(arr,0);
System.out.println(ans);
scanner.close();
}
private static void f(int[] arr,int k) {
if(k==9)
{
check(arr);
return;
}
for(int i=k;i<arr.length;i++) {
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
f(arr,k+1);
temp = arr[i];
arr[i]=arr[k];
arr[k]=temp;
}
}
private static void check(int[] arr) {
for(int i = 1;i <= 7;i++) {
int num1 = toNum(arr,0,i);
if(num1>=N) continue;
for(int j=1;j<=8-i;j++) {
int num2=toNum(arr,i,j);
int num3=toNum(arr,i+j,9-i-j);
if(num2%num3 == 0 && num1+num2/num3==N) {
ans++;
}
}
}
}
private static int toNum(int[] arr,int position,int length) {
int times=1;
int result = 0;
for(int i = position+length-1;i>=position;i--) {
result += arr[i] * times;
times *= 10;
}
return result;
}
}
小结：本题用到了全排列，以后碰到类似数字只能出现一次的情况，就可以用这种方法去解决。然后就是考虑到‘+’和‘/’的放置问题。
B.错误票据
题目：
每张票据有唯一的 ID 号，全年所有票据的 ID 号是连续的，但 ID 的开始数码是随机选定的。因为工作人员疏忽，在录入 ID 号的时候发生了一处错误，造成了某个 ID 断号，另外一个 ID 重号。
你的任务是通过编程，找出断号的 ID 和重号的 ID。
数据保证断号不可能发生在最大和最小号。
第一行输入一个整数N，后面输入N行数据，每一行的数据是不同的，中间用空格分开。
思路：
这道题就是在一个连续的数字集合中找到中间断掉的一个数和重复的一个数，难点在于前面的输入部分。采用字符串的输入方式输入一行，然后用空格分开，再转化为整型排序，用两个指针比对就能够找出来。
代码：
点击查看代码
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<Integer>();
int N = scanner.nextInt();
scanner.nextLine(); //记住吃掉整数后面的换行符，不然会报错
for( int i = 0;i<N;i++) {
String line = scanner.nextLine();//先读取一行
String[] split=line.split(" ");//再分隔
for(int j = 0;j < split.length;j++) { //分隔后转化为整数放进集合，这样多行数据最后会变成一行
list.add(Integer.parseInt(split[j]));
}
}
Collections.sort(list);
int a=0,b=0;
for(int i = 1;i<list.size();i++) {
if(list.get(i)-list.get(i-1)==2){
a = list.get(i)-1;
}
if(list.get(i).equals(list.get(i-1))) {
b = list.get(i);
}
}
System.out.println(a+" "+b);
scanner.close();
}
}
小结：本题用到的输入方式对于java来说比较特别，可以记住这种输入方式，以后可能会用到。
C.翻硬币
题目：
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零），比如可能情形是 oooooo，如果同时翻转左边的两个硬币，则变为 oooo**oooo。现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币，那么对特定的局面，最少要翻动多少次呢？
思路：
本题求最少次数，就是先找到不同的地方然后从左到右依次两个两个地翻就能够求到最小次数。
代码：
点击查看代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String m = scanner.nextLine();
String n = scanner.nextLine();
char[] origin = new char[1000];
char[] changed = new char[1000];
origin = m.toCharArray();
changed = n.toCharArray();
Coin(origin,changed);
}
public static char rese(char ch) {
if(ch=='o')
return ch='*';
else if(ch == '*')
return ch='o';
else
return ' ';
}
public static void Coin(char[] origin,char[] changed) {
int count = 0;
for(int i = 0;i < origin.length;i++) {
if(origin[i]!=changed[i]) {
origin[i] = rese(origin[i]);
origin[i+1] = rese(origin[i+1]);
count++;
}
else
continue;
}
System.out.println(count);
}
}
小结：本题主要是根据题目给的样例找出规律进行解答。
D.灵能传输
这道题我还没弄懂，后面学了相关算法知识再尝试解决。
E.后缀表达式
题目：
给定 N 个加号、 M 个减号以及 N+M+1 个整数 A1,A2,A{N+M+1}，小明想知道在所有由这 N 个加号、 M 个减号以及 N+M+1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个。
请你输出这个最大的结果。
例如使用 1 2 3 + -，则 2 3 + 1 - 这个后缀表达式结果是 4，是最大的。
思路：
这道题首先要弄懂后缀表达式，与我们平时使用的是中缀表达式是不同的。然后就是要注意一下m为0的情况是可以直接加的，m!=0时，我们先给数组排个序，然后用最大值减去最小值，其余的数如果和符号组成负数，放在括号的里面，就能变成正数，如果是正数，就直接放在括号的外面，这样不管是正数还是负数相加就行，只要一个最大值减最小值就行，其余的相加。
代码：
点击查看代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
long[] nums = new long[n + m + 1];
for (int i = 0; i < n + m + 1; i++) {
nums[i] = scanner.nextLong();
}
long sum = 0;
if (m == 0) {
for (int i = 0; i < n + m + 1; i++) {
sum += nums[i];
}
} else {
Arrays.sort(nums);
sum += Math.abs(nums[0] - nums[n + m]);
for (int i = 1; i < n + m; i++) {
sum += Math.abs(nums[i]);
}
}
System.out.println(sum);
scanner.close();
}
}
小结：做这种题要从各个方面去考虑，需要仔细地分类讨论一下。
F.等差数列
题目：
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 \(N\) 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？
例如：包含 2,6,4,10,20 的最短的等差数列是 2,4,6,8,10,12,14,16,18,20。
思路：
首先排下序，然后找到所有相邻数的差的最大公因数，然后就能得到这个最小等差数列。
代码：
点击查看代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
for(int i=0;i<arr.length;i++){
arr[i] = scanner.nextInt();
}
Arrays.sort(arr,0,n);
int d = 0;
for(int i = 1;i<n-1;i++){
d=gcd(d,arr[i+1]-arr[i]);
}
if(d==0){
System.out.println(n);
}
else{
int len=(arr[n-1]-arr[0])/d+1;
System.out.println(len);
}
scanner.close();
}
public static int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
}
小结：这道题主要就是求一个最大公因数，类似这些基础的算法一定要把基础打牢。
G.特别数的和
题目：
小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 00），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 n 中，所有这样的数的和是多少？
思路：
这道题主要就是找数然后加起来，看一个数里面是否包含一个个位数就是不断取10的余数，如果余数中有的话就有。
代码：
点击查看代码
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int sum=0;
for(int i=1;i<=n;i++) {
int num=i;
while(num!=0) {
int result = num%10;
if(result == 2||result == 0||result == 1||result == 9) {
sum+=i;
break;
}
num=num/10;
}
}
System.out.println(sum);
scanner.close();
}
}
小结：从本题中我抽取到了这种找数的方法。
H.完全二叉树的权值
题目：
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1,A2, AN，如下图所示：
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 1。
思路：
将每一个深度的权值之和放到一个数组中，然后取最大值就可以了。注意弄清楚完全二叉树和满二叉树的区别，不然会造成数组越界。
代码：
点击查看代码
import java.util.Scanner;
public class MainH {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[] arr = new int[N];
int count=0,num = N;
for(int i = 0;i < N;i++) {
arr[i] = scanner.nextInt();
}
while(num>=1) {
num = num/2;
count++;
}
int[] arr1 = new int[count];
int max = arr[0];
int sum = 0;
int maxi = 0;
for(int i = 0;i < count;i++) {
sum = 0;
if(i==count-1) {
for(int j = (int)(Math.pow(2, i))-1;j<N;j++) {
sum += arr[j];
}
}else {
for(int j = (int)(Math.pow(2, i))-1;j <(int)(Math.pow(2, i+1))-1 ;j++) {
sum += arr[j];
}
}
arr1[i] = sum;
}
for(int i = 0;i < count;i++) {
if(arr1[i]>max) {
max = arr1[i];
}
}
for(int i = 0;i <count;i++) {
if(max == arr1[i]) {
maxi = i+1;
break;
}
}
System.out.println(maxi);
}
}