k sum problem （k 个数的求和问题）

问题陈述：

在一个数组，从中找出k个数（每个数不能重复取。数组中同一个值有多个，可以取多个），使得和为零。找出所有这样的组合，要求没有重复项（只要值不同即可，不要求在原数组中的index不同）

解法：

2 sum 用hash table做，可以时间O(n)，空间O（n），
2 sum 如果用sort以后，在前后扫描，可以时间O(nlogn + n) = O(nlogn)，空间O(1)
2 sum 用hash table做的好处是快，但是等于是利用了不用排序的特点。排序的办法，在高维度（也就是k sum问题，k>2）的时候，nlogn就不是主要的时间消耗成分，也就更适合2sum的sort后双指针扫描查找的办法。

那么，对于k sum， k>2的，如果用sort的话， 可以 对 n-2的数做嵌套循环，因为已经sort过了，最后剩下的两维用2 sum的第二个办法， 时间是O(nlogn + n^(k-2) * n) = O(n^(n-1))，空间O(1)。 但是这样跟纯嵌套循环没有什么区别，只是最后一层少了一个因子n。有什么办法能优化？
就是说，对于 k sum (k>2) 问题 （一个size为n的array, 查找k个数的一个tuple，满足总和sum为0）， 有没有时间复杂度在O(n^(k-2))的办法？

之前常规的一层一层剥离，n的次数是递增的。只有在最后一层，还有两个维度的时候，时间开销上减少一个n的因子，但是这样时间开销还是太多

我们可以通过对问题分解来解决
举个例子
...-5，-4，-3，-2，-1, 0，1, 2, 3, 4, 5.... 要找 4 sum = 0
那么先分解
4 分成 2 sum + 2 sum 来解决，但是这里的子问题2 sum没有sum=0的要求，是保留任何中间值。只有当子问题的2 sum解决以后，回归原问题的时候，我们才又回归原始的2 sum问题，这时候sum=0
子问题，空间和时间消耗，都是O(n^2)
回归大问题，时间消耗，是O(n^2)

假设k sum中  k = 2^m, 那么一共有m层，会有m次分解
分解到最底层，时间空间消耗 从 原始O(n)变为新的O(n^2)
分解到次底层，时间空间消耗 从 O(n^2)变为新的O((n^2)^2)
...
到达最顶层，时间空间消耗就都变成了O(n^(2*m)) = O(n^(2logk))

和之前的方法O(n^(k-1))相比，O(n^(2logk))的时间是少了很多，但是空间消耗却很大。
因为子问题无法确定把哪一个中间结果留下，那么就需要把子问题的结果全部返回，到最后，空间消耗就很大了。整体效果算是空间换时间吧。

通过 问题的分解 + hashtable的运用，能明显减少时间消耗， 但是空间消耗变大是个问题。比如说，如果有10^6的int类型数组，我如果用这个hashtable的办法，就要有10^12的pair，这就有10T以上的空间消耗。

问题的分解是个很好的思路，但是中间值得保留迫使空间消耗增大，这和用不用hashtable倒没有很大关系，只是说，如果不用hashtable，时间消耗会更大。





另外，还有一些题目的变形，比如如果要求所有组合，满足
sum < k,
sum = k,
sum > k,
或者是 closest to k
遇到这些变形的时候，hashtable的做法就显得乏力了，但是嵌套循环的方式却仍是可行的。尤其是对closest to k这种非确定性的要求。

Reservoir Sampling Proof

http://en.wikipedia.org/wiki/Reservoir_sampling

array R[k];    // result
integer i, j;

// fill the reservoir array
for each i in 1 to k do
    R[i] := S[i]
done;

// replace elements with gradually decreasing probability
for each i in k+1 to length(S) do
    j := random(1, i);   // important: inclusive range
    if j <= k then
        R[j] := S[i]
    fi
done

 一开始有k个
每个数字被选进来的概率都是1

第k+1个，要放进去，那么前面每个被换出去的概率是 1/(k+1), 没被换出去的概率是k/(k+1)
有k-1个数字，是留下来了，留下来的概率是k/(k+1)
有1个数字，换出去了，新进来的，被选进来的概率是 k/(k+1)
所有数字留下来的概率都是k/(k+1)

