1、手写代码：求n以内的最大质数
素数又称质数。所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。
思路：因此判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。
import java.util.Scanner;
//求n以内的最大质数
public class PrimeNumber {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
if (N % 2 == 0)
N--;
for (int i = N; i > 2; i--) {
if (isPrime(i)) {
System.out.print("N以内最大质数为：" + i);
break;
}
}
}
// 判断某整数是否为质数
public static boolean isPrime(int m) {
if (m < 2) {
return false;
}
for (int i = 2; i * i <= m; i++) {
if (m % i == 0) {
return false;
}
}
return true;
}
}
2、合并两个排序数组
public class mergeTwoArrays {
public static void main(String[] args) {
int[] num1 = {1,2,3,4,5,7,8,9};
int[] num2 = {3,4,5,6,7};
int[] res = merge(num1,num2);
for(int i = 0; i <res.length; i++) {
System.out.println(res[i]);
}
}
public static int[] merge(int[] num1,int[] num2) {
int length1 = num1.length;
int length2 = num2.length;
int i = length1 - 1;
int j = length2 - 1;
int[] nums1 = new int[length1+length2];
while(i >= 0 && j >=0) {
if(num1[i]>num2[j]){
nums1[i+j+1]=num1[i];
i--;
}
else{
nums1[i+j+1]=num2[j];
j--;
}
}
while(i>=0){
nums1[i+j+1]=num1[i];
i--;
}
while(j>=0){
nums1[i+j+1]=num2[j];
j--;
}
return nums1;
}
}
3、有三种面值的硬币k1 < k2 < k3 ，找k面值的零钱，最少需要多少硬币
参考回答：
当i = 0 时， d(0) = 0。不需要凑零钱，当然也不需要任何硬币了。
当i = 1 时，因为有 1 元的硬币，所以直接在第 1 步的基础上，加上 1 个 1 元硬币，得出 d(1) = 1。
当i = 2 时，因为并没有 2 元的硬币，所以只能拿 1 元的硬币来凑。在第 2 步的基础上，加上 1 个 1 元硬币，得出 d(2) = 2。
当i = 3 时，可以在第 3 步的基础上加上 1 个 1 元硬币，得到 3 这个结果。但其实有 3 元硬币，所以这一步的最优结果不是建立在第 3 步的结果上得来的，而是应该建立在第 1 步上，加上 1 个 3 元硬币，得到 d(3) = 1。
除了第1 步这个看似基本的公理外，其他往后的结果都是建立在它之前得到的某一步的最优解上，加上 1 个硬币得到。得出：
d(i) = d(j) + 1
这里j < i。通俗地讲，我们需要凑出 i 元，就在凑出 j 的结果上再加上某一个硬币就行了。
那这里我们加上的是哪个硬币呢。嗯，其实很简单，把每个硬币试一下就行了：
• 假设最后加上的是1 元硬币，那 d(i) = d(j) + 1 = d(i - 1) + 1。
• 假设最后加上的是3 元硬币，那 d(i) = d(j) + 1 = d(i - 3) + 1。
• 假设最后加上的是5 元硬币，那 d(i) = d(j) + 1 = d(i - 5) + 1。
我们分别计算出d(i - 1) + 1，d(i - 3) + 1，d(i - 5) + 1 的值，取其中的最小值，即为最优解，也就是 d(i)。
public class MinimumCoins {
public static void main(String[] args) throws Exception {
MinimumCoins min = new MinimumCoins();
min.test();
}
private int[] d; // 储存结果
private int[] coins = { 1, 3, 5 }; // 硬币种类
public void test() throws Exception {
int sum = 11; // 需要凑 11 元
d = new int[sum + 1]; // 初始化数组
d_func(0, sum); // 计算需要凑出 0 ～ sum 元需要的硬币数量
for (int i = 0; i <= sum; i++) {
System.out.println("凑齐 " + i + " 元需要 " + d[i] + " 个硬币");
}
}
private void d_func(int i, int num) {
if (i == 0) {
d[i] = 0;
d_func(i + 1, num);
} else {
int min = 9999999;
for (int coin : coins) {
if (i >= coin && d[i - coin] + 1 < min) {
min = d[i - coin] + 1;
}
}
d[i] = min;
if (i < num) {
d_func(i + 1, num);
}
}
}
}
如何减小时间复杂度：不用全局变量来保存计算过的值，也不用递归的方法来实现，用一个一维数组，再用循环来实现。
package TestCase01;
public class MinimumCoins_02 {
public static void main(String[] args) {
int[] coins = { 1, 3, 5 };
int amount = 11;
int res = coinChange(coins, amount);
System.out.println(res);
}
public static int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount <= 0)
return 0;
int[] minNumber = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
minNumber[i] = amount + 1;
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i && minNumber[i - coins[j]] != amount + 1)
minNumber[i] = Integer.min(minNumber[i], 1 + minNumber[i - coins[j]]);
}
}
if (minNumber[amount] == amount + 1)
return -1;
else
return minNumber[amount];
}
}
4、统计排序数组中出现次数最多的元素出现的次数？
package TestCase01;
public class findMostElements {
public static void main(String[] args) {
int[] array = { 1, 1, 2, 2, 2, 3, 4, 5, 6, 6, 6, 6, 6, 7, 8, 8, 9 };
findmost(array);
}
public static void findmost(int[] array) {
int lastEle = array[0];
int maxTime = 0;
int presentTime = 1;
int maxEle = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] == lastEle)
presentTime++;
else {
if (presentTime > maxTime) {
maxTime = presentTime;
maxEle = lastEle;
}
lastEle = array[i];
presentTime = 1;
}
if (i == array.length - 1 && presentTime > maxTime)// 考虑到比较到最大的元素（排在最后的元素），需要在循环推出前比较一次
{
maxTime = presentTime;
maxEle = lastEle;
}
}
System.out.println("出现次数最多的元素" + maxEle + " " + "出现的次数" + maxTime);
}
}