Java修炼 2024.7.26 0:24

题目 1：字符串逆转

问题：编写一个方法，将给定的字符串逆转。例如，输入 “hello”，输出 “olleh”。

public class StringReverse {
    public static String reverse(String str)
    {
        return new StringBuilder(str).reverse().toString();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(reverse(s));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

题目 2：斐波那契数列

编写一个方法，使用递归计算第 n 个斐波那契数（0 和 1 开始）。例如，输入 5，输出 5。

public class Fibonaci {
    public static int fib(int n)
    {
        if(n<=1)
            return n;
        return fib(n-1)+fib(n-2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = sc.nextInt();
        System.out.println(fib(i));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

题目 3：判断回文字符串

编写一个方法来判断一个字符串是否为回文字符串（即前后相同）。例如，输入 “racecar”，输出 true

public class Palindrome {
    public static boolean pld(String str)
    {
        String tmp = new StringBuilder(str).reverse().toString();
        return tmp.equals(str);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(pld(s));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

题目 4：找出数组中第二大元素

编写一个方法，找出一个整数数组中的第二大元素。例如，输入 [3, 5, 1, 8, 7]，输出 7。

public class SecondLargest {
    public static int secondlargest(int[] nums)
    {
        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;
        for (int num : nums) {
            if(num>largest)
            {
                secondLargest = largest;
                largest = num;
            }
            else if(num>secondLargest&&num!=largest)
            {
                secondLargest = num;
            }

        }
        return secondLargest;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] nums = new int[100];
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(secondlargest(nums));
    }
}
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

题目 5：冒泡排序

实现一个冒泡排序算法，对给定的整数数组进行排序

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");  // 输出: 11 12 22 25 34 64 90
        }
    }
}

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

题目 6：查找数组中的众数（Majority Element）

问题：编写一个方法，找出一个数组中的众数（出现次数超过数组长度一半的元素）。例如，输入 [2, 2, 1, 1, 2]，输出 2。

public class MajorityElement {
    public static int findMajorityElement(int[] nums)
    {
        HashMap<Integer,Integer> map = new HashMap<>();
        int MajorityElementcnt = nums.length/2;
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0)+1); //注意这里getOrdefault方法的使用，即不存在时默认为0，否则为当前值，然后都+1
            if(map.get(num)>MajorityElementcnt)
            {
                return num;
            }
        }
        return -1;// 如果没有众数，返回 -1
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 2};
        System.out.println(findMajorityElement(nums));  // 输出: 2
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

题目 7：实现一个简单的链表（感受Java和c++的区别）

问题：实现一个单向链表，并提供基本的操作（添加、删除、查找元素）。

 class Node{
        int data;
        Node next;

        public Node(int data)
        {
            this.data = data;
            this.next = null;
        }
    }

    class LinkList{
        private Node head;

        public  void add(int data)
        {
            Node newnode = new Node(data);
            if(head==null)
            {
                head = newnode;
            }
            else
            {
                Node cur = head;
                while(cur.next!=null)
                {
                    cur = cur.next;
                }
                cur.next = newnode;
            }
        }
        public void delete(int data)
        {
            if(head==null) return;

            if(head.data==data)
            {
                head = head.next;
                return;
            }

            Node cur = head;
            while (cur.next!=null)
            {
                if(cur.next.data==data)
                {
                    cur.next = cur.next.next;
                    return;
                }
                cur = cur.next;
            }
        }

        public boolean find(int data)
        {
            Node cur = head;
            while(cur!=null)
            {
                if(cur.data==data)
                    return true;
                cur = cur.next;
            }
            return false;

        }

        public void printList()
        {
            Node cur = head;
            while(cur!=null)
            {
                System.out.print(cur.data + " ");
                cur = cur.next;
            }
            System.out.println('\n');
        }

        public static void main(String[] args) {
            LinkList list = new LinkList();
            list.add(1);
            list.add(2);
            list.add(3);
            list.printList();  // 输出: 1 2 3
            list.delete(2);
            list.printList();  // 输出: 1 3
            System.out.println(list.find(3)); // 输出: 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
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

题目 8：实现一个栈（Stack）

问题：使用数组实现栈，并提供基本操作（push、pop、peek、isEmpty）。

public class Stack {
    private int maxSize;
    private int[] stackArray;
    private int top;

    public Stack(int size)
    {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1;
    }

    public void push(int value)
    {
        if(top+1<maxSize)
        {
            stackArray[++top] = value;
        }
        else {
            System.out.println("Stack is full");
        }
    }
    public boolean isEmpty() {
        return top == -1;
    }

    public int pop()
    {
        if(!isEmpty())
        {
            return stackArray[top--];
        }
        else {
            System.out.println("Stack is empty");
            return -1; // 错误值
        }
    }

    public int peek() {
        if (!isEmpty()) {
            return stackArray[top];
        } else {
            System.out.println("Stack is empty");
            return -1; // 错误值
        }
    }

    public static void main(String[] args) {
        Stack stack = new Stack(5);
        stack.push(1);
        stack.push(2);
        System.out.println(stack.peek()); // 输出: 2
        stack.pop();
        System.out.println(stack.peek()); // 输出: 1
    }
}
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

题目 9：查找所有子串

问题：编写一个方法来查找一个给定字符串的所有子串。

public class SubString {
    public static List<String> findAllSubString(String str)
    {
        List<String> list = new ArrayList<>();
        int len = str.length();
        for(int i=0;i<len;i++)
        {
            for(int j=i+1;j<=len;j++)
            {
                list.add(str.substring(i,j));
            }
        }
        return list;
    }

    public static void main(String[] args) {
        String input = "abc";
        List<String> substrings = findAllSubString(input);
        System.out.println(substrings);  // 输出: [a, ab, abc, b, bc, c]
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

题目 10：实现快速排序

问题：实现快速排序算法。

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // 交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 交换最后的 pivot
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 80, 30, 90, 40, 50, 20};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");  // 输出: 10 20 30 40 50 80 90
        }
    }
}

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