Huahua’s Tech Road

花花酱 LeetCode 2133. Check if Every Row and Column Contains All Numbers

By zxi on January 16, 2022

An n x n matrix is valid if every row and every column contains all the integers from 1 to n (inclusive).

Given an n x n integer matrix matrix, return true if the matrix is valid. Otherwise, return false.

Example 1:

Input: matrix = [[1,2,3],[3,1,2],[2,3,1]]
Output: true
Explanation: In this case, n = 3, and every row and column contains the numbers 1, 2, and 3.
Hence, we return true.

Example 2:

Input: matrix = [[1,1,1],[1,2,3],[1,2,3]]
Output: false
Explanation: In this case, n = 3, but the first row and the first column do not contain the numbers 2 or 3.
Hence, we return false.

Constraints:

n == matrix.length == matrix[i].length
1 <= n <= 100
1 <= matrix[i][j] <= n

Solution: Bitset / hashtable

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

C++

// Author: Huahua

class Solution {

public:

bool checkValid(vector<vector<int>>& matrix) {

const int n = matrix.size();

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

bitset<101> row;

bitset<101> col;

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

col[matrix[i][j]] = row[matrix[j][i]] = true;

if (row.count() != n || col.count() != n)

return false;

}

return true;

}

};

花花酱 LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words

By zxi on January 9, 2022

You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

Example 1:

Input: words = ["lc","cl","gg"]
Output: 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Note that "clgglc" is another longest palindrome that can be created.

Example 2:

Input: words = ["ab","ty","yt","lc","cl","ab"]
Output: 8
Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.
Note that "lcyttycl" is another longest palindrome that can be created.

Example 3:

Input: words = ["cc","ll","xx"]
Output: 2
Explanation: One longest palindrome is "cc", of length 2.
Note that "ll" is another longest palindrome that can be created, and so is "xx".

Constraints:

1 <= words.length <= 10⁵
words[i].length == 2
words[i] consists of lowercase English letters.

Solution: Match mirrored words

For any pair of mirrored words, e.g. ‘ab’ <-> ‘ba’ or ‘aa’ <-> ‘aa’, we can extend the existing longest palindrome, ans += 4.
For any unpaired words with same letter, e.g. ‘cc’, we can only use one and put in the middle of the pladrome, ans += 2.

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

C++

// Author: Huahua

class Solution {

public:

int longestPalindrome(vector<string>& words) {

int ans = 0;

int same = 0;

vector<vector<int>> m(26, vector<int>(26));

for (const string& word : words) {

const int a = word[0] - 'a';

const int b = word[1] - 'a';

if (m[b][a]) {

--m[b][a];

ans += 4;

} else {

++m[a][b];

}

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

if (m[i][i]) {

ans += 2;

break;

}

return ans;

}

};

花花酱 LeetCode 2130. Maximum Twin Sum of a Linked List

By zxi on January 9, 2022

In a linked list of size n, where n is even, the i^th node (0-indexed) of the linked list is known as the twin of the (n-1-i)^th node, if 0 <= i <= (n / 2) - 1.

For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.

Example 2:

Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Example 3:

Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

Constraints:

The number of nodes in the list is an even integer in the range [2, 10⁵].
1 <= Node.val <= 10⁵

Solution: Two Pointers + Reverse List

Use fast slow pointers to find the middle point and reverse the second half.

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

C++

// Author: Huahua

class Solution {

public:

int pairSum(ListNode* head) {

auto reverse = [](ListNode* head, ListNode* prev = nullptr) {

while (head) {

swap(head->next, prev);

swap(head, prev);

}

return prev;

};

ListNode* fast = head;

ListNode* slow = head;

while (fast) {

fast = fast->next->next;

slow = slow->next;

}

slow = reverse(slow);

int ans = 0;

while (slow) {

ans = max(ans, head->val + slow->val);

head = head->next;

slow = slow->next;

}

return ans;

}

};

花花酱 LeetCode 2129. Capitalize the Title

By zxi on January 8, 2022

You are given a string title consisting of one or more words separated by a single space, where each word consists of English letters. Capitalize the string by changing the capitalization of each word such that:

If the length of the word is 1 or 2 letters, change all letters to lowercase.
Otherwise, change the first letter to uppercase and the remaining letters to lowercase.

Return the capitalized title.

Example 1:

Input: title = "capiTalIze tHe titLe"
Output: "Capitalize The Title"
Explanation:
Since all the words have a length of at least 3, the first letter of each word is uppercase, and the remaining letters are lowercase.

Example 2:

Input: title = "First leTTeR of EACH Word"
Output: "First Letter of Each Word"
Explanation:
The word "of" has length 2, so it is all lowercase.
The remaining words have a length of at least 3, so the first letter of each remaining word is uppercase, and the remaining letters are lowercase.

Example 3:

Input: title = "i lOve leetcode"
Output: "i Love Leetcode"
Explanation:
The word "i" has length 1, so it is lowercase.
The remaining words have a length of at least 3, so the first letter of each remaining word is uppercase, and the remaining letters are lowercase.

Constraints:

1 <= title.length <= 100
title consists of words separated by a single space without any leading or trailing spaces.
Each word consists of uppercase and lowercase English letters and is non-empty.

Solution: Straight forward

Without splitting the sentence into words, we need to take care the word of length one and two.

Tips: use std::tolower, std::toupper to transform letters.

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

C++

// Author: Huahua

class Solution {

public:

string capitalizeTitle(string title) {

const int n = title.size();

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

if ((i == 0 || title[i - 1] == ' ')

&& i + 2 < n && title[i + 1] != ' ' && title[i + 2] != ' ')

title[i] = toupper(title[i]);

else

title[i] = tolower(title[i]);

}

return title;

}

};

