# 2022-06-16

## 384. Shuffle an Array

### Description

Given an integer array `nums`, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the `Solution` class:

• `Solution(int[] nums)` Initializes the object with the integer array `nums`.

• `int[] reset()` Resets the array to its original configuration and returns it.

• `int[] shuffle()` Returns a random shuffling of the array.

Example 1:

``````Input
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // Shuffle the array [1,2,3] and return its result.
// Any permutation of [1,2,3] must be equally likely to be returned.
// Example: return [3, 1, 2]
solution.reset();      // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle();    // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]``````

Constraints:

• `1 <= nums.length <= 50`

• `-10^6 <= nums[i] <= 10^6`

• All the elements of `nums` are unique.

• At most `10^4` calls in total will be made to `reset` and `shuffle`.

### Solution

#### Approach #0

``````type Solution struct {
nums, original []int
}

func Constructor(nums []int) Solution {
return Solution{nums, append([]int(nil), nums...)}
}

func (this *Solution) Reset() []int {
copy(this.nums, this.original)
return this.nums
}

func (this *Solution) Shuffle() []int {
shuffle := make([]int, len(this.nums))
for i := range shuffle {
j := rand.Intn(len(this.nums))
shuffle[i] = this.nums[j]
this.nums = append(this.nums[:j], this.nums[j+1:]...)
}
this.nums = shuffle
return this.nums
}

/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.Reset();
* param_2 := obj.Shuffle();
*/``````

#### Approach #1

``````type Solution struct {
nums, original []int
}

func Constructor(nums []int) Solution {
return Solution{nums, append([]int(nil), nums...)}
}

func (this *Solution) Reset() []int {
copy(this.nums, this.original)
return this.nums
}

func (this *Solution) Shuffle() []int {
n := len(this.nums)
for i := range this.nums {
j := i + rand.Intn(n-i)
this.nums[i], this.nums[j] = this.nums[j], this.nums[i]
}
return this.nums
}

/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.Reset();
* param_2 := obj.Shuffle();
*/``````

## 202. Happy Number

### Description

Write an algorithm to determine if a number `n` is happy.

A happy number is a number defined by the following process:

• Starting with any positive integer, replace the number by the sum of the squares of its digits.

• Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.

• Those numbers for which this process ends in 1 are happy.

Return `true` if `n` is a happy number, and `false` if not.

Example 1:

``````Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1``````

Example 2:

``````Input: n = 2
Output: false``````

Constraints:

• `1 <= n <= 2^31 - 1`

### Solution

#### Approach #0: Fast ans slow pointer

``````func isHappy(n int) bool {
slow, fast := n, step(n)
for fast != 1 && fast != slow {
slow = step(slow)
fast = step(step(fast))
}
return fast == 1
}

func step(n int) int {
var sum int
for n > 0 {
sum += (n % 10) * (n % 10)
n /= 10
}
return sum
}``````

## 149. Max Points on a Line

### Description

Given an array of `points` where `points[i] = [xi, yi]` represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

``````Input: points = [[1,1],[2,2],[3,3]]
Output: 3``````

Example 2:

``````Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4``````

Constraints:

• `1 <= points.length <= 300`

• `points[i].length == 2`

• `-104 <= xi, yi <= 104`

• All the `points` are unique.

### Solution

#### Approach #0

``````func maxPoints(points [][]int) (ans int) {
n := len(points)
if n <= 2 {
return n
}
for i, p := range points {
if ans >= n-i || ans > n/2 {
break
}
cnt := make(map[int]int)
for _, q := range points[i+1:] {
x, y := p[0]-q[0], p[1]-q[1]
if x == 0 {
y = 1
}
if y == 0 {
x = 1
}
if y < 0 {
x, y = -x, -y
}
g := gcd(abs(x), abs(y))
x /= g
y /= g
cnt[y+20001*x]++
}
for _, c := range cnt {
ans = max(ans, c+1)
}
}
return
}

func gcd(a, b int) int {
for a > 0 {
a, b = b%a, a
}
return b
}

func abs(a int) int {
if a < 0 {
return -a
}
return a
}

func max(a, b int) int {
if a > b {
return a
}
return b
}``````

## 532. K-diff Pairs in an Array

### Description

Given an array of integers `nums` and an integer `k`, return the number of unique k-diff pairs in the array.

A k-diff pair is an integer pair `(nums[i], nums[j])`, where the following are true:

• `0 <= i, j < nums.length`

• `i != j`

• `nums[i] - nums[j] == k`

Notice that `|val|` denotes the absolute value of `val`.

Example 1:

``````Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.``````

Example 2:

``````Input: nums = [1,2,3,4,5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).``````

Example 3:

``````Input: nums = [1,3,1,5,4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).``````

Constraints:

• `1 <= nums.length <= 10^4`

• `-10^7 <= nums[i] <= 10^7`

• `0 <= k <= 10^7`

### Solution

#### Approach #0

``````func findPairs(nums []int, k int) (ans int) {
sort.Ints(nums)
j, n := 0, len(nums)
for i, num := range nums {
if i == 0 || nums[i-1] != num {
for j < n && (nums[j] < k+num || j <= i) {
j++
}
if j < n && nums[j] == k+num {
ans++
}
}
}
return
}``````

Last updated