花花酱 LeetCode 221. Maximal Square

By zxi on September 18, 2017

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:

// Author: Huahua

// Time complexity: O(n^3)

// Running time: 39 ms

class Solution {

public:

int maximalSquare(vector<vector<char>>& matrix) {

if (matrix.empty()) return 0;

int m = matrix.size();

int n = matrix[0].size();

// sums[i][j] = sum(matrix[0][0] ~ matrix[i-1][j-1])

vector<vector<int>> sums(m + 1, vector<int>(n + 1, 0));

for (int i = 1; i <= m; ++i)

for (int j = 1; j <= n; ++j)

sums[i][j] = matrix[i - 1][j - 1] - '0'

+ sums[i - 1][j]

+ sums[i][j - 1]

- sums[i - 1][j - 1];

int ans = 0;

for (int i = 1; i <= m; ++i)

for (int j = 1; j <= n; ++j)

for (int k = min(m - i + 1, n - j + 1); k > 0; --k) {

int sum = sums[i + k - 1][j + k - 1]

- sums[i + k - 1][j - 1]

- sums[i - 1][j + k - 1]

+ sums[i - 1][j - 1];

// full of 1

if (sum == k*k) {

ans = max(ans, sum);

break;

}

return ans;

}

};

Solution 2:

// Author: Huahua

// Time complexity: O(n^2)

// Running time: 6 ms

class Solution {

public:

int maximalSquare(vector<vector<char>>& matrix) {

if (matrix.empty()) return 0;

int m = matrix.size();

int n = matrix[0].size();

vector<vector<int>> sizes(m, vector<int>(n, 0));

int ans = 0;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

sizes[i][j] = matrix[i][j] - '0';

if (!sizes[i][j]) continue;

if (i == 0 || j == 0) {

// do nothing

} else if (i == 0)

sizes[i][j] = sizes[i][j - 1] + 1;

else if (j == 0)

sizes[i][j] = sizes[i - 1][j] + 1;

else

sizes[i][j] = min(min(sizes[i - 1][j - 1],

sizes[i - 1][j]),

sizes[i][j - 1]) + 1;

ans = max(ans, sizes[i][j]*sizes[i][j]);

}

return ans;

}

};

花花酱 LeetCode 677. Map Sum Pairs

By zxi on September 18, 2017

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:

Input: insert("apple", 3), Output: Null

Input: sum("ap"), Output: 3

Input: insert("app", 2), Output: Null

Input: sum("ap"), Output: 5

Idea:

Prefix tree

Solution 1

// Author: Huahua

// Running time: 3 ms

class MapSum {

public:

/** Initialize your data structure here. */

MapSum() {}

void insert(const string& key, int val) {

int inc = val;

if (vals_.count(key)) {

inc -= vals_[key];

}

vals_[key] = val;

for (int i = 1; i <= key.length(); ++i)

sums_[key.substr(0,i)] += inc;

}

int sum(const string& prefix) {

return sums_[prefix];

}

private:

unordered_map<string, int> vals_;

unordered_map<string, int> sums_;

};

Solution 2:

class MapSum {

public:

/** Initialize your data structure here. */

MapSum() {}

void insert(string key, int val) {

int inc = val - vals_[key];

Trie* p = &root;

for (const char c : key) {

if (!p->children[c])

p->children[c] = new Trie();

p->children[c]->sum += inc;

p = p->children[c];

}

vals_[key] = val;

}

int sum(string prefix) {

Trie* p = &root;

for (const char c : prefix) {

if (!p->children[c]) return 0;

p = p->children[c];

}

return p->sum;

}

private:

struct Trie {

Trie():children(128, nullptr), sum(0){}

~Trie() {

for (auto child : children)

if (child) delete child;

children.clear();

}

vector<Trie*> children;

int sum;

};

Trie root; // dummy root

unordered_map<string, int> vals_; // key -> val

};

with std::unique_ptr

// Author: Huahua

// Running time: 5 ms

class MapSum {

public:

/** Initialize your data structure here. */

MapSum(): root_(new Trie()) {}

void insert(string key, int val) {

int inc = val - vals_[key];

Trie* p = root_.get();

for (const char c : key) {

if (!p->children[c])

p->children[c] = new Trie();

p->children[c]->sum += inc;

p = p->children[c];

}

vals_[key] = val;

}

int sum(string prefix) {

Trie* p = root_.get();

for (const char c : prefix) {

if (!p->children[c]) return 0;

p = p->children[c];

}

return p->sum;

}

private:

struct Trie {

Trie():children(128, nullptr), sum(0){}

~Trie() {

for (auto child : children)

if (child) {

delete child;

child = nullptr;

}

children.clear();

}

vector<Trie*> children;

int sum;

};

std::unique_ptr<Trie> root_;

unordered_map<string, int> vals_; // key -> val

};

花花酱 LeetCode 680. Valid Palindrome II

By zxi on September 17, 2017

