Press "Enter" to skip to content

Posts tagged as “hard”

花花酱 LeetCode 4. Median of Two Sorted Arrays

题目大意:求两个已经排序的数组的中位数(如果合并后)。

Problem:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

Example 2:



Idea:

Binary Search

Time complexity: O(log(min(n1,n2)))

Space complexity: O(1)

 

Solution: Binary Search

C++

Java

Related Problem:

花花酱 LeetCode 149. Max Points on a Line

Problem:

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.



Idea:

count by slope

Time complexity: O(n^2)

Space complexity: O(n)

Solution:

C++ / pair

C++ / long

花花酱 LeetCode 124. Binary Tree Maximum Path Sum

Problem:

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

Return 6.



Idea:

Recursion

Time complexity O(n)

Space complexity O(h)

Solution: Recursion

C++

Python3

Related Problems:

花花酱 LeetCode 128. Longest Consecutive Sequence

 

Problem:

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.



Idea:

Hashtable / Hashset

 

Time complexity: O(n)

Space complexity: O(n)

Solution 1: C++ / online

 

Solution 2: C++ / offline

 

花花酱 LeetCode 126. Word Ladder II

Problem:

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

  1. Only one letter can be changed at a time
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Return

Note:

  • Return an empty list if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

Idea:

BFS to construct the graph + DFS to extract the paths



Solutions:

C++, BFS 1


C++ / BFS 2

 

C++ / Bidirectional BFS