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();
*/
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.
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
}
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.
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
}
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
}
