花花酱 LeetCode 961. N-Repeated Element in Size 2N Array

By zxi on December 23, 2018

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

Input: [1,2,3,3]
Output: 3

Example 2:

Input: [2,1,2,5,3,2]
Output: 2

Example 3:

Input: [5,1,5,2,5,3,5,4]
Output: 5

Note:

4 <= A.length <= 10000
0 <= A[i] < 10000
A.length is even

Solution: Randomization

Randomly pick two numbers in the array, if they are the same (25% probability) return the number, do it until the two numbers are the same.

Time complexity: O(1) expected 4
Space complexity: O(1)

C++

// Author: Huahua, running time: 72 ms

class Solution {

public:

int repeatedNTimes(vector<int>& A) {

int i = 0;

int j = 0;

while (i == j || A[i] != A[j]) {

i = rand() % A.size();

j = rand() % A.size();

}

return A[i];

}

};

花花酱 LeetCode 78. Subsets

By zxi on December 22, 2018

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:[  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]

Solution: Combination

Time complexity: O(2^n)
Space complexity: O(n)

Implemention 1: DFS

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<vector<int>> subsets(vector<int>& nums) {

vector<vector<int>> ans;

vector<int> cur;

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

dfs(nums, i, 0, cur, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int n, int s,

vector<int>& cur, vector<vector<int>>& ans) {

if (n == cur.size()) {

ans.push_back(cur);

return;

}

for (int i = s; i < nums.size(); ++i) {

cur.push_back(nums[i]);

dfs(nums, n, i + 1, cur, ans);

cur.pop_back();

}

};

Python3

# Author: Huahua, running time: 60 ms

class Solution:

def subsets(self, nums):

ans = []

def dfs(n, s, cur):

if n == len(cur):

ans.append(cur.copy())

return

for i in range(s, len(nums)):

cur.append(nums[i])

dfs(n, i + 1, cur)

cur.pop()

for i in range(len(nums) + 1):

dfs(i, 0, [])

return ans

Implementation 2: Binary

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<vector<int>> subsets(vector<int>& nums) {

const int n = nums.size();

vector<vector<int>> ans;

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

vector<int> cur;

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

if (s & (1 << i)) cur.push_back(nums[i]);

ans.push_back(cur);

}

return ans;

}

};

Python3

# Author: Huahua, 40 ms

class Solution:

def subsets(self, nums):

n = len(nums)

return [[nums[i] for i in range(n) if s & 1 << i > 0] for s in range(1 << n)]

花花酱 LeetCode 220. Contains Duplicate III

By zxi on December 20, 2018

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Solution: Sliding Window + Multiset (OrderedSet)

Maintaining a sliding window of sorted numbers of k + 1. After the i-th number was inserted into the sliding window, check whether its left and right neighbors satisfy abs(nums[i] – neighbor) <= t

Time complexity: O(nlogk)
Space complexity: O(k)

C++

// Author: Huahua, running time: 12 ms

class Solution {

public:

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {

multiset<long> s;

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

if (i > k)

s.erase(s.find(nums[i - k - 1]));

auto it = s.insert(nums[i]);

if (it != begin(s) && *it - *prev(it) <= t)

return true;

if (next(it) != end(s) && *next(it) - *it <= t)

return true;

}

return false;

}

};

花花酱 LeetCode 957. Prison Cells After N Days

By zxi on December 19, 2018

There are 8 prison cells in a row, and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
Otherwise, it becomes vacant.

(Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.

Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

Example 1:

Input: cells = [0,1,0,1,1,0,0,1], N = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

Example 2:

Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000
Output: [0,0,1,1,1,1,1,0]

Note:

cells.length == 8
cells[i] is in {0, 1}
1 <= N <= 10^9

Solution: Simulation

Simulate the process, since there must be loops, record the last day when a state occurred.

Time complexity: O(2^8)
Space complexity: O(2^8)

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<int> prisonAfterNDays(vector<int>& cells, int N) {

vector<int> seen(1 << 8, -1);

auto getKey = [] (const vector<int>& cells) {

int key = 0;

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

key |= cells[i] << i;

return key;

};

while (N > 0) {

const int key = getKey(cells);

if (seen[key] > 0)

N %= seen[key] - N;

seen[key] = N--;

if (N < 0) break;

vector<int> c(8);

for (int i = 1; i < 7; ++i)

c[i] = cells[i - 1] == cells[i + 1];

cells.swap(c);

}

return cells;

}

};

花花酱 LeetCode 960. Delete Columns to Make Sorted III

By zxi on December 19, 2018

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = ["babca","bbazb"] and deletion indices {0, 1, 4}, then the final array after deletions is ["bc","az"].

Suppose we chose a set of deletion indices D such that after deletions, the final array has every element (row) in lexicographic order.

For clarity, A[0] is in lexicographic order (ie. A[0][0] <= A[0][1] <= ... <= A[0][A[0].length - 1]), A[1] is in lexicographic order (ie. A[1][0] <= A[1][1] <= ... <= A[1][A[1].length - 1]), and so on.

Return the minimum possible value of D.length.

Example 1:

Input: ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is A = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. A[0][0] <= A[0][1] and A[1][0] <= A[1][1]).
Note that A[0] > A[1] - the array A isn't necessarily in lexicographic order.

Example 2:

Input: ["edcba"]
Output: 4
Explanation: If we delete less than 4 columns, the only row won't be lexicographically sorted.

Example 3:

Input: ["ghi","def","abc"]
Output: 0
Explanation: All rows are already lexicographically sorted.

Note:

1 <= A.length <= 100
1 <= A[i].length <= 100

Solution: DP

dp[i] := max length of increasing sub-sequence (of all strings) ends with i-th letter.
dp[i] = max(dp[j] + 1) if all A[*][j] <= A[*][i], j < i
Time complexity: (n*L^2)
Space complexity: O(L)

C++

// Author: Huahua, running time: 24 ms

class Solution {

public:

int minDeletionSize(vector<string>& A) {

vector<int> dp(A[0].length(), 1);

for (int i = 0; i < A[0].length(); ++i)

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

bool valid = true;

for (const auto& a : A)

if (a[j] > a[i]) {

valid = false;

break;

}

if (valid) dp[i] = max(dp[i], dp[j] + 1);

}

return A[0].length() - *max_element(begin(dp), end(dp));

}

};

Python3

// Author: Huahua, running time: 176 ms

class Solution:

def minDeletionSize(self, A):

n = len(A[0])

dp = [1] * n

for i in range(1, n):

for j in range(i):

valid = True

for a in A:

if a[j] > a[i]:

valid = False

break

if valid:

dp[i] = max(dp[i], dp[j] + 1)

return n - max(dp)

Huahua's Tech Road

花花酱 LeetCode 961. N-Repeated Element in Size 2N Array

Solution: Randomization

C++

花花酱 LeetCode 78. Subsets

Solution: Combination

Implemention 1: DFS

C++

Python3

Implementation 2: Binary

C++

Python3

花花酱 LeetCode 220. Contains Duplicate III

Solution: Sliding Window + Multiset (OrderedSet)

C++

花花酱 LeetCode 957. Prison Cells After N Days

Solution: Simulation

C++

花花酱 LeetCode 960. Delete Columns to Make Sorted III

Solution: DP

C++

Python3