每日LeetCode——Java版（一）

第一题：素数个数统计
统计n以内的素数个数
素数：只能被1和自身整除的自然数，0、1除外
例如： 输入：100
输出：25
重点考察：埃筛法
法一（暴力法）：

package com;
import java.util.Scanner;
public class Sushu {
    public static void main(String[] args) {
        // 创建Scanner对象
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(bf(n));
    }
    //暴力算法
    public static int bf(int n){
        int count = 0;

        for(int i = 2;i < n;i++){
            count += isPrime(i) ? 1 : 0;
        }
        return count;

    }

    public static boolean isPrime(int x){
        for(int i = 2; i*i <= x;i++){
            if(x % i == 0){
                return false;
            }
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

知识点补充
（1）关于Java在控制台（键盘）输入的方法：
可以使用Scanner 对象，调用起输入方法即可。

// 创建Scanner对象
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
1
2
3

（2）为什么isPrime的for循环要用ii <= x，我们可以知道例如
例如：12可以等于
26
34
√ 12 * √ 12
43
62
其实有一半是重复的，那么我们只需要求一半就好，就是到√ 12即可，其实在if判断只会求到一半，如果x不是素数的话，那么它在前半段就会被求出，但是如果x是素数的话，那么他可能需要循环到最后一次，中间就会有重复，导致算法效率下降，因此用i*i < =x,也就是i<=√ X作为判断条件。

法二（埃筛法）：

//埃筛法 非素数（合数）

    /**
     * 主要思想就是求到一个素数就对它进行倍增
     * 例如 2
     * 那么 2 * 2 = 4 合数
     *     2 * 3 = 6 合数
     *     2 * 4 = 8 合数
     *     …………
     *  那么就是这些倍增出来的合数就不遍历了，减少遍历的次数
     */
    public static int eratosthenes(int n){
        //打个标记位
        boolean[] isPrime = new boolean[n]; //默认false,代表素数，true代表素数
        int count = 0;
        for(int i = 2;i < n;i++){
            if(!isPrime[i]){
                count++;
                for(int j = i * i;j<n;j+=i){ //j就是合数标记位
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

第二题：java冒泡排序

package com;

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

/**
 * 冒泡排序
 */
public class BubbleSort {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> arrayList = new ArrayList<>();

        System.out.println("请输入数组元素：");
        
        while (scanner.hasNextInt()){
            arrayList.add(scanner.nextInt());
        }
        
        //转换为ArrayList为数组
        int[] array = new int[arrayList.size()];
        for(int i = 0; i < arrayList.size(); i++){
            array[i] = arrayList.get(i);
        }
        
        //关闭Scanner
        scanner.close();
        
        //System.out.println("原数组：");
        //printArray(array);
        
        //调用冒泡排序方法
        bubbleSort(array);

        System.out.println("排序后的数组：");
        printArray(array);
        
        
        
    }
    
    //冒泡排序方法
    public static void bubbleSort(int[] array){
        int n = array.length;
        for(int i = 0;i < n-1; i++){
            for(int j = 0; j < n-i-1; j++){
                //如果当前元素大于下一个元素，则交换它们
                if(array[j] > array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }
    
    //打印数组的方法
    public static void printArray(int[] array){
        for(int i = 0;i < array.length; i++){
            System.out.println(array[i] + "");
        }
        System.out.println();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

第三题：set去重

package com;

import java.util.HashSet;
import java.util.Set;


/**
 * Java 中的 `Set` 接口的实现类，例如 `HashSet`, `LinkedHashSet`, 和 `TreeSet`，会自动去重。`Set` 不允许包含重复元素，每个元素在集合中是唯一的。
 *
 * 具体来说：
 *
 * - **HashSet：** 无序集合，不保证元素的顺序，但是对于大多数情况，插入和查找元素的速度非常快。
 *
 * - **LinkedHashSet：** 保留元素插入的顺序，可以认为是有序的。插入和访问速度比 `HashSet` 稍微慢一点，但在迭代时会更快。
 *
 * - **TreeSet：** 基于红黑树的实现，保证元素按照升序排列。插入、删除和查找的速度比 `HashSet` 和 `LinkedHashSet` 稍慢，但仍然非常快。
 *
 * 无论使用哪个实现类，`Set` 都会确保其中的元素不重复。如果你尝试向 `Set` 中添加重复的元素，新元素将被忽略，不会导致集合中存在重复项。
 */
public class setDemo {
    public static void main(String[] args) {
        // 创建一个 HashSet
        Set<String> stringSet = new HashSet<>();

        // 添加元素
        stringSet.add("apple");
        stringSet.add("banana");
        stringSet.add("orange");
        stringSet.add("apple"); // 这个元素是重复的，不会被加入

        // 打印 Set 中的元素
        System.out.println("Set 中的元素：");
        for (String element : stringSet) {
            System.out.println(element);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38