Huahua’s Tech Road

花花酱 LeetCode 1510. Stone Game IV

By zxi on July 17, 2020

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player’s turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Example 4:

Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0). 
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).

Example 5:

Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.

Constraints:

1 <= n <= 10^5

Solution: Recursion w/ Memoization / DP

Let win(n) denotes whether the current play will win or not.
Try all possible square numbers and see whether the other player will lose or not.
win(n) = any(win(n – i*i) == False) ? True : False
base case: win(0) = False

Time complexity: O(nsqrt(n))
Space complexity: O(n)

C++

class Solution {

public:

bool winnerSquareGame(int n) {

vector<int> cache(n + 1, 0); // 0:Unknown, 1:Win, -1:Lose

function<int(int)> win = [&](int n) -> int {

if (n == 0) return -1;

if (cache[n]) return cache[n];

for (int i = sqrt(n); i >= 1; --i)

if (win(n - i * i) < 0) return cache[n] = 1;

return cache[n] = -1;

};

return win(n) > 0;

}

};

Java

class Solution {

private int[] cache;

public boolean winnerSquareGame(int n) {

this.cache = new int[n + 1];

return this.win(n) > 0;

}

private int win(int n) {

if (n == 0) return -1;

if (this.cache[n] != 0) return this.cache[n];

for (int i = (int)Math.sqrt(n); i >= 1; --i)

if (win(n - i * i) < 0)

return this.cache[n] = 1;

return this.cache[n] = -1;

}

Python3

class Solution:

def winnerSquareGame(self, n: int) -> bool:

dp = [None] * (n + 1)

dp[0] = False

for i in range(0, n):

if dp[i]: continue

for j in range(1, n + 1):

if i + j * j > n: break

dp[i + j * j] = True

return dp[n]

花花酱 LeetCode 1512. Number of Good Pairs

By zxi on July 16, 2020

Given an array of integers nums.

A pair (i,j) is called good if nums[i] == nums[j] and i < j.

Return the number of good pairs.

Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.

Example 3:

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

Constraints:

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

Solution 1: Brute Force

Enumerate all the pairs.

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

C++

class Solution {

public:

int numIdenticalPairs(vector<int>& nums) {

int ans = 0;

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

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

ans += nums[i] == nums[j];

return ans;

}

};

Java

class Solution {

public int numIdenticalPairs(int[] nums) {

int ans = 0;

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

for (int j = i + 1; j < nums.length; ++j)

if (nums[i] == nums[j]) ++ans;

return ans;

}

Python3

class Solution:

def numIdenticalPairs(self, nums: List[int]) -> int:

n = len(nums)

ans = 0

for i in range(n):

for j in range(i + 1, n):

if nums[i] == nums[j]: ans += 1

return ans

Solution 2: Hashtable

Store the frequency of each number so far, when we have a number x at pos j, and it appears k times before. Then we can form additional k pairs.

Time complexity: O(n)
Space complexity: O(range)

C++

// Author: Huahua

class Solution {

public:

int numIdenticalPairs(vector<int>& nums) {

int ans = 0;

vector<int> f(101);

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

ans += f[nums[i]]++;

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int numIdenticalPairs(int[] nums) {

int ans = 0;

int[] f = new int[101];

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

ans += f[nums[i]]++;

return ans;

}

Python3

# Author: Huahua

class Solution:

def numIdenticalPairs(self, nums: List[int]) -> int:

f = defaultdict(int)

ans = 0

for x in nums:

ans += f[x]

f[x] += 1

return ans

花花酱 LeetCode 1514. Path with Maximum Probability

By zxi on July 11, 2020

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

Example 2:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000

Example 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.

Constraints:

2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
There is at most one edge between every two nodes.

Solution: Dijkstra’s Algorithm

max(P1*P2*…*Pn) => max(log(P1*P2…*Pn)) => max(log(P1) + log(P2) + … + log(Pn) => min(-(log(P1) + log(P2) … + log(Pn)).

Thus we can convert this problem to the classic single source shortest path problem that can be solved with Dijkstra’s algorithm.

Time complexity: O(ElogV)
Space complexity: O(E+V)

C++

// Author: Huahua

class Solution {

public:

double maxProbability(int n, vector<vector<int>>& edges,

vector<double>& succProb, int start, int end) {

vector<vector<pair<int, double>>> g(n); // u -> {v, -log(w)}

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

const double w = -log(succProb[i]);

g[edges[i][0]].emplace_back(edges[i][1], w);

g[edges[i][1]].emplace_back(edges[i][0], w);

}

vector<double> dist(n, FLT_MAX);

priority_queue<pair<double, int>> q;

q.emplace(-0.0, start);

vector<int> seen(n);

while (!q.empty()) {

const double d = -q.top().first;

const int u = q.top().second;

q.pop();

seen[u] = 1;

if (u == end) return exp(-d);

for (const auto& [v, w] : g[u]) {

if (seen[v] || d + w > dist[v]) continue;

q.emplace(-(dist[v] = d + w), v);

}

return 0;

}

};

Java

// Author: Huahua

import java.util.AbstractMap;

class Solution {

public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {

var g = new ArrayList<List<Map.Entry<Integer, Double>>>();

for (int i = 0; i < n; ++i) g.add(new ArrayList<Map.Entry<Integer, Double>>());

for (int i = 0; i < edges.length; ++i) {

g.get(edges[i][0]).add(new AbstractMap.SimpleEntry<>(edges[i][1], -Math.log(succProb[i])));

g.get(edges[i][1]).add(new AbstractMap.SimpleEntry<>(edges[i][0], -Math.log(succProb[i])));

}

var seen = new boolean[n];

var dist = new double[n];

Arrays.fill(dist, Double.MAX_VALUE);

seen[start] = true;

dist[start] = 0.0;

// {u, dist[u]}

var q = new PriorityQueue<Map.Entry<Integer, Double>>(Map.Entry.comparingByValue());

q.offer(new AbstractMap.SimpleEntry<>(start, 0.0));

while (!q.isEmpty()) {

var node = q.poll();

final int u = node.getKey();

if (u == end) return Math.exp(-dist[end]);

seen[u] = true;

for (var e : g.get(u)) {

final int v = e.getKey();

final double w = e.getValue();

if (seen[v] || dist[u] + w > dist[v]) continue;

dist[v] = dist[u] + w;

q.offer(new AbstractMap.SimpleEntry<>(v, dist[v]));

}

return 0;

}

Python3

# Author: Huahua

class Solution:

def maxProbability(self, n: int, edges: List[List[int]],

succProb: List[float], start: int, end: int) -> float:

g = [[] for _ in range(n)]

for i, e in enumerate(edges):

g[e[0]].append((e[1], -math.log(succProb[i])))

g[e[1]].append((e[0], -math.log(succProb[i])))

seen = [False] * n

dist = [float('inf')] * n

dist[start] = 0.0

q = [(dist[start], start)]

while q:

_, u = heapq.heappop(q)

if seen[u]: continue

seen[u] = True

if u == end: return math.exp(-dist[u])

for v, w in g[u]:

if seen[v] or dist[u] + w > dist[v]: continue

dist[v] = dist[u] + w

heapq.heappush(q, (dist[v], v))

return 0

花花酱 LeetCode 1508. Range Sum of Sorted Subarray Sums

By zxi on July 11, 2020

Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.

Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.

Example 1:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13 
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.

Example 2:

Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.

Example 3:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50

Constraints:

1 <= nums.length <= 10^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2

Solution 1: Brute Force

Find sums of all the subarrays and sort the values.

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

C++

// Author: Huahua

class Solution {

public:

int rangeSum(vector<int>& nums, int n, int left, int right) {

constexpr int kMod = 1e9 + 7;

vector<int> sums;

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

for (int j = i, sum = 0; j < n; ++j)

sums.push_back(sum += nums[j]);

sort(begin(sums), end(sums));

return accumulate(begin(sums) + left - 1, begin(sums) + right, 0LL) % kMod;

}

};

Java

// Author: Huahua

class Solution {

public int rangeSum(int[] nums, int n, int left, int right) {

final int kMod = (int)(1e9 + 7);

int[] sums = new int[n * (n + 1) / 2];

int idx = 0;

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

for (int j = i, sum = 0; j < n; ++j, ++idx)

sums[idx] = sum += nums[j];

Arrays.sort(sums);

int ans = 0;

for (int i = left; i <= right; ++i)

ans = (ans + sums[i - 1]) % kMod;

return ans;

}

Python3

# Author: Huahua

class Solution:

def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:

sums = []

for i in range(n):

s = 0

for j in range(i, n):

s += nums[j]

sums.append(s)

sums.sort()

return sum(sums[left - 1:right])

Solution 2: Priority Queue / Min Heap

For each subarray, start with one element e.g nums[i], put them into a priority queue (min heap). Each time, we have the smallest subarray sum, and extend that subarray and put the new sum back into priority queue. Thought it has the same time complexity as the brute force one in worst case, but space complexity can be reduce to O(n).

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

C++

struct Entry {

int sum;

int i;

bool operator<(const Entry& e) const { return sum > e.sum; }

};

class Solution {

public:

int rangeSum(vector<int>& nums, int n, int left, int right) {

constexpr int kMod = 1e9 + 7;

priority_queue<Entry> q; // Sort by e.sum in descending order.

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

q.push({nums[i], i});

long ans = 0;

for (int j = 1; j <= right; ++j) {

const auto e = std::move(q.top()); q.pop();

if (j >= left) ans += e.sum;

if (e.i + 1 < n) q.push({e.sum + nums[e.i + 1], e.i + 1});

}

return ans % kMod;

}

};

Java

import java.util.AbstractMap;

class Solution {

public int rangeSum(int[] nums, int n, int left, int right) {

final int kMod = (int)(1e9 + 7);

var q = new PriorityQueue<Map.Entry<Integer, Integer>>((a, b) -> a.getKey() - b.getKey());

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

q.offer(new AbstractMap.SimpleEntry<>(nums[i], i));

int ans = 0;

for (int k = 1; k <= right; ++k) {

var e = q.poll();

int sum = e.getKey();

int i = e.getValue();

if (k >= left)

ans = (ans + sum) % kMod;

if (i + 1 < n)

q.offer(new AbstractMap.SimpleEntry<>(sum + nums[i + 1], i + 1));

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:

q = [(num, i) for i, num in enumerate(nums)]

heapq.heapify(q)

ans = 0

for k in range(1, right + 1):

s, i = heapq.heappop(q)

if k >= left:

ans += s

if i + 1 < n:

heapq.heappush(q, (s + nums[i + 1], i + 1))

return ans % int(1e9 + 7)

Solution 3: Binary Search + Sliding Window

Use binary search to find S s.t. that there are at least k subarrys have sum <= S.

Given S, we can use sliding window to count how many subarrays have sum <= S and their total sum.

ans = sums_of_first(right) – sums_of_first(left – 1).

Time complexity: O(n * log(sum(nums))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int rangeSum(vector<int>& nums, int n, int left, int right) {

constexpr int kMod = 1e9 + 7;

// Returns number of subarrays that have

// sum <= target and their total sum.

auto countAndSum = [&](int target) -> pair<int, long> {

int count = 0;

long cur = 0;

long sum = 0;

long total_sum = 0;

for (long j = 0, i = 0; j < n; ++j) {

cur += nums[j];

sum += nums[j] * (j - i + 1);

while (cur > target) {

sum -= cur;

cur -= nums[i++];

}

count += j - i + 1;

total_sum += sum;

}

return {count, total_sum};

};

// Returns the total sums of smallest k subarrays.

// Use binary search to find the smallest sum l s.t.

// there are at least k of subarrays have sums <= l.

const int min_sum = *min_element(begin(nums), end(nums));

const int max_sum = accumulate(begin(nums), end(nums), 0) + 1;

auto sumOfFirstK = [&](int k) -> long {

int l = min_sum;

int r = max_sum;

while (l < r) {

int mid = l + (r - l) / 2;

if (countAndSum(mid).first >= k)

r = mid;

else

l = mid + 1;

}

const auto [count, sum] = countAndSum(l);

// There can be more subarrays have the same sum of l.

return sum - l * (count - k);

};

return (sumOfFirstK(right) - sumOfFirstK(left - 1)) % kMod;

}

};

花花酱 LeetCode 1507. Reformat Date

By zxi on July 11, 2020

Given a date string in the form Day Month Year, where:

Day is in the set {"1st", "2nd", "3rd", "4th", ..., "30th", "31st"}.
Month is in the set {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"}.
Year is in the range [1900, 2100].

Convert the date string to the format YYYY-MM-DD, where:

YYYY denotes the 4 digit year.
MM denotes the 2 digit month.
DD denotes the 2 digit day.

Example 1:

Input: date = "20th Oct 2052"
Output: "2052-10-20"

Example 2:

Input: date = "6th Jun 1933"
Output: "1933-06-06"

Example 3:

Input: date = "26th May 1960"
Output: "1960-05-26"

Constraints:

The given dates are guaranteed to be valid, so no error handling is necessary.

Solution: String + HashTable

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

C++

// Author: Huahua

class Solution {

public:

string reformatDate(string date) {

stringstream ss(date);

string day, month, year;

ss >> day >> month >> year;

unordered_map<string, string> m{{"Jan", "01"},

{"Feb", "02"},

{"Mar", "03"},

{"Apr", "04"},

{"May", "05"},

{"Jun", "06"},

{"Jul", "07"},

{"Aug", "08"},

{"Sep", "09"},

{"Oct", "10"},

{"Nov", "11"},

{"Dec", "12"}};

day = day.substr(0, day.length() - 2);

if (day.length() == 1) day = "0" + day;

return year + "-" + m[month] + "-" + day;

}

};

Java

// Author: Huahua

class Solution {

public String reformatDate(String date) {

Map<String, String> m = new HashMap<String, String>();

m.put("Jan", "01");

m.put("Feb", "02");

m.put("Mar", "03");

m.put("Apr", "04");

m.put("May", "05");

m.put("Jun", "06");

m.put("Jul", "07");

m.put("Aug", "08");

m.put("Sep", "09");

m.put("Oct", "10");

m.put("Nov", "11");

m.put("Dec", "12");

String[] items = date.split(" ");

String day = items[0].substring(0, items[0].length() - 2);

if (day.length() == 1) day = "0" + day;

return items[2] + "-" + m.get(items[1]) + "-" + day;

}

Python

# Author: Huahua

class Solution:

def reformatDate(self, date: str) -> str:

m = {"Jan": "01", "Feb": "02", "Mar": "03",

"Apr": "04", "May": "05", "Jun": "06",

"Jul": "07", "Aug": "08", "Sep": "09",

"Oct": "10", "Nov": "11", "Dec": "12"}

items = date.split(" ")

day = items[0][:-2]

if len(day) == 1: day = "0" + day

return items[2] + "-" + m[items[1]] + "-" + day

Huahua's Tech Road

花花酱 LeetCode 1510. Stone Game IV

Solution: Recursion w/ Memoization / DP

C++

Java

Python3

花花酱 LeetCode 1512. Number of Good Pairs

Solution 1: Brute Force

C++

Java

Python3

Solution 2: Hashtable

C++

Java

Python3

花花酱 LeetCode 1514. Path with Maximum Probability

Solution: Dijkstra’s Algorithm

C++

Java

Python3

花花酱 LeetCode 1508. Range Sum of Sorted Subarray Sums

Solution 1: Brute Force

C++

Java

Python3

Solution 2: Priority Queue / Min Heap

C++

Java

Python3

Solution 3: Binary Search + Sliding Window

C++

花花酱 LeetCode 1507. Reformat Date

Solution: String + HashTable

C++

Java

Python