[编程题]回文序列

如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如： {1, 2, 1}, {15, 78, 78, 15} , {112} 是回文序列,  {1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是回文序列。 现在给出一个数字序列，允许使用一种转换操作： 选择任意两个相邻的数，然后从序列移除这两个数，并用这两个数字的和插入到这两个数之前的位置(只插入一个和)。 现在对于所给序列要求出最少需要多少次操作可以将其变成回文序列。

输入描述:

输入为两行，第一行为序列长度n ( 1 ≤ n ≤ 50) 第二行为序列中的n个整数item[i] (1 ≤ iteam[i] ≤ 1000)，以空格分隔。

输出描述:

输出一个数，表示最少需要的转换次数

输入例子:

4 1 1 1 3

输出例子:

2      解题思路：

将该序列左右两端同时开始向中间合并。无论怎么样最终会变成一个数字，也只是最坏的一种情况。

源代码：

import java.util.Scanner; /** * * @author 慕一春 * @version 1.0.0 * @filename Main.java * @time 2016-9-21 下午2:50:56 * @copyright(C) 2016 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int arr[]; while(sc.hasNext()){ int n = sc.nextInt(); arr = new int[n]; for (int i = 0; i < n; i++){ arr[i] = sc.nextInt(); } System.out.println(solve(n, arr)); } sc.close(); } private static int solve(int n, int arr[]) { int left = 0; int right = n - 1; int ans = 0; while (left < right){ if (arr[left] > arr[right]){ arr[right-1] += arr[right]; right--; ans++; }else if(arr[left] < arr[right]){ arr[left+1] += arr[left]; left++; ans++; }else{ left++; right--; } } return ans; } }

[编程题] 优雅的点

小易有一个圆心在坐标原点的圆，小易知道圆的半径的平方。小易认为在圆上的点而且横纵坐标都是整数的点是优雅的，小易现在想寻找一个算法计算出优雅的点的个数，请你来帮帮他。 例如：半径的平方如果为25 优雅的点就有：(+/-3, +/-4), (+/-4, +/-3), (0, +/-5) (+/-5, 0)，一共12个点。 

输入描述:

输入为一个整数，即为圆半径的平方,范围在32位int范围内。

输出描述:

输出为一个整数，即为优雅的点的个数

输入例子:

25

输出例子:

12     解题思路：

说白了就是求一个数能否写成另外两个数平方和？ 一共有几组呢？

源代码：

import java.util.Scanner; /** * * @author 慕一春 * @version 1.0.0 * @filename Main.java * @time 2016-9-21 下午2:50:56 * @copyright(C) 2016 */ public class Main { public static int sum = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int x = 0,y = 0; for (int i=1; i*i <= n; i++){ x = i*i; y = (int) Math.sqrt(n - x); if (x + y*y == n) { sum++; } } System.out.println(sum*4); } }

[编程题] 跳石板

小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3....... 这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。 例如： N = 4，M = 24： 4->6->8->12->18->24 于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板 

输入描述:

输入为一行，有两个整数N，M，以空格隔开。 (4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)

输出描述:

输出小易最少需要跳跃的步数,如果不能到达输出-1

输入例子:

4 24

输出例子:

5 解题思路：

基础的动态规划问题

dp[i] 表示走到 i 位置需要的最短步数 在计算的时候，由于我们知道i位置的可以向前走的距离 当 i 位置可以走的时候，计算走到 i + x 位置时候的 最小步数

源代码：

import java.util.Arrays; import java.util.Scanner; import java.util.TreeSet; /** * * @author 慕一春 * @version 1.0.0 * @filename Main.java * @time 2016-9-21 下午2:50:56 * @copyright(C) 2016 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int dp[] = new int[m+1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[n] = 0; // 到达起始位置步数为0步 for (int i = n; i <= m; i++){ if (dp[i] == Integer.MAX_VALUE) dp[i] = -1; else{ TreeSet<Integer> list = bcd(i); while (!list.isEmpty()){ int temp = list.pollFirst(); if (i + temp <= m) dp[i+temp] = Math.min(dp[i+temp], dp[i]+1); } } } System.out.println(dp[m]); } /** * * @author 慕一春 * @param num * @return 一个数的最大公约数集list */ public static TreeSet<Integer> bcd(int num){ TreeSet<Integer> list = new TreeSet<Integer>(); int len = (int) Math.sqrt(num); for (int i = 2; i <= len; i++){ if (num % i == 0){ list.add(i); list.add(num/i); } } return list; } }

