花花酱 LeetCode 433. Minimum Genetic Mutation

By zxi on March 24, 2018

Problem

题目大意：给你一个基因库，问一个基因最少需要变异多少次才能变为另外一个基因。每次变异只能修改一个字符，并且必须在基因库里。

https://leetcode.com/problems/minimum-genetic-mutation/description/

A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T".

Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things – start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.

Note:

Starting point is assumed to be valid, so it might not be included in the bank.
If multiple mutations are needed, all mutations during in the sequence must be valid.
You may assume start and end string is not the same.

Example 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1

Example 2:

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2

Example 3:

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3

Solution: BFS Shortest Path

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int minMutation(string start, string end, vector<string>& bank) {

queue<string> q;

q.push(start);

unordered_set<string> visited;

visited.insert(start);

int mutations = 0;

while (!q.empty()) {

size_t size = q.size();

while (size--) {

string curr = std::move(q.front()); q.pop();

if (curr == end) return mutations;

for (const string& gene : bank) {

if (visited.count(gene) || !validMutation(curr, gene)) continue;

visited.insert(gene);

q.push(gene);

}

++mutations;

}

return -1;

}

private:

bool validMutation(const string& s1, const string& s2) {

int count = 0;

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

if (s1[i] != s2[i] && count++) return false;

return true;

}

};

花花酱 LeetCode 437. Path Sum III

By zxi on March 24, 2018

Problem

题目大意：给你一棵二叉树，返回单向的路径和等于sum的路径数量。

https://leetcode.com/problems/path-sum-iii/description/

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Solution 1: Recursion

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 21 ms

class Solution {

public:

int pathSum(TreeNode* root, int sum) {

if (!root) return 0;

return numberOfPaths(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);

}

private:

int numberOfPaths(TreeNode* root, int left) {

if (!root) return 0;

left -= root->val;

return (left == 0 ? 1 : 0) + numberOfPaths(root->left, left) + numberOfPaths(root->right, left);

}

};

Solution 2: Running Prefix Sum

Same idea to 花花酱 LeetCode 560. Subarray Sum Equals K

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 13 ms (beats 97.74%)

public:

int pathSum(TreeNode* root, int sum) {

ans_ = 0;

sums_ = {{0, 1}};

pathSum(root, 0, sum);

return ans_;

}

private:

int ans_;

unordered_map<int, int> sums_;

void pathSum(TreeNode* root, int cur, int sum) {

if (!root) return;

cur += root->val;

ans_ += sums_[cur - sum];

++sums_[cur];

pathSum(root->left, cur, sum);

pathSum(root->right, cur, sum);

--sums_[cur];

}

};

Problem

题目大意：返回字符串中的非空白字符连续的字串数量。

https://leetcode.com/problems/number-of-segments-in-a-string/description/

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable characters.

Example:

Input: "Hello, my name is John"
Output: 5

Solution

Be aware of special cases: like ” “.

Time complexity: O(n)

Space complexity: O(1)

C++

class Solution {

public:

int countSegments(string s) {

if (s.empty()) return 0;

int ans = 0;

int i = 0;

while (i < s.length()) {

while (i < s.length() && s[i] == ' ') ++i;

if (i == s.length()) break;

while (i < s.length() && s[i] != ' ') ++i;

++ans;

++i;

}

return ans;

}

};

Python3

"""

Author: Huahua

Running time: 40 ms

"""

class Solution:

def countSegments(self, s):

return len(s.split())

花花酱 LeetCode 94. Binary Tree Inorder Traversal

By zxi on March 23, 2018

Problem

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

For example:
Given binary tree [1,null,2,3],

return [1,3,2].

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

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

vector<int> inorderTraversal(TreeNode* root) {

vector<int> ans;

inorderTraversal(root, ans);

return ans;

}

private:

void inorderTraversal(TreeNode* root, vector<int>& ans) {

if (root == nullptr) return;

inorderTraversal(root->left, ans);

ans.push_back(root->val);

inorderTraversal(root->right, ans);

}

};

Solution 2: Iterative

// Author: Huahua

// Running time: 3 ms

lass Solution {

public:

vector<int> inorderTraversal(TreeNode* root) {

if (root == nullptr) return {};

vector<int> ans;

stack<TreeNode*> s;

TreeNode* curr = root;

while (curr != nullptr || !s.empty()) {

while (curr != nullptr) {

s.push(curr);

curr = curr->left;

}

curr = s.top(); s.pop();

ans.push_back(curr->val);

curr = curr->right;

}

return ans;

}

};

花花酱 LeetCode 448. Find All Numbers Disappeared in an Array

By zxi on March 23, 2018

Problem

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 128 ms (beats 93.70%)

class Solution {

public:

vector<int> findDisappearedNumbers(vector<int>& nums) {

for (size_t i = 0; i != nums.size(); ++i) {

int index = abs(nums[i]) - 1;

if (nums[index] > 0) nums[index] *= -1;

}

vector<int> ans;

for (size_t i = 0; i != nums.size(); ++i)

if (nums[i] > 0) ans.push_back(i + 1);

return ans;

}

};

Posts published in March 2018

花花酱 LeetCode 433. Minimum Genetic Mutation

Problem

Solution: BFS Shortest Path

花花酱 LeetCode 437. Path Sum III

Problem

Example:

Solution 1: Recursion

Solution 2: Running Prefix Sum

Related Problem

花花酱 LeetCode 434. Number of Segments in a String

Problem

Solution

花花酱 LeetCode 94. Binary Tree Inorder Traversal

Problem

Solution: Recursion

Solution 2: Iterative

花花酱 LeetCode 448. Find All Numbers Disappeared in an Array

Problem

Solution