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)

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…