Huahua’s Tech Road

花花酱 LeetCode 1796. Second Largest Digit in a String

By zxi on March 20, 2021

Given an alphanumeric string s, return the second largest numerical digit that appears in s, or -1 if it does not exist.

An alphanumericstring is a string consisting of lowercase English letters and digits.

Example 1:

Input: s = "dfa12321afd"
Output: 2
Explanation: The digits that appear in s are [1, 2, 3]. The second largest digit is 2.

Example 2:

Input: s = "abc1111"
Output: -1
Explanation: The digits that appear in s are [1]. There is no second largest digit.

Constraints:

1 <= s.length <= 500
s consists of only lowercase English letters and/or digits.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int secondHighest(string s) {

vector<int> d(10);

for (char c : s)

if (c >= '0' && c <= '9')

d[c - '0'] = 1;

int order = 0;

for (int i = 9; i >= 0; --i)

if (d[i] && ++order == 2)

return i;

return -1;

}

};

花花酱 LeetCode 1793. Maximum Score of a Good Subarray

By zxi on March 18, 2021

You are given an array of integers nums (0-indexed) and an integer k.

The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). A good subarray is a subarray where i <= k <= j.

Return the maximum possible score of a good subarray.

Example 1:

Input: nums = [1,4,3,7,4,5], k = 3
Output: 15
Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15.

Example 2:

Input: nums = [5,5,4,5,4,1,1,1], k = 0
Output: 20
Explanation: The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 2 * 10⁴
0 <= k < nums.length

Solutions: Two Pointers

maintain a window [i, j], m = min(nums[i~j]), expend to the left if nums[i – 1] >= nums[j + 1], otherwise expend to the right.

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

C++

// Author: Huahua

class Solution {

public:

int maximumScore(vector<int>& nums, int k) {

const int n = nums.size();

int ans = 0;

for (int i = k, j = k, m = nums[k];;) {

ans = max(ans, m * (j - i + 1));

if (j - i + 1 == n) break;

int l = i ? nums[i - 1] : -1;

int r = j + 1 < n ? nums[j + 1] : -1;

if (l >= r)

m = min(m, nums[--i]);

else

m = min(m, nums[++j]);

}

return ans;

}

};

花花酱 LeetCode 1792. Maximum Average Pass Ratio

By zxi on March 13, 2021

There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes, where classes[i] = [pass_i, total_i]. You know beforehand that in the i^th class, there are total_i total students, but only pass_i number of students will pass the exam.

You are also given an integer extraStudents. There are another extraStudents brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents students to a class in a way that maximizes the average pass ratio across all the classes.

The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.

Return the maximum possible average pass ratio after assigning the extraStudents students. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Output: 0.78333
Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.

Example 2:

Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
Output: 0.53485

Constraints:

1 <= classes.length <= 10⁵
classes[i].length == 2
1 <= pass_i <= total_i <= 10⁵
1 <= extraStudents <= 10⁵

Solution: Greedy + Heap

Sort by the ratio increase potential (p + 1) / (t + 1) – p / t.

Time complexity: O((m+n)logn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {

const int n = classes.size();

auto ratio = [&](int i, int delta = 0) {

return static_cast<double>(classes[i][0] + delta) /

(classes[i][1] + delta);

};

priority_queue<pair<double, int>> q;

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

q.emplace(ratio(i, 1) - ratio(i), i);

while (extraStudents--) {

const auto [r, i] = q.top(); q.pop();

++classes[i][0];

++classes[i][1];

q.emplace(ratio(i, 1) - ratio(i), i);

}

double total_ratio = 0;

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

total_ratio += ratio(i);

return total_ratio / n;

}

};

Python3

# Author: Huahua

class Solution:

def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:

def ratio(i, delta=0):

return (classes[i][0] + delta) / (classes[i][1] + delta)

q = []

for i, c in enumerate(classes):

heapq.heappush(q, (-(ratio(i, 1) - ratio(i)), i))

for _ in range(extraStudents):

_, i = heapq.heappop(q)

classes[i][0] += 1

classes[i][1] += 1

heapq.heappush(q, (-(ratio(i, 1) - ratio(i)), i))

return mean(ratio(i) for i, _ in enumerate(classes))

花花酱 LeetCode 1791. Find Center of Star Graph

By zxi on March 13, 2021

There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.

You are given a 2D integer array edges where each edges[i] = [u_i, v_i] indicates that there is an edge between the nodes u_i and v_i. Return the center of the given star graph.

Example 1:

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

Example 2:

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

Constraints:

3 <= n <= 10⁵
edges.length == n - 1
edges[i].length == 2
1 <= u_i, v_i <= n
u_i != v_i
The given edges represent a valid star graph.

Solution: Graph / Hashtable

Count the degree of each node, return the one with n-1 degrees.

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

C++

// Author: Huahua

class Solution {

public:

int findCenter(vector<vector<int>>& edges) {

unordered_map<int, int> degrees;

for (const auto& e : edges) {

++degrees[e[0]];

++degrees[e[1]];

}

const int n = degrees.size();

for (const auto& [id, d] : degrees)

if (d == n - 1) return id;

return -1;

}

};

Since the center node must appear in each edge, we just need to find the mode of edges[0] + edges[1]

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

Python

# Author: Huahua

class Solution:

def findCenter(self, e):

return mode(e[0] + e[1])

花花酱 LeetCode 1790. Check if One String Swap Can Make Strings Equal

By zxi on March 13, 2021

You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.

Return true if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings. Otherwise, return false.

Example 1:

Input: s1 = "bank", s2 = "kanb"
Output: true
Explanation: For example, swap the first character with the last character of s2 to make "bank".

Example 2:

Input: s1 = "attack", s2 = "defend"
Output: false
Explanation: It is impossible to make them equal with one string swap.

Example 3:

Input: s1 = "kelb", s2 = "kelb"
Output: true
Explanation: The two strings are already equal, so no string swap operation is required.

Example 4:

Input: s1 = "abcd", s2 = "dcba"
Output: false

Constraints:

1 <= s1.length, s2.length <= 100
s1.length == s2.length
s1 and s2 consist of only lowercase English letters.

Solution: Remember two indices

There needs to be either 0 or 2 indices are different. Otherwise return false.
s1[idx1] == s2[idx2] and s1[idx2] == s2[idx1]

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

C++

// Author: Huahua

class Solution {

public:

bool areAlmostEqual(string s1, string s2) {

vector<int> idx;

for (int i = 0; i < s1.length() && idx.size() <= 2; ++i)

if (s1[i] != s2[i]) idx.push_back(i);

if (idx.size() == 0) return true;

if (idx.size() != 2) return false;

return s1[idx[0]] == s2[idx[1]] && s1[idx[1]] == s2[idx[0]];

}

};

Huahua's Tech Road

花花酱 LeetCode 1796. Second Largest Digit in a String

Solution: Hashtable

C++

花花酱 LeetCode 1793. Maximum Score of a Good Subarray

Solutions: Two Pointers

C++

花花酱 LeetCode 1792. Maximum Average Pass Ratio

Solution: Greedy + Heap

C++

Python3

花花酱 LeetCode 1791. Find Center of Star Graph

Solution: Graph / Hashtable

C++

Python

花花酱 LeetCode 1790. Check if One String Swap Can Make Strings Equal

Solution: Remember two indices

C++