Knuth 洗牌算法的Java代码

Knuth 洗牌算法，也称 Fisher–Yates 洗牌算法，是一种随机打乱一个数组的算法。下面是 Java 代码实现：

import java.util.Random;

public class KnuthShuffle {
    public static void shuffle(int[] nums) {
        Random rand = new Random();
        for (int i = nums.length - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}

使用方法：

int[] nums = {1, 2, 3, 4, 5};
KnuthShuffle.shuffle(nums);

以上代码会随机打乱数组 nums 中的元素。

相关问题

java利用复循环洗牌算法_实现不重复取数两种算法（洗牌算法）

好的，下面是我给您的答案。

Java利用Fisher-Yates算法（又称Knuth shuffle算法）实现不重复取数洗牌算法：

public static int[] shuffle(int[] arr) {
    Random rand = new Random();
    for (int i = arr.length - 1; i > 0; i--) {
        // 随机生成一个 [0, i] 之间的索引
        int j = rand.nextInt(i + 1);
        // 交换 arr[i] 和 arr[j]
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    return arr;
}

Java实现另一种不重复取数算法：

public static int[] randomSelect(int[] arr, int n) {
    Random rand = new Random();
    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
        // 随机生成一个 [i, arr.length - 1] 之间的索引
        int j = i + rand.nextInt(arr.length - i);
        // 交换 arr[i] 和 arr[j]
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        result[i] = arr[i];
    }
    return result;
}

这两种算法都可以实现不重复取数洗牌，第一种算法是经典的Fisher-Yates算法，效率较高，但需要修改原数组；第二种算法则是每次从剩余的数中随机选择一个，效率略低，但不会修改原数组。

kmp算法 java

KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。它的核心思想是利用已经匹配过的部分信息，尽量减少不必要的比较次数，从而提高匹配效率。

KMP算法的实现主要包括两个步骤：构建next数组和进行匹配。

1. 构建next数组：
- 首先，我们需要定义一个next数组，用于存储模式串中每个位置的最长公共前后缀长度。
- 然后，从模式串的第二个字符开始，依次计算每个位置的最长公共前后缀长度。
- 最后，将计算得到的最长公共前后缀长度填入next数组中。

2. 进行匹配：
- 在匹配过程中，我们需要维护两个指针：主串指针i和模式串指针j。
- 当主串和模式串的当前字符匹配时，i和j同时向后移动一位。
- 当主串和模式串的当前字符不匹配时，根据next数组的值调整模式串指针j的位置。
- 如果j等于模式串的长度，表示匹配成功，返回主串中匹配的起始位置。

下面是KMP算法的Java实现示例：

public class KMP {
    public static int kmp(String text, String pattern) {
        int[] next = getNext(pattern);
        int i = 0, j = 0;
        while (i < text.length() && j < pattern.length()) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == pattern.length()) {
            return i - j;
        } else {
            return -1;
        }
    }

    private static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];
        next[0] = -1;
        int i = 0, j = -1;
        while (i < pattern.length() - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }
}