easy – Page 43 – Huahua’s Tech Road

花花酱 LeetCode 144. Binary Tree Preorder Traversal

By zxi on January 29, 2020

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution 1: Recursion

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

C++

// Author: Huahua

class Solution {

public:

vector<int> preorderTraversal(TreeNode* root) {

vector<int> ans;

function<void(TreeNode*)> preorder = [&](TreeNode* n) {

if (!n) return;

ans.push_back(n->val);

preorder(n->left);

preorder(n->right);

};

preorder(root);

return ans;

}

};

Solution 2: Stack

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

C++

// Author: Huahua

class Solution {

public:

vector<int> preorderTraversal(TreeNode* root) {

vector<int> ans;

stack<TreeNode*> s;

if (root) s.push(root);

while (!s.empty()) {

TreeNode* n = s.top();

ans.push_back(n->val);

s.pop();

if (n->right) s.push(n->right);

if (n->left) s.push(n->left);

}

return ans;

}

花花酱 LeetCode 1332. Remove Palindromic Subsequences

By zxi on January 26, 2020

Given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string, if it is generated by deleting some characters of a given string without changing its order.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

Input: s = "ababa"
Output: 1
Explanation: String is already palindrome

Example 2:

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "". 
Remove palindromic subsequence "a" then "bb".

Example 3:

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "". 
Remove palindromic subsequence "baab" then "b".

Example 4:

Input: s = ""
Output: 0

Constraints:

0 <= s.length <= 1000
s only consists of letters ‘a’ and ‘b’

Solution: Math

if s is empty => 0 step
if s is a palindrome => 1 step
Otherwise, 2 steps…
1. delete all the as
2. delete all the bs

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

C++

// Author: Huahua

class Solution {

public:

int removePalindromeSub(string s) {

if (s.empty()) return 0;

if (s == string(rbegin(s), rend(s))) return 1;

return 2;

}

};

花花酱 LeetCode 1331. Rank Transform of an Array

By zxi on January 26, 2020

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

Rank is an integer starting from 1.
The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
Rank should be as small as possible.

Example 1:

Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3:

Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]

Constraints:

0 <= arr.length <= 10⁵
-10⁹ <= arr[i] <= 10⁹

Solution: Sorting + HashTable

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

C++

// Author: Huahua

class Solution {

public:

vector<int> arrayRankTransform(vector<int>& arr) {

set<int> s(begin(arr), end(arr));

unordered_map<int, int> m;

int r = 0;

for (const int v : s) m[v] = ++r;

vector<int> ans(arr.size());

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

ans[i] = m[arr[i]];

return ans;

}

};

花花酱 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 1317. Convert Integer to the Sum of Two No-Zero Integers

By zxi on January 13, 2020

Given an integer n. No-Zero integer is a positive integer which doesn’t contain any 0 in its decimal representation.

Return a list of two integers [A, B] where:

A and B are No-Zero integers.
A + B = n

It’s guarateed that there is at least one valid solution. If there are many valid solutions you can return any of them.

Example 1:

Input: n = 2

Output: [1,1]

Explanation: A = 1, B = 1. A + B = n and both A and B don't contain any 0 in their decimal representation.

Example 2:

1 2	<strong>Input:</strong> n = 11 <strong>Output:</strong> [2,9]

Example 3:

1 2	<strong>Input:</strong> n = 10000 <strong>Output:</strong> [1,9999]

Example 4:

1 2	<strong>Input:</strong> n = 69 <strong>Output:</strong> [1,68]

Example 5:

1 2	<strong>Input:</strong> n = 1010 <strong>Output:</strong> [11,999]

Constraints:

2 <= n <= 10^4

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getNoZeroIntegers(int n) {

auto valid = [](int x) {

if (!x) return false;

while (x) {

if (x % 10 == 0) return false;

x /= 10;

}

return true;

};

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

if (valid(i) && valid(n - i))

return {i, n - i};

return {};

}

};

Posts tagged as “easy”

花花酱 LeetCode 144. Binary Tree Preorder Traversal

Solution 1: Recursion

C++

Solution 2: Stack

C++

花花酱 LeetCode 1332. Remove Palindromic Subsequences

Solution: Math

C++

花花酱 LeetCode 1331. Rank Transform of an Array

Solution: Sorting + HashTable

C++

花花酱 LeetCode 1323. Maximum 69 Number

Solution: Greedy

C++

花花酱 LeetCode 1317. Convert Integer to the Sum of Two No-Zero Integers

Solution: Brute Force

C++