384. 打乱数组

给你一个整数数组 nums ,设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

  • Solution(int[] nums) 使用整数数组 nums 初始化对象

  • int[] reset() 重设数组到它的初始状态并返回

  • int[] shuffle() 返回数组随机打乱后的结果

  • 示例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 输入
    ["Solution", "shuffle", "reset", "shuffle"]
    [[[1, 2, 3]], [], [], []]
    // 输出
    [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

    // 解释
    Solution solution = new Solution([1, 2, 3]);
    solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如,返回 [3, 1, 2]
    solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
    solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如,返回 [1, 3, 2]
  • 提示:

    1. 1 <= nums.length <= 200
    2. -106 <= nums[i] <= 106
    3. nums 中的所有元素都是 唯一的
    4. 最多可以调用 5 * 104 次 reset 和 shuffle

题解

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
// Fisher-Yates 洗牌算法
// 官方题解
class Solution {
private int[] array;
private int[] original;

Random rand = new Random();

private int randRange(int min, int max) {
return rand.nextInt(max - min) + min;
}

private void swapAt(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

public Solution(int[] nums) {
array = nums;
original = nums.clone();
}

public int[] reset() {
array = original;
original = original.clone();
return original;
}

public int[] shuffle() {
for (int i = 0; i < array.length; i++) {
swapAt(i, randRange(i, array.length));
}
return array;
}
}

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为:

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。

  • 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。

  • 如果 可以变为 1,那么这个数就是快乐数。

  • 如果 n 是快乐数就返回 true ;不是,则返回 false 。

  • 示例 1:

1
2
3
4
5
6
7
输入:19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
  • 示例 2:
1
2
输入:n = 2
输出:false
  • 提示:
1
1 <= n <= 231 - 1

题 解

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

private static Set<Integer> cycleMembers =
new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));

public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}

public boolean isHappy(int n) {
while (n != 1 && !cycleMembers.contains(n)) {
n = getNext(n);
}
return n == 1;
}
}