# Huahua's Tech Road

Problem:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Idea:

Dynamic programming

Solution 0: O(n^5)

Solution 1: O(n^3)

Solution 2: O(n^2)

Solution 1:

Solution 2:

https://leetcode.com/problems/map-sum-pairs/description/

Problem:

Implement a MapSum class with insert, and sum methods.

For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix.

Example 1:

Idea:

Prefix tree

Solution 1

Solution 2:

with std::unique_ptr

Problem:

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Example 2:

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Idea:

Greedy, delete the first unmatched char

Time complexity

O(n)

Solution:

Problem:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

Idea:

Recursion

Time Complexity O(n)

# Related Problems

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/

Problem:

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

1. insert(val): Inserts an item val to the collection.
2. remove(val): Removes an item val from the collection if present.
3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Idea:

Hashtable + array

Solution:

Java

Related Problems:

Mission News Theme by Compete Themes.