一道关于飞机加油的问题

问题：
每个飞机只有一个邮箱，飞机之间可以互相加油并且一箱油可供一架飞机绕地球飞半圈， 问为使至少一架飞机绕地球一圈飞回起飞的地方，至少需要出动几架飞机？ （所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场）


不知道这道题的正确解是多少，这里给出4架安排的方法。

为方便起见先给地球标上坐标。从起点开始自西向东分别标记为 0->1->2->3->4->5->0

plane A: from 0 to 1, oil = 1/2 - 1/6 = 2/6 when x = 1
plane B: from 0 to 1, oil=2/6 when x = 1

1/6 oil from B to A, now, plane A oil = 1/2, plane B oil = 1/6

plane B back to start point
plane A fly to x = 4

meanwhile

plane B from 0 to 5, oil = 2/6 at x = 5
plane C from 0 to 5, oil = 2/6 at x = 5

1/6 oil from B to C, now plane C has 3/6 oil and plane B has 1/6 oil

plane B back to start point
plane C from 5 to 4 with 2/6 oil at x = 4

at this point, plane C meets plane A

1/6 from C to A, now both A and C has 1/6 oil

meanwhile,
plane B and plane D starts from 0 and fly to x = 5
at x = 5, both B and D has 2/6 oil

also at x = 5, B and D meet A and C

B and D give 1/6 to A and C
and all of them can fly back to the start point



===================

I have no idea if we can do this with only three planes. It seems that the plane D is not fully used...

Longest Palindrome Substring O(n) Algorithm

Here is a very detailed explanation of the O(n) algorithm: https://www.felix021.com/blog/page.php?pageid=6

The key ideas are :

• We look for the center of the palindrom
• when scan the string we want to use the previous calculation
• palindrome is symmetric and we want to take advantage of this symmetric structure

This algorithm is a combination of Dynamic Program and Pruning. 

Here is the implementation:

int longestPalindromeSubstring(string inStr) {
    
    // insert "space" between charaters in the orignal string.
    // this is a very useful pre-processing; it unifies the odd-length and even-length palindrom substring
    // It is obvious that we should use a character that does not appear in the original string.
    string s;
    for (int i = 0; i < inStr.size(); ++i) {
        s = s + '#';
        s = s + inStr[i];
    }
    s = s + '#';
    
    
    
    vector<int> P(s.size(), 0);
    
    // Here is the definition of the op_center and op_length:
    // op_center + op_length is the right-most boundary of the known palindrome substring.
    
    int op_center = -1;
    int op_length = 0;
    int record = numeric_limits<int>::min();
    
    // now, we scan the string and update op_center and op_length as well as the maximum lenght
    // of the palindrome substring.
    
    for (int i = 0; i < s.size(); ++i) {
        int curr_length = 0;
        if (i <= op_center + op_length) {   // when current position is covered by a known palindrome substring
            int j = 2 * op_center - i;      // here we take advantage of the symmetric structure
            curr_length = P[j];
        }
        
        // perform the two direction search
        while (i + curr_length < s.size() && i - curr_length >= 0 &&
               s[i+curr_length] == s[i-curr_length]) {
            ++curr_length;
        }
        
        P[i] = --curr_length;
        
        // update the record
        record = max(record, curr_length);
        if (i + curr_length > op_center + op_length) {
            op_center = i;
            op_length = curr_length;
        }
        
    }
    
    return record;
}

LeetCode 287 Find the Duplicate Number

Problem:

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Here is a O(nlogn) algorithm. The key idea is to use binary search. Every time we will make a guess, it is the mid value of the current range of candidates. We then compute the following values:

count_lt_mid = #{x: x < guessed value}
count_eq_mid = #{x: x == guessed value}

if count_eq_mid > 1, we need to return guessed value (obvious).

The key observation here is if count_eq_mid >= guessed value,  the duplicated value must be smaller than guessed value because [1 .. guessed value - 1] has only "guessed value - 1" possibilities.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        return helper(nums, 1, nums.size()-1);
        
    }
    
    int helper(vector<int>& nums, int start, int end) {
        
        if (start == end) return start;
        
        int guess = (start + end) / 2;
        
        int count_lt_mid = 0;
        int count_eq_mid = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] < guess) ++count_lt_mid;
            if (nums[i] == guess) ++count_eq_mid;
        }
        
        if (count_eq_mid > 1) return guess;
        
        if (count_lt_mid >= guess) return helper(nums, start, guess-1);
        if (count_lt_mid < guess) return helper(nums, guess+1, end);
        
        return -1;

    }
};

