Huahua’s Tech Road

花花酱 LeetCode 1329. Sort the Matrix Diagonally

By zxi on January 26, 2020

Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.

Example 1:

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

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100

Solution: HashTable

Collect each diagonal’s (keyed by i – j) elements into an array and sort it separately.
If we offset the key by n, e.g. i – j + n, we can use an array instead of a hashtable.

Time complexity: O(m*n + (m+n) * (m+n) * log(m + n))) = (n^2*logn)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {

const int m = mat.size();

const int n = mat[0].size();

vector<deque<int>> qs(m + n);

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

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

qs[i - j + n].push_back(mat[i][j]);

for (auto& q : qs)

sort(begin(q), end(q));

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

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

mat[i][j] = qs[i - j + n].front();

qs[i - j + n].pop_front();

}

return mat;

}

};

花花酱 LeetCode 1328. Break a Palindrome

By zxi on January 26, 2020

Given a palindromic string palindrome, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn’t a palindrome.

After doing so, return the final string. If there is no way to do so, return the empty string.

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"

Example 2:

Input: palindrome = "a"
Output: ""

Constraints:

1 <= palindrome.length <= 1000
palindrome consists of only lowercase English letters.

Solution: Greedy

For the first half of the string, replace the first non ‘a’ character to ‘a’.

e.g. abcdcba => aacdcba

If not found which means the the entire string is ‘a’ expect the middle one if the length is odd, like aa or aba, replace the last character to ‘b’.

aa => ab
aba => abb

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

C++

// Author: Huahua

class Solution {

public:

string breakPalindrome(string palindrome) {

const int n = palindrome.length();

if (n == 1) return "";

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

if (palindrome[i] != 'a') {

palindrome[i] = 'a';

return palindrome;

}

palindrome.back() = 'b';

return palindrome;

}

};

花花酱 Minimum Spanning Tree (MST) 最小生成树 SP18

By zxi on January 24, 2020

Prim’s Algorithm

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

C++

// Author: Huahua

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

int main(int argc, char** argv) {

const int n = 4;

vector<vector<int>> edges{{0,1,1},{0,3,3},{0,2,6},{2,3,2},{1,2,4},{1,3,5}};

vector<vector<pair<int, int>>> g(n);

for (const auto& e : edges) {

g[e[0]].emplace_back(e[1], e[2]);

g[e[1]].emplace_back(e[0], e[2]);

}

priority_queue<pair<int, int>> q; // (-w, v)

vector<int> seen(n);

q.emplace(0, 0); // (-w, v)

int cost = 0;

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

while (true) {

const int w = -q.top().first;

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

q.pop();

if (seen[v]++) continue;

cost += w;

for (const auto& p : g[v]) {

if (seen[p.first]) continue;

q.emplace(-p.second, p.first);

}

break;

}

cout << cost << endl;

return 0;

}

Python

# Author: Huahua

from collections import defaultdict

from heapq import *

n = 4

edges = [[0,1,1],[0,3,3],[0,2,6],[2,3,2],[1,2,4],[1,3,5]]

g = defaultdict(list)

for e in edges:

g[e[0]].append((e[1], e[2]))

g[e[1]].append((e[0], e[2]))

q = []

cost = 0

seen = set()

heappush(q, (0, 0))

for _ in range(n):

while True:

w, u = heappop(q)

if u in seen: continue

cost += w

seen.add(u)

for v, w in g[u]:

if v in seen: continue

heappush(q, (w, v))

break

print(cost)

Kruskal’s Algorithm

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

C++

// Author: Huahua

#include <iostream>

#include <queue>

#include <vector>

#include <functional>

#include <numeric>

using namespace std;

int main(int argc, char** argv) {

const int n = 4;

vector<vector<int>> edges{{0,1,1},{0,3,3},{0,2,6},{2,3,2},{1,2,4},{1,3,5}};

vector<vector<int>> q; // (w, u, v)

for (const auto& e : edges)

q.push_back({e[2], e[0], e[1]});

sort(begin(q), end(q));

vector<int> p(n);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

return x == p[x] ? x : p[x] = find(p[p[x]]);

};

int cost = 0;

for (const auto& t : q) {

int w = t[0], u = t[1], v = t[2];

int ru = find(u), rv = find(v);

if (ru == rv) continue;

p[ru] = rv; // merge (u, v)

cost += w;

}

cout << cost << endl;

return 0;

}

Python

from collections import defaultdict

from heapq import *

n = 4

edges = [[0,1,1],[0,3,3],[0,2,6],[2,3,2],[1,2,4],[1,3,5]]

p = list(range(n))

def find(x):

if x != p[x]: p[x] = find(p[p[x]])

return p[x]

cost = 0

for u, v, w in sorted(edges, key=lambda x: x[2]):

ru, rv = find(u), find(v)

if ru == rv: continue

p[ru] = rv

cost += w

print(cost)

花花酱 LeetCode 1323. Maximum 69 Number

By zxi on January 20, 2020

Given a positive integer num consisting only of digits 6 and 9.

Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

Example 1:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666. 
The maximum number is 9969.

Example 2:

Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.

Example 3:

Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.

Constraints:

1 <= num <= 10^4
num‘s digits are 6 or 9.

Solution: Greedy

Replace the highest 6 to 9, if no 6, return the original number.

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

C++

// Author: Huahua

class Solution {

public:

int maximum69Number (int num) {

string s = to_string(num);

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

if (s[i] == '6') {

s[i] = '9';

return stoi(s);

}

return num;

}

};

花花酱 LeetCode 1325. Delete Leaves With a Given Value

By zxi on January 20, 2020

Given a binary tree root and an integer target, delete all the leaf nodes with value target.

Note that once you delete a leaf node with value target, if it’s parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you can’t).

Example 1:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

Example 2:

Input: root = [1,3,3,3,2], target = 3
Output: [1,3,null,null,2]

Example 3:

Input: root = [1,2,null,2,null,2], target = 2
Output: [1]
Explanation: Leaf nodes in green with value (target = 2) are removed at each step.

Example 4:

Input: root = [1,1,1], target = 1
Output: []

Example 5:

Input: root = [1,2,3], target = 1
Output: [1,2,3]

Constraints:

1 <= target <= 1000
Each tree has at most 3000 nodes.
Each node’s value is between [1, 1000].

Solution: Recursion

Post-order traversal

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* removeLeafNodes(TreeNode* root, int target) {

if (!root) return nullptr;

root->left = removeLeafNodes(root->left, target);

root->right = removeLeafNodes(root->right, target);

return root->left || root->right || root->val != target

? root : nullptr;

}

};

Huahua's Tech Road

花花酱 LeetCode 1329. Sort the Matrix Diagonally

Solution: HashTable

C++

花花酱 LeetCode 1328. Break a Palindrome

Solution: Greedy

C++

花花酱 Minimum Spanning Tree (MST) 最小生成树 SP18

Prim’s Algorithm

C++

Python

Kruskal’s Algorithm

C++

Python

花花酱 LeetCode 1323. Maximum 69 Number

Solution: Greedy

C++

花花酱 LeetCode 1325. Delete Leaves With a Given Value

Solution: Recursion

C++