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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://a.b.cr/dictionary/algorithm/diary/2022/06/2022-06-16.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.