Using the merge sort based on the linked list.

  • find the middle point by using fast and slow pointer
  • cut the linked list into two parts: left: [begin, mid], right : [mid + 1, end]
  • recursively sort left and right
  • merge the results from left and right
Merge sort base on linked list solution screenshot
/**
* class LLNode {
* public:
* int val;
* LLNode *next;
* };
*/
void merge_sort(LLNode* left, LLNode* right){
if (left == right) return…

Range DP usually traverse all possible ranges. If we have an array of length n, then traversing all ranges will have the complexity of O(n²)

Maximal Expression

const int N = 210;
int maxf[N][N];
int minf[N][N];
const int INF = 0x3f3f3f3f;
const int NEGINF = 0xcfcfcfcf;
int maxdp(vector<int>& nums, int i, int j);
int mindp(vector<int>& nums, int i, int j);
int mindp(vector<int>& nums, int i, int j) {
if (i == j) {
return minf[i][i] = nums[i];
}
if (minf[i][j] != …

A nice problem can be solved by using Trie, DFS and hash table.

677. Map Sum Pairs

Reference Code

struct TrieNode{
public:
bool is_word = false;
vector<TrieNode*> children;
TrieNode(){
children.assign(26, nullptr);
}
};
class MapSum {
public:
unordered_map<string, int> m;
TrieNode* root;
/** Initialize your data structure here. */
MapSum() {
root = new TrieNode();
}

void insert(string key, int val) {
if (m.find(key) != m.end()) {…

If we solve it naively based on the problem description, we will get TLE.

const int INF = 0x3f3f3f3f;
vector<pair<int, int>> dirs = {{0, 1},{0, -1},{1, 0},{-1, 0}};
class Solution {
public:
void bfs(int i, int j, vector<vector<int>>& mat, vector<vector<int>>& dis){
vector<pair<int, int>> Q;
Q.emplace_back(i, j);
const int n = mat.size(), m = mat[0].size();
vector<vector<int>> seen(n, vector<int>(m, 0));
int level = 1…

A 4th question of Biweekly LeetCode contest.

1944. Number of Visible People in a Queue

We can use a monotonic queue to solve this problem.

class Solution {
public:
vector<int> canSeePersonsCount(vector<int>& heights) {
const int n = heights.size();
vector<int> ret(n);
vector<int> q;
for (int i = n - 1; i >=0; --i){
while (!q.empty() && heights[i] > q.back()){
ret[i]++;
q.pop_back();
}
if (!q.empty())ret[i]++;
q.push_back(heights[i]);
}
return ret;
}
};

The following code is adjusted from [3]. Credit goes to 66brother.

const int BITS = 32, SAME = 2, PREV = 2, CONSEC = 2;
int f[BITS][SAME][PREV][CONSEC];
class Solution {
public:
int dp( vector<int>& bits, int i, int same, int prev, int consec){
if (i == bits.size()) return consec ? 0 : 1;
if (f[i][same][prev][consec] != -1) return f[i][same][prev][consec];
int ret = 0, newprev = 0, newsame = 0, newconsec = 0…

126. Word Ladder II

For this problem, we can build the graph in two ways:

  1. Graph A: Check all posible pair of string to see whether they have distance of 1 and build the graph.
  2. Graph B: Change one character of the word to a new word and check whether the new word in unexplored word list.

Backtracking Graph A got TLE

class Solution {
public:
string end;
int len = INT_MAX;
bool disOne(string a, string b){
int cnt = 0;
for (int…

Recursion is a powerful method if you know how to use it properly.

A nice binary tree problem can be found:

814. Binary Tree Pruning

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* pruneTree(TreeNode* root) {
if (root == nullptr) return nullptr;
root -> left = pruneTree(root -> left);
root -> right = pruneTree(root -> right);
if (root -> val == 1 || root -> left || root -> right)return root;
return nullptr;
}
};

Pretty nice, right? Thanks for reading.


In this article, I summarize two XOR related problems which can be solved by Trie.

Problem 1

421. Maximum XOR of Two Numbers in an Array

Explanation

  • Each number is a 32 bits binary numbers
  • Organize the numbers in a tree and each node has two children: 0 and 1
  • The maximum XOR of a specified num can be found in the tree with the complexity of O(32)
In this example, we have 3 number: 0b00, 0b01, 0b11.

Code

class TrieNode{
public:
vector<TrieNode*> children;
TrieNode(){
children.assign(2, nullptr);
}
};
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
TrieNode* root = new TrieNode();
TrieNode* curr = root…

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store