Problem:

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

Example 1:

1 2	Input: "aba" Output: True

Example 2:

Input: "abca"

Output: True

Explanation: You could delete the character 'c'.

Note:

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:

// Author: Huahua

// Running time: 118 ms

class Solution {

public:

bool validPalindrome(const string& s) {

int l = -1;

int r = s.length();

while (++l < --r)

if (s[l] != s[r])

return isPalindrome(s, l+1, r)

|| isPalindrome(s, l, r-1);

return true;

}

private:

bool isPalindrome(const string& s, int l, int r) {

while (l < r)

if (s[l++] != s[r--]) return false;

return true;

}

};

花花酱 LeetCode 297. Serialize and Deserialize Binary Tree

By zxi on September 17, 2017

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

/ \

2 3

/ \

4 5

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)

Solution 1: ASCII

C++

// Author: Huahua

// Running time: 39 ms

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

ostringstream out;

serialize(root, out);

return out.str();

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

istringstream in(data);

return deserialize(in);

}

private:

void serialize(TreeNode* root, ostringstream& out) {

if (!root) {

out << "# ";

return;

}

out << root->val << " ";

serialize(root->left, out);

serialize(root->right, out);

}

TreeNode* deserialize(istringstream& in) {

string val;

in >> val;

if (val == "#") return nullptr;

TreeNode* root = new TreeNode(stoi(val));

root->left = deserialize(in);

root->right = deserialize(in);

return root;

}

};

Solution 2: Binary

C++

// Author: Huahua

// Running time: 23 ms (beat 98.07%)

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

ostringstream out;

serialize(root, out);

return out.str();

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

istringstream in(data);

return deserialize(in);

}

private:

enum STATUS {

ROOT_NULL = 0x0,

ROOT = 0x1,

LEFT = 0x2,

RIGHT = 0x4

};

void serialize(TreeNode* root, ostringstream& out) {

char status = 0;

if (root) status |= ROOT;

if (root && root->left) status |= LEFT;

if (root && root->right) status |= RIGHT;

out.write(&status, sizeof(char));

if (!root) return;

out.write(reinterpret_cast<char*>(&(root->val)), sizeof(root->val));

if (root->left) serialize(root->left, out);

if (root->right) serialize(root->right, out);

}

TreeNode* deserialize(istringstream& in) {

char status;

in.read(&status, sizeof(char));

if (!status & ROOT) return nullptr;

auto root = new TreeNode(0);

in.read(reinterpret_cast<char*>(&root->val), sizeof(root->val));

root->left = (status & LEFT) ? deserialize(in) : nullptr;

root->right = (status & RIGHT) ? deserialize(in) : nullptr;

return root;

}

};

// Your Codec object will be instantiated and called as such:

// Codec codec;

// codec.deserialize(codec.serialize(root));

C++ (string)

// Author: Huahua

// Running time: 23 ms (<98.13%)

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

string s;

serialize(root, s);

return s;

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

int pos = 0;

return deserialize(data, pos);

}

private:

enum STATUS {

ROOT_NULL = 0x0,

ROOT = 0x1,

LEFT = 0x2,

RIGHT = 0x4

};

void serialize(TreeNode* root, string& s) {

char status = ROOT_NULL;

if (root) status |= ROOT;

if (root && root->left) status |= LEFT;

if (root && root->right) status |= RIGHT;

s.push_back(status);

if (!root) return;

s.append(reinterpret_cast<char*>(&root->val), sizeof(root->val));

if (root->left) serialize(root->left, s);

if (root->right) serialize(root->right, s);

}

TreeNode* deserialize(const string& s, int& pos) {

char status = s[pos++];

if (!status) return nullptr;

TreeNode* root = new TreeNode(0);

memcpy(&root->val, s.data() + pos, sizeof(root->val));

pos += sizeof(root->val);

root->left = (status & LEFT) ? deserialize(s, pos) : nullptr;

root->right = (status & RIGHT) ? deserialize(s, pos) : nullptr;

return root;

}

};

花花酱 LeetCode 221. Maximal Square

花花酱 LeetCode 677. Map Sum Pairs

花花酱 LeetCode 680. Valid Palindrome II

花花酱 LeetCode 297. Serialize and Deserialize Binary Tree

Solution 1: ASCII

C++

Solution 2: Binary

C++

C++ (string)

Related Problems

花花酱 LeetCode 381. Insert Delete GetRandom O(1) – Duplicates allowed

Huahua's Tech Road

花花酱 LeetCode 221. Maximal Square

花花酱 LeetCode 677. Map Sum Pairs

花花酱 LeetCode 680. Valid Palindrome II

花花酱 LeetCode 297. Serialize and Deserialize Binary Tree

Solution 1: ASCII

C++

Solution 2: Binary

C++

C++ (string)

Related Problems

花花酱 LeetCode 381. Insert Delete GetRandom O(1) – Duplicates allowed