前言

题目比较简单，第一题经典筛质数；第二题送分题；第三题也是比较简单的题目，所以这种笔试就要争取全A啦

第一题

给定一个正整数n，求出小于等于n的所有素数，并输出它们。函数签名: public static ListfindPrimeNumbers(int n)

要求和提示: 素数(质数)是指只能被1和自身整除的正整数。1不是素数最小的素数是2。

可以使用暴力循环的方式判断每个数是否是素数，但效率较低。可以使用筛选法来提高效率。

可以使用数组或集合来存储素数。

注意边界条件和特殊情况的处理。

输入描述

n: 正整数，表示上限值

输出描述

返回一个List，包含小于等于n的所有素数。

示例1

输入

2

输出

[2]

思路与代码

找出小于等于n的所有素数，判断素数的时候采用筛选法而不是暴力

1. 首先判断n是否小于1，如果是，则返回false，因为小于1的数不是质数。
2. 接着判断n是否小于等于3，如果是，则返回true，因为2和3是质数。
3. 然后判断n是否能被2或3整除，如果能整除，则返回false，因为质数不能被2或3整除。
4. 接下来使用一个循环，从5开始，每次增加6（即i+=6）。这是因为质数的特性是除了2和3之外，其他质数都可以表示为6k±1的形式，其中k为正整数。
5. 在循环中，判断n是否能被i整除或(i+2)整除，如果能整除，则返回false。
6. 循环结束后，如果没有返回false，说明n是质数，返回true。

这个算法的优化之处在于，只需要遍历到√n，而不是遍历到n，这样可以减少循环次数，提高效率。同时，通过判断6k±1的形式，可以排除一部分非质数，进一步提高效率。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> res = getResult(n);
        System.out.println(res);
    }
    public static boolean isPrime(int n){
        if(n<1){
            return false;
        }
        if(n<=3){
            return true;
        }
        if(n%2 == 0 || n%3 == 0){
            return false;
        }
        for(int i=5;i*i<=n;i+=6){
            if(n%i == 0 || n%(i+2)==0){
                return false;
            }
        }
        return true;
    }
    public static List<Integer> getResult(int n){
        List<Integer> res = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if(isPrime(i)){
                res.add(i);
            }
        }
        return res;
    }
}

第二题

给定一个整数数组，编写一个程序来找到数组中两个数字之和等于目标值的下标。假设每个输入只有一个解，且不能重复使用相同的元素。

实现一个Solution类，其中包含一个方法twoSum，输入参数为一个整数数组nums和一个目标值target，返回两个数字之和等于目标值的下标。

输入描述

1, 2, 3;3
即表示输入 整数数组 nums=[1,2,3],目标值 target =3

输出

Indices: 0,1

思路与代码

两数之和，输入字符串需要分割成数组和目标值，然后根据两数之和的搜索结果打印不同的输出

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String[] parts = s.split("[,;]");
        String last = parts[parts.length-1].trim();
        int target = Integer.parseInt(last);
        int[] nums = new int[parts.length-1];
        if(nums.length<2){
            System.out.println("No two sum solution");
            return;
        }
        for (int i = 0; i < parts.length - 1; i++) {
            nums[i] = Integer.parseInt(parts[i].trim());
        }
        int[] res = twoSum(nums,target);
        if(res[0]==-1 && res[1]==-1){
            System.out.println("No two sum solution");
        }
        System.out.println("Indices:"+res[0]+','+res[1]);
    }
    private static int[] twoSum(int[] nums, int target){
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            int sub = target-nums[i];
            if(map.containsKey(sub)){
                return new int[]{map.get(sub),i};
            }
            map.put(nums[i],i);
        }
        return new int[]{-1,-1};
    }
}

第三题

给定一个字符串，编写一个Java程序，找出字符串中最长的回文子串(回文串是指正着读和倒着读一样的字符串)。如果存在多个最长回文子串，只需返回其中一个即可。

要求:1.字符串长度不超过1000。 2.考虑回文串的大小写敏感。

输入描述

长度不超过1000的一个字符串，例如"babad"

输出描述

给定字符串中最长的回文子串，例如"bab”或“abat”

示例1

输入

abac

输出

aba

思路与代码

最长回文子串，使用中心扩展算法

import java.util.Scanner;
public class Main2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        String longestPalindrome = findLongestPalindrome(input);
        System.out.println(longestPalindrome);
    }
    public static String findLongestPalindrome(String s){
        if(s == null || s.length() < 1){
            return "";
        }
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            //分别使用两次扩展算法，计算最长回文子串并比较，取最大值
            int len1 = expandAroundCenter(s,i,i);
            int len2 = expandAroundCenter(s,i,i+1);
            int len = Math.max(len1,len2);
            //计算最大串的起始位置和终点
            if(len > end - start){
                start = i-(len-1)/2;
                end = i+len/2;
            }
        }
        return s.substring(start,end+1);
    }
    private static int expandAroundCenter(String s,int left,int right){
        while (left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return right-left-1;
    }
}