Posts tagged as “medium”

花花酱 LeetCode 332. Reconstruct Itinerary

By zxi on September 12, 2017

Problem:

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Idea:

Convert the graph to a tree and do post-order traversal

Solution:

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

vector<string> findItinerary(vector<pair<string, string>> tickets) {

route_.clear();

trips_.clear();

for(const auto& pair : tickets)

trips_[pair.first].push_back(pair.second);

for(auto& pair : trips_) {

auto& dests = pair.second;

std::sort(dests.begin(), dests.end());

}

const string kStart = "JFK";

visit(kStart);

return vector<string>(route_.crbegin(), route_.crend());

}

private:

// src -> {dst1, dest2, ..., destn}

unordered_map<string, deque<string>> trips_;

// ans (reversed)

vector<string> route_;

void visit(const string& src) {

auto& dests = trips_[src];

while (!dests.empty()) {

// Get the smallest dest

const string dest = dests.front();

// Remove the ticket

dests.pop_front();

// Visit dest

visit(dest);

}

// Add current node to the route

route_.push_back(src);

}

};

花花酱 LeetCode 300. Longest Increasing Subsequence

By zxi on September 10, 2017

Problem:

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n²) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Idea:

Dynamic Programming

Time Complexity:

O(n^2)

Solution 1:

// Author: Huahua

// Running time: 29 ms

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

if (nums.empty()) return 0;

int n = nums.size();

auto f = vector<int>(n, 1);

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

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

if (nums[i] > nums[j])

f[i] = max(f[i], f[j] + 1);

return *max_element(f.begin(), f.end());

}

};

Solution 2: DP + Binary Search / Patience Sort

dp[i] := smallest tailing number of a increasing subsequence of length i + 1.

dp is an increasing array, we can use binary search to find the index to insert/update the array.

ans = len(dp)

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

C++

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

const int n = nums.size();

if (n == 0) return 0;

vector<int> dp;

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

auto it = lower_bound(begin(dp), end(dp), nums[i]);

if (it == end(dp))

dp.push_back(nums[i]);

else

*it = nums[i];

}

return dp.size();

}

};

Python3

class Solution:

def lengthOfLIS(self, nums: List[int]) -> int:

d = []

for x in nums:

i = bisect_left(d, x)

if i == len(d):

d.append(x)

else:

d[i] = x

return len(d)

Related Problems:

花花酱 LeetCode 62. Unique Paths

By zxi on September 9, 2017

Problem:

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Idea:

Dynamic Programming

Solution1:

C++

// Author: Huahua

class Solution {

public:

int uniquePaths(int m, int n) {

if (m < 0 || n < 0) return 0;

if (m == 1 && n == 1) return 1;

if (f_[m][n] > 0) return f_[m][n];

int left_paths = uniquePaths(m - 1, n);

int top_paths = uniquePaths(m, n - 1);

f_[m][n] = left_paths + top_paths;

return f_[m][n];

}

private:

unordered_map<int, unordered_map<int, int>> f_;

};

Java

// Author: Huahua

// Running time: 0 ms

class Solution {

private int[][] dp;

private int m;

private int n;

public int uniquePaths(int m, int n) {

this.dp = new int[m][n];

this.m = m;

this.n = n;

return dfs(0, 0);

}

private int dfs(int x, int y) {

if (x > m - 1 || y > n - 1)

return 0;

if (x == m - 1 && y == n - 1)

return 1;

if (dp[x][y] == 0)

dp[x][y] = dfs(x + 1, y) + dfs(x , y + 1);

return dp[x][y];

}

Solution2:

// Author: Huahua

class Solution {

public:

int uniquePaths(int m, int n) {

auto f = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));

f[1][1] = 1;

for (int y = 1; y <= n; ++y)

for(int x = 1; x <= m; ++x) {

if (x == 1 && y == 1) {

continue;

} else {

f[y][x] = f[y-1][x] + f[y][x-1];

}

return f[n][m];

}

};

花花酱 LeetCode 654. Maximum Binary Tree

By zxi on September 4, 2017

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5]

Output: return the tree root node representing the following tree:

/ \

3 5

\ /

2 0

Idea:

Recursion

Solution:

With copy

Time complexity: O(nlogn) ~ O(n^2)

Space complexity: O(nlogn) ~ O(n^2)

running time 79ms

// Author: Huahua

class Solution {

public:

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

if(nums.empty()) return nullptr;

auto it = std::max_element(nums.begin(), nums.end());

TreeNode* root=new TreeNode(*it);

vector<int> left(nums.begin(), it);

vector<int> right(it+1, nums.end());

root->left = constructMaximumBinaryTree(left);

root->right = constructMaximumBinaryTree(right);

return root;

}

Without copy

Time complexity: O(nlogn) ~ O(n^2)

Space complexity: O(logn) ~ O(n)

running time 66ms

// Author: Huahua

class Solution {

public:

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

return makeMBT(nums, 0, nums.size());

}

private:

TreeNode* makeMBT(const vector<int>& nums, int begin, int end) {

if(begin>=end) return nullptr;

auto it = std::max_element(nums.begin() + begin, nums.begin() + end);

TreeNode* root=new TreeNode(*it);

int index = it - nums.begin();

root->left = makeMBT(nums, begin, index);

root->right = makeMBT(nums, index+1, end);

return root;

}

};

花花酱 LeetCode 21: Merge Two Sorted Lists

By zxi on September 3, 2017

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution 1: Iterative O(n)

// Author: Huahua

class Solution {

public:

Solution 1: Iterative

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail=&dummy;

while(l1 && l2) {

if(l1->val < l2->val) {

tail->next=l1;

l1=l1->next;

}else{

tail->next=l2;

l2=l2->next;

}

tail=tail->next;

}

if(l1) tail->next = l1;

if(l2) tail->next = l2;

return dummy.next;

}

};

Solution 2: Recursive O(n)

// Author: Huahua

class Solution {

public:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

// If one of the list is emptry, return the other one.

if(!l1 || !l2) return l1 ? l1 : l2;

// The smaller one becomes the head.

if(l1->val < l2->val) {

l1->next = mergeTwoLists(l1->next, l2);

return l1;

} else {

l2->next = mergeTwoLists(l1, l2->next);

return l2;

}

};