For the given island that’s represented in a matrix of 0's and 1's, we usually use a depth-first search or a breadth-first search algorithm to solve. Today, I’ll introduce how to solve and compare such a problem using both approaches.
Problem
Given a non-empty 2D array
gridof 0's and 1's, an island is a group of1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example:
…The sliding window algorithm is often used to find the target number in a string/list. Today, I’ll introduce how to solve this leetcode problem using the sliding window algorithm and optimize its running time.
Problem description
You are given an array of integers
nums, there is a sliding window of sizekwhich is moving from the very left of the array to the very right. You can only see theknumbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7]…We know tree well, a binary search tree performs well in searching. Today, I’ll introduce another tree-like data structure, which is widely used for retrieval of a key in a dataset of strings: trie.
Introduction
A trie also called prefix-tree, is a type of search tree, a tree data structure used for locating specific keys from within a set. These keys are always strings and characters. A trie is structured by trie nodes. …
My previous post introduced the Knapsack problem. It states how to solve using the dynamic programming algorithm. Besides Knapsack, there’s one series of problems that you might encounter in a coding interview: the house robber problems. Today, let’s talk about it.
Problem description
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a…
Dynamic programming problems are frequently asked in a tech interview. For me, dynamic programming problems are challenging to understand and to solve. Recently, I see a post demonstrating that dynamic programming problems can be categorized. One of the categories is the Knapsack problem. Today, I'll introduce what’s knapsack problem and its related topics.
Definition
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and…
It’s often asked during a technical interview: write a function to get the subsets/combinations/permutations for a given set. These problems seem difficult to solve in the first place, but have similarities when applying the backtracking algorithm. In this post, I’ll illustrate how to solve these problems using the backtracking algorithm.
Definitions
Assume we are given a set A, and it contains several elements. For example, A = [1, 2, 3].
- Subset: In definition, a set B is a subset of set A if all elements of B are also elements of A. Note that the empty set is a subset of…
For a given string, to get the minimum substring that contains all the characters we want is not easy to do. When screening through the string, we always use an algorithm called “sliding window” which uses two pointers to locate the substring. In this post, I’ll introduce this algorithm by solving this problem together: minimum window substring.
Problem Description
Given two strings
sandt, return the minimum window inswhich will contain all the characters int. If there is no such window insthat covers all characters int, return the empty string"".Note that If there…
It’s a quite common problem in real life: how to find the minimum number of coins, to pay a specific amount with coins of different denominations? When I first see this problem in Leetcode, it took me a while to figure it out. After learning more about dynamic programming, I found it’s easy to understand and solve this problem. In this post, I'll introduce the algorithm and code to solve this classic problem.
Problem description
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need…
Problem description
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
The Linked List is represented in the input/output as a list of
nnodes. Each node is represented as a pair of[val, random_index]where:
val: an integer representingNode.val
random_index: the index of the node (range from0ton-1) where random pointer points to, ornullif it does not point to any node.
Example:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]For the linear data structure, elements are inserted/deleted in a specific order. For example, the queue follows FIFO(first-in-first-out) pattern, whereas the stack follows the FILO(first-in-last-out) pattern. In the real world, only following fixed rules will not solve problems. For instance, jobs sent to a printer are placed in a queue. If we have a really important job that’s needed immediately, we might want the job to be run as soon as the printer is available. This particular scenario needs a special kind of queue, known as a priority queue. …
Wangyy
on the way to become a programmer