然后，处理第k+2个
第k+2个，要放进去，那么前面每个被换出去的概率是 1/(k+2), 没被换出去的概率是(k+1)/(k+2),
有k-1个数字, 是留下来了, (k+1)/(k+2), 再加上上一次的概率，留下来的总概率是k/(k+1)  *   (k+1)/(k+2) = k/(k+2)
有1个数字，换出去了，那么新进来的数字被选进来的概率是 k/(k+2)
所有数字留下来的概率都是k/(k+2)


假设当前处理了n个样本，选出了k个数，并且满足条件
k个选出的样本，每个样本在n个样本中被抽出的概率都是k/n
那么处理第n+1个样本的时候
1). 第n+1个样本被选进k的概率是 k/(n+1)，即，被换进的样本的概率是 k/(n+1)
2). 对于前k个样本，留下的概率是 n/(n+1)，与之前的概率 k/n，做条件概率相乘，截止到目前该样本仍然留在k个样本中的总概率是 n/(n+1) * k/n = k/(n+1)
综合1) 2), k个样本每个留下的概率都是 k/(n+1)

以此类推，对于每个状态，即处理过的样本总量为n的时候，所有留下来的样本的全局总概率都是k/n 

Farthest Ascending Pair

Problem :
Given a sequence of integers A[n], find a pair of integers A[x]<A[y], such that y-x >= j-i and A[i]<A[j]

Solution:
In courtesy of JConstantine

 
class Solution
{
    public:
    std::vector<int> findLongestAscendingPair(const std::vector<int> &v) {
        std::vector<int> ret(2,0);
        int n = v.size();
        if(n == 0) return ret;
        std::vector<int> left(n,0);
        std::vector<int> right(n,0);
        left[0] = v[0];
        right[n-1] = v[n-1];
        for(int i=1; i<n; i++){
            left[i] = std::min(v[i], left[i-1]);
        }
        
        for(int i=n-2; i>=0; i--){
            right[i] = std::max(v[i], right[i+1]);
        }
        
        int i = 0, j = 0, distance = 0;
        while(i < n && j < n)
        {
            if(left[i] < right[j])
            {
                distance = std::max(j-i, distance);
                ret[0] = i;
                ret[1] = j;
                j = j + 1;
            }
            else
            {
                i = i+ 1;
            }
        }
        return ret;
    }
};

longest increasing sequence

Link : http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.cpp

 
#include < vector >
using namespace std;

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector < int > & a, vector < int > & b)
{
    vector < int > p(a.size());
    int u, v;
    
    if(a.empty()) return;
    
    b.push_back(0);
    
    for(size_t i = 1; i < a.size(); i++)
    {
        // If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
        if(a[b.back()] < a[i])
        {
            p[i] = b.back();
            b.push_back(i);
            continue;
        }
        
        // Binary search to find the smallest element referenced by b which is just bigger than a[i]
        // Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.
        for(u = 0, v = b.size() - 1; u < v;)
        {
            int c = (u + v) / 2;
            if(a[b[c]] < a[i]) u = c + 1;
            else v = c;
        }
        
        // Update b if new value is smaller then previously referenced value
        if(a[i] < a[b[u]])
        {
            if(u > 0) p[i] = b[u - 1];
            b[u] = i;
        }
    }
    
    for(u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}

/* Example of usage: */
#include < cstdio >
int main()
{
    int a[] = {
        1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7
    };
    vector < int > seq(a, a + sizeof(a) / sizeof(a[0])); // seq : Input Vector
    vector < int > lis; // lis : Vector containing indexes of longest subsequence
    find_lis(seq, lis);
    
    //Printing actual output
    for(size_t i = 0; i < lis.size(); i++)
    printf("%d ", seq[lis[i]]);
    printf("\n");
    
    return 0;
}

[LeetCode] Maximal Rectangle

Link : http://oj.leetcode.com/problems/maximal-rectangle/

More information:
http://dp2.me/blog/?p=482

Thanks for your help. --> 无齿的兔子, 鹿杖客

 
#include <iostream>
#include <vector>

class Solution {
    public:
    int maximalRectangle(std::vector<std::vector<char> > &matrix) {
        int n = matrix.size();
        if(n==0) return 0;
        int m = matrix[0].size();
        if(m==0) return 0;
        std::vector<int> height(m, 0);
        std::vector<int> left(m, 0);
        std::vector<int> right(m, 0);
        int maxArea = 0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                height[j] = (matrix[i][j]=='1')? height[j]+1 : 0;
                left[j] = j;
                while(left[j]>0 && height[left[j]-1]>=height[j])
                left[j] = left[left[j]-1];
            }
            for(int j=m-1; j>=0; j--)
            {
                right[j] = j;
                while(right[j]<m-1 && height[j]<=height[right[j]+1])
                right[j] = right[right[j]+1];
            }
            for(int j=0; j<m; j++)
            maxArea = std::max(maxArea, (right[j]-left[j]+1)*height[j]);
        }
        return maxArea;
    }
};

