# 2022-06-16

## [384. Shuffle an Array](https://leetcode.com/problems/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

```go
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

```go
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](https://leetcode.com/problems/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

```go
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](https://leetcode.com/problems/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:**

![](https://img.content.cc/a/2022/06/16/12-09-16-209-cbe6aba7765e7f7058ce81a5d6b81fdc-a2150a.png)

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

**Example 2:**

![](https://img.content.cc/a/2022/06/16/12-09-31-367-55b7e0bb7e5fbe9d168655dfb0b8e1fa-d6246d.png)

```
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

```go
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](https://leetcode.com/problems/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

```go
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
}
```