bfs Archives - shawnlyu

August 19, 2020August 19, 2020

[Leetcode]1553. Minimum Number of Days to Eat N Oranges

There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:
Eat one orange.
If the number of remaining oranges (n) is divisible by 2 then you can eat  n/2 oranges.
If the number of remaining oranges (n) is divisible by 3 then you can eat  2*(n/3) oranges.
You can only choose one of the actions per day.
Return the minimum number of days to eat n oranges.
Constraints:
1 <= n <= 2*10^9

August 17, 2020August 17, 2020

BFS and Bi-directional BFS

Apart from vanilla BFS introduced in Intro to Graph Algorithms – BFS & DFS, there’s another variant of BFS called bi-directional BFS. Instead of searching from source to target, bi-directional BFS starts with the source and the target at the same time, and search the graph simultaneously. The improvement of time complexities is shown as below, as referring to @Huahua.

June 29, 2020July 9, 2020

[Leetcode]279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example 1:
Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.

June 15, 2020June 26, 2020

Shortest Path Algorithms I – Dijkstra

The shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. (Wikipedia) In this and coming posts some of the most common algorithms to solve the shortest path problems will be explained. Today’s topic is Dijkstra.

June 9, 2020June 26, 2020

[Leetcode problems] 45 Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4] 
Output: 2 
Explanation: The minimum number of jumps to reach the last index is 2. 
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.

May 31, 2020September 18, 2020

Graph Algorithm: Topological Sort

When we are scheduling jobs or tasks, they may have dependencies, i.e., before we finish task $a$ , we have to finish $b$ first. In this case, given a set of tasks and their dependencies, how shall we arrange our schedules? There comes another graph algorithm: Topological Sort.

May 29, 2020June 20, 2020

[Leetcode for Interviews]DFS, BFS, and Backtracking I

After Intro to Graph Algorithms – BFS & DFS, let’s take a look at some popular and most common interview questions. Questions that fall under this category are quite typical and static, so it’s not difficult to master them if you go through the following lists, and then you will find patterns in their solutions.

May 29, 2020June 1, 2020

Intro to Graph Algorithms – BFS & DFS

Graphs are a pervasive data structure in computer science, and algorithms for working with them are fundamental to the field.
Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2009.

Given a graph defined as $G=(V,E)$ which is a set of vertices and edges, we’d be curious about how to represent it and how to search it systematically so as to visit the vertices following the edges. This blog will briefly introduce two ways of representations of a graph, and then will dive deep into two graph search algorithms: Breadth-First-Search (BFS) and Depth-First-Search (DFS).