Posts tagged as “easy”

花花酱 LeetCode 111. Minimum Depth of Binary Tree

By zxi on December 15, 2018

Problem

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its minimum depth = 2.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 4 ms

class Solution {

public:

int minDepth(TreeNode* root) {

if (!root) return 0;

if (!root->left && !root->right) return 1;

int l = root->left ? minDepth(root->left) : INT_MAX;

int r = root->right ? minDepth(root->right) : INT_MAX;

return min(l, r) + 1;

}

};

Python3

class Solution:

def minDepth(self, root):

if not root: return 0

if not root.left and not root.right: return 1

l = self.minDepth(root.left)

r = self.minDepth(root.right)

if not root.left: return 1 + r

if not root.right: return 1 + l

return 1 + min(l, r)

Problem

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its depth = 3.

Solution: Recursion

maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 4 ms

class Solution {

public:

int maxDepth(TreeNode* root) {

if (!root) return 0;

int l = maxDepth(root->left);

int r = maxDepth(root->right);

return max(l, r) + 1;

}

};

Python3

# Author: Huahua, 80 ms

class Solution:

def maxDepth(self, root):

if not root: return 0

l = self.maxDepth(root.left)

r = self.maxDepth(root.right)

return max(l, r) + 1

花花酱 LeetCode 953. Verifying an Alien Dictionary

By zxi on December 9, 2018

Problem

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Example 1:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2:

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

Example 3:

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

Note:

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
All characters in words[i] and order are english lowercase letters.

Solution: Hashtable

Time complexity: O(sum(len(words[i])))

Space complexity: O(26)

C++

// Author: Huahua, 8 ms

class Solution {

public:

bool isAlienSorted(vector<string>& words, string order) {

vector<char> m(26);

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

m[order[i] - 'a'] = 'a' + i;

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

for (int j = 0; j < words[i].length(); ++j)

words[i][j] = m[words[i][j] - 'a'];

if (i > 0 && words[i] < words[i - 1]) return false;

}

return true;

}

};

花花酱 LeetCode 942. DI String Match

By zxi on November 18, 2018

Problem

Given a string S that only contains “I” (increase) or “D” (decrease), let N = S.length.

Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

If S[i] == "I", then A[i] < A[i+1]
If S[i] == "D", then A[i] > A[i+1]

Example 1:

Input: "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: "III"
Output: [0,1,2,3]

Example 3:

Input: "DDI"
Output: [3,2,0,1]

Note:

1 <= S.length <= 10000
S only contains characters "I" or "D".

Solution: Greedy

“I” -> use the smallest possible number

“D” -> use the largest possible number

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 44 ms

class Solution {

public:

vector<int> diStringMatch(string S) {

const int n = S.length();

vector<int> ans;

int lo = 0;

int hi = n;

for (char c : S) {

if (c == 'I')

ans.push_back(lo++);

else

ans.push_back(hi--);

}

ans.push_back(lo);

return ans;

}

};

花花酱 LeetCode 941. Valid Mountain Array

By zxi on November 18, 2018

Problem

Given an array A of integers, return true if and only if it is a valid mountain array.

Recall that A is a mountain array if and only if:

A.length >= 3
There exists some i with 0 < i < A.length - 1 such that:
- A[0] < A[1] < ... A[i-1] < A[i]
- A[i] > A[i+1] > ... > A[B.length - 1]

Example 1:

Input: [2,1]
Output: false

Example 2:

Input: [3,5,5]
Output: false

Example 3:

Input: [0,3,2,1]
Output: true

Note:

0 <= A.length <= 10000
0 <= A[i] <= 10000

Solution

Use has_up and has_down to track whether we have A[i] > A[i – 1] and A[i] < A[i – 1] receptively.

return false if any of the following happened:

size(A) < 3
has_down happened before has_up
not has_down or not has_up
A[i – 1] < A[i] after has_down
A[i – 1] > A[i] before has_up

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 24 ms

class Solution {

public:

bool validMountainArray(vector<int>& A) {

if (A.size() < 3) return false;

bool has_up = false;

bool has_down = false;

for (int i = 1; i < A.size(); ++i) {

if (A[i] > A[i - 1]) {

if (has_down) return false;

has_up = true;

}

else if (A[i] < A[i - 1]){

if (!has_up) return false;

has_down = true;

} else {

return false;

}

return has_up && has_down;

}

};

Posts tagged as “easy”

花花酱 LeetCode 111. Minimum Depth of Binary Tree

Problem

Solution: Recursion

C++

Python3

Related Problem

花花酱 LeetCode 104. Maximum Depth of Binary Tree

Problem

Solution: Recursion

C++

Python3

花花酱 LeetCode 953. Verifying an Alien Dictionary

Problem

Solution: Hashtable

C++

花花酱 LeetCode 942. DI String Match

Problem

Solution: Greedy

C++

花花酱 LeetCode 941. Valid Mountain Array

Problem

Solution

C++