第一题：数组中出现次数超过一半的数字

描述
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：
n≤50000，数组中元素的值
0≤val≤10000
要求：空间复杂度：O(1)，时间复杂度：O(n)

输入描述：
保证数组输入非空，且保证有解

示例1

输入： [1,2,3,2,2,2,5,4,2]
返回值： 2

示例2

输入： [3,3,3,3,2,2,2]
返回值： 3

示例3

输入： [1]
返回值： 1

解题思路：

1. 如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在出现次数超过一半的数字，最后留下的数肯定是众数
2. 判断数组为空以及只有一个数字的情况

代码实现：

public class Solution {public int MoreThanHalfNum_Solution(int [] array) {if(null == array || array.length == 0) {return 0;}if(array.length == 1) {return array[0];}int ret = array[0];int times = 0;for(int i = 1;i < array.length;++i) {if(times != 0) {if(array[i] == ret) {++times;}else {--times;}} else {ret = array[i];times = 1;}}times = 0;for(int i = 0;i < array.length;++i) {if(array[i] == ret) {++times;}}return times > 2/array.length ? ret : 0;    }
}

第二题：进制转换

描述
给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数
输入描述：
输入为一行，M(32位整数)、N(2 ≤ N ≤ 16)，以空格隔开。
输出描述：
为每个测试实例输出转换后的数，每个输出占一行。如果N大于9，则对应的数字规则参考16进制（比如，10用A表示，等等）

示例1

输入： 7 2
输出： 111

解题思路：

1. 判断m为0的情况
2. 进行取模余数求得当前低进制的位的值，通过除掉进制数，进入下一个进制位的计算,用StringBuilder拼接起来
3. 判断m是否为负数，若为负数，最后拼接负号，然后逆置字符串

代码实现：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextInt()) {int m = in.nextInt();int n = in.nextInt();if(m == 0) {System.out.println(0);}boolean flg = false;if(m < 0) {m = -m;flg = true;}String table = "0123456789ABCDEF";StringBuilder ret = new StringBuilder();while(m != 0) {ret.append(table.charAt(m%n));m = m/n; }if(flg) {ret.append('-');}ret.reverse();System.out.println(ret.toString());}}
}

第三题：统计回文

描述
“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。
例如：
A = “aba”，B = “b”。这里有4种把B插入A的办法：

• 在A的第一个字母之前: “baba” 不是回文
• 在第一个字母‘a’之后: “abba” 是回文
• 在字母‘b’之后: “abba” 是回文
• 在第二个字母’a’之后 “abab” 不是回文
  所以满足条件的答案为2

输入描述：
每组输入数据共两行。 第一行为字符串A 第二行为字符串B 字符串长度均小于100且只包含小写字母
输出描述：
输出一个数字，表示把字符串B插入字符串A之后构成一个回文串的方法数

示例1

输入： aba b
输出： 2

解题思路：

1. 暴力求解方式计算，遍历str1，将str2 insert进入str1的每个位置，判断是否是回文
2. 判断回文的时候，直接将字符串逆置，判断是否相等，如果相等，++count

代码实现：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextLine()) {String s1 = in.nextLine();String s2 = in.nextLine();int count = 0;for(int i = 0;i <= s1.length();i++) {StringBuilder str1 = new StringBuilder(s1);str1.insert(i,s2);StringBuilder str2 = new StringBuilder(str1);StringBuilder str3 = str2.reverse();if(str1.toString().equals(str3.toString())) {count++;}}System.out.println(count);}}
}

第四题：连续最大和

描述
一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3
输入描述：
输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。
输出描述：
所有连续子数组中和最大的值。

示例1

输入： 3
-1 2 1
输出： 3

解题思路：

本题为动态规划问题，状态方程为 max( dp[ i ] )=getMax( max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] ）

代码实现：

import java.util.Scanner;public class Main {public static int getMax(int a, int b) {return a > b ? a : b;}public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextInt()) {int n = in.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = in.nextInt();}int max = arr[0];int sum = arr[0];for (int i = 0; i < n; i++) {sum = getMax(sum + arr[i], arr[i]);if (sum >= max) {max = sum;}}System.out.println(max);}}
}

第五题：不要二

描述
二货小易有一个W*H的网格盒子，网格的行编号为0_{H-1，网格的列编号为0}W-1。每个格子至多可以放一块蛋糕，任意两块蛋糕的欧几里得距离不能等于2。
对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为:( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) ) 的算术平方根，小易想知道最多可以放多少块蛋糕在网格盒子里。
输入描述：
每组数组包含网格长宽W,H，用空格分割.(1 ≤ W、H ≤ 1000)
输出描述：
输出一个最多可以放的蛋糕数

示例1

输入： 3 2
输出： 4

解题思路：

1. 分析题意可得，如果放蛋糕的位置是(x1,y1)，则不能放蛋糕的位置(x2,y2)，满足x1 == x2,y1-y2== 2或者x1-x2 == 2,y1 == y2.
2. 定义一个二维数组，开空间并初始化，每个位置初始化为0，当a[i][j]位置放蛋糕，则可以标记处a[i][j+2]和a[i+1][j]位置不能放蛋糕，遍历一遍二维数组，标记处不能放蛋糕的位置，就统计出了当蛋糕的位置数

代码实现：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextInt()) {int col = in.nextInt();int row = in.nextInt();int[][] arr = new int[row][col];int count = 0;for(int i = 0;i < row;i++) {for(int j = 0;j < col;j++) {if(arr[i][j] == 0) {count++;if(i+2 < row) {arr[i+2][j] = 1;}if(j+2 < col) {arr[i][j+2] = 1;}}}}System.out.println(count);}}
}