[LeetCode] LRU Cache

 
class LRUCache{
    public:
    typedef std::pair<int, int> ENTRY;
    LRUCache(int capacity) {
        max = capacity;
        count = 0;
    }
    
    int get(int key) {
        if(map.find(key)==map.end())
        return -1;
        else
        {
            entry.splice(entry.begin(), entry, map[key]);
            return (map[key])->second;
        }
    }
    
    void set(int key, int value) {
        if(map.find(key)==map.end())
        {
            entry.push_front(ENTRY(key, value));
            map[key] = entry.begin();
            if(++count>max)
            {
                int tmp = entry.back().first;
                entry.erase(--entry.end());
                count--;
                map.erase(tmp);
            }
        }
        else
        {
            entry.splice(entry.begin(), entry, map[key]);
            map[key]->second = value;
        }
    }
    
    int count;
    int max;
    std::list<std::pair<int, int>> entry;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map;
};

[LeetCode] Reorder List

Link : http://oj.leetcode.com/problems/reorder-list/

Analysis :
Two pointers, head and tail

head pointer : scans from the start
tail pointer  : first dig into the list until and last one. From there tail behaves as the node pointer pointing to the last node

head and tail scan from two ends and modify the link list as expected.
Be careful of the stop case.

 
/**
* Definition for singly-linked list.
* struct ListNode {
    *     int val;
    *     ListNode *next;
    *     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
    public:
    void reorderList(ListNode *head) {
        if(head==NULL)
            return;
        int n=0;
        ListNode dummy(0);
        dummy.next = head;
        ListNode * cursor = &dummy;
        reorder(cursor, cursor);
    }
    
    bool reorder(ListNode*& head, ListNode* tail)
    {
        // base case
        if(tail->next==NULL)
            return true;
        // tail point to second to last node
        
        // stop case
        if(!reorder(head, tail->next)||head==tail||head->next==tail);
            return false;
        ListNode* tmp = tail->next;
        tail->next=NULL;
        
        tmp->next = head->next;
        head->next = tmp;
        
        head = head->next->next;
        return true;
    }
};

[LeetCode] Sort List

Link : http://oj.leetcode.com/problems/sort-list/
Sort a linked list in O(n log n) time using constant space complexity.

iterative version of merge sort.
Code is ugly and needs substantial modification.

class Solution {
    public:
    
    ListNode *sortList(ListNode *head) {
        if(!head) return NULL;
        ListNode dummy(0);
        dummy.next = head;
        // get length
        int n=0;
        ListNode* cursor=&dummy;
        ListNode* tmp;
        while(cursor->next) { n++; cursor=cursor->next; }
        
        ListNode* current_first=head;
        ListNode* next_first=NULL;
        
        ListNode* merge_head=NULL;
        ListNode* merge_tail=NULL;
        
        // scan using different step
        for(int step=1; step<n; step*=2)
        {
            // initialization
            cursor = &dummy;
            current_first = dummy.next;
            // for each step, merge two adjacent sub lists
            for(int i=0; i<n; i+=step*2)
            {
                next_first = moveNode(current_first, step*2-1);
                if(next_first) // cut link between different sub list
                {
                    tmp = next_first->next;
                    next_first->next = NULL;
                    next_first = tmp;
                }
                merge(current_first, step, merge_head, merge_tail);
                cursor->next = merge_head; // concatenation
                cursor = merge_tail; // ready for next concatenation
                current_first = next_first; // ready for next merge
            }
        }
        return dummy.next;
    }
    
    ListNode* moveNode(ListNode* p, int step)
    {
        while(step-->0&&p) p=p->next;
        return p;
    }
    
    void merge(ListNode* head, int step, ListNode*& merge_head, ListNode*& merge_tail)
    {
        if(head==NULL) return;
        ListNode dummy(0);
        ListNode* tmp;
        
        ListNode* cursor = &dummy;
        ListNode* l1 = head;
        // get second sub-list
        ListNode* l2 = head;
        // get the node pointing to the head of second sub-list
        l2 = moveNode(l2, step-1);
        if(l2) // cut link between different sub list
        {
            tmp = l2->next;
            l2->next = NULL;
            l2 = tmp;
        }
        
        while(l1||l2)
        {
            if((l1&&!l2)||(l1&&l2&& l1->val <= l2->val))
            {
                tmp = l1->next;
                l1->next=NULL;
                cursor->next = l1;
                
                l1=tmp;
                cursor=cursor->next;
            }
            else
            {
                tmp = l2->next;
                l2->next=NULL;
                cursor->next = l2;
                
                l2=tmp;
                cursor=cursor->next;
            }
        }
        merge_head = dummy.next;
        merge_tail = cursor;
    }
    
};

[LeetCode] Binary Tree Preorder Traversal

Link : http://oj.leetcode.com/problems/binary-tree-preorder-traversal/

/**
* Definition for binary tree
* struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };


class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> ret;
        if(root==NULL)
            return ret;
        std::stack<TreeNode*> ss;
        ss.push(root);
        TreeNode* node;
        while(ss.size()>0)
        {
            node = ss.top();
            ss.pop();
            ret.push_back(node->val);
            if(node->right)
                ss.push(node->right);
            if(node->left)
                ss.push(node->left);
            
        }
        return ret;
    }
};

[LeetCode] Binary Tree Postorder Traversal

Link : http://oj.leetcode.com/problems/binary-tree-postorder-traversal/

/**
* Definition for binary tree
* struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
    public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> ret;
        if(root==NULL)
            return ret;
        TreeNode* current;
        stack<TreeNode*> s;
        s.push(root);
        while(s.size()>0)
        {
            current = s.top();
            s.pop();
            if(current==NULL)
            {
                current = s.top();
                s.pop();
                ret.push_back(current->val);
                continue;
            }
            s.push(current);
            s.push(NULL);
            if(current->right)
                s.push(current->right);
            if(current->left)
                s.push(current->left);
        }
        return ret;
    }
};

user defined hash function in C++ STL unordered_map and unordered_set

Reference :
http://mikecvet.wordpress.com/2011/01/28/customizing-tr1-unordered_map-hashing-and-equality-functions/
http://en.cppreference.com/w/cpp/utility/hash
http://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key

template<class Key,          class T,          class Hash = hash<Key>,          class Pred = std::equal_to<Key>,          class Alloc = std::allocator<std::pair<const Key, T> > > typedef struct {   long operator() (const AggregateKey &k) const { return my_hash_fnct (k); } } AggregateKeyHash; typedef struct {   bool operator() (const AggregateKey &x, const AggregateKey &y) const { return my_eq_test (x, y); } } AggregateKeyEq; AggregateKey k; {...} // Now, hash value generation and equality&nbsp;testing are // defined for the AggregateKeyHash&nbsp;type, so declare the // map using the functors&nbsp;above in the object's template list std::tr1::unordered_map<AggregateKey, int, AggregateKeyHash, AggregateKeyEq> M; M[k] = 1; {...} std::tr1::unordered_map<int, int> M; const std::tr1::unordered_map<int, int>::hasher &hfn = M.hash_function (); const std::tr1::unordered_map<int, int>::key_equal &eqfn = M.key_eq (); long h = hfn (123); bool b = eqfn (1, 2);

struct Key{ std::string first; std::string second; int third; bool operator==(const Key &other) const { return (first == other.first && second == other.second && third == other.third); } }; namespace std { template <> struct hash<Key> { std::size_t operator()(const Key& k) const { using std::size_t; using std::hash; using std::string; // Compute individual hash values for first, // second and third and combine them using XOR // and bit shifting: return ((hash<string>()(k.first) ^ (hash<string>()(k.second) << 1)) >> 1) ^ (hash<int>()(k.third) << 1); } }; } int main() { std::unordered_map<Key,std::string> m6 = { { {"John", "Doe", 12}, "example"}, { {"Mary", "Sue", 21}, "another"} }; }

struct Key{ std::string first; std::string second; int third; bool operator==(const Key &other) const { return (first == other.first && second == other.second && third == other.third); } }; struct KeyHasher { std::size_t operator()(const Key& k) const { using std::size_t; using std::hash; using std::string; return ((hash<string>()(k.first) ^ (hash<string>()(k.second) << 1)) >> 1) ^ (hash<int>()(k.third) << 1); } }; int main() { std::unordered_map<Key,std::string,KeyHasher> m6 = { { {"John", "Doe", 12}, "example"}, { {"Mary", "Sue", 21}, "another"} }; }