Leetcode 44: Wildcard Matcher

class Solution {
public:
    bool isMatch(string s, string p) {
        // handle the easy corner case
        if (p == "") return s == "";

        Node* automaton = buildAutomaton(p);
        
        // use a hash map to keep track of calculation when we go throug the search
        map< pair<int,int>, bool > dp;
        return matchPattern(s, 0, automaton, dp);
    }
    
    
    struct Node {
        bool isAny;         // mark if this node is redirected by '*'
                            // note that when we find a '*', we do not create a new node
        bool isSingle;      // mark if this node is created by '?'
        bool isStart;       // mark the node as the start node. This seems to be redundant
        bool isEnd;         // makr the node as termination node
        char code;          // only when the character matches the code, we can move to next node
        int  remaining;     // the minimum number that we need to satisfy the remaining pattern node chain
        int id;             // id of the node. This is one of the key used in the hash map
        Node* next;         // pointer to the next node
        Node() : isAny(false), isSingle(false), isStart(false), isEnd(false), code('\0'), next(nullptr), id(0), remaining(0) {};
    };
    
    Node* buildAutomaton(string& s) {
        Node* start_node = new Node();
        start_node->isStart = true;
        start_node->id = 0;
        int count = 0;
        for (char c : s) if (c != '*') ++count;
        start_node->remaining = count;
        
        // start with start_node, which is also returned by the function
        Node* curr = start_node;
        
        for (int i = 0; i < s.size(); ++i) {
            char ch = s[i];
            
            if (ch == '*') {
                curr->isAny = true; // note that we do not move to the next node
            } else if (ch == '?') {
                curr->isSingle = true;
                Node* new_node = new Node();
                new_node->id = curr->id + 1;
                new_node->remaining = curr->remaining - 1;
                curr->next = new_node;
                curr = new_node;
            } else {
                Node* new_node = new Node();
                curr->code = ch;
                curr->next = new_node;
                new_node->id = curr->id + 1;
                new_node->remaining = curr->remaining - 1;
                curr = new_node;
            }
        }
        
        // mark the current node as the end node
        curr->isEnd = true;
        return start_node;
    }
    
    bool matchPattern(string& s, int level, Node* node, map<pair<int,int>, bool>& dp) {
        /*
        cout << "level: " << level << ", id: " << node->id << ", remaining: " << node->remaining << endl;
        cout << "isAny: " << (node->isAny ? "true" : "false") << endl;
        cout << "isSingle: " << (node->isSingle ? "true" : "false" ) << endl;
        cout << "isEnd: " << (node->isEnd ? "true" : "false") << endl; 
        //*/
        
        // if we have already met this situation, return the calculation result directly
        if (dp.find(make_pair(level, node->id)) != dp.end()) return dp[make_pair(level, node->id)];
        
        // this case, the pattern is '*', which match all the string.
        if (node->isStart && node->isEnd) return true;
        
        // if we arrive at end node, we check
        // (1) if we arrive at the end of the string
        // (2) if we are at '*'. In this case, the last character in the pattern string is '*'
        //     which matches all the remaining string
        // (3) otherwise, we have a mismatch
        if (node->isEnd) {
            if (level == s.size()) {
                return true;
            } else if (node->isAny) {
                return true;
            } else {
                return false;
            }
   
        }
        
        // if we arrive at the end of hte string, check if we arrive at the end of pattern string
        if (level == s.size()) return (node->isEnd);
        
        pair<int,int> mypair{level, node->id};
        
        // prune the search space
        if (level + node->remaining > s.size()) {
            dp[mypair] = false;
            return dp[mypair];
        }
        
        
        // the order of test is important. We need to test if the node is '*' first
        // because it may be possible that a node is '*' and '?' at the same time.
        if (node->isAny) {
            if (node->code == s[level] || node->isSingle) {
                dp[mypair] = matchPattern(s, level+1, node->next, dp) || matchPattern(s, level+1, node, dp);
            } else {
                dp[mypair] = matchPattern(s, level+1, node, dp);
            }
        } else if (node->isSingle) {    
            dp[mypair] = matchPattern(s, level+1, node->next, dp);
        } else {
            dp[mypair] = (node->code == s[level] && matchPattern(s, level+1, node->next, dp));
        }
        
        return dp[mypair];
    }
    
    

};

Double Linked List and Binary Search Tree transformation in O(n)

This code shows that double linked list and binary tree is essentially the same thing. We can convert one data structure to another in O(n).

#ifndef practice_doubleLinkedList2BST_h
#define practice_doubleLinkedList2BST_h