Python3

# Author: Huahua

class Solution:

def capitalizeTitle(self, title: str) -> str:

return " ".join(map(lambda w: w.lower() if len(w) <= 2 else w[0].upper() + w[1:].lower(), title.split()))

花花酱 LeetCode 2126. Destroying Asteroids

By zxi on January 2, 2022

You are given an integer mass, which represents the original mass of a planet. You are further given an integer array asteroids, where asteroids[i] is the mass of the i^th asteroid.

You can arrange for the planet to collide with the asteroids in any arbitrary order. If the mass of the planet is greater than or equal to the mass of the asteroid, the asteroid is destroyed and the planet gains the mass of the asteroid. Otherwise, the planet is destroyed.

Return true if all asteroids can be destroyed. Otherwise, return false.

Example 1:

Input: mass = 10, asteroids = [3,9,19,5,21]
Output: true
Explanation: One way to order the asteroids is [9,19,5,3,21]:
- The planet collides with the asteroid with a mass of 9. New planet mass: 10 + 9 = 19
- The planet collides with the asteroid with a mass of 19. New planet mass: 19 + 19 = 38
- The planet collides with the asteroid with a mass of 5. New planet mass: 38 + 5 = 43
- The planet collides with the asteroid with a mass of 3. New planet mass: 43 + 3 = 46
- The planet collides with the asteroid with a mass of 21. New planet mass: 46 + 21 = 67
All asteroids are destroyed.

Example 2:

Input: mass = 5, asteroids = [4,9,23,4]
Output: false
Explanation: 
The planet cannot ever gain enough mass to destroy the asteroid with a mass of 23.
After the planet destroys the other asteroids, it will have a mass of 5 + 4 + 9 + 4 = 22.
This is less than 23, so a collision would not destroy the last asteroid.

Constraints:

1 <= mass <= 10⁵
1 <= asteroids.length <= 10⁵
1 <= asteroids[i] <= 10⁵

Solution: Greedy

Sort asteroids by weight. Note, mass can be very big (10⁵*10⁵), for C++/Java, use long instead of int.

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

C++

// Author: Huahua

class Solution {

public:

bool asteroidsDestroyed(int mass, vector<int>& asteroids) {

long long curr = mass;

sort(begin(asteroids), end(asteroids));

for (int a : asteroids) {

if (curr < a) return false;

curr += a;

}

return true;

}

};

Huahua's Tech Road

花花酱 LeetCode 2133. Check if Every Row and Column Contains All Numbers

Solution: Bitset / hashtable

C++

花花酱 LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words

Solution: Match mirrored words

C++

花花酱 LeetCode 2130. Maximum Twin Sum of a Linked List

Solution: Two Pointers + Reverse List

C++

花花酱 LeetCode 2129. Capitalize the Title

Solution: Straight forward

C++

Python3

花花酱 LeetCode 2126. Destroying Asteroids

Solution: Greedy

C++