花花酱 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;

}

};

Related Problems

LeetCode 449. Serialize and Deserialize BST

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

By zxi on September 17, 2017

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.

insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
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:

// Author: Huahua

// Running time: 49 ms

class RandomizedCollection {

public:

/** Initialize your data structure here. */

RandomizedCollection() {}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */

bool insert(int val) {

m_[val].push_back(vals_.size());

vals_.emplace_back(val, m_[val].size() - 1);

return m_[val].size() == 1u;

}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */

bool remove(int val) {

if (!m_.count(val)) return false;

int index_to_evict = m_[val].back();

const auto& last_entry = vals_.back();

// Update index

m_[last_entry.first][last_entry.second] = index_to_evict;

// Swap vals

swap(vals_.back(), vals_[index_to_evict]);

// Clenup

vals_.pop_back();

m_[val].pop_back();

if (m_[val].empty()) m_.erase(val);

return true;

}

/** Get a random element from the collection. */

int getRandom() {

return vals_[rand() % vals_.size()].first;

}

private:

// val -> indices array: indices in vals_

unordered_map<int, vector<int>> m_;

// {val, index in the indices array}

vector<pair<int,int>> vals_;

};

Java

// Author: Huahua

// Running time: 122 ms (<94.53%)

class RandomizedCollection {

class Entry {

public int value;

public int index;

public Entry(int val, int idx) {

value = val;

index = idx;

}

private Map<Integer, List<Integer>> m;

private List<Entry> vals;

private Random rand;

/** Initialize your data structure here. */

public RandomizedCollection() {

m = new HashMap<>();

vals = new ArrayList<>();

rand = new Random();

}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */

public boolean insert(int val) {

List<Integer> l = m.getOrDefault(val, new ArrayList<Integer>());

l.add(vals.size());

m.put(val, l);

vals.add(new Entry(val, l.size() - 1));

return l.size() == 1;

}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */

public boolean remove(int val) {

if (!m.containsKey(val)) return false;

List<Integer> l = m.get(val);

int index_to_evict = l.get(l.size() - 1);

Entry last_entry = vals.get(vals.size() - 1);

// Update index

m.get(last_entry.value).set(last_entry.index, index_to_evict);

// Swap vals

vals.set(index_to_evict, last_entry);

// Cleanup

vals.remove(vals.size() - 1);

l.remove(l.size() - 1);

if (l.size() == 0) m.remove(val);

return true;

}

/** Get a random element from the collection. */

public int getRandom() {

return vals.get(rand.nextInt(vals.size())).value;

}

Related Problems:

花花酱 LeetCode 380. Insert Delete GetRandom O(1)

By zxi on September 16, 2017

Problem:

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

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Idea:

Hashtable + array

Time complexity:

O(1)

Solution:

// Author: Huahua

// Running time: 49 ms

class RandomizedSet {

public:

/** Initialize your data structure here. */

RandomizedSet() {}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */

bool insert(int val) {

if(m_.count(val)) return false;

m_[val] = vals_.size();

vals_.push_back(val);

return true;

}

/** Removes a value from the set. Returns true if the set contained the specified element. */

bool remove(int val) {

if(!m_.count(val)) return false;

int index = m_[val];

m_[vals_.back()] = index;

m_.erase(val);

std::swap(vals_[index], vals_.back());

vals_.pop_back();

return true;

}

/** Get a random element from the set. */

int getRandom() {

int index = rand() % vals_.size();

return vals_[index];

}

private:

// val -> index in the array

unordered_map<int, int> m_;

vector<int> vals_;

};

Related Problems:

花花酱 LeetCode 673. Number of Longest Increasing Subsequence

By zxi on September 15, 2017

https://leetcode.com/problems/number-of-longest-increasing-subsequence

Problem:

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]

Output: 2

Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]

Output: 5

Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

Idea:

Dynamic programming

Solution1:

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

int findNumberOfLIS(vector<int>& nums) {

int n = nums.size();

if (n == 0) return 0;

c_ = vector<int>(n, 0);

l_ = vector<int>(n, 0);

// Find the length LIS.

int max_len = 0;

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

max_len = max(max_len, len(nums, i));

// Checking all endings.

int ans = 0;

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

if (len(nums, i) == max_len)

ans += count(nums, i);

return ans;

}

private:

vector<int> c_; // c[i]: number of LIS ends with nums[i] / NLIS'

vector<int> l_; // l[i]: lengeh of LIS ends with nums[i] / LIS'

// Number of LIS ends with nums[n]

int count(const vector<int>& nums, int n) {

if (n == 0) return 1;

if (c_[n] > 0) return c_[n];

int total_count = 0;

int l = len(nums, n);

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

if (nums[n] > nums[i] && len(nums, i) == l-1)

total_count += count(nums, i);

if (total_count == 0)

total_count = 1;

return c_[n] = total_count;

}

// Length of LIS ends with nums[n]

int len(const vector<int>& nums, int n) {

if (n == 0) return 1;

if (l_[n] > 0) return l_[n];

int max_len = 1;

// Check every subarray

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

if (nums[n] > nums[i])

max_len = max(max_len, len(nums, i) + 1);

return l_[n] = max_len;

}

};

Solution2:

// Author: Huahua

// Running time: 33 ms

class Solution {

public:

int findNumberOfLIS(vector<int>& nums) {

int n = nums.size();

if (n == 0) return 0;

vector<int> c(n, 1);

vector<int> l(n, 1);

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

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

if (nums[i] > nums[j]) {

if (l[j] + 1 > l[i]) {

l[i] = l[j] + 1;

c[i] = c[j];

} else if (l[j] + 1 == l[i]) {

c[i] += c[j];

}

int max_len = *max_element(l.begin(), l.end());

int ans = 0;

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

if (l[i] == max_len)

ans += c[i];

return ans;

}

};

Related Problems:

Huahua's Tech Road

花花酱 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

花花酱 LeetCode 380. Insert Delete GetRandom O(1)

花花酱 LeetCode 673. Number of Longest Increasing Subsequence