花花酱 LeetCode 401. Binary Watch

By zxi on March 17, 2018

Problem:

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

The order of output does not matter.
The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

Solution 1:

Time complexity: O(11*59*n)

C++

// Author: Huahua

// Running time: 2 ms (beats 100%)

class Solution {

public:

vector<string> readBinaryWatch(int num) {

vector<string> ans;

for (int i = 0; i <= num; ++i)

for (int h : nums(i, 12))

for (int m : nums(num - i, 60))

ans.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));

return ans;

}

private:

// Return numbers in [0,r) that has b 1s in their binary format.

vector<int> nums(int b, int r) {

vector<int> ans;

for (int n = 0; n < r; ++n)

if (__builtin_popcount(n) == b) ans.push_back(n);

return ans;

}

};

花花酱 LeetCode 396. Rotate Function

By zxi on March 16, 2018

Problem:

Given an array of integers A and let n to be its length.

Assume B_k to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * B_k[0] + 1 * B_k[1] + ... + (n-1) * B_k[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note:
n is guaranteed to be less than 10⁵.

Example:

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Solution 1: Brute Force

Time complexity: O(n^2) TLE

Space complexity: O(1)

Solution 2: Math

F(K)          =               0A[K] + 1A[K+1] + 2A[K+2] + ... + (n-2)A[K-2] + (n-1)A[K-1]
F(K-1)        =     0A[K-1] + 1A[K] + 2A[K+1] + 3A[K+2] + ... + (n-1)A[K-2]
F(K) - F(K-1) = (n-1)A[K-1] - 1A[K] - 1A[K+1] - 1A[K+2] - ... -     1A[K-2]
              = (n-1)A[K-1] - (1A[K] + 1A[K+1] + ... + 1A[K-2] + 1A[K-1] - 1A[K-1])
              = nA[K-1] - sum(A)
compute F(0)
F(i)          = F(i-1) + nA[i-1] - sum(A)

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

int maxRotateFunction(vector<int>& A) {

const int n = A.size();

int sum = 0;

int f = 0;

for (int i = 0; i < n; ++i) {

sum += A[i];

f += i * A[i];

}

int ans = f;

for (int i = 0; i < n - 1; ++i) {

f = f + sum - n * A[n - i - 1];

ans = max(ans, f);

}

return ans;

}

};

花花酱 LeetCode 398. Random Pick Index

By zxi on March 16, 2018

Problem:

https://leetcode.com/problems/random-pick-index/description/

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};

Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.

solution.pick(1);

Solution: Reservoir sampling

https://en.wikipedia.org/wiki/Reservoir_sampling

Time complexity: O(query * n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 92 ms

class Solution {

public:

Solution(vector<int> nums) {

nums_ = std::move(nums);

}

int pick(int target) {

int n = 0;

int index = -1;

for (int i = 0; i < nums_.size(); ++i) {

if (nums_[i] != target) continue;

++n;

if (rand() % n == 0) index = i;

}

return index;

}

private:

vector<int> nums_;

};

花花酱 LeetCode 384. Shuffle an Array

By zxi on March 16, 2018

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.

int[] nums = {1,2,3};

Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.

solution.shuffle();

// Resets the array back to its original configuration [1,2,3].

solution.reset();

// Returns the random shuffling of array [1,2,3].

solution.shuffle();

C++

// Author: Huahua

// Running time: 249 ms

class Solution {

public:

Solution(vector<int> nums) {

nums_ = std::move(nums);

}

/** Resets the array to its original configuration and return it. */

vector<int> reset() {

return nums_;

}

/** Returns a random shuffling of the array. */

vector<int> shuffle() {

vector<int> output(nums_);

const int n = nums_.size();

for (int i = 0; i < n - 1; ++i) {

int j = rand() % (n - i) + i;

std::swap(output[i], output[j]);

}

return output;

}

private:

vector<int> nums_;

};

Huahua's Tech Road

花花酱 LeetCode 401. Binary Watch

Problem:

Solution 1:

花花酱 LeetCode 382. Linked List Random Node

Problem:

Solution:

花花酱 LeetCode 396. Rotate Function

Problem:

Solution 1: Brute Force

Solution 2: Math

花花酱 LeetCode 398. Random Pick Index

Problem:

Example:

Solution: Reservoir sampling

花花酱 LeetCode 384. Shuffle an Array