[编程题] 暗黑的字符串

一个只包含'A'、'B'和'C'的字符串，如果存在某一段长度为3的连续子串中恰好'A'、'B'和'C'各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑的。例如： BAACAACCBAAA 连续子串"CBA"中包含了'A','B','C'各一个，所以是纯净的字符串 AABBCCAABB 不存在一个长度为3的连续子串包含'A','B','C',所以是暗黑的字符串 你的任务就是计算出长度为n的字符串(只包含'A'、'B'和'C')，有多少个是暗黑的字符串。 

输入描述:

输入一个整数n，表示字符串长度(1 ≤ n ≤ 30)

输出描述:

输出一个整数表示有多少个暗黑字符串

输入例子:

2 3

输出例子:

9 21

解题思路：

我们只需要考虑当前字符串最后两个字母的两种状态： 相同，例如：AA等 不相同，例如：AB等

动态规划，dp[i][0] 第i个字母以两相同字母结尾的暗黑字符串，dp[i][1] 第i个字母以两个不同字母结尾的暗黑字符串

状态转移方程式： dp[i][0] = dp[i-1][0] + dp[i-1][1] dp[i][1] = 2 * dp[i-1][0] + dp[i-1][1];

源代码：

import java.util.Scanner; /** * * @author 慕一春 * @version 1.0.0 * @filename Main.java * @time 2016-9-21 下午2:50:56 * @copyright(C) 2016 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); if (n == 1){ System.out.println(3); return; } long dp[][] = new long[n+1][2]; dp[1][0] = 0; dp[1][1] = 0; dp[2][0] = 3; dp[2][1] = 6; for (int i = 3; i <= n; i++){ dp[i][0] = dp[i-1][0] + dp[i-1][1]; dp[i][1] = 2 * dp[i-1][0] + dp[i-1][1]; } System.out.println(dp[n][0] + dp[n][1]); } }

[编程题] 数字翻转

对于一个整数X，定义操作rev(X)为将X按数位翻转过来，并且去除掉前导0。例如: 如果 X = 123，则rev(X) = 321; 如果 X = 100，则rev(X) = 1. 现在给出整数x和y,要求rev(rev(x) + rev(y))为多少？ 

输入描述:

输入为一行，x、y(1 ≤ x、y ≤ 1000)，以空格隔开。

输出描述:

输出rev(rev(x) + rev(y))的值

输入例子:

123 100

输出例子:

223 解题思路：

5分钟调试完，没什么难度。

源代码：

import java.util.Scanner; /** * * @author 慕一春 * @version 1.0.0 * @filename Main.java * @time 2016-9-21 下午2:50:56 * @copyright(C) 2016 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String x = sc.next(); String y = sc.next(); System.out.println(rev(String.valueOf(rev(x) + rev(y)))); } public static int rev(String str){ StringBuffer sb = new StringBuffer(str); return Integer.parseInt(sb.reverse().toString()); } }

[编程题] 最大的奇约数

小易是一个数论爱好者，并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题： 定义函数f(x)为x最大的奇数约数，x为正整数。 例如:f(44) = 11. 现在给出一个N，需要求出 f(1) + f(2) + f(3).......f(N) 例如： N = 7  f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 1 + 1 + 3 + 1 + 5 + 3 + 7 = 21 小易计算这个问题遇到了困难，需要你来设计一个算法帮助他。 

输入描述:

输入一个整数N (1 ≤ N ≤ 1000000000)

输出描述:

输出一个整数，即为f(1) + f(2) + f(3).......f(N)

输入例子:

7

输出例子:

21

解题思路：

很明显，f(n) 当n为奇数时，f(n) == n。

当n为偶数时，n不断除以2，直到n为奇数记作n'，即 f(n) == n' 。

推导状态转移方程式：

f(n)为奇数时， f(n) = f(n-1) + n;

f(n)为偶数时， f(n) = f(n/2) + 1 + 3 + 5 + ... + (n-1) ——> f(n) = f(n/2) + n*n/4 （一张纸，一支笔很快就可以写出方程式。）

源代码：

import java.math.BigInteger; import java.util.Scanner; /** * * @author 慕一春 * @version 1.0.0 * @filename Main.java * @time 2016-9-21 下午2:50:56 * @copyright(C) 2016 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(solve1(n)); System.out.println(solve2(n)); } private static BigInteger solve2(int n) { BigInteger sum = BigInteger.ZERO; while (true){ if (n == 1){ sum = sum.add(BigInteger.ONE); break; } else if(n % 2 == 1) { sum = sum.add(BigInteger.valueOf(n)); n--; }else{ sum = sum.add(BigInteger.valueOf(n).multiply(BigInteger.valueOf(n)).divide(BigInteger.valueOf(4))); n /= 2; } } return sum; } public static BigInteger solve1(int n) { if (n == 1) return BigInteger.ONE; if (n % 2 == 1) return solve1(n-1).add(BigInteger.valueOf(n)); else return solve1(n/2).add(BigInteger.valueOf(n).multiply(BigInteger.valueOf(n)).divide(BigInteger.valueOf(4))); } }

[编程题] 买苹果

小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。 

输入描述:

输入一个整数n，表示小易想购买n(1 ≤ n ≤ 100)个苹果

输出描述:

输出一个整数表示最少需要购买的袋数，如果不能买恰好n个苹果则输出-1

输入例子:

20

输出例子:

3

解题思路：

水题 ！[1,100]的数据量暴力一下就好！

源代码：

import java.util.Scanner; /** * * @author 慕一春 * @version 1.0.0 * @filename Main.java * @time 2016-9-21 下午2:50:56 * @copyright(C) 2016 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int r = n / 6; int c = n / 8; int min = Integer.MAX_VALUE; for (int i = 0; i <= r; i++){ for (int j = 0; j <= c; j++){ if (i*6 + j*8 == n){ if (min > i+j) min = i+j; } } } if (min == Integer.MAX_VALUE) System.out.println(-1); else System.out.println(min); } }

[编程题] 计算糖果

A,B,C三个人是好朋友,每个人手里都有一些糖果,我们不知道他们每个人手上具体有多少个糖果,但是我们知道以下的信息： A - B, B - C, A + B, B + C. 这四个数值.每个字母代表每个人所拥有的糖果数. 现在需要通过这四个数值计算出每个人手里有多少个糖果,即A,B,C。这里保证最多只有一组整数A,B,C满足所有题设条件。 

输入描述:

输入为一行，一共4个整数，分别为A - B，B - C，A + B，B + C，用空格隔开。 范围均在-30到30之间(闭区间)。

输出描述:

输出为一行，如果存在满足的整数A，B，C则按顺序输出A，B，C，用空格隔开，行末无空格。 如果不存在这样的整数A，B，C，则输出No

输入例子:

1 -2 3 4

输出例子:

2 1 3 解题思路：

3个未知数，仅需3个一元一次方程就可以解答。这里多了一个就是一个限制条件而已了。 注意A，B，C都是整数！

源代码：

import java.util.Scanner; /** * * @author 慕一春 * @version 1.0.0 * @filename Main.java * @time 2016-9-21 下午2:50:56 * @copyright(C) 2016 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); int d = sc.nextInt(); if ((a+c)%2!=0 || (b+d)%2!=0) System.out.println("No"); else{ int A = (a+c)/2; int B = A-a; int C = B-b; if (B+C == d) System.out.println(A+" "+B+" "+C); else System.out.println("No"); } } }