using namespace std;


struct Node {
    int val;
    Node* left;
    Node* right;
    Node(): val(0), left(nullptr), right(nullptr) {};
    Node(int _val) : val(_val), left(nullptr), right(nullptr) {};
};

Node* helper_doubleLinkedList2BST(Node*& node, int start, int end) {
    if (start > end) return nullptr;
    
    if (start == end) {
        return node; // here we can see the the pointer stops at the end of the linked list.
                     // and the function returns the root of the newly created tree.
    }
    
    int mid = (start + end) / 2;
    
    Node* ptr_mid;
    Node* ptr_left;
    Node* ptr_right;
    
    if (start == mid) { // in this case, there is no left tree
        ptr_left = nullptr;
        ptr_mid = node;
        node = node->right;
        node->left = nullptr;
        ptr_right = helper_doubleLinkedList2BST(node, mid+1, end);
    } else {
        ptr_left = helper_doubleLinkedList2BST(node, start, mid-1);
        // now the node pointes to mid-1
        ptr_mid = node->right;
        node->right = nullptr;
        node = ptr_mid->right;
        node->left = nullptr;
        ptr_right = helper_doubleLinkedList2BST(node, mid+1, end);
    }
    
    ptr_mid->left = ptr_left;
    ptr_mid->right = ptr_right;
    return ptr_mid;
}


Node* doubleLinkedList2BST(Node* node, int length) {
    return helper_doubleLinkedList2BST(node, 0, length-1);
}



pair<Node*, Node*> helper_BST2DoubleLinkedList(Node* node) {
    if (!node) return make_pair(nullptr, nullptr);
    
    pair<Node*, Node*> left = helper_BST2DoubleLinkedList(node->left);
    pair<Node*, Node*> right = helper_BST2DoubleLinkedList(node->right);
    
    left.second->right = node;
    node->left = left.second;
    
    node->right = right.first;
    right.first->left = node;
    
    return make_pair(left.first, right.second);
}

Node* BST2DoubleLinkedList(Node* node) {
    pair<Node*, Node*> result = helper_BST2DoubleLinkedList(node);
    return result.first;
}


#endif

LeetCode329: Longest Increasing Path in a Matrix

Here is a very nice solution from the LeetCode community.

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        
        // some boundary cases
        if (matrix.empty()) return 0;
        
        int nrow = matrix.size();
        int ncol = matrix[0].size();
        
        vector<vector<int>> hashtable(nrow, vector<int>(ncol, 0));
        
        int record = 1;
        
        for (int i = 0; i < nrow; ++i) {
            for (int j = 0; j < ncol; ++j) {
                record = max(record, helper(matrix, i,j, matrix[i][j] - 1, hashtable));
            }
        }
        
        return record;
    }
    
    int helper(vector<vector<int>>& matrix, int i, int j, int level, vector<vector<int>>& hashtable) {
        // see comments at the end of this section.

        if (i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size()) return 0;
        
        vector<int> di{1,-1,0,0};
        vector<int> dj{0,0,1,-1};
        

        // level keeps the information from previous step. Note that this function is trigger by an 
        // adjacent cell so if current value matrix[i][j] is less than to equal to level, we should return 0
        // it means that given the level, the contribution of current cell is zero.

        // this step is very important in the sense that it breaks the infinite recursive call.
        // Suppose we are at cell (i, j) and we will go through all the adjacent cells. Let say
        // we are now at cell (i, j+1). We will be allowed to go back to cell (i,j) again becasue 
        // it is one of the adjacent cells of the cell (i, j+1) 

        int curr_val = matrix[i][j];
        if (curr_val <= level) return 0;
        
        
        // hashtable memorizes previous calculation. If we have already met the cell (i,j) before, we should
        // have the result ready.
        if (hashtable[i][j] != 0) return hashtable[i][j];
        
        
        // If we arrive here, we need to do the computation to get the value for cell (i,j)
        int record = numeric_limits<int>::min();
        
        // iterate through the adjacent cells.
        // the "1" in the formula of record is important. It comes from the fact that the current
        // cell will contribute at least 1 to the final longest strict increasing subsequence.

        for (int k = 0; k < 4; ++k) {
            record = max(record, 1 + helper(matrix, i + di[k], j + dj[k], curr_val, hashtable));
        }

        // we now have a clearer view of the hashtable. hashtable[i][j] records the longest length of the strictly 
        // increasing subsequence which starts from hashtable[i][j]
        
        hashtable[i][j] = max(hashtable[i][j], record);
        
        return record;
        
        
        
    }
};