Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 785. Is Graph Bipartite?

Video is forĀ čŠ±čŠ±é…± LeetCode 886. Possible Bipartition, but the algorithm is exact the same.

Problem

https://leetcode.com/problems/is-graph-bipartite/

Given an undirectedĀ graph, returnĀ trueĀ if and only if it is bipartite.

Recall that a graph isĀ bipartiteĀ if we can split it’s set of nodes into two independentĀ subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form:Ā graph[i]Ā is a list of indexesĀ jĀ for which the edge between nodesĀ iĀ andĀ jĀ exists.Ā  Each node is an integer betweenĀ 0Ā andĀ graph.length - 1.Ā  There are no self edges or parallel edges:Ā graph[i]Ā does not containĀ i, and it doesn’t contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.

 

Note:

  • graphĀ will have length in rangeĀ [1, 100].
  • graph[i]Ā will contain integers in rangeĀ [0, graph.length - 1].
  • graph[i]Ā will not containĀ iĀ or duplicate values.
  • The graph is undirected: if any elementĀ jĀ is inĀ graph[i], thenĀ iĀ will be inĀ graph[j].

Solution: Graph Coloring

For each node

  • If has not been colored, color it to RED(1).
  • Color its neighbors with a different color RED(1) to BLUE(-1) or BLUE(-1) to RED(-1).

If we can finish the coloring then the graph is bipartite. All red nodes on the left no connections between them and all blues nodes on the right, again no connections between them. red and blue nodes are neighbors.

Time complexity: O(V+E)

Space complexity: O(V)

C++ / DFS

Related Problem

花花酱 LeetCode 875. Koko Eating Bananas

Problem

Koko loves to eat bananas.Ā  There areĀ NĀ piles of bananas, theĀ i-thĀ pile hasĀ piles[i]Ā bananas.Ā  The guards have gone and will come back inĀ HĀ hours.

Koko can decide her bananas-per-hour eating speed ofĀ K.Ā  Each hour, she chooses some pile of bananas, and eats K bananas from that pile.Ā  If the pile has less thanĀ KĀ bananas, she eats all of them instead, and won’t eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integerĀ KĀ such that she can eat all the bananas withinĀ HĀ hours.

Example 1:

Input: piles = [3,6,7,11], H = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], H = 6
Output: 23

Note:

  • 1 <= piles.length <= 10^4
  • piles.length <= H <= 10^9
  • 1 <= piles[i] <= 10^9

Solution: Binary Search

search for the smallest k [1, max_pile_height] such that eating time h <= H.

Time complexity: O(nlogh)

Space complexity: O(1)

 

花花酱 LeetCode 874. Walking Robot Simulation

Problem

A robot on an infinite grid starts at point (0, 0) and faces north.Ā  The robot can receive one of three possible types of commands:

  • -2: turn left 90 degrees
  • -1: turn right 90 degrees
  • 1 <= x <= 9: move forwardĀ xĀ units

Some of the grid squares are obstacles.

TheĀ i-th obstacle is at grid pointĀ (obstacles[i][0], obstacles[i][1])

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return theĀ squareĀ of the maximum Euclidean distance that the robot will be from the origin.

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

Note:

  1. 0 <= commands.length <= 10000
  2. 0 <= obstacles.length <= 10000
  3. -30000 <= obstacle[i][0] <= 30000
  4. -30000 <= obstacle[i][1] <= 30000
  5. The answer is guaranteed to be less thanĀ 2 ^ 31.

Solution: Simulation

Time complexity: O(n + sum(x)) = O(n)

Space complexity: O(n)

C++

 

花花酱 LeetCode 873. Length of Longest Fibonacci Subsequence

Problem

A sequenceĀ X_1, X_2, ..., X_nĀ isĀ fibonacci-likeĀ if:

  • n >= 3
  • X_i + X_{i+1} = X_{i+2}Ā for allĀ i + 2 <= n

Given aĀ strictly increasingĀ arrayĀ AĀ of positive integers forming a sequence, find theĀ lengthĀ of the longest fibonacci-like subsequence ofĀ A.Ā  If one does not exist, return 0.

(Recall that a subsequence is derived from another sequenceĀ AĀ byĀ deleting any number ofĀ elements (including none)Ā fromĀ A, without changing the order of the remaining elements.Ā  For example,Ā [3, 5, 8]Ā is a subsequence ofĀ [3, 4, 5, 6, 7, 8].)

Example 1:

Input: [1,2,3,4,5,6,7,8]
Output: 5
Explanation:
The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: [1,3,7,11,12,14,18]
Output: 3
Explanation:
The longest subsequence that is fibonacci-like:
[1,11,12], [3,11,14] or [7,11,18].

Note:

  • 3 <= A.length <= 1000
  • 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
  • (The time limit has been reduced by 50% for submissions in Java, C, and C++.)

Ā 

Solution 1: DP

C++

C++ V2

Solution 2: HashTable

Time complexity: O(n^3)

Space complexity: O(n)

C++