metadata
tags:
- sentence-transformers
- sentence-similarity
- feature-extraction
- dense
- generated_from_trainer
- dataset_size:4088
- loss:CoSENTLoss
base_model: microsoft/unixcoder-base
widget:
- source_sentence: |-
Name: Split BST | Code: // Time: O(n)
// Space: O(h)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode*> splitBST(TreeNode* root, int V) {
if (!root) {
return {nullptr, nullptr};
} else if (root->val <= V) {
const auto& result = splitBST(root->right, V);
root->right = result[0];
return {root, result[1]};
} else {
const auto& result = splitBST(root->left, V);
root->left = result[1];
return {result[0], root};
}
}
};
| Tags: Binary Search Tree,Binary Tree,Recursion,Tree
sentences:
- |-
Name: Parallel Courses III | Code: // Time: O(|V| + |E|)
// Space: O(|E|)
class Solution {
public:
int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
vector<vector<int>> adj(n);
vector<int> in_degree(n);
for (const auto& relation : relations) {
adj[relation[0] - 1].emplace_back(relation[1] - 1);
++in_degree[relation[1] - 1];
}
vector<int> q;
vector<int> dist(n);
for (int u = 0; u < n; ++u) {
if (in_degree[u]) {
continue;
}
q.emplace_back(u);
dist[u] = time[u];
}
while (!empty(q)) {
vector<int> new_q;
for (const auto& u : q) {
for (const auto& v : adj[u]) {
dist[v] = max(dist[v], dist[u] + time[v]);
--in_degree[v];
if (!in_degree[v]) {
new_q.emplace_back(v);
}
}
}
q = move(new_q);
}
return *max_element(cbegin(dist), cend(dist));
}
};
| Tags: Array,Dynamic Programming,Graph,Topological Sort
- >-
Name: Determine Whether Matrix Can Be Obtained By Rotation | Code: //
Time: O(m * n)
// Space: O(1)
class Solution {
public:
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
vector<function<bool (int, int)>> checks = {
[&mat, &target](int i, int j) { return mat[i][j] == target[i][j]; },
[&mat, &target](int i, int j) { return mat[i][j] == target[j][size(mat) - 1 - i]; },
[&mat, &target](int i, int j) { return mat[i][j] == target[size(mat) - 1 - i][size(mat[0]) - 1 - j]; },
[&mat, &target](int i, int j) { return mat[i][j] == target[size(mat[0]) - 1 - j][i]; },
};
const auto& traverse = [&mat, &target](const auto& check) {
for (int i = 0; i < size(mat); ++i) {
for (int j = 0; j < size(mat[0]); ++j) {
if (!check(i, j)) {
return false;
}
}
}
return true;
};
for (const auto& check : checks) {
if (traverse(check)) {
return true;
}
}
return false;
}
};
| Tags: Array,Matrix
- >-
Name: Maximum Total Reward Using Operations I | Code: // Time: O(nlogn
+ r^2), r = max(rewardValues)
// Space: O(r)
// sort, dp, bitset
class Solution {
public:
int maxTotalReward(vector<int>& rewardValues) {
static const int MAX_VALUE = 20000;
unordered_set<int> v_set(cbegin(rewardValues), cend(rewardValues));
vector<int> sorted_v(cbegin(v_set), cend(v_set));
sort(begin(sorted_v), end(sorted_v));
bitset<(MAX_VALUE - 1) + 1> dp, mask;
dp[0] = true;
int i = 0;
for (int i = 0, j = 0; i + 1 < size(sorted_v); ++i) {
while (j < sorted_v[i]) {
mask[j++] = true;
}
dp |= (dp & mask) << sorted_v[i];
}
int result = sorted_v.back() - 1;
for (; !dp[result]; --result);
return sorted_v.back() + result;
}
};
// Time: O(nlogn + r^2), r = max(rewardValues)
// Space: O(r)
// sort, dp, bitset
class Solution2 {
public:
int maxTotalReward(vector<int>& rewardValues) {
static const int MAX_VALUE = 20000;
unordered_set<int> v_set(cbegin(rewardValues), cend(rewardValues));
vector<int> sorted_v(cbegin(v_set), cend(v_set));
sort(begin(sorted_v), end(sorted_v));
bitset<(MAX_VALUE * 2 - 1) + 1> dp, mask;
dp[0] = true;
int i = 0;
for (int i = 0, j = 0; i < size(sorted_v); ++i) {
while (j < sorted_v[i]) {
mask[j++] = true;
}
dp |= (dp & mask) << sorted_v[i];
}
int result = 2 * sorted_v.back() - 1;
for (; !dp[result]; --result);
return result;
}
};
// Time: O(nlogn + r^2), r = max(rewardValues)
// Space: O(r)
// sort, dp
class Solution3 {
public:
int maxTotalReward(vector<int>& rewardValues) {
unordered_set<int> v_set(cbegin(rewardValues), cend(rewardValues));
vector<int> sorted_v(cbegin(v_set), cend(v_set));
sort(begin(sorted_v), end(sorted_v));
const int mx = sorted_v.back();
vector<bool> dp((mx - 1) + 1);
dp[0] = true;
for (int i = 0; i + 1 < size(sorted_v); ++i) {
for (int x = 0; x < min(sorted_v[i], mx - sorted_v[i]); ++x) {
if (dp[x]) {
dp[sorted_v[i] + x] = dp[x];
}
}
}
int result = mx - 1;
for (; !dp[result]; --result);
return mx + result;
}
};
// Time: O(nlogn + r^2), r = max(rewardValues)
// Space: O(r)
// sort, dp
class Solution4 {
public:
int maxTotalReward(vector<int>& rewardValues) {
unordered_set<int> v_set(cbegin(rewardValues), cend(rewardValues));
vector<int> sorted_v(cbegin(v_set), cend(v_set));
sort(begin(sorted_v), end(sorted_v));
const int mx = sorted_v.back();
vector<bool> dp((mx * 2 - 1) + 1);
dp[0] = true;
for (int i = 0; i < size(sorted_v); ++i) {
for (int x = 0; x < sorted_v[i]; ++x) {
if (dp[x]) {
dp[sorted_v[i] + x] = dp[x];
}
}
}
int result = 2 * mx - 1;
for (; !dp[result]; --result);
return result;
}
};
| Tags: Array,Dynamic Programming
- source_sentence: |-
Name: Valid Perfect Square | Code: // Time: O(logn)
// Space: O(1)
class Solution {
public:
bool isPerfectSquare(int num) {
int left = 1, right = num;
while (left <= right) {
const int mid = left + (right - left) / 2;
if (mid >= num / mid) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left == num / left && num % left == 0;
}
};
| Tags: Binary Search,Math
sentences:
- |-
Name: Shortest Bridge | Code: // Time: O(n^2)
// Space: O(n^2)
class Solution {
public:
template <typename T>
struct PairHash {
size_t operator()(const pair<T, T>& p) const {
size_t seed = 0;
seed ^= std::hash<T>{}(p.first) + 0x9e3779b9 + (seed<<6) + (seed>>2);
seed ^= std::hash<T>{}(p.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
return seed;
}
};
int shortestBridge(vector<vector<int>>& A) {
static const vector<pair<int, int>> directions{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
unordered_set<pair<int, int>, PairHash<int>> lookup;
unordered_set<pair<int, int>, PairHash<int>> target;
auto islands = get_islands(A);
lookup = move(islands[0]);
target = move(islands[1]);
queue<pair<pair<int, int>, int>> q;
for (const auto& node : lookup) {
q.emplace(node, 0);
}
while (!q.empty()) {
pair<int, int> node;
int dis;
tie(node, dis) = q.front(); q.pop();
if (target.count(node)) {
return dis - 1;
}
for (const auto& d : directions) {
pair<int, int> nei = make_pair(node.first + d.first, node.second + d.second);
if (0 > nei.first || nei.first >= A.size() ||
0 > nei.second || nei.second >= A[0].size() ||
lookup.count(nei)) {
continue;
}
q.emplace(nei, dis + 1);
lookup.emplace(nei);
}
}
}
private:
vector<unordered_set<pair<int, int>, PairHash<int>>> get_islands(const vector<vector<int>>& A) {
static const vector<pair<int, int>> directions{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<unordered_set<pair<int, int>, PairHash<int>>> islands;
unordered_set<pair<int, int>, PairHash<int>> done;
for (int r = 0; r < A.size(); ++r) {
for (int c = 0; c < A[0].size(); ++c) {
if (A[r][c] == 0 || done.count(make_pair(r, c))) {
continue;
}
vector<pair<int, int>> s{{r, c}};
unordered_set<pair<int, int>, PairHash<int>> lookup(s.cbegin(), s.cend());
while (!s.empty()) {
auto node = s.back(); s.pop_back();
for (const auto& d : directions) {
pair<int, int> nei = make_pair(node.first + d.first, node.second + d.second);
if (0 > nei.first || nei.first >= A.size() ||
0 > nei.second || nei.second >= A[0].size() ||
lookup.count(nei) || A[nei.first][nei.second] == 0) {
continue;
}
s.emplace_back(nei);
lookup.emplace(nei);
}
}
for (const auto& node : lookup) {
done.emplace(node);
}
islands.emplace_back(move(lookup));
if (islands.size() == 2) {
break;
}
}
}
return islands;
}
};
| Tags: Array,Breadth-First Search,Depth-First Search,Matrix
- |-
Name: Merge Two Binary Trees | Code: // Time: O(n)
// Space: O(h)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (!t1) {
return t2;
}
if (!t2) {
return t1;
}
t1->val += t2->val;
t1->left = mergeTrees(t1->left, t2->left);
t1->right = mergeTrees(t1->right, t2->right);
return t1;
}
};
| Tags: Binary Tree,Breadth-First Search,Depth-First Search,Tree
- |-
Name: Sum of Square Numbers | Code: // Time: O(sqrt(c) * logc)
// Space: O(1)
class Solution {
public:
bool judgeSquareSum(int c) {
for (long long a = 0; a * a <= c; ++a) {
auto b = static_cast<int>(sqrt(c - a * a));
if (a * a + b * b == c) {
return true;
}
}
return false;
}
};
| Tags: Binary Search,Math,Two Pointers
- source_sentence: >-
Name: Count Paths That Can Form a Palindrome in a Tree | Code: // Time:
O(n)
// Space: O(n)
// iterative dfs, freq table
class Solution {
public:
long long countPalindromePaths(vector<int>& parent, string s) {
unordered_map<int, int> cnt;
cnt[0] = 1;
vector<vector<int>> adj(size(parent));
for (int u = 0; u < size(parent); ++u) {
if (parent[u] != -1) {
adj[parent[u]].emplace_back(u);
}
}
const auto& iter_dfs = [&]() {
int64_t result = 0;
vector<pair<int, int>> stk = {{0, 0}};
while (!empty(stk)) {
auto [u, mask] = stk.back(); stk.pop_back();
if (u) {
mask ^= 1 << (s[u] - 'a');
for (int i = 0; i < 26; ++i) {
if (cnt.count(mask ^ (1 << i))) {
result += cnt[mask ^ (1 << i)];
}
}
result += cnt[mask]++;
}
for (const auto& v : adj[u]) {
stk.emplace_back(v, mask);
}
}
return result;
};
return iter_dfs();
}
};
// Time: O(n)
// Space: O(n)
// dfs, freq table
class Solution2 {
public:
long long countPalindromePaths(vector<int>& parent, string s) {
unordered_map<int, int> cnt;
cnt[0] = 1;
vector<vector<int>> adj(size(parent));
for (int u = 0; u < size(parent); ++u) {
if (parent[u] != -1) {
adj[parent[u]].emplace_back(u);
}
}
const function<int64_t (int, int)> dfs = [&](int u, int mask) {
int64_t result = 0;
if (u) {
mask ^= 1 << (s[u] - 'a');
for (int i = 0; i < 26; ++i) {
if (cnt.count(mask ^ (1 << i))) {
result += cnt[mask ^ (1 << i)];
}
}
result += cnt[mask]++;
}
for (const auto& v : adj[u]) {
result += dfs(v, mask);
}
return result;
};
return dfs(0, 0);
}
};
| Tags: Bit Manipulation,Bitmask,Depth-First Search,Dynamic Programming,Tree
sentences:
- |-
Name: Recover a Tree From Preorder Traversal | Code: // Time: O(n)
// Space: O(h)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// iterative stack solution
class Solution {
public:
TreeNode* recoverFromPreorder(string S) {
int i = 0;
vector<TreeNode *> stack;
while (i < S.length()) {
int j = S.find_first_not_of("-", i);
int level = j - i;
i = j;
while (stack.size() > level) {
stack.pop_back();
}
j = S.find_first_of("-", i);
auto node = new TreeNode(stoi(S.substr(i, j - i)));
i = j;
if (!stack.empty()) {
if (!stack.back()->left) {
stack.back()->left = node;
} else{
stack.back()->right = node;
}
}
stack.emplace_back(node);
}
return stack.front();
}
};
// Time: O(n)
// Space: O(h)
// recursive solution
class Solution2 {
public:
TreeNode* recoverFromPreorder(string S) {
int i = 0;
return recoverFromPreorderHelper(S, 0, &i);
}
private:
TreeNode* recoverFromPreorderHelper(const string& S, int level, int *i) {
int j = S.find_first_not_of("-", *i);
if (level != j - *i) {
return nullptr;
}
*i = j;
j = S.find_first_of("-", *i);
auto node = new TreeNode(stoi(S.substr(*i, j - *i)));
*i = j;
node->left = recoverFromPreorderHelper(S, level + 1, i);
node->right = recoverFromPreorderHelper(S, level + 1, i);
return node;
}
};
| Tags: Binary Tree,Depth-First Search,String,Tree
- |-
Name: Separate the Digits in an Array | Code: // Time: O(n * logr)
// Space: O(1)
// array
class Solution {
public:
vector<int> separateDigits(vector<int>& nums) {
vector<int> result;
for (int i = size(nums) - 1; i >= 0; --i) {
for (int x = nums[i]; x; x /= 10) {
result.emplace_back(x % 10);
}
}
reverse(begin(result), end(result));
return result;
}
};
// Time: O(n * logr)
// Space: O(logr), r = max(nums)
// array
class Solution2 {
public:
vector<int> separateDigits(vector<int>& nums) {
vector<int> result;
for (const auto& x : nums) {
for (const auto& c : to_string(x)) {
result.emplace_back(c - '0');
}
}
return result;
}
};
| Tags: Array,Simulation
- |-
Name: Strobogrammatic Number II | Code: // Time: O(n * 5^(n/2))
// Space: O(n)
class Solution {
public:
vector<string> findStrobogrammatic(int n) {
static const unordered_map<string, string> lookup{{"0", "0"}, {"1", "1"},
{"6", "9"}, {"8", "8"},
{"9", "6"}};
vector<string> result = {""};
if (n % 2) {
result = {"0", "1", "8"};
}
for (int i = n % 2; i < n; i += 2) {
vector<string> new_result;
for (const auto& num : result) {
for (const auto& [a, b] : lookup) {
if (i != n - 2 || a != "0") {
new_result.emplace_back(a + num + b);
}
}
}
result = move(new_result);
}
return result;
}
};
// Time: O(n * 5^(n/2))
// Space: O(n)
class Solution2 {
public:
vector<string> findStrobogrammatic(int n) {
return findStrobogrammaticRecu(n, n);
}
private:
vector<string> findStrobogrammaticRecu(const int n, int k) {
static const unordered_map<string, string> lookup{{"0", "0"}, {"1", "1"},
{"6", "9"}, {"8", "8"},
{"9", "6"}};
if (k == 0) {
return {""};
} else if (k == 1) {
return {"0", "1", "8"};
}
vector<string> result;
for (const auto& num : findStrobogrammaticRecu(n, k - 2)) {
for (const auto& kvp : lookup) {
if (n != k || kvp.first != "0") {
result.emplace_back(kvp.first + num + kvp.second);
}
}
}
return result;
}
};
| Tags: Array,Recursion,String
- source_sentence: |-
Name: Most Frequent IDs | Code: // Time: O(nlogn)
// Space: O(n)
// heap
class Solution {
public:
vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {
vector<long long> result;
unordered_map<int, int64_t> cnt;
priority_queue<pair<int64_t, int>> max_heap;
for (int i = 0; i < size(nums); ++i) {
cnt[nums[i]] += freq[i];
max_heap.emplace(cnt[nums[i]], nums[i]);
while (!empty(max_heap) && max_heap.top().first != cnt[max_heap.top().second]) {
max_heap.pop();
}
result.emplace_back(!empty(max_heap) ? max_heap.top().first : 0);
}
return result;
}
};
// Time: O(nlogn)
// Space: O(n)
// bst
class Solution2 {
public:
vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {
vector<long long> result;
unordered_map<int, int64_t> cnt;
map<int64_t, int> bst;
for (int i = 0; i < size(nums); ++i) {
if (--bst[cnt[nums[i]]] == 0) {
bst.erase(cnt[nums[i]]);
}
cnt[nums[i]] += freq[i];
++bst[cnt[nums[i]]];
result.emplace_back(rbegin(bst)->first);
}
return result;
}
};
| Tags: Array,Hash Table,Heap (Priority Queue),Ordered Set
sentences:
- |-
Name: Design HashSet | Code: // Time: O(1)
// Space: O(n)
class MyHashSet {
public:
/** Initialize your data structure here. */
MyHashSet() : data_(10000) {
}
void add(int key) {
auto& list = data_[key % data_.size()];
auto it = find(list.begin(), list.end(), key);
if (it == list.end()) {
list.emplace_back(key);
}
}
void remove(int key) {
auto& list = data_[key % data_.size()];
auto it = find(list.begin(), list.end(), key);
if (it != list.end()) {
list.erase(it);
}
}
/** Returns true if this set did not already contain the specified element */
bool contains(int key) {
auto& list = data_[key % data_.size()];
auto it = find(list.begin(), list.end(), key);
return it != list.end();
}
private:
vector<list<int>> data_;
};
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet obj = new MyHashSet();
* obj.add(key);
* obj.remove(key);
* bool param_3 = obj.contains(key);
*/
| Tags: Array,Design,Hash Function,Hash Table,Linked List
- |-
Name: Max Area of Island | Code: // Time: O(m * n)
// Space: O(m * n), the max depth of dfs may be m * n
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int result = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
int area = 0;
if (dfs(i, j, &grid, &area)) {
result = max(result, area);
}
}
}
return result;
}
private:
bool dfs(const int i, const int j, vector<vector<int>> *grid, int *area) {
static const vector<pair<int, int>> directions{{-1, 0}, { 1, 0},
{ 0, 1}, { 0, -1}};
if (i < 0 || i >= grid->size() ||
j < 0 || j >= (*grid)[0].size() ||
(*grid)[i][j] <= 0) {
return false;
}
(*grid)[i][j] *= -1;
++(*area);
for (const auto& d : directions) {
dfs(i + d.first, j + d.second, grid, area);
}
return true;
}
};
| Tags: Array,Breadth-First Search,Depth-First Search,Matrix,Union Find
- |-
Name: Stone Game VII | Code: // Time: O(n^2)
// Space: O(n)
class Solution {
public:
int stoneGameVII(vector<int>& stones) {
vector<int> prefix(1);
for (const auto& stone : stones) {
prefix.emplace_back(prefix.back() + stone);
}
const auto& score = [&prefix](int i, int j) {
return prefix[j + 1] - prefix[i];
};
vector<vector<int>> dp(2, vector<int>(size(stones)));
for (int i = size(stones) - 1; i >= 0; --i) {
for (int j = i + 1; j < size(stones); ++j) {
dp[i % 2][j] = max(score(i + 1, j) - dp[(i + 1) % 2][j],
score(i, j - 1) - dp[i % 2][j - 1]);
}
}
return dp[0][size(stones) - 1];
}
};
| Tags: Array,Dynamic Programming,Game Theory,Math
- source_sentence: |-
Name: Arithmetic Slices | Code: // Time: O(n)
// Space: O(1)
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int res = 0, i = 0;
for (int i = 0; i + 2 < A.size(); ++i) {
const auto start = i;
while (i + 2 < A.size() && A[i + 2] + A[i] == 2 * A[i + 1]) {
res += (i++) - start + 1;
}
}
return res;
}
};
| Tags: Array,Dynamic Programming,Sliding Window
sentences:
- >-
Name: Prefix and Suffix Search | Code: // Time: ctor: O(w * l^2), w
is the number of words, l is the word length on average
// search: O(p + s) , p is the length of the prefix, s is the
length of the suffix,
// Space: O(t), t is the number of trie nodes
class WordFilter {
public:
WordFilter(vector<string> words) {
for (int i = 0; i < words.size(); ++i) {
for (int j = 0; j <= words[i].length(); ++j) {
trie_.insert(words[i].substr(j) + SEPARATOR + words[i], i);
}
}
}
int f(string prefix, string suffix) {
return trie_.find(suffix + SEPARATOR + prefix);
}
private:
struct TrieNode {
int weight;
vector<TrieNode *> leaves;
TrieNode() : weight(0), leaves(27) {}
void insert(const string& s, const int weight) {
auto* p = this;
p->weight = weight;
for (const auto& c : s) {
if (!p->leaves[c - 'a']) {
p->leaves[c - 'a'] = new TrieNode;
}
p = p->leaves[c - 'a'];
p->weight = weight;
}
}
int find(const string& s) const {
auto* p = this;
for (const auto& c : s) {
if (!p->leaves[c - 'a']) {
return -1;
}
p = p->leaves[c - 'a'];
}
return p->weight;
}
~TrieNode() {
for (auto& node : leaves) {
if (node) {
delete node;
}
}
}
};
const string SEPARATOR = "{"; // ascii code of 'z' + 1
TrieNode trie_;
};
// Time: ctor: O(w * l), w is the number of words, l is the word
length on average
// search: O(p + s + max(m, n)), p is the length of the prefix, s
is the length of the suffix,
// m is the number of the prefix
match, n is the number of the suffix match
// Space: O(w * l)
class WordFilter2 {
public:
WordFilter(vector<string> words) {
for (int i = words.size() - 1; i >= 0; --i) {
auto word = words[i];
prefix_trie_.insert(word, i);
reverse(word.begin(), word.end());
suffix_trie_.insert(word, i);
}
}
int f(string prefix, string suffix) {
const auto& prefix_match = prefix_trie_.find(prefix);
reverse(suffix.begin(), suffix.end());
const auto& suffix_match = suffix_trie_.find(suffix);
int i = 0, j = 0;
while (i != prefix_match.size() && j != suffix_match.size()) {
if (prefix_match[i] == suffix_match[j]) {
return prefix_match[i];
} else if (prefix_match[i] > suffix_match[j]) {
++i;
} else {
++j;
}
}
return -1;
}
private:
struct TrieNode {
vector<int> words; // index of words
vector<TrieNode *> leaves;
TrieNode() : leaves(26) {}
void insert(const string& s, const int i) {
auto* p = this;
p->words.emplace_back(i);
for (const auto& c : s) {
if (!p->leaves[c - 'a']) {
p->leaves[c - 'a'] = new TrieNode;
}
p = p->leaves[c - 'a'];
p->words.emplace_back(i);
}
}
const vector<int>& find(const string& s) const {
auto* p = this;
for (const auto& c : s) {
if (!p->leaves[c - 'a']) {
static const vector<int> empty;
return empty;
}
p = p->leaves[c - 'a'];
}
return p->words;
}
~TrieNode() {
for (auto& node : leaves) {
if (node) {
delete node;
}
}
}
};
TrieNode prefix_trie_, suffix_trie_;
};
/**
* Your WordFilter object will be instantiated and called as such:
* WordFilter obj = new WordFilter(words);
* int param_1 = obj.f(prefix,suffix);
*/
| Tags: Array,Design,Hash Table,String,Trie
- |-
Name: Reverse Odd Levels of Binary Tree | Code: // Time: O(n)
// Space: O(n)
// bfs
class Solution {
public:
TreeNode* reverseOddLevels(TreeNode* root) {
vector<TreeNode*> q = {root};
for (int parity = 0; !empty(q); parity ^= 1) {
if (parity) {
for (int left = 0, right = size(q) - 1; left < right; ++left, --right) {
swap(q[left]->val, q[right]->val);
}
}
if (!q[0]->left) {
break;
}
vector<TreeNode*> new_q;
for (const auto& node : q) {
new_q.emplace_back(node->left);
new_q.emplace_back(node->right);
}
q = move(new_q);
}
return root;
}
};
| Tags: Binary Tree,Breadth-First Search,Depth-First Search,Tree
- |-
Name: Arithmetic Subarrays | Code: // Time: O(n * q)
// Space: O(n)
class Solution {
public:
vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
vector<bool> result(size(l));
for (int i = 0; i < size(l); ++i) {
result[i] = isArith(vector<int>(cbegin(nums) + l[i], cbegin(nums) + r[i] + 1));
}
return result;
}
private:
bool isArith(const vector<int>& nums) {
unordered_set<int> lookup(cbegin(nums), cend(nums));
int mn = *min_element(cbegin(nums), cend(nums));
int mx = *max_element(cbegin(nums), cend(nums));
if (mx == mn) {
return true;
}
if ((mx - mn) % (size(nums) - 1)) {
return false;
}
int d = (mx - mn) / (size(nums) - 1);
for (int i = mn; i <= mx; i += d) {
if (!lookup.count(i)) {
return false;
}
}
return true;
}
};
| Tags: Array,Hash Table,Sorting
pipeline_tag: feature-extraction
library_name: sentence-transformers
metrics:
- pearson_cosine
- spearman_cosine
model-index:
- name: SentenceTransformer based on microsoft/unixcoder-base
results:
- task:
type: semantic-similarity
name: Semantic Similarity
dataset:
name: unixcoder leetcode eval
type: unixcoder_leetcode_eval
metrics:
- type: pearson_cosine
value: 0.8844784116914098
name: Pearson Cosine
- type: spearman_cosine
value: 0.8840382708528214
name: Spearman Cosine
license: mit
language:
- en
SentenceTransformer based on microsoft/unixcoder-base
This is a sentence-transformers model finetuned from microsoft/unixcoder-base. It maps sentences & paragraphs to a 768-dimensional dense vector space and can be used for semantic textual similarity, semantic search, paraphrase mining, text classification, clustering, and more.
Model Details
Model Description
- Model Type: Sentence Transformer
- Base model: microsoft/unixcoder-base
- Maximum Sequence Length: 256 tokens
- Output Dimensionality: 768 dimensions
- Similarity Function: Cosine Similarity
Model Sources
- Documentation: Sentence Transformers Documentation
- Repository: Sentence Transformers on GitHub
- Hugging Face: Sentence Transformers on Hugging Face
Full Model Architecture
SentenceTransformer(
(0): Transformer({'max_seq_length': 256, 'do_lower_case': False, 'architecture': 'RobertaModel'})
(1): Pooling({'word_embedding_dimension': 768, 'pooling_mode_cls_token': True, 'pooling_mode_mean_tokens': False, 'pooling_mode_max_tokens': False, 'pooling_mode_mean_sqrt_len_tokens': False, 'pooling_mode_weightedmean_tokens': False, 'pooling_mode_lasttoken': False, 'include_prompt': True})
)
Usage
Direct Usage (Sentence Transformers)
First install the Sentence Transformers library:
pip install -U sentence-transformers
Then you can load this model and run inference.
from sentence_transformers import SentenceTransformer
# Download from the 🤗 Hub
model = SentenceTransformer("sentence_transformers_model_id")
# Run inference
sentences = [
'Name: Arithmetic Slices | Code: // Time: O(n)\n// Space: O(1)\n\nclass Solution {\npublic:\n int numberOfArithmeticSlices(vector<int>& A) {\n int res = 0, i = 0;\n for (int i = 0; i + 2 < A.size(); ++i) {\n const auto start = i;\n while (i + 2 < A.size() && A[i + 2] + A[i] == 2 * A[i + 1]) {\n res += (i++) - start + 1;\n }\n }\n return res;\n }\n};\n | Tags: Array,Dynamic Programming,Sliding Window',
'Name: Arithmetic Subarrays | Code: // Time: O(n * q)\n// Space: O(n)\n\nclass Solution {\npublic:\n vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {\n vector<bool> result(size(l));\n for (int i = 0; i < size(l); ++i) {\n result[i] = isArith(vector<int>(cbegin(nums) + l[i], cbegin(nums) + r[i] + 1));\n }\n return result;\n }\n\nprivate:\n bool isArith(const vector<int>& nums) {\n unordered_set<int> lookup(cbegin(nums), cend(nums));\n int mn = *min_element(cbegin(nums), cend(nums));\n int mx = *max_element(cbegin(nums), cend(nums));\n if (mx == mn) {\n return true;\n }\n if ((mx - mn) % (size(nums) - 1)) {\n return false;\n }\n int d = (mx - mn) / (size(nums) - 1);\n for (int i = mn; i <= mx; i += d) {\n if (!lookup.count(i)) {\n return false;\n }\n }\n return true;\n }\n};\n | Tags: Array,Hash Table,Sorting',
'Name: Reverse Odd Levels of Binary Tree | Code: // Time: O(n)\n// Space: O(n)\n\n// bfs\nclass Solution {\npublic:\n TreeNode* reverseOddLevels(TreeNode* root) {\n vector<TreeNode*> q = {root};\n for (int parity = 0; !empty(q); parity ^= 1) {\n if (parity) {\n for (int left = 0, right = size(q) - 1; left < right; ++left, --right) {\n swap(q[left]->val, q[right]->val);\n }\n }\n if (!q[0]->left) {\n break;\n }\n vector<TreeNode*> new_q;\n for (const auto& node : q) {\n new_q.emplace_back(node->left);\n new_q.emplace_back(node->right);\n }\n q = move(new_q);\n }\n return root;\n }\n};\n | Tags: Binary Tree,Breadth-First Search,Depth-First Search,Tree',
]
embeddings = model.encode(sentences)
print(embeddings.shape)
# [3, 768]
# Get the similarity scores for the embeddings
similarities = model.similarity(embeddings, embeddings)
print(similarities)
# tensor([[1.0000, 0.7905, 0.5824],
# [0.7905, 1.0000, 0.6028],
# [0.5824, 0.6028, 1.0000]])
Evaluation
Metrics
Semantic Similarity
- Dataset:
unixcoder_leetcode_eval - Evaluated with
EmbeddingSimilarityEvaluator
| Metric | Value |
|---|---|
| pearson_cosine | 0.8845 |
| spearman_cosine | 0.884 |
Training Details
Training Dataset
Unnamed Dataset
- Size: 4,088 training samples
- Columns:
text1,text2, andscore - Approximate statistics based on the first 1000 samples:
text1 text2 score type string string float details - min: 51 tokens
- mean: 224.9 tokens
- max: 256 tokens
- min: 77 tokens
- mean: 226.23 tokens
- max: 256 tokens
- min: 0.14
- mean: 0.43
- max: 1.0
- Samples:
text1 text2 score Name: As Far from Land as Possible | Code: // Time: O(m * n)
// Space: O(m * n)
class Solution {
public:
int maxDistance(vector>& grid) {
static const vector> directions{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
queue> q;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[i].size(); ++j) {
if (grid[i][j]) {
q.emplace(i, j);
}
}
}
if (q.size() == grid.size() * grid[0].size()) {
return -1;
}
int level = -1;
while (!q.empty()) {
queue> next_q;
while (!q.empty()) {
const auto [x, y] = q.front(); q.pop();
for (const auto& [dx, dy] : directions) {
const auto& nx = x + dx;
const auto& ny = y + dy;
if (!(0 <= nx && nx < grid.size() &&
...Name: Maximum Manhattan Distance After K Changes | Code: // Time: O(n)
// Space: O(1)
// greedy
class Solution {
public:
int maxDistance(string s, int k) {
int result = 0;
for (int i = 0, x = 0, y = 0; i < size(s); ++i) {
if (s[i] == 'E') {
++x;
} else if (s[i] == 'W') {
--x;
} else if (s[i] == 'N') {
++y;
} else if (s[i] == 'S') {
--y;
}
result = max(result, min(abs(x) + abs(y) + 2 * k, i + 1));
}
return result;
}
};
| Tags: Counting,Hash Table,Math,String0.3427242051079267Name: Wiggle Sort II | Code: // Time: O(n) ~ O(n^2), O(n) on average.
// Space: O(1)
// Tri Partition (aka Dutch National Flag Problem) with virtual index solution. (44ms)
class Solution {
public:
void wiggleSort(vector& nums) {
int mid = (nums.size() - 1) / 2;
nth_element(nums.begin(), nums.begin() + mid, nums.end()); // O(n) ~ O(n^2) time
reversedTriPartitionWithVI(nums, nums[mid]); // O(n) time, O(1) space
}
void reversedTriPartitionWithVI(vector& nums, int val) {
const int N = nums.size() / 2 * 2 + 1;
#define Nums(i) nums[(1 + 2 * (i)) % N]
for (int i = 0, j = 0, n = nums.size() - 1; j <= n;) {
if (Nums(j) > val) {
swap(Nums(i++), Nums(j++));
} else if (Nums(j) < val) {
swap(Nums(j), Nums(n--));
} else {
++j;
}
}
}
};
// Time: O(n) ~ O(n^2)
// Space: O(n)
// Tri Partition (aka Dutch National Flag Pro...Name: Array With Elements Not Equal to Average of Neighbors | Code: // Time: O(n) ~ O(n^2), O(n) on average
// Space: O(1)
// Tri Partition (aka Dutch National Flag Problem) with virtual index solution
class Solution {
public:
vector rearrangeArray(vector& nums) {
int mid = (size(nums) - 1) / 2;
nth_element(begin(nums), begin(nums) + mid, end(nums)); // O(n) ~ O(n^2) time
reversedTriPartitionWithVI(nums, nums[mid]); // O(n) time, O(1) space
return nums;
}
private:
void reversedTriPartitionWithVI(vector& nums, int val) {
const int N = size(nums) / 2 * 2 + 1;
#define Nums(i) nums[(1 + 2 * (i)) % N]
for (int i = 0, j = 0, n = size(nums) - 1; j <= n;) {
if (Nums(j) > val) {
swap(Nums(i++), Nums(j++));
} else if (Nums(j) < val) {
swap(Nums(j), Nums(n--));
} else {
++j;
}
}
}
};
// Time: O(nlogn)
...0.7248856548541956Name: Minimum Time to Visit a Cell In a Grid | Code: // Time: O(m * n * log(m * n))
// Space: O(m * n)
// dijkstra's algorithm
class Solution {
public:
int minimumTime(vector>& grid) {
static const vector> DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
if (min(grid[0][1], grid[1][0]) > 1) {
return -1;
}
const auto& dijkstra = [&](const pair& start, const pair& target) {
vector> best(size(grid), vector(size(grid[0]), numeric_limits::max()));
best[start.first][start.second] = 0;
using Data = tuple;
priority_queue, greater> min_heap;
min_heap.emplace(0, start.first, start.second);
while (!empty(min_heap)) {
const auto [curr, i, j] = min_heap.top(); min_heap.pop();
if (best[i][j] < curr) {
continue;
...Name: Sentence Similarity III | Code: // Time: O(n)
// Space: O(1)
class Solution {
public:
bool areSentencesSimilar(string sentence1, string sentence2) {
if (size(sentence1) > size(sentence2)) {
swap(sentence1, sentence2);
}
int count = 0;
for (int step = 0; step < 2; ++step) {
for (int i = 0; i <= size(sentence1); ++i) {
char c1 = i != size(sentence1) ? sentence1[step == 0 ? i : size(sentence1) - 1 - i] : ' ';
char c2 = i != size(sentence2) ? sentence2[step == 0 ? i : size(sentence2) - 1 - i] : ' ';
if (c1 != c2) {
break;
}
if (c1 == ' ') {
++count;
}
}
}
return count >= count_if(cbegin(sentence1), cend(sentence1),
[](char x) { return x == ' '; }) + 1;
}
};
| Tags: Array,String,Two Pointers0.2964020586887101 - Loss:
CoSENTLosswith these parameters:{ "scale": 20.0, "similarity_fct": "pairwise_cos_sim" }
Training Hyperparameters
Non-Default Hyperparameters
eval_strategy: stepslearning_rate: 2e-05num_train_epochs: 2warmup_steps: 102use_cpu: Truedata_seed: 42remove_unused_columns: Falseload_best_model_at_end: Truedataloader_pin_memory: Falsegradient_checkpointing: True
All Hyperparameters
Click to expand
overwrite_output_dir: Falsedo_predict: Falseeval_strategy: stepsprediction_loss_only: Trueper_device_train_batch_size: 8per_device_eval_batch_size: 8per_gpu_train_batch_size: Noneper_gpu_eval_batch_size: Nonegradient_accumulation_steps: 1eval_accumulation_steps: Nonetorch_empty_cache_steps: Nonelearning_rate: 2e-05weight_decay: 0.0adam_beta1: 0.9adam_beta2: 0.999adam_epsilon: 1e-08max_grad_norm: 1.0num_train_epochs: 2max_steps: -1lr_scheduler_type: linearlr_scheduler_kwargs: {}warmup_ratio: 0.0warmup_steps: 102log_level: passivelog_level_replica: warninglog_on_each_node: Truelogging_nan_inf_filter: Truesave_safetensors: Truesave_on_each_node: Falsesave_only_model: Falserestore_callback_states_from_checkpoint: Falseno_cuda: Falseuse_cpu: Trueuse_mps_device: Falseseed: 42data_seed: 42jit_mode_eval: Falseuse_ipex: Falsebf16: Falsefp16: Falsefp16_opt_level: O1half_precision_backend: autobf16_full_eval: Falsefp16_full_eval: Falsetf32: Nonelocal_rank: 0ddp_backend: Nonetpu_num_cores: Nonetpu_metrics_debug: Falsedebug: []dataloader_drop_last: Falsedataloader_num_workers: 0dataloader_prefetch_factor: Nonepast_index: -1disable_tqdm: Falseremove_unused_columns: Falselabel_names: Noneload_best_model_at_end: Trueignore_data_skip: Falsefsdp: []fsdp_min_num_params: 0fsdp_config: {'min_num_params': 0, 'xla': False, 'xla_fsdp_v2': False, 'xla_fsdp_grad_ckpt': False}fsdp_transformer_layer_cls_to_wrap: Noneaccelerator_config: {'split_batches': False, 'dispatch_batches': None, 'even_batches': True, 'use_seedable_sampler': True, 'non_blocking': False, 'gradient_accumulation_kwargs': None}deepspeed: Nonelabel_smoothing_factor: 0.0optim: adamw_torch_fusedoptim_args: Noneadafactor: Falsegroup_by_length: Falselength_column_name: lengthddp_find_unused_parameters: Noneddp_bucket_cap_mb: Noneddp_broadcast_buffers: Falsedataloader_pin_memory: Falsedataloader_persistent_workers: Falseskip_memory_metrics: Trueuse_legacy_prediction_loop: Falsepush_to_hub: Falseresume_from_checkpoint: Nonehub_model_id: Nonehub_strategy: every_savehub_private_repo: Nonehub_always_push: Falsehub_revision: Nonegradient_checkpointing: Truegradient_checkpointing_kwargs: Noneinclude_inputs_for_metrics: Falseinclude_for_metrics: []eval_do_concat_batches: Truefp16_backend: autopush_to_hub_model_id: Nonepush_to_hub_organization: Nonemp_parameters:auto_find_batch_size: Falsefull_determinism: Falsetorchdynamo: Noneray_scope: lastddp_timeout: 1800torch_compile: Falsetorch_compile_backend: Nonetorch_compile_mode: Noneinclude_tokens_per_second: Falseinclude_num_input_tokens_seen: Falseneftune_noise_alpha: Noneoptim_target_modules: Nonebatch_eval_metrics: Falseeval_on_start: Falseuse_liger_kernel: Falseliger_kernel_config: Noneeval_use_gather_object: Falseaverage_tokens_across_devices: Falseprompts: Nonebatch_sampler: batch_samplermulti_dataset_batch_sampler: proportionalrouter_mapping: {}learning_rate_mapping: {}
Training Logs
| Epoch | Step | Training Loss | unixcoder_leetcode_eval_spearman_cosine |
|---|---|---|---|
| 1.6634 | 850 | 2.6601 | - |
| 1.7613 | 900 | 2.5066 | 0.8875 |
| 1.8591 | 950 | 2.3788 | - |
| 1.9569 | 1000 | 2.34 | 0.8840 |
- The bold row denotes the saved checkpoint.
Framework Versions
- Python: 3.12.11
- Sentence Transformers: 5.1.0
- Transformers: 4.55.2
- PyTorch: 2.8.0+cu126
- Accelerate: 1.10.0
- Datasets: 4.0.0
- Tokenizers: 0.21.4
Citation
BibTeX
Sentence Transformers
@inproceedings{reimers-2019-sentence-bert,
title = "Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks",
author = "Reimers, Nils and Gurevych, Iryna",
booktitle = "Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing",
month = "11",
year = "2019",
publisher = "Association for Computational Linguistics",
url = "https://arxiv.org/abs/1908.10084",
}
CoSENTLoss
@online{kexuefm-8847,
title={CoSENT: A more efficient sentence vector scheme than Sentence-BERT},
author={Su Jianlin},
year={2022},
month={Jan},
url={https://kexue.fm/archives/